Comparative analysis of model assessment in community detection

Tatsuro Kawamoto, Yoshiyuki KabashimaarXiv 2016 · arXiv

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:

  1. Greedy Algorithms: Specifically the Louvain method (optimizing modularity) and Infomap (optimizing the map equation).
  2. Statistical Inference: Using the Expectation-Maximization (EM) algorithm combined with Belief Propagation (BP) to minimize the Bethe free energy.
  3. 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.

Theoretical relationships between modularity, normalized cuts, and their matrix representations.

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.

Eigenvalue distribution of the modularity matrix used for cluster estimation.

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

Abstract

We conduct a comparative analysis on various estimates of the number of clusters in community detection. An exhaustive comparison requires testing of all possible combinations of frameworks, algorithms, and assessment criteria. In this paper we focus on the framework based on a stochastic block model, and investigate the performance of greedy algorithms, statistical inference, and spectral methods. For the assessment criteria, we consider modularity, map equation, Bethe free energy, prediction errors, and isolated eigenvalues. From the analysis, the tendency of overfit and underfit that the assessment criteria and algorithms have, becomes apparent. In addition, we propose that the alluvial diagram is a suitable tool to visualize statistical inference results and can be useful to determine the number of clusters.
BibTeX
@misc{kawamoto2016comparative,
  author = {Tatsuro Kawamoto and Yoshiyuki Kabashima},
  title = {{Comparative analysis of model assessment in community detection}},
  year = {2016},
  eprint = {1606.07668},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1606.07668},
}
Figure