Parallel Louvain Algorithms with Convergence Guarantee

Community detection is a fundamental problem in network science. The Louvain algorithm is a widely used hierarchical method applied to scientific, social, biological, and commercial networks. Scaling Louvain to large networks requires parallelization, but existing parallel implementations lack convergence guarantees and often rely on outdated modularity data due to concurrent updates. We present the first parallel Louvain algorithms with provable convergence. We give two distinct parallelization schemes for Louvain's local-move phase: (1) distance-2 community coloring, an expository approach that prevents concurrent access to the same community at high cost, and (2) community versioning, which enforces consistency through version numbers. Both ensure convergence, filling a key theoretical gap. Our OpenMP-based implementation shows that community versioning achieves strong empirical performance on large, real-world networks, matching the speed and modularity quality of state-of-the-art methods while providing formal convergence guarantees.