How Many Communities Are There?

Diego Franco Saldana, Yi Yu, Yang Feng

Abstract

Stochastic blockmodels (SBMs) and their variants are fundamental tools for community detection in social and relational networks. These models partition nodes into disjoint sets, yet determining the optimal number of communities ($K$) remains a significant challenge. Traditional model selection criteria, such as the Bayesian Information Criterion (BIC), often fail in practice because they rely on a conditional independence assumption that real-world networks frequently violate. This paper introduces the Composite Likelihood Bayesian Information Criterion (CL-BIC), a robust alternative designed to handle model misspecification. By utilizing a penalty term derived from the Godambe information matrix and estimated via a jackknife procedure, CL-BIC accurately identifies the number of communities even in the presence of complex edge dependencies.

Introduction

In the study of social, biological, and relational networks, community detection—the partitioning of nodes into clusters based on connectivity patterns—is a primary objective. The Stochastic Blockmodel (SBM) provides a statistical framework for this task, but it typically requires the user to pre-specify the number of communities, $K$. Selecting $K$ is a classic model selection problem, often approached using the Bayesian Information Criterion (BIC).

The efficacy of BIC is predicated on the assumption that edges are conditionally independent given the community assignments. In empirical networks, this assumption is rarely met; dependencies such as transitivity (the "friend of a friend" effect) create correlations that standard BIC interprets as evidence for additional, often spurious, communities. Consequently, traditional methods tend to overfit, leading to an overestimation of $K$ and the discovery of "communities" that offer little analytical value.

Methodology: The CL-BIC Approach

To address the limitations of standard BIC, we propose the Composite Likelihood Bayesian Information Criterion (CL-BIC). This method shifts the focus from the full joint likelihood of the network to a composite likelihood framework.

Composite Likelihood and the Godambe Penalty

Instead of modeling the entire complex joint distribution of the network, CL-BIC employs a product of marginal distributions of individual edges. The critical innovation lies in the adjustment of the model complexity penalty. While standard BIC penalizes a model based simply on the number of parameters, CL-BIC incorporates the Godambe information matrix (also known as the sandwich information matrix). This adjustment accounts for the "effective" information content in the data, essentially discounting the statistical weight of correlated edges. In a correlated network, 100 edges might only provide the statistical weight of 50 independent edges; CL-BIC recognizes this discrepancy.

Jackknife Estimation

Calculating the Godambe information requires knowledge of the underlying correlation structure, which is typically unknown in real-world data. To make the method practical, we utilize a jackknife covariance estimator. By systematically omitting one node at a time and re-estimating the model, we can derive a robust penalty term directly from the observed graph. This "plug-and-play" nature allows CL-BIC to be applied to various models, including the Standard SBM, the Degree-Corrected SBM (DCBM), and the Mixed Membership SBM.

Experimental Results

The robustness of CL-BIC was evaluated through both synthetic simulations and real-world datasets.

Synthetic Networks

In simulations where edge dependencies were intentionally introduced ("correlation-contaminated" networks), traditional BIC and Variational Bayes (VB) methods failed significantly. These methods often selected the maximum allowed number of communities (e.g., $K=18$ when the true $K=4$). In contrast, CL-BIC consistently and accurately identified the true community structure, demonstrating its resilience to model misspecification.

International Trade Network

Analyzing a 1995 dataset of trade volumes between 58 countries, CL-BIC identified $K=3$ communities, corresponding to high-GDP, industrialized, and developing nations. Traditional BIC suggested $K=10$, resulting in fragmented, "noisy" clusters—some containing only a single country—which lacked meaningful interpretability.

School Friendship Network

Using data from the AddHealth study (School 7), which includes 433 students across grades 7 through 12, CL-BIC correctly identified $K=6$. This result perfectly aligns with the six grade levels present in the school. Traditional BIC over-partitioned the network, suggesting 9 communities and unnecessarily splitting cohesive grade-level groups.

Discussion and Limitations

CL-BIC offers a robust framework for network model selection by acknowledging that our models are often misspecified. By adjusting the penalty term to reflect the true information density of the data, it avoids the "independence trap" that plagues traditional criteria.

However, several areas for future research remain:

  • Network Sparsity: The current performance of CL-BIC is well-documented in relatively dense graphs; its behavior in extremely sparse regimes warrants further study.
  • Theoretical Foundations: While empirical results for the Degree-Corrected SBM are promising, formal proofs of consistency for CL-BIC in the context of DCBM remain an open mathematical challenge.
  • Computational Scale: The jackknife procedure is computationally intensive. For massive networks with millions of nodes, developing more efficient approximations of the Godambe information will be essential for practical application.

Conclusion

The proposed CL-BIC provides a principled and practical solution to the problem of determining the number of communities in complex networks. By providing robustness against model misspecification, it ensures that the discovered community structures are both statistically sound and substantively meaningful.

Summary updated

Abstract

Stochastic blockmodels and variants thereof are among the most widely used approaches to community detection for social networks and relational data. A stochastic blockmodel partitions the nodes of a network into disjoint sets, called communities. The approach is inherently related to clustering with mixture models; and raises a similar model selection problem for the number of communities. The Bayesian information criterion (BIC) is a popular solution, however, for stochastic blockmodels, the conditional independence assumption given the communities of the endpoints among different edges is usually violated in practice. In this regard, we propose composite likelihood BIC (CL-BIC) to select the number of communities, and we show it is robust against possible misspecifications in the underlying stochastic blockmodel assumptions. We derive the requisite methodology and illustrate the approach using both simulated and real data. Supplementary materials containing the relevant computer code are available online.
BibTeX
@article{saldana2015how,
  author = {Diego Franco Saldana and Yi Yu and Yang Feng},
  title = {{How Many Communities Are There?}},
  journal = {Journal of Computational and Graphical Statistics},
  year = {2015},
  doi = {10.1080/10618600.2015.1096790},
}
Figure