Girvan-Newman communities

Repeatedly removes the edge of highest betweenness (recomputed after every removal by Brandes' algorithm; ties go to the lexicographically smallest edge) and scores each new split by the modularity of the original graph, Q = sum_c (e_c / m - (K_c / 2m)^2). Returns the partition of maximum Q, or the first with n_communities components. Any non-zero entry of the symmetric matrix is an edge.

Usage

GirvanNewman(G, n_communities = NULL)

Arguments

G

Adjacency matrix of an undirected graph.

n_communities

Optional number of communities.

Value

list(labels (0-based), estimate, modularity, n_communities, removed (edges, 0-based), path (components and modularity per split)).

References

Girvan, M. and Newman, M. E. J. (2002). Community structure in social and biological networks. PNAS 99, 7821-7826. Newman, M. E. J. and Girvan, M. (2004). Physical Review E 69, 026113.

Examples

A <- matrix(0, 6, 6)
A[cbind(c(1, 1, 2, 3, 4, 4, 5), c(2, 3, 3, 4, 5, 6, 6))] <- 1
GirvanNewman(A + t(A))$labels
#> [1] 0 0 0 1 1 1