leading.eigenvector.community     package:igraph     R Documentation

_C_o_m_m_u_n_i_t_y _s_t_r_u_c_t_u_r_e _d_e_t_e_c_t_i_n_g _b_a_s_e_d _o_n _t_h_e _l_e_a_d_i_n_g _e_i_g_e_n_v_e_c_t_o_r
_o_f _t_h_e _c_o_m_m_u_n_i_t_y _m_a_t_r_i_x

_D_e_s_c_r_i_p_t_i_o_n:

     These functions try to find densely connected subgraphs in a graph
     by calculating the leading non-negative eigenvector of the
     modularity matrix of the graph.

_U_s_a_g_e:

     leading.eigenvector.community(graph, steps = -1,
            options = igraph.arpack.default)
     leading.eigenvector.community.naive(graph, steps = -1,
            options = igraph.arpack.default)
     leading.eigenvector.community.step (graph, fromhere = NULL,
         membership = rep(0, vcount(graph)), community = 0,
         options=igraph.arpack.default)
     community.le.to.membership(merges, steps, membership) 

_A_r_g_u_m_e_n_t_s:

   graph: The input graph. Should be undirected as the method needs a
          symmetric matrix.

   steps: The number of steps to take, this is actually the number of
          tries to make a step. It is not a particularly useful
          parameter.

          For 'community.le.to.membership' the number of merges to
          produce from the supplied 'membership' vector. 

   naive: Logical constant, it defines how the algorithm tries to find
          more divisions after the first division was made. If 'TRUE'
          then it simply considers both communities as separate graphs
          and then creates modularity matrices for both communities,
          etc. This method however does not maximize modularity, see
          the paper in the references section below. If it is 'FALSE'
          then the proper method is used which maximizes modularity.

fromhere: An object returned by a previous call to
          'leading.eigenvector.community.step'. This will serve as a
          starting point to take another step. This argument is ignored
          if it is 'NULL'.

membership: The starting community structure. It is a numeric vector
          defining the membership of every vertex in the graph with a
          number between 0 and the total number of communities at this
          level minus one. By default we start with a single community
          containing all vertices. This argument is ignored if
          'fromhere' is not 'NULL'.

          For 'community.le.to.memberhip' the starting community
          structure on which 'steps' merges are performed. 

community: The id of the community which the algorithm will try to
          split.

 options: A named list to override some ARPACK options.

  merges: The merge matrix, possible from the result of
          'leading.eigenvector.community'.

_D_e_t_a_i_l_s:

     The functions documented in these section implement the  'leading
     eigenvector' method developed by Mark Newman and  published in MEJ
     Newman: Finding community structure using the eigenvectors of
     matrices, arXiv:physics/0605087. TODO: proper citation.

     The heart of the method is the definition of the modularity
     matrix, 'B', which is 'B=A-P', 'A' being the adjacency matrix of
     the (undirected)  network, and 'P' contains the probability that
     certain edges are present according to the 'configuration model'.
     In other words, a 'P[i,j]' element of 'P' is the probability that
     there is an edge between vertices 'i' and 'j' in a random network
     in which the degrees of all vertices are the same as in the input
     graph.

     The leading eigenvector method works by calculating the
     eigenvector of the modularity matrix for the largest positive
     eigenvalue and then separating vertices into two community based
     on the sign of the corresponding element in the eigenvector. If
     all elements in the eigenvector are of the same sign that means
     that the network has no underlying comuunity structure. Check
     Newman's paper to understand why this is a good method for
     detecting community structure.

     'leading.eigenvector.community' is the proper implementation of
     the proposed algorithm. 'leading.eigenvector.community.naive' is
     considered worse, in this implementation a community found after a
     division is considered as a separate graph for further divisions.
     'leading.eigenvector.community.step' is the proper implementation,
     but makes only one step, by trying to split the specified
     community.

     From igraph 0.5 these functions use ARPACK to calculate the
     eigenvectors. See 'arpack' for details.

     'community.le.to.memberhip' creates a membership vector from the
     result of 'leading.eigenvector.community' or
     'leading.eigenvector.community.naive'. It takes 'membership' and
     permformes 'steps' merges, according to the supplied 'merges'
     matrix.

_V_a_l_u_e:

     'leading.eigenvector.community' and
     'leading.eigenvector.community.naive' return a named list with the
     following members: 

membership: The membership vector at the end of the algorithm, when no
          more splits are possible.

  merges: The merges matrix starting from the state described by the
          'membership' member. This is a two-column matrix and each
          line describes a merge of two communities, the first line is
          the first merge and it creates community ''N'', 'N' is the
          number of initial communities in the graph, the second line
          creates community 'N+1', etc. 

 options: Information about the underlying ARPACK computation, see
          'arpack' for details. 

membership: The new membership vector after the split. If no split was
          done then this is the same as the input membership vector.

   split: Logical scalar, if 'TRUE' that means that the community was
          successfully splitted.

eigenvector: The eigenvector of the community matrix, or 'NULL' if the
          'eigenvector' argument was 'FALSE'.

eigenvalue: The largest positive eigenvalue of the modularity matrix.

 options: Information about the underlying ARPACK computation, see
          'arpack' for details. 

membership: A membership vector, a numerical vector indication which
          vertex belongs to which community. The communities are always
          numbered from zero.

   csize: A numeric vector giving the sizes of the communities.

_A_u_t_h_o_r(_s):

     Gabor Csardi csardi@rmki.kfki.hu

_R_e_f_e_r_e_n_c_e_s:

     MEJ Newman: Finding community structure using the eigenvectors of
     matrices, arXiv:physics/0605087

_S_e_e _A_l_s_o:

     'modularity', 'walktrap.community', 'edge.betweenness.community',
     'fastgreedy.community', 'as.dendrogram'

_E_x_a_m_p_l_e_s:

     g <- graph.full(5) %du% graph.full(5) %du% graph.full(5)
     g <- add.edges(g, c(0,5, 0,10, 5, 10))
     leading.eigenvector.community(g)

     lec <- leading.eigenvector.community.step(g)
     lec$membership
     # Try one more split
     leading.eigenvector.community.step(g, fromhere=lec, community=0)
     leading.eigenvector.community.step(g, fromhere=lec, community=1)

