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