Past exam of the mathematical and Computational Biology course of the University of Cambridge / 2025 / Paper 2 / 6 / f / Solution

The Louvain method approximately maximizes network modularity. Start with each vertex in its own community. Repeatedly visit each vertex, evaluate moving it into each neighbouring community, and accept the move with the greatest positive modularity gain. When no such local move improves the score, contract each community into a new weighted vertex, summing inter-community edge weights and retaining internal edges as self-loops. Repeat local optimization and contraction until no further gain is obtained, then map the communities back to the original vertices.^[ref]

For an undirected unweighted graph with $m$ edges, degrees of vertices $k_i$ and community labels $c_i$, the objective isThe term $k_i{k}_j/(2m)$ subtracts the expected connectivity in a degree-based network null model. If all vertices are put in one community, the observed and expected total weights cancel, so $Q=0$. A partition with excess internal connectivity can have $Q>0$, and merging away that structure reduces the score. The modularity objective and positive-gain rule prevent arbitrary merging merely to increase cluster size. They do not forbid a single community in every possible network: if there is no better modular partition, one community may be an appropriate result. The method is a greedy heuristic, so it does not guarantee the global maximum of $Q$.