Abstract: Determining the optimal number of communities ($q$) in a network is a fundamental challenge in network science. This study provides a rigorous comparative analysis of assessment criteria and algorithms, revealing that popular greedy methods often overfit by detecting spurious structures. Through evaluations on synthetic and real-world datasets, the authors demonstrate that statistical inference and non-backtracking spectral methods offer more robust estimates of community structure.
Introduction
Community detection is the process of grouping nodes in a network into clusters. A fundamental challenge in this field is model selection: how many clusters should we look for? Choosing too few leads to underfitting and missing sub-structures, while choosing too many leads to overfitting, where random noise is identified as significant clusters. This paper investigates the typical behaviors and biases of different assessment criteria across various algorithms.
Methodology
The authors focus on the Stochastic Block Model (SBM) and its degree-corrected variant. They compare three main approaches:
- Greedy Algorithms: Specifically the Louvain method (optimizing modularity) and Infomap (optimizing the map equation).
- Statistical Inference: Using the Expectation-Maximization (EM) algorithm combined with Belief Propagation (BP) to minimize the Bethe free energy.
- Spectral Methods: Analyzing the eigenvalues of the modularity matrix and the non-backtracking matrix.
Crucially, the study decouples the assessment criterion (the quality measure) from the algorithm (the search mechanism) to determine if overfitting stems from the mathematical goal or the search mechanics.
Experimental Setup
The study utilizes a broad range of data:
- Synthetic Networks: LFR (Lancichinetti-Fortunato-Radicchi) benchmarks, which emulate real-world properties like power-law degree distributions.
- Real-World Networks: 16 diverse datasets, including Zachary’s Karate Club, political blogs, protein interaction networks, and large-scale social networks like Enron and Epinions.
Key Insights and Results
The Overfitting Trap
Greedy algorithms like Louvain and Infomap are highly prone to overfitting, often detecting hundreds of fictitious clusters in sparse networks. For example, in synthetic tests where the true $q$ was 2, greedy Infomap sometimes detected over 150 clusters as networks became larger and sparser. The authors found that the criteria themselves (modularity or the map equation) are not inherently broken; rather, the greedy algorithms used to optimize them are the primary source of overfitting.
Spectral and Inference Performance
Statistical inference using Bethe free energy and cross-validation errors proved to be the most accurate at identifying the "planted" number of clusters in synthetic data. In spectral analysis, the non-backtracking matrix was found to be superior to standard Laplacians because it avoids "localization," where high-degree nodes distort eigenvalues.
As shown in the eigenvalue histogram above, spectral methods rely on identifying outliers from the bulk of the spectrum to estimate community counts. However, the modularity matrix tended to underfit real-world data (e.g., finding only 1 cluster in complex protein networks), while the non-backtracking matrix sometimes overfit.
Conclusion
The paper concludes that in community detection, underfitting is generally preferable to overfitting, as the former provides a coarse view while the latter creates fictitious information. For many real-world networks, there is no single "correct" $q$, but rather a range of plausible values where community structure remains stable. Future work may extend this analysis to overlapping or hierarchical community structures.
Summary updated