Source-linked AI summary
Engineering Parallel Algorithms for Community Detection in Massive Networks
Christian L. Staudt, Henning Meyerhenke
TL;DR
Massive graph datasets require fast community detection, but few existing implementations exploit parallelism at scale. The paper introduces a shared-memory framework with parallel label propagation, Louvain variants, and an ensemble, finding fast and qualitatively strong methods suitable for billion-edge graphs.
Problem
Few community-detection implementations exploit parallelism despite graph datasets reaching billions of edges and requiring near-linear-time processing.
Method
The paper develops a flexible shared-memory framework implementing parallel label propagation, parallel Louvain, Louvain with refinement, and an ensemble scheme.
Results
PLP reaches 50M edges per second on large graphs, while PLM and PLMR provide fast, qualitatively strong solutions and three algorithms reach the Pareto frontier against state-of-the-art methods.
Takeaways & Limitations
The authors recommend PLM and PLMR as qualitatively strong and fast methods for massive networks, with implementations suitable for billion-edge datasets.
Abstract
from arXiv · showhide
The amount of graph-structured data has recently experienced an enormous growth in many applications. To transform such data into useful information, fast analytics algorithms and software tools are necessary. One common graph analytics kernel is disjoint community detection (or graph clustering). Despite extensive research on heuristic solvers for this task, only few parallel codes exist, although parallelism will be necessary to scale to the data volume of real-world applications. We address the deficit in computing capability by a flexible and extensible community detection framework with shared-memory parallelism. Within this framework we design and implement efficient parallel community detection heuristics: A parallel label propagation scheme; the first large-scale parallelization of the well-known Louvain method, as well as an extension of the method adding refinement; and an ensemble scheme combining the above. In extensive experiments driven by the algorithm engineering paradigm, we identify the most successful parameters and combinations of these algorithms. We also compare our implementations with state-of-the-art competitors. The processing rate of our fastest algorithm often reaches 50M edges/second. We recommend the parallel Louvain method and our variant with refinement as both qualitatively strong and fast. Our methods are suitable for massive data sets with billions of edges.
I. INTRODUCTION
Massive graph datasets make fast community detection increasingly necessary, yet few parallel implementations handle billions of edges. The paper develops and evaluates a shared-memory framework and parallel heuristics targeting high quality and short runtimes.
- Motivation and goals: Only two of 15 DIMACS modularity-optimization implementations used parallelism, and very few handled billion-edge graphs reasonably quickly.
- Motivation and goals: The authors target algorithms that process billion-edge networks in minutes rather than hours while remaining competitive with established sequential methods.
- Contributions: The framework implements parallel label propagation, the first large-scale parallel Louvain method, Louvain with refinement, and an ensemble combining these approaches.
- Results: PLP reaches 50M edges per second on large graphs, while PLM is fast and qualitatively strong, PLMR can improve solution quality, and EPP can reduce time to solution on some instances.
- Results: Three implementations lie on the Pareto frontier against state-of-the-art algorithms in comparative experiments.
- Framework: The C++ framework is flexible and extensible, supports rapid algorithm-engineering iteration, and is distributed through NetworKit.
III. ALGORITHMS
The algorithms section describes parallel label propagation for weighted graphs and implementation choices that address asynchronous updates and load imbalance in heterogeneous networks.
- Parallel Label Propagation: Label propagation repeatedly assigns each node the most frequent neighboring label until densely connected groups reach a stable consensus.
- Parallel Label Propagation: PLP adapts label propagation to weighted graphs by selecting the neighborhood label with maximum incident edge weight.
- Parallel Label Propagation: PLP stops when the number of nodes changing labels falls below threshold θ.
- Implementation: Parallel execution shares a label array across threads, allowing asynchronous updates in which neighboring nodes may expose labels from different iterations.
- Implementation: Guided scheduling assigns decreasing node ranges to threads to mitigate degree-driven load imbalance in scale-free networks.
B. Parallel Louvain Method (PLM)
PLM parallelizes Louvain’s local moves and graph coarsening within a shared-memory implementation. It accepts stale move data for parallelism, while optimizing modularity computations and coarsening overhead.
- Algorithm: Louvain repeatedly moves nodes to neighboring communities for local modularity gains, then contracts communities into supernodes and continues recursively.
- Modularity: Local modularity changes can be computed by scanning only a moved node’s neighborhood.
- Parallelization: Parallel moves may use stale data, so monotonous modularity increase is not guaranteed and some moves can temporarily decrease modularity.
- Parallelization: PLM parallelizes both the node-move phase and the coarsening phase of Louvain.
- Implementation: Replacing per-node maps with one vector per thread accelerates PLM by a factor of 2 on average at memory cost O(p · n).
- Coarsening: Parallel coarsening builds thread-local coarse graphs and merges their adjacencies in parallel.
C. Parallel Louvain Method with Refinement (PLMR)
PLMR extends parallel Louvain with an additional move phase after each prolongation, allowing node assignments to be reconsidered at coarser levels. The refinement improves solution quality at the cost of additional iterations.
- PLMR adds a move phase after each prolongation in the multilevel Louvain hierarchy.This re-evaluates node assignments after changes at the next coarser level.
- The refinement creates additional opportunities for modularity improvement while increasing iterations over the node set at each level.
- PLMR is implemented recursively using the same concepts as the parallel Louvain method.
D. Ensemble Preprocessing (EPP)
Ensemble Preprocessing combines multiple base community assignments to identify consensus communities, coarsen the graph, and apply a final algorithm to the reduced problem. A parallel hashing implementation constructs these consensus labels efficiently.
- Interface: EPP takes a graph G = (V, E) and ensemble size b as input and returns communities ζ : V →N.
- EPP workflow: Ensemble Preprocessing assigns the graph to multiple base algorithms, coarsens it using consensus communities, and applies a final algorithm before prolongating results.Coarsening reduces the problem size and distinguishes contested from unambiguous graph regions.
- Consensus construction: Only node pairs placed in the same community by every base solution are assigned together in the core communities.The consensus criterion is defined across all base assignments.
- Parallel implementation: A b-way hash maps the community identifiers from base solutions to new core-community identifiers in parallel.The implementation uses the djb2 hash function; collisions are described as unlikely.
A. Framework and Settings
The framework implements parallel community-detection algorithms in C++11 on a general-purpose adjacency-array graph structure. It is released as reusable software with a Python interface, and experiments average repeated runs to reduce fluctuations.
- Implementation framework: All implementations use C++11 and a general-purpose adjacency-array graph structure for community detection.Adjacencies are stored in std::vector structures supporting efficient node and edge insertions and deletions.
- Software availability: NetworKit publishes the community-detection implementations under a permissive free-software license for reproduction, reuse, and contribution.The toolkit combines parallel C++ algorithms with an interactive Python interface.
- Experimental settings: Representative experiments average quality and speed over multiple runs to compensate for fluctuations.The experimental platform is documented in Table I.
B. Networks
The evaluation uses a diverse collection of real-world and synthetic networks, emphasizing complex networks while including multiple application domains. The networks are undirected and unweighted, and results assess both solution quality and running time across graphs of varied structure and size.
- Network diversity: The test set spans web, internet topology, social, scientific coauthorship, and other real-world and synthetic graph categories.The study focuses on real-world complex networks while adding non-complex and synthetic instances for variety.
- Test-set design: 20 networks from different domains form the main test set, selected to support comparison with competing codes and generalizable results.Most test networks come from the DIMACS Implementation Challenge and Stanford Large Network Dataset collections.
- Graph properties: The graphs are undirected and unweighted, with structural summaries covering size, maximum degree, connected components, and local clustering coefficient.Maximum degree indicates possible load-balancing issues, connected components indicate isolated groups, and local clustering signals dense subgraphs.
- Evaluation measures: The evaluation measures solution quality and running time for every network in the test set.Figures break results down by network, with charts ordered by graph size.
- Performance aggregation: A Pareto evaluation condenses the per-network performance results into a single performance score.
A. Parallel Label Propagation (PLP)
PLP scales effectively on a massive web graph and offers very high processing speed, but its faster runtime can come with lower community-detection quality than PLM. The broader experiments also examine refinement and ensemble strategies as quality-oriented alternatives.
- Scaling: A speedup of about factor 8 is achieved when scaling PLP from 1 to 32 threads on the uk-2007-05 web graph.The experiment uses 16 physical cores; the 16-to-32-thread step relies on hyperthreading.
- Quality and runtime: PLP can solve instances in only half the time required by PLM, but at a significant loss of modularity.
- Refinement: Adding a refinement phase generally leads to a sometimes significant improvement in modularity, paid for by a small increase in running time.
- Ensemble approach: The ensemble approach improves modularity on most instances by exploiting differences in base solutions and classifying contested nodes.
- Ensemble approach: For larger networks, the ensemble approach costs about 5 times the running time of PLP alone.For small networks, overhead can dominate; compared with PLM, quality is slightly worse in most cases.
E. Comparison with State-of-the-Art Competitors
Compared with state-of-the-art competitors, the parallel methods occupy strong speed–quality positions, while the highest-quality alternatives are often much more computationally expensive. PLM and PLMR emerge as recommended candidates for large-network community detection.
- CLU_TBB solves larger instances faster than PLM, but PLM has clearly superior quality on most networks.
- RG, CGGC, and CGGCi achieve very high quality but often require orders of magnitude more computation time than PLM.
- PLP is fastest, but its solution quality is suboptimal.
- PLM and PLMR are qualitatively strong and fast, with PLMR improving solution quality for a small computational extra charge.
- The LFR benchmark evaluates ground-truth recovery as the mixing parameter µ increases and difficulty rises.
H. One More Massive Network
On a 3.3-billion-edge web graph, the parallel methods process massive data in minutes while offering different quality–time trade-offs. The paper also notes that community detection can simplify visual representation, but domain-specific validation remains outside scope.
- On uk-2007-05, PLM requires about 156 seconds and reaches slightly higher modularity than EPP(4,PLP,PLMR), which takes about 219 seconds.
- Weak-scaling experiments double graph size and thread count, while perfect scaling is not expected because of complex input structure.
- The study evaluates modularity and running time but leaves domain-specific validation beyond its scope because reliable ground truth is often unavailable.
- PLM, PLMR, and EPP(4,PLP,PLMR) produce similar-resolution community graphs with approximately 100 communities for PGPgiantcompo.
- PLM detects high-quality communities in a 3.3-billion-edge network in under 3 minutes using 32 threads.
- The implementations are published as part of the open-source NetworKit package.
APPENDIX
The appendix documents additional performance and scaling comparisons for PLP, PLM, PLMR, EPP, CGGCi, and PLM*.
- Figures 12 and 13 characterize PLP through active and updated labels and per-iteration running time.
- Figure 10 reports weak scaling for PLP and PLM on HUD graphs.
- Figure 14 reports weak scaling for PLP and PLM on R-MAT graphs.
- Figure 15 compares EPP(4,PLP,PLMR) with single PLP on quality difference and running-time ratio.
- Figure 16 compares competitor CGGCi with baseline PLM, while Figure 17 compares PLM* with baseline PLM.