edge.betweenness.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_o_n _b_a_s_e_d _o_n _e_d_g_e _b_e_t_w_e_e_n_n_e_s_s

_D_e_s_c_r_i_p_t_i_o_n:

     Many networks consist of modules which are densely connected
     themselves but sparsely connected to other modules.

_U_s_a_g_e:

     edge.betweenness.community (graph, directed = TRUE,
         edge.betweenness = TRUE, merges = TRUE, bridges = TRUE,
         labels = TRUE)
     edge.betweenness.community.merges (graph, edges)

_A_r_g_u_m_e_n_t_s:

   graph: The graph to analyze.

directed: Logical constant, whether to calculate directed edge
          betweenness for directed graphs. It is ignored for undirected
          graphs.

edge.betweenness: Logical constant, whether to return the edge
          betweenness of the edges at the time of their removal.

  merges: Logical constant, whether to return the merge matrix
          representing the hierarchical community structure of the
          network. This argument is called 'merges', even if the
          community structure algorithm itself is divisive and not
          agglomerative: it builds the tree from top to bottom. There
          is one line for each merge (ie. split) in matrix, the first
          line is the first merge (last split). The communities are
          identified by integer number starting from zero. Community
          ids smaller than ''N'', the number of vertices in the graph,
          belong to singleton communities, ie. individual vertices.
          Before the first merge we have ''N'' communities numbered
          from zero to ''N-1''. The first merge, the first line of the
          matrix creates community ''N'', the second merge creates
          community ''N+1'', etc. 

 bridges: Logical constant, whether to return a list the edge removals
          which actually splitted a component of the graph.

  labels: Logical constant, whether to contain the labels of the
          vertices in the result. More precisely, if the graph has a
          vertex attribute valled 'name', it will be part of the result
          object.

   edges: Numeric vector, the ids of the edges to be removed from a
          graph, all edges should be present in the vector, their order
          specifies the order of removal.

_D_e_t_a_i_l_s:

     The edge betweenness score of an edge measures the number of
     shortest paths through it, see 'edge.betweenness' for details. The
     idea of the edge betweenness based community structure detection
     is that it is likely that edges connecting separate modules have
     high edge betweenness as all the shortest paths from one module to
     another must traverse through them. So if we gradually remove the
     edge with the highest edge betweenness score we will get a
     hierarchical map, a rooted tree, called a dendrogram of the graph.
     The leafs of the tree are the individual vertices and the root of
     the tree represents the whole graph. 

     'edge.betweenness.community' performs this algorithm by
     calculating the edge betweenness of the graph, removing the edge
     with the highest edge betweenness score, then recalculating edge
     betweenness of the edges and again removing the one with the
     highest score, etc.

     'edge.betweeness.community' returns various information collected
     throught the run of the algorithm. See the return value down here.

     'edge.betweenness.community.merges' gets a list of edges and by
     gradually removes them from the graph it creates a merge matrix
     similar to the one returned by 'edge.betweenness.community'.

_V_a_l_u_e:

     A named list is returned by 'edge.betweenness.community', with the
     following components: 

removed.edges: Numeric vector, the edges of the graph, in the order of
          their removal.

edge.betweenness: Numeric vector, the edge betweenness value of the
          removed edges, the order is the same as in 'removed.edges'.

  merges: Matrix containing the merges (ie. divisions) the algorithm
          performed, see the 'merges' argument for the format.

 bridges: Numeric vector, the steps (ie. edge removals) which resulted
          a split of a component in the graph.

  labels: The 'name' argument of the vertices.


     Note that some components may be missing or 'NULL' if you do not
     request them, see the parameters.

     A numeric matrix is returned by
     'edge.betweenness.community.merges'. The matrix has two column and
     its format is the same as the 'merges' slot of the result of
     'edge.betweenness.community'.

_A_u_t_h_o_r(_s):

     Gabor Csardi csardi@rmki.kfki.hu

_R_e_f_e_r_e_n_c_e_s:

     M Newman and M Girvan: Finding and evaluating community structure
     in networks, _Physical Review E_ 69, 026113 (2004)

_S_e_e _A_l_s_o:

     'edge.betweenness' for the definition and calculation of the edge
     betweenness, 'walktrap.community', 'fastgreedy.community',
     'leading.eigenvector.community' for other community detection
     methods. 'as.dendrogram' for creating an R dendrogram object from
     the result of the clustering. See 'community.to.membership' to
     create the actual communities after a number of edges removed from
     the network.

_E_x_a_m_p_l_e_s:

     g <- barabasi.game(100,m=2)
     eb <- edge.betweenness.community(g)

     g <- graph.full(10) %du% graph.full(10)
     g <- add.edges(g, c(0,10))
     eb <- edge.betweenness.community(g)
     E(g) [ eb$removed.edges[1] ]            

