Leiden community detection

Traag, Waltman and van Eck (2019), Algorithm A.2: fast local moving (queue-based, random visiting order), refinement inside each community (well-connected singletons join well-connected sub-communities with probability proportional to exp(dH / theta)) and aggregation of the refined partition, repeated until every community is one aggregate node. Quality is modularity (node weight = strength, r = gamma / 2m) or the constant Potts model of the paper's eq. (2) (node weight 1, r = gamma); moving v into D gains k_vD - r w_v W_D.

Usage

Leidenclus(
  graph,
  resolution = 1,
  quality = "modularity",
  max_iter = 20,
  theta = 0.01,
  seed = 0
)

Arguments

graph

Symmetric non-negative weighted adjacency matrix.

resolution

The resolution parameter gamma.

quality

"modularity" or "cpm".

max_iter

Leiden iterations; stops once an iteration changes nothing.

theta

Randomness of the refinement merge.

seed

Philox seed.

Value

list: labels, estimate, quality, n_communities, connected, passes, n, method.

Details

Randomness: the visiting orders and refinement draws come from the morie Philox stream (a new stream per phase, same order as the Python arm), so runs agree exactly across arms.

References

Traag, V. A., Waltman, L. and van Eck, N. J. (2019). From Louvain to Leiden: guaranteeing well-connected communities. Scientific Reports 9, 5233.

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
Leidenclus(A + t(A))$labels
#> [1] 0 0 0 1 1 1