cluster_edge_betweenness
Community structure detection based on edge betweenness
Many networks consist of modules which are densely connected themselves but sparsely connected to other modules.
- Keywords
- graphs
Usage
cluster_edge_betweenness(graph, weights = E(graph)$weight, directed = TRUE,
edge.betweenness = TRUE, merges = TRUE, bridges = TRUE,
modularity = TRUE, membership = TRUE)
Arguments
- graph
The graph to analyze.
- weights
The edge weights. Supply
NULL
to omit edge weights. By default the ‘weight
’ edge attribute is used, if it is present. Edge weights are used to calculate weighted edge betweenness. This means that edges are interpreted as distances, not as connection strengths.- 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 (i.e. split) in matrix, the first line is the first merge (last split). The communities are identified by integer number starting from one. Community ids smaller than or equal to \(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 one to \(N\). The first merge, the first line of the matrix creates community \(N+1\), the second merge creates community \(N+2\), etc.- bridges
Logical constant, whether to return a list the edge removals which actually splitted a component of the graph.
- modularity
Logical constant, whether to calculate the maximum modularity score, considering all possibly community structures along the edge-betweenness based edge removals.
- membership
Logical constant, whether to calculate the membership vector corresponding to the highest possible modularity score.
Details
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.
cluster_edge_betweenness
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.
Value
cluster_edge_betweenness
returns a
communities
object, please see the communities
manual page for details.
References
M Newman and M Girvan: Finding and evaluating community structure in networks, Physical Review E 69, 026113 (2004)
See Also
edge_betweenness
for the definition and calculation
of the edge betweenness, cluster_walktrap
,
cluster_fast_greedy
,
cluster_leading_eigen
for other community detection
methods.
See communities
for extracting the results of the community
detection.
Examples
# NOT RUN {
g <- sample_pa(100, m = 2, directed = FALSE)
eb <- cluster_edge_betweenness(g)
g <- make_full_graph(10) %du% make_full_graph(10)
g <- add_edges(g, c(1,11))
eb <- cluster_edge_betweenness(g)
eb
# }
Community examples
g <- sample_pa(100, m = 2, directed = FALSE) eb <- cluster_edge_betweenness(g) g <- make_full_graph(10) %du% make_full_graph(10) g <- add_edges(g, c(1,11)) eb <- cluster_edge_betweenness(g) eb
g <- sample_pa(100, m = 2, directed = FALSE) eb <- cluster_edge_betweenness(g) g <- make_full_graph(10) %du% make_full_graph(10) g <- add_edges(g, c(1,11)) eb <- cluster_edge_betweenness(g) eb