= 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>.<Fast unfolding of communities in large networks by Vincent D. Blondel and others>[§2, Method, pp. 4–5 of the preprint: local moves followed by aggregation]{ref}
For an undirected unweighted <graph> with $m$ edges, <degrees of vertices> $k_i$ and community labels $c_i$, the objective is
$$
Q=\frac1{2m}\sum_{i,j}\left(A_{ij}-\frac{k_ik_j}{2m}\right)\mathbf1\{c_i=c_j\}.
$$
The term $k_ik_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. \b[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$.
Back to article page
