TL;DR
Determining the number of communities in a social or relational network is a notoriously difficult "model selection" problem. This paper introduces CL-BIC (Composite Likelihood Bayesian Information Criterion), a robust method that accurately estimates the number of communities even when the network violates standard independence assumptions—a common occurrence in messy, real-world data.
What Problem Does This Paper Address?
In community detection, we try to group nodes (like people in a social network) into clusters or "communities." Most popular algorithms, such as the Stochastic Blockmodel (SBM), require the user to pre-specify the number of communities ($K$).
To estimate $K$ automatically, researchers often use the Bayesian Information Criterion (BIC). However, BIC relies on a "conditional independence" assumption: it assumes that once you know which communities two nodes belong to, the existence of an edge between them is independent of all other edges. In reality, networks are full of dependencies—if Alice is friends with Bob and Charlie, Bob and Charlie are much more likely to be friends with each other. When these assumptions are violated (model misspecification), traditional BIC tends to overfit, "discovering" far more communities than actually exist.
Methods
The authors propose CL-BIC, which shifts the framework from full likelihood to composite likelihood.
- Composite Likelihood: Instead of trying to model the entire complex joint distribution of the network, the authors use a product of marginal distributions (the probabilities of individual edges).
- The Godambe Information Matrix: The core innovation lies in the penalty term. While traditional BIC penalizes a model based simply on the number of parameters, CL-BIC uses a penalty derived from the "Godambe information." This effectively adjusts the penalty based on how much "unique" information is actually in the data, accounting for the correlation between edges.
- Jackknife Estimation: To make this practical, the authors use a jackknife covariance estimator (systematically leaving out one node at a time) to calculate the penalty term without needing to know the true underlying correlation structure of the network.
The method is designed to be "plug-and-play" with various models, including the Standard SBM, the Degree-Corrected SBM (which accounts for "hub" nodes), and the Mixed Membership SBM (where nodes can belong to multiple groups).
Datasets
The authors evaluated CL-BIC using:
- Synthetic Networks: "Correlation-contaminated" simulations where the authors intentionally introduced dependencies between edges to break traditional BIC.
- International Trade Network (1995): A dataset of trade volumes between 58 countries.
- School Friendship Network: Data from the "AddHealth" study (School 7), consisting of 433 students across grades 7 through 12.
Key Insights and Ideas
- Robustness is Key: The "Aha!" moment is that we don't need a perfect model of the network's dependencies to choose the right number of clusters. By acknowledging that our model is "wrong" (misspecified) and adjusting the penalty term accordingly, we get a much more stable estimate of $K$.
- Overcoming the "Independence Trap": Traditional BIC treats every edge as a fresh piece of evidence. CL-BIC recognizes that in a correlated network, 100 edges might only provide the "statistical weight" of 50 independent edges.
- Practicality: By using the jackknife method, the authors provide a way to estimate the necessary penalty directly from the observed graph, making the theory applicable to real-world datasets where the true correlation structure is unknown.
Key Results
- Simulation Superiority: In tests with high edge correlation, traditional BIC and Variational Bayes (VB) methods failed completely, often choosing the maximum possible number of communities (e.g., $K=18$). CL-BIC consistently identified the true $K=4$.
- Trade Networks: CL-BIC identified 3 sensible communities (High GDP, Industrialized, and Developing nations). In contrast, traditional BIC split the network into 10 groups, creating "noisy" communities as small as a single country, which offers little analytical value.
- Friendship Networks: In the school dataset, CL-BIC correctly identified $K=6$, perfectly matching the six grade levels (7th–12th) present in the school. Traditional BIC overshot, suggesting 9 communities and unnecessarily fragmenting the grade levels.
Limitations and Future Work
- Network Sparsity: The examples provided focus on relatively dense graphs. The authors note that real-world networks are often very sparse, and the performance of CL-BIC in extremely sparse regimes warrants further study.
- Theoretical Consistency: While the numerical results for the Degree-Corrected SBM (DCBM) were strong, the authors acknowledge that proving the theoretical consistency of CL-BIC for DCBM remains an open mathematical challenge.
- Computational Scale: The jackknife procedure requires re-estimating the model multiple times. For massive networks with millions of nodes, more computationally efficient approximations of the Godambe information might be necessary.
Summary updated