Louvain Community Detection

Communities without a definition

A social network, a citation graph, a protein-interaction map — all of these have visible clusters of densely interconnected nodes with comparatively sparse connections between clusters, but "community" has no single formal definition. The Louvain method (Blondel, Guillaume, Lambiotte and Lefebvre, 2008) sidesteps the definitional problem by optimizing a concrete, computable score called modularity, and letting whatever partition maximizes that score stand in for "the communities."

live demo · agents clustering into distinct flocking groups● LIVE

Modularity: more edges inside than chance predicts

Modularity Q compares the actual fraction of a graph's edges that fall inside proposed communities against the fraction you would expect if the same degree sequence were connected up at random:

Q = (1 / 2m) Σ_ij [ A_ij - (k_i k_j) / (2m) ] δ(c_i, c_j)

A_ij   = 1 if an edge connects nodes i, j, else 0
k_i    = degree of node i
m      = total number of edges in the graph
δ(c_i,c_j) = 1 if i and j are in the same community, else 0

The term k_i·k_j / 2m is the expected number of edges between i and j under a random-graph null model that preserves each node's degree (the configuration model). Q sums, over every pair of nodes placed in the same community, how much more (or less) connected they actually are than that random baseline predicts. Real-world networks with visible community structure typically score Q between roughly 0.3 and 0.7; a random graph scores close to zero.

Phase 1: local moving

Start with every node in its own singleton community. Visit each node in turn and consider moving it into the community of each of its neighbours, computing the resulting change in Q for each candidate move (which can be computed in constant time per neighbour using only local information — the algorithm's key efficiency trick). Move the node to whichever neighbouring community gives the largest positive gain in Q, or leave it where it is if no move helps. Repeat over all nodes, in random order, until no single move can improve Q any further.

Phase 2: aggregation, then repeat

Collapse every community found in phase 1 into a single super-node. Edges within a community become a self-loop on its super-node (weighted by the number of internal edges); edges between two communities become a single weighted edge between the corresponding super-nodes. Run phase 1 again on this much smaller, coarser graph — merging communities into larger communities exactly the way phase 1 merged nodes into communities. Alternate the two phases until Q stops improving. Each pass typically shrinks the graph by an order of magnitude, so the whole process converges in only a handful of passes even on networks with tens of millions of edges — this speed is the main reason Louvain became the default community-detection algorithm across so many fields.

A worked shrinkage

pass 1:  120,000 nodes  →  local moving  →  4,800 communities
pass 2:    4,800 nodes  →  local moving  →    310 communities
pass 3:      310 nodes  →  local moving  →     18 communities
pass 4:       18 nodes  →  local moving  →     18 communities   (Q stable, stop)

The resolution limit

Modularity maximization has a known structural bias called the resolution limit: in a sufficiently large network, two genuinely distinct small communities can score a higher Q when merged into one than when kept separate, simply because the random-graph baseline term k_i·k_j/2m shrinks as the whole network grows, making almost any merger look statistically significant. As a rule of thumb, communities much smaller than √(2m) risk being swallowed by a neighbour regardless of how internally dense they are. This is not a bug in Louvain specifically — it affects any algorithm that maximizes global modularity — but it is a real reason to treat fine-grained sub-communities detected in a very large graph with some caution.

Frequently asked questions

What exactly does modularity measure?

Modularity Q compares the actual fraction of edges falling inside communities against the fraction you would expect if edges were rewired at random while keeping each node's degree fixed. Q near 0 means the community structure is no better than chance; Q approaching 1 (rarely reached in practice) means edges are overwhelmingly concentrated inside communities. Real-world networks with strong community structure typically score Q between about 0.3 and 0.7.

Why does Louvain need two alternating phases instead of one?

The first phase (local moving) only searches for small, node-level improvements, which alone would get stuck detecting only tiny communities. The second phase (aggregation) collapses each detected community into a single super-node, so the next round of local moving operates one level higher and can merge communities into larger ones. Alternating the two phases lets the algorithm build a full hierarchy from individual nodes up to a handful of top-level communities.

What is the resolution limit and why does it matter?

Modularity maximization has a known bias: in a large network, communities smaller than roughly the square root of the total number of edges can fail to register as separate communities even when they are clearly distinct, because merging them with a neighbour increases global Q more than keeping them apart. This means Louvain (and any modularity-maximizing method) can silently merge small, real communities in very large graphs — a limitation worth knowing before trusting fine-grained structure in a huge network.

Try it live

Everything above runs in your browser — open Community Detection (Louvain) and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open Community Detection (Louvain) simulation

Louvain Community Detection: Finding Structure in Networks