Module community 

Communities, by moving nodes until modularity stops going up.

Two algorithms and the measure they both optimise.

louvain() is Blondel, Guillaume, Lambiotte and Lefebvre, “Fast unfolding of communities in large networks”, J. Stat. Mech. 2008, with the queue driven local move from Traag, “Faster unfolding of communities”, Phys. Rev. E 2015.

leiden() is Traag, Waltman and van Eck, “From Louvain to Leiden: guaranteeing well-connected communities”, Scientific Reports 2019.

What modularity is

A community is supposed to be a group with more edges inside it than you would expect by chance. Modularity is that sentence as a number: for each community, the share of all edge ends that are inside it, minus the share you would get if the same nodes kept their degrees and rewired at random. It runs from about -0.5 to 1, and a real social graph split sensibly comes out around 0.4 to 0.7.

The resolution turns the dial on what “expected” means. Above one, chance looks more likely and communities come out smaller; below one, larger. It is the honest way to deal with modularity’s resolution limit, which is that at resolution one no method can see a community much smaller than the square root of the edge count.

Why Leiden and not just Louvain

Louvain has a defect that took eleven years to write down: a community it returns can be internally disconnected. It happens when a node that was acting as the only bridge inside its community moves out, and the community is then aggregated into a single node before anybody notices it fell into two pieces. Once aggregated the pieces can never be separated again. On real graphs the 2019 paper found this in a few percent of communities, and it is not a rounding error: a “community” in two halves with nothing joining them is not a community by any reading.

Leiden fixes it by putting a step between the moving and the aggregating. The partition found by moving is refined: inside each community, nodes start alone again and merge only into subsets that are well connected to the rest of the community, and merges are chosen randomly among the good ones rather than greedily. The graph is then aggregated on the refined subsets rather than on the communities, so a community that fell into two pieces arrives at the next level as two nodes and can still be pulled apart.

Both are here because the difference is worth being able to measure, and because Louvain is still the thing everybody else reports.

Why the answer is fixed

The visiting order is random in both, and Leiden’s merges are random by design, which is where the guarantee comes from. All of it is drawn from yo_common::Rng on a fixed seed, so two runs over one snapshot agree.

use yo_graph::{Graph, NO_PROPS, Snapshot, algo};

let mut g = Graph::new();
// Two four cliques joined by a single edge.
for (a, b) in [(1u64, 2u64), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)] {
    g.link(a, b, 1, NO_PROPS)?;
    g.link(a + 10, b + 10, 1, NO_PROPS)?;
}
g.link(4, 11, 1, NO_PROPS)?;

let s = Snapshot::of(&g);
let c = algo::leiden(&s);
assert_eq!(c.count(), 2);
assert!(algo::modularity(&s, c.labels()) > 0.4);

Constants

RESOLUTION

The resolution that makes modularity mean what the 2004 paper says.

Functions

leiden

The communities of g, by the Leiden method.

leiden_with

The same, at a resolution other than one.

louvain

The communities of g, by the Louvain method.

louvain_with

The same, at a resolution other than one.

modularity

How good a partition of g is, at resolution one.

modularity_with

The same, at a resolution other than one.