walktrap.community          package:igraph          R Documentation

_C_o_m_m_u_n_i_t_y _s_t_r_u_c_u_r_e _v_i_a _s_h_o_r_t _r_a_n_d_o_m _w_a_l_k_s

_D_e_s_c_r_i_p_t_i_o_n:

     This function tries to find densely connected subgraphs, also
     called communities in a graph via random walks. The idea is that
     short random walks tend to stay in the same community.

_U_s_a_g_e:

     walktrap.community(graph, weights = E(graph)$weight, steps = 4, merges =
               TRUE, modularity = FALSE, labels = TRUE)

_A_r_g_u_m_e_n_t_s:

   graph: The input graph.

 weights: The edge weights.

   steps: The length of the random walks to perform.

  merges: Logical scalar, whether to include the merge matrix in the
          result.

modularity: Logical scalar, whether to include the vector of the
          modularity scores in the result.

  labels: Logical scalar, if 'TRUE' and the graph has a vertex
          attribute called 'name' then it will be included in the
          result, in the list member called 'labels'.

_D_e_t_a_i_l_s:

     This function is the implementation of the Walktrap community
     finding algorithm, see Pascal Pons, Matthieu Latapy: Computing
     communities in large networks using random walks, 
     http://arxiv.org/abs/physics/0512106

_V_a_l_u_e:

     A named list with three members: 

  merges: The merges performed by the algorithm will be stored here.
          Each merge is a row in a two-column matrix and contains the
          ids of the merged communities. Communities are numbered from
          zero and cluster number  smaller than the number of nodes in
          the network belong to the individual vertices as singleton
          communities. In each step a new community is created from two
          other communities and its id will be  one larger than the
          largest community id so far. This means that  before the
          first merge we have 'n' communities (the number of vertices
          in the graph) numbered from zero to 'n-1'. The first merge
          created community 'n', the second community 'n+1', etc. 

modularity: Numeric vector, the modularity score of the current
          community structure after each merge operation.  

  labels: The labels of the vertices in the graph. The 'name' vertex
          attribute will be copied here, if exists. 

_A_u_t_h_o_r(_s):

     Pascal Pons google@for.it and Gabor Csardi csardi@rmki.kfki.hu for
     the R and igraph interface

_R_e_f_e_r_e_n_c_e_s:

     Pascal Pons, Matthieu Latapy: Computing communities in large
     networks using random walks,  http://arxiv.org/abs/physics/0512106

_S_e_e _A_l_s_o:

     'modularity' and  'fastgreedy.community', 'spinglass.community',
     'leading.eigenvector.community', 'edge.betweenness.community' for
     other community detection methods.

_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))
     walktrap.community(g)

