One Leiden refinement pass over an existing partition

Louvain can leave a community internally disconnected. Leiden inserts a refinement phase between local moving and aggregation: each community is broken back into singletons and rebuilt from the inside, and a node only joins a sub-community that is itself well connected to the rest of its original community.

Usage

Sgtleid(A, labels, gamma = 1)

Arguments

A

Non-negative weighted adjacency matrix, symmetrised on entry.

labels

Current community index of each node.

gamma

CPM resolution, default 1.

Value

List with labels_new, Q_new, n_communities, n.

Details

Determinism: nodes are visited in index order and communities in order of first appearance; no random restarts.

Formula: CPM quality H = sum_c [e_c - gamma * C(n_c, 2)]; a subset C of community S is well connected when E(C, S \ C) >= gamma * |C| * (|S| - |C|).

References

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

Examples

A <- matrix(0, 6, 6)
A[1:3, 1:3] <- 1; A[4:6, 4:6] <- 1; A[3, 4] <- A[4, 3] <- 1; diag(A) <- 0
Sgtleid(A, labels = c(1, 1, 1, 2, 2, 2))$n_communities
#> [1] 6