Louvain Algorithm: Theory, Design, and Implementation

The Louvain algorithm is a fast, accurate community‑detection method based on multi‑level modularity optimization, widely regarded as one of the best algorithms for uncovering hierarchical community structures in large networks.

Its optimization goal is to maximize the overall modularity of the graph, where modularity is computed using the total number of edges (m), node degree sums (k_i, k_j), and edge weights (A_{i,j}). The algorithm does not invent modularity but provides an efficient way to optimize it.

The algorithm operates in two iterative steps: Step 1 scans all nodes, evaluating the modularity gain of moving each node to the community of each neighbor and joining the community that yields the highest gain; Step 2 collapses each discovered community into a single super‑node, recomputing edge weights between these super‑nodes for the next round of Step 1. Step 1 runs in O(N) time per iteration (N = number of edges), while Step 2 runs in O(M + N) (M = number of nodes in the current iteration).

To support efficient execution, a custom graph data structure is designed, avoiding heavy hash‑table or set allocations. Each node stores fields such as count , clsid , next , prev , first , kin , kout , clskin , clstot , and eindex , while edges store their weights. This layout requires roughly 60 bytes per node and 24 bytes per edge, e.g., a graph with 10 million nodes and 20 million edges needs about 1.08 GB of memory, which remains constant throughout iterations.

The article illustrates the iterative process with a small example of five nodes, showing how nodes are merged into communities, collapsed, and re‑scanned until a single community remains, at which point the algorithm converges.

An example C implementation based on the described data structures is available at https://github.com/liuzhiqiangruc/dml/blob/master/cls/louvain.c . On a real‑world graph with 700 k nodes and 2 M edges, the algorithm converges in 1.77 seconds, demonstrating its suitability for large‑scale graph analysis.