The idea: move nodes, then zoom out
A community is a group of nodes that has many edges inside it and few edges to the rest of the graph: friend circles in a social network, groups of pages about one topic, modules in a software dependency graph. The Louvain method (Blondel et al., 2008) finds them in two phases that repeat. In phase 1 every node moves to the neighbouring community where it fits best. In phase 2 each community becomes one super-node, and phase 1 runs again on that smaller graph. It stops when nothing moves.
The page runs it on 12 nodes and m = 19 edges. Each half is two triangles joined by 3 edges, and one bridge, 5–6, joins the two halves. A good answer is the two halves. Louvain gets there in two levels.
Modularity: a score for a split
Modularity Q compares the edges inside each community with the number you would expect if the same nodes kept their degrees but the edges were wired at random:
Q = Σ over communities c of [ in_c / 2m − (tot_c / 2m)² ]
| Term | Meaning | In the page |
|---|---|---|
m | total edge weight | 19 |
in_c | edges inside c, each counted twice (once from each end) | a triangle: 6 |
tot_c | sum of the degrees of the nodes in c, written Σtot | triangle {0, 1, 2}: 3 + 3 + 3 = 9 |
(tot_c / 2m)² | the share of edge ends you would expect inside c by chance | (9 / 38)² = 0.056 |
Q is 0 when there are no more edges inside the communities than chance would give, and it goes up as communities get denser than chance. With every node alone, Q = −0.084. With the 4 triangles it is 0.381, and with the 2 halves it is 0.447. Putting the whole graph in one community gives Q = 0, because then there is nothing to compare against.
Phase 1: local moves and ΔQ
Every node starts alone. Louvain visits the nodes in order. Each node takes itself out of its community and works out what it would gain by joining each neighbour's community, or by going back to its own. Only local numbers are needed:
ΔQ(join C) = k_i,in / m − Σtot_C · k_i / 2m²
Here k_i,in is the number of edges from node i into C, k_i is i's degree, and
Σtot_C is C's total degree. The first term rewards edges into C. The second term is a
penalty for joining a big community, where many edges would land anyway. The node joins the community
with the largest ΔQ. A sweep visits every node once, and sweeps repeat until one moves
nothing. Each move can only raise Q, so phase 1 always ends.
A worked example (Demo: a second sweep moves node 6 again). In sweep 1, node 6 joined node 7, then node 7 left for {7, 8}. So in sweep 2 node 6 is alone. It has degree k = 4 (three triangle edges and the bridge):
| Option | k_i,in | Σtot | ΔQ |
|---|---|---|---|
| join {3, 4, 5} over the bridge | 1 | 10 | −0.003 |
| stay alone | 0 | 0 | 0.000 |
| join {7, 8} | 2 | 6 | +0.072 |
| join {9, 10, 11} | 1 | 9 | +0.003 |
Node 6 joins {7, 8} and Q rises to 0.381. A sweep 3 then moves nothing, so phase 1 ends with the 4 triangles (Demo: phase 1 finds 4 triangles). The order matters: real implementations shuffle the nodes, which can give a slightly different result on each run.
Phase 2: collapse communities into super-nodes
Phase 1 is stuck. Moving one node from a triangle to its partner triangle would break up a triangle and lower Q. But moving a whole triangle would raise Q. Phase 2 makes that possible: each community becomes one node. Edges inside a community become a self-loop weight on its super-node, and the edges between two communities add up into one weighted edge (Demo: collapse triangles into super-nodes).
Q does not change during the collapse: it is the same split, just drawn smaller. Phase 1 then runs on 4 super-nodes. A joins B (ΔQ = +0.033) and C joins D, so Q = 0.447. The next collapse leaves 2 super-nodes, AB and CD, joined by the single bridge edge. At level 3 neither moves, so Louvain stops and reports the two halves (Demo: full Louvain, 2 levels to 2 halves).
Why it is fast, and its weak spots
| Property | What it means |
|---|---|
| Local work | A node only looks at its neighbours, so one sweep costs O(m). |
| Shrinking graph | Each level has far fewer nodes, so later levels are cheap. Graphs with millions of nodes finish in minutes. |
| A hierarchy for free | Every level is a coarser split: triangles inside halves here, neighbourhoods inside cities in a real network. |
| Badly connected communities | A node that holds a community together can leave it, and the rest can fall apart into pieces that are no longer connected. The Leiden algorithm adds a refinement step that fixes this. |
| Resolution limit | Maximizing Q can merge small, clearly separate groups in a large graph. A resolution parameter γ, written (tot_c / 2m)² · γ, tunes the size of the communities. |
See also PageRank (another way to read structure from a large graph), hierarchical clustering (merging clusters bottom-up, like Louvain's levels), connected components (groups with no edges between them at all) and k-means (clustering points, where you choose k up front; Louvain finds the number of communities itself).
What the page leaves out
Random node order and the run-to-run differences it causes; weighted and directed graphs as input (the formulas are the same with weights, and the directed version uses in- and out-degrees); the resolution parameter γ; Leiden's refinement phase and its guarantee that communities stay connected; other ways to find communities, such as label propagation, Infomap and spectral clustering; and the fact that finding the split with the highest modularity is NP-hard, so Louvain is a fast heuristic that usually finds a good split, not always the best one.