Source-linked AI summary
A Comparative Analysis of Community Detection Algorithms on Artificial Networks
Zhao Yang, René Algesheimer, Claudio Juan Tessone
TL;DR
Community-detection algorithms remain difficult to compare because real-world benchmarks are small and lack objective community ground truth. The paper evaluates eight algorithms on LFR benchmark networks using complementary accuracy measures and real computing time, then derives selection guidelines from network size and mixing parameter. Across the examined benchmarks, Multilevel offers the best combined accuracy–time performance, while the recommendations identify trustworthy methods across network conditions.
Problem
Algorithm performance in accuracy and computing time remains difficult to assess because real-world networks are often small and lack objectively defined communities.
Method
The study tests eight state-of-the-art algorithms on undirected, unweighted LFR networks with non-overlapping communities, measuring complementary accuracy metrics and effective computing time across network sizes and mixing parameters.
Results
Multilevel outperforms the other examined algorithms when accuracy and computing time are considered together.
Takeaways & Limitations
Algorithm choice can be guided by observable network size and mixing parameter, with recommendations specifying methods suitable for different conditions.
Takeaways & Limitations
The study focuses mainly on mixing parameter and node number, while average degree and degree-distribution and community-distribution exponents may also affect algorithm comparisons.
Abstract
from arXiv · showhide
Many community detection algorithms have been developed to uncover the mesoscopic properties of complex networks. However how good an algorithm is, in terms of accuracy and computing time, remains still open. Testing algorithms on real-world network has certain restrictions which made their insights potentially biased: the networks are usually small, and the underlying communities are not defined objectively. In this study, we employ the Lancichinetti-Fortunato-Radicchi benchmark graph to test eight state-of-the-art algorithms. We quantify the accuracy using complementary measures and algorithms' computing time. Based on simple network properties and the aforementioned results, we provide guidelines that help to choose the most adequate community detection algorithm for a given network. Moreover, these rules allow uncovering limitations in the use of specific algorithms given macroscopic network properties. Our contribution is threefold: firstly, we provide actual techniques to determine which is the most suited algorithm in most circumstances based on observable properties of the network under consideration. Secondly, we use the mixing parameter as an easily measurable indicator of finding the ranges of reliability of the different algorithms. Finally, we study the dependency with network size focusing on both the algorithm's predicting power and the effective computing time.
Introduction
Community detection seeks groups with dense internal and sparse external connections, but algorithm performance is difficult to compare because real networks are small and lack objective community ground truth. The LFR benchmark addresses these limitations with heterogeneous network structure and supports evaluation across mixing parameters and network sizes.
- Motivation: Community detection identifies densely interconnected groups at the mesoscopic level of complex networks.These groups can reveal relationships among nodes and affect processes such as epidemic and innovation spreading.
- Research problem: Algorithm comparisons must balance community-identification accuracy against computational complexity, despite methods using different community definitions.Different definitions can make algorithm outputs difficult to compare directly.
- Benchmark limitations: The GN benchmark is limited by equal expected degrees, identical community separation, and an unrealistically small network size.These properties make it a poor proxy for real complex networks, which commonly have heterogeneous degree distributions and community sizes.
- Benchmark design: The LFR benchmark generalizes GN by introducing power-law distributions of node degree and community size, creating a harder test that exposes algorithm limitations.LFR is used because real networks typically exhibit heterogeneity in both degree distributions and community sizes.
- Benchmark design: The mixing parameter µ is treated as a global LFR property and is identified as the benchmark’s most influential parameter.It represents the external-connectivity ratio under the standard planted l-partition assumptions.
- Study scope: The study evaluates eight state-of-the-art algorithms on undirected, unweighted LFR graphs with non-overlapping communities to guide algorithm choice from observable network properties.It examines reliability ranges through µ and studies both predictive accuracy and effective computing time as network size changes.
Results
Using LFR benchmark networks, the study compares eight community detection algorithms across complementary accuracy measures, mixing parameters, network sizes, and real computing times. Results show that algorithm suitability depends strongly on network size and mixing parameter, with accuracy–speed trade-offs across methods.
- Evaluation framework: Accuracy is measured with normalised mutual information and the detected-to-generated community-count ratio, while computing time is measured directly.The community-count ratio must be interpreted alongside NMI because LFR community sizes are heterogeneous.
- Accuracy: Most algorithms detect communities well when the mixing parameter µ is small, but accuracy declines as µ and network size increase.Performance changes often become abrupt near µ = 1/2, while Fastgreedy declines smoothly and Leading eigenvector falls rapidly at small µ.
- Accuracy: For N ≤1000, Infomap, Multilevel, Walktrap, and Spinglass generally achieve higher NMI with small standard deviations; for N > 1000, Infomap, Multilevel, and Walktrap remain relatively stronger.Spinglass and Edge betweenness are too slow for large networks, while Label propagation is unstable because of its larger standard deviations.
- Community-count recovery: Community-count estimates worsen for µ ⪆1/2, with Multilevel, Walktrap, and Spinglass performing better among algorithms on small networks.Fastgreedy consistently underestimates community counts, whereas other algorithms show size- and mixing-dependent overestimation or underestimation.
- Observed mixing parameter: The inferred mixing parameter agrees with the true value at small µ but diverges as µ increases, except that Multilevel remains accurate up to µ = 0.75 across analysed network sizes.Infomap and Label propagation can fail at larger µ; Edge betweenness overestimates, while Fastgreedy, Walktrap, and Spinglass slightly underestimate.
- Computing time: Computing time follows T ∝N^α, with Label propagation scaling best by network size, Leading eigenvector and Multilevel remaining reasonable, and Edge betweenness suitable only for small networks.Fastgreedy, Infomap, Walktrap, and Spinglass scale substantially worse than the fastest methods.
Discussion
The study benchmarks eight community detection algorithms across LFR networks, comparing accuracy and computing time to derive topology-dependent recommendations. It also identifies practical limitations involving memory, network realism, research questions, and algorithm reliability.
- Benchmark scope: The study evaluates eight algorithms on LFR benchmark graphs spanning approximately 200 to 32,000 nodes, varying the mixing parameter µ at fixed average degree.The LFR benchmark provides a broad range of network sizes and mixing parameters for comparing accuracy and computing time.
- Overall comparison: Considering both accuracy and computing time, Multilevel outperforms the other tested algorithms on the examined benchmarks.The authors note that modularity-based methods, including Multilevel, are known to suffer from modularity’s resolution limit.
- Algorithm selection: For small networks, algorithm choice should prioritize accuracy; for larger networks, Infomap, Label propagation, Multilevel, and Walktrap are initial choices because they detect structure in reasonable time.Spinglass is limited to small networks by its computing time, while the recommended choices vary with network size and mixing parameter.
- Adaptive workflow: The proposed decision procedure first estimates µ with Spinglass or Multilevel, then selects an algorithm using network size and µ, and may repeat detection when NMI variability indicates instability.For larger networks, Spinglass cannot be used for estimating µ because of prohibitive computing time; unstable results may require recalculation or switching algorithms.
- Interpretation: Recommendations should be combined with the research question and available metadata because different questions can imply different community definitions and ground truths.A purely mechanical application of the recommendations may bias results.
- Limitations: The benchmark remains limited because more realistic network properties are needed, and average degree and distribution exponents may also affect algorithm comparisons.The study focuses mainly on mixing parameter and network size; memory consumption is likewise not analysed for larger-scale networks.
Methods
The study evaluates community-detection algorithms on benchmark networks with known structure, using controlled network generation and comparable implementations. It measures accuracy, computational effort, and algorithm-specific mechanisms across several methods.
- Benchmark design: The evaluation uses artificial networks with known community structure, including real and generative benchmarks for controlled comparison.The LFR model generates networks with specified degree and community-size distributions while preserving the degree sequence and targeting a mixing parameter.
- Benchmark design: The LFR benchmark constructs N-node graphs with power-law degree and community-size distributions, then rewires edges to match the mixing parameter µ.The mixing parameter represents the fraction of a node’s edges connecting outside its community.
- Algorithms: Eight state-of-the-art algorithms are evaluated using comparable implementations from the igraph software package.The tested methods include Edge betweenness, Fastgreedy, Infomap, Label propagation, Leading eigenvector, Multilevel, Spinglass, and Walktrap.
- Algorithms: The algorithms use distinct mechanisms, including modularity optimisation, random-walk information flow, spin-glass modelling, and hierarchical clustering.Multilevel repeatedly moves nodes to improve modularity and has computational complexity O(N logN); Walktrap merges communities based on short random walks.
- Implementation: Computations use matched virtual-machine environments with consistent hardware and execution conditions.The setup assigns each virtual machine an entire physical node with equivalent hardware specifications.
Competing interests
The supplied passages state that the authors declare no competing financial interests. The remaining passages describe figures, tables, assumptions, and results rather than competing interests.
- Competing interests: The authors declare no competing financial interests.