spinglass.community          package:igraph          R Documentation

_F_i_n_d_i_n_g _c_o_m_m_u_n_i_t_i_e_s _i_n _g_r_a_p_h_s _b_a_s_e_d _o_n _s_t_a_t_i_s_t_i_c_a_l _m_e_a_c_h_a_n_i_c_s

_D_e_s_c_r_i_p_t_i_o_n:

     This function tries to find communities in graphs via a spin-glass
     model and simulated annealing.

_U_s_a_g_e:

     spinglass.community(graph, weights=NULL, spins=25, parupdate=FALSE,
                         start.temp=1, stop.temp=0.1, cool.fact=0.99,
                         update.rule=c("config", "random", "simple"), gamma=1)
     spinglass.community(graph, weights=NULL, vertex, spins=25,
                         update.rule=c("config", "random", "simple"), gamma=1)

_A_r_g_u_m_e_n_t_s:

   graph: The input graph, can be directed but the direction of the
          edges is neglected.

 weights: The weights of the edges. Either a numeric vector or 'NULL'.
          If it is null and the input graph has a 'weight' edge
          attribute then that will be used. If 'NULL' and no such
          attribute is present then the edges will have equal weights.

   spins: Integer constant, the number of spins to use. This is the
          upper limit for the number of communities. It is not a
          problem to supply a (reasonably) big number here, in which
          case some spin states will be unpopulated. 

parupdate: Logical constant, whether to update the spins of the
          vertices in parallel (synchronously) or not. This argument is
          ignored if the second form of the function is used (ie. the
          ''vertex'' argument is present). 

start.temp: Real constant, the start temperature. This argument is
          ignored if the second form of the function is used (ie. the
          ''vertex'' argument is present). 

stop.temp: Real constant, the stop temperature. The simulation
          terminates if the temperature lowers below this level. This
          argument is ignored if the second form of the function is
          used (ie. the ''vertex'' argument is present). 

cool.fact: Cooling factor for the simulated annealing. This argument is
          ignored if the second form of the function is used (ie. the
          ''vertex'' argument is present). 

update.rule: Character constant giving the 'null-model' of the
          simulation. Possible values: "simple" and "config". "simple"
          uses a random graph with the same number of edges as the
          baseline probability and "config" uses a random graph with
          the same vertex degrees as the input graph.

   gamma: Real constant, the gamma argument of the algorithm. This
          specifies the balance between the importance of present and
          non-present edges in a community. Roughly, a comunity is a
          set of vertices having many edges inside the community and
          few edges outside the community. The default 1.0 value makes
          existing and non-existing links equally important. Smaller
          values make the existing links, greater values the missing
          links more important.

  vertex: This parameter can be used to calculate the community of a
          given vertex without calculating all communities. Note that
          if this argument is present then some other arguments are
          ignored.

_D_e_t_a_i_l_s:

     This function tries to find communities in a graph. A community is
     a set of nodes with many edges inside the community and  few edges
     between outside it (ie. between the community itself and the rest
     of the graph.

_V_a_l_u_e:

     If the 'vertex' argument is not given, ie. the first form is used
     then a named list is returned with the following slots: 

membership: Integer vector giving the communities found. The
          communities have ids starting from zero and for each graph
          vertex ids community id is given in this vector.

   csize: The sizes of the communities in the order of their ids.

modularity: The modularity score of the result, as defined by Newman
          and Girvan, see references.

temperature: The temperature of the system when the algorithm
          terminated.

community: Numeric vector giving the ids of the vertices in the same
          community as 'vertex'.

cohesion: The cohesion score of the result, see references.

adhesion: The adhesion score of the result, see references.

inner.links: The number of edges within the community of 'vertex'.

outer.links: The number of edges between the community of 'vertex' and
          the rest of the graph. 

_A_u_t_h_o_r(_s):

     Jorg Reichardt lastname@physik.uni-wuerzburg.de for the original
     code and Gabor Csardi csardi@rmki.kfki.hu for the igraph glue code

_R_e_f_e_r_e_n_c_e_s:

     J. Reichardt and S. Bornholdt: Statistical Mechanics of Community
     Detection, _Phys. Rev. E_, 74, 016110 (2006), <URL:
     http://arxiv.org/abs/cond-mat/0603718>

     M. E. J. Newman and M. Girvan: Finding and evaluating community
     structure in networks, _Phys. Rev. E_ 69, 026113 (2004)

_S_e_e _A_l_s_o:

     'clusters'

_E_x_a_m_p_l_e_s:

       g <- erdos.renyi.game(10, 5/10) %du% erdos.renyi.game(9, 5/9)
       g <- add.edges(g, c(0, 11))
       g <- subgraph(g, subcomponent(g, 0))
       spinglass.community(g, spins=2)
       spinglass.community(g, vertex=0)

