Community detection: fast greedy modularity and walktrap

GraphModularity: Newman's modularity of a partition of a weighted graph. FastGreedyModularity: Clauset-Newman-Moore greedy merging, as igraph::cluster_fast_greedy. WalktrapCommunities: Pons-Latapy random-walk distances with vertex loops, as igraph::cluster_walktrap. Both return the partition of largest modularity along the merge sequence. Identical to the Python arm morie.fn.communities.

Usage

GraphModularity(A, membership)

FastGreedyModularity(A)

WalktrapCommunities(A, steps = 4L)

Arguments

A

Symmetric non-negative weighted adjacency matrix.

membership

Community labels.

steps

Random-walk length.

Value

Modularity (numeric) or list with membership, modularity, merges, max_modularity.

References

Clauset, A., Newman, M. E. J. and Moore, C. (2004). Finding community structure in very large networks. Physical Review E 70, 066111.

Pons, P. and Latapy, M. (2006). Computing communities in large networks using random walks. Journal of Graph Algorithms and Applications 10, 191-218.

Newman, M. E. J. (2004). Analysis of weighted networks. Physical Review E 70, 056131.

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
A <- A + t(A)
FastGreedyModularity(A)$membership
#> [1] 1 1 1 2 2 2
WalktrapCommunities(A)$membership
#> [1] 1 1 1 2 2 2
GraphModularity(A, c(1, 1, 1, 2, 2, 2))
#> [1] 0.3571429