A Bit of History
From modularity to fast unfolding
The important shift was computational: instead of repeatedly calculating expensive global edge scores, Louvain makes cheap local moves and periodically shrinks the graph. That combination made modularity optimization practical on much larger sparse networks.
What Counts as a Community?
A community is not merely a visibly dense patch. It is a group whose internal connectivity is surprisingly high relative to a degree-preserving null model. A celebrity with thousands of links should contribute less evidence than the same link from a low-degree vertex, because the celebrity would connect widely even in a randomized network.
Observed signal
How much edge weight actually falls inside each proposed group?
Random baseline
How much internal weight would be expected after random rewiring that preserves vertex strengths?
Modularity
The excess of observed internal connection over that baseline, summed across groups.
Modularity, Term by Term
For an undirected weighted graph, let $A_{ij}$ be the edge weight between $i$ and $j$, $k_i=\sum_j A_{ij}$ be vertex $i$’s strength, and $m$ be the total undirected edge weight. A common resolution-aware form is:
$A_{ij}$ = observed weight $k_i k_j/(2m)$ = expected weight $\delta(c_i,c_j)$ = same-group gate $\gamma$ = resolution
The Kronecker delta discards every pair in different communities. The remaining terms reward unexpectedly strong internal edges and penalize groups whose total degree alone would make many internal edges unsurprising. An equivalent community-level form is often easier to compute:
Here $w_{\mathrm{in}}(C)$ counts each undirected internal edge once, while $\mathrm{vol}(C)=\sum_{i\in C}k_i$. Modularity is a score for a partition, not proof that the partition is uniquely correct.
Reading the sign of $\Delta Q$
A positive $\Delta Q$ means the proposed move improves the objective; zero gives no improvement; negative makes the partition worse. Louvain accepts only improving moves, so modularity never decreases during a run—although the final local optimum can depend on vertex order and tie-breaking.
The Two Alternating Phases
- Initialize. Put every current vertex in its own community and record community volumes. At later levels, a “vertex” may already represent many original vertices.
- Remove and test. Temporarily remove vertex $i$ from its group. Accumulate its edge weight into each neighboring community and evaluate the insertion score for each candidate.
- Take the best improving move. Insert $i$ into the community with the largest positive modularity gain. Repeat vertex sweeps until a complete sweep makes no move.
- Contract. Replace each discovered community by one super-node. Sum parallel inter-community edges; turn internal edges into self-loops. Total edge weight is conserved.
- Repeat and lift labels. Run local moving on the smaller weighted graph. When no level improves modularity, map the super-node labels back to the original vertices.
After temporarily removing $i$, implementations compare candidate communities using a scaled insertion score:
The first term favors communities connected strongly to $i$; the second resists dumping everything into one enormous group. The omitted positive constant is shared by all candidates, so comparing these scores gives the same choice as comparing exact modularity gains.
Visual Walkthrough: From Vertices to Super-Nodes
Suppose a local phase settles eight vertices into three groups. Contraction does not throw information away: it records internal edge weight as a loop and sums every edge crossing the same pair of groups. The next local phase therefore optimizes the same objective on a smaller representation.
Resolution, Order, and Stopping
| Control | What it changes | Practical guidance |
|---|---|---|
| Resolution $\gamma$ | Higher values penalize large-volume groups more, usually producing smaller communities; lower values favor larger ones. | Sweep several values and inspect stability instead of treating $\gamma=1$ as universally correct. |
| Vertex order | Greedy moves alter the choices available later in the same sweep. | Run several randomized seeds; compare modularity and membership stability. |
| Tolerance | Defines how much gain counts as meaningful and when a level stops. | Use a small positive tolerance to avoid floating-point churn. |
| Edge weights | Stronger relationships contribute more to degrees, attachment, and modularity. | Require finite, nonnegative weights for the standard formulation and document preprocessing. |
Disconnected components can be processed independently. An isolated vertex has zero strength and contributes neither reward nor penalty, so it can remain a singleton. Standard modularity is not designed for arbitrary negative weights; signed networks require a modified objective.
Implementation
The tabs below implement the local-moving kernel for a weighted, undirected graph. Store each edge weight once, but include both directions in the adjacency list, as the examples do. The crucial detail is to remove a vertex from its old community before comparing insertion scores—including the score for returning to the old community.
What the kernel deliberately leaves out
These compact listings show one local-moving phase. A full production implementation also renumbers the resulting communities, builds the contracted weighted graph, preserves self-loops, composes labels across levels, randomizes or controls vertex order, and returns the best level. Mature graph libraries are preferable for large or high-stakes workloads.
Contraction pseudocode
def contract(edges, community):
coarse_weight = defaultdict(float)
for u, v, w in edges: # each undirected edge appears once
a, b = community[u], community[v]
key = (min(a, b), max(a, b))
coarse_weight[key] += w # a == b becomes a self-loop
return [(a, b, w) for (a, b), w in coarse_weight.items()]
# Repeat:
# labels = louvain_phase1(coarse_graph)
# coarse_graph = contract(coarse_graph, labels)
# compose labels with the original-vertex mapping
The contraction step sums parallel edges instead of discarding them. That is what makes the coarse graph encode exactly how strongly the discovered communities interact.
Complexity Analysis
With cached vertex strengths, community volumes, and edge weight from a vertex into neighboring communities, one full sweep is proportional to the adjacency entries examined:
If a level uses $s_\ell$ sweeps and the contracted graph at that level has $E_\ell$ edges, a more honest total is $O(\sum_\ell s_\ell E_\ell)$. The graph usually shrinks quickly and only a few sweeps are needed, so Louvain is often described as near-linear in practice. That phrase is empirical—not a universal worst-case guarantee.
Why it is fast
A candidate move does not recompute $Q$ from scratch. It needs only the vertex strength, candidate-community volume, and weight from the vertex into that community. Contraction then reduces the next level’s problem size.
Choosing a Community Method
| Method | Main idea | Strength | Watch for |
|---|---|---|---|
| Louvain | Greedy modularity moves + contraction | Very fast; naturally multilevel | Order dependence; disconnected or weakly connected groups can occur |
| Leiden | Louvain plus partition refinement | Better-connected communities; strong default for modularity-style work | Still depends on objective, resolution, and random seed |
| Girvan–Newman | Remove high-betweenness edges | Intuitive dendrogram on small graphs | Far too expensive for large networks |
| Label propagation | Adopt neighbors’ dominant label | Extremely simple and fast | Unstable outcomes and limited objective control |
| Spectral partitioning | Use Laplacian eigenvectors | Strong mathematical foundation | Eigenvector computation and choice of cut/cluster count |
Real-World Applications
Social networks
Discover circles of interaction, interest groups, or organizational substructures from weighted relationships.
Biological networks
Find modules in protein-interaction, metabolic, ecological, or gene co-expression graphs.
Behavior graphs
Group products, sessions, or accounts connected by co-purchase, co-view, or transaction patterns.
In every domain, a detected group is a hypothesis generated from the graph and objective. Validate it with domain labels, temporal stability, held-out behavior, or downstream usefulness; high modularity alone does not establish a real-world category.
Exercises
Build the intuition
- Draw two triangles joined by one bridge. Starting from singleton communities, identify which candidate communities each bridge endpoint must evaluate.
- Explain why moving a vertex into the largest neighboring community is not always the best modularity move.
- Contract your two triangles. What becomes a self-loop, and what becomes the edge between the two super-nodes?
- Predict how increasing $\gamma$ affects community size. Then test several values in a library implementation.
- Challenge: run multiple random seeds, align the resulting labels, and calculate how often each pair of vertices appears in the same community.
Hint: community IDs such as 0 and 4 have no semantic meaning. Compare sets of vertices or a co-assignment matrix, not the raw numeric labels.
Limitations
What a high modularity score does not guarantee
- No unique truth: many very different partitions can have nearly identical modularity.
- Resolution limit: small genuine groups may be merged in a large network; tuning $\gamma$ changes but does not magically remove model dependence.
- Local optimum: vertex order, seed, and ties can lead to different final partitions.
- Connectivity: Louvain may output communities that are internally disconnected or only weakly connected; Leiden is often preferred when this matters.
- Static snapshot: temporal, overlapping, directed, signed, or multilayer networks may need objectives designed for those structures.
Report the graph construction, edge-weight meaning, objective, resolution, seed policy, number of runs, selected level, and stability checks. Community detection is most useful when its modeling choices are visible.