Community structure detection based on edge betweenness
Many networks consist of modules which are densely connected themselves but sparsely connected to other modules.
edge.betweenness.community (graph, weights = E(graph)$weight, directed = TRUE, edge.betweenness = TRUE, merges = TRUE, bridges = TRUE, modularity = TRUE, membership = TRUE)
- The graph to analyze.
- The edge weights. Supply
NULLto omit edge weights. By default the
edge attribute is used, if it is present.
- Logical constant, whether to calculate directed edge betweenness for directed graphs. It is ignored for undirected graphs.
- Logical constant, whether to return the edge betweenness of the edges at the time of their removal.
- 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 agglomerat
- Logical constant, whether to return a list the edge removals which actually splitted a component of the graph.
- Logical constant, whether to calculate the maximum modularity score, considering all possibly community structures along the edge-betweenness based edge removals.
- Logical constant, whether to calculate the membership vector corresponding to the highest possible modularity score.
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
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
edge.betweeness.community returns various information collected
throught the run of the algorithm. See the return value down here.
- Edge betweenness
- Community structure
M Newman and M Girvan: Finding and evaluating community structure in networks, Physical Review E 69, 026113 (2004)
communities for extracting the results of the
g <- barabasi.game(100,m=2) eb <- edge.betweenness.community(g) g <- graph.full(10) %du% graph.full(10) g <- add.edges(g, c(1,11)) eb <- edge.betweenness.community(g) eb