Selecting the Number of Communities for Weighted Degree-Corrected Stochastic Block Models

Yucheng Liu, Xiaodong LiAISTATS 2025

Abstract

Determining the number of communities ($K$) is a fundamental challenge in network analysis, particularly for weighted networks where traditional likelihood-based methods often fail due to incorrect distributional assumptions. We present Stepwise Variance Profile Scaling (SVPS), a distribution-free approach for selecting $K$ in weighted degree-corrected stochastic block models. By utilizing matrix scaling and sequential spectral testing, SVPS provides a consistent and robust estimation of community structure across various noise distributions.

Introduction

In network analysis, community detection aims to identify groups of nodes that are more densely connected internally than to the rest of the network. While significant progress has been made for unweighted networks, real-world data—such as trade volumes between nations or frequency of social interactions—is often weighted. Existing methods for weighted networks typically rely on likelihood-based models, which require strict assumptions about the underlying probability distribution (e.g., Poisson or Gaussian). If these assumptions are violated, the accuracy of community selection diminishes.

This research introduces a flexible, consistent method to select $K$ for weighted networks without requiring a full likelihood specification, addressing a critical gap in current network analysis techniques.

Methodology

The Weighted DCSBM

The authors propose a Weighted Degree-Corrected Stochastic Block Model (DCSBM) characterized by two primary components:

  1. Mean Structure: The average edge weight is determined by community membership and node-specific "popularity" parameters.
  2. Variance Structure: A variance function $\nu(\cdot)$ links the variance of an edge weight to its mean, allowing for a more nuanced representation of noise.

Stepwise Variance Profile Scaling (SVPS)

The SVPS algorithm operates through a sequential testing framework. It begins by assuming $m=1$ community and iteratively increases $m$. For each candidate $m$, the algorithm performs the following:

  • Matrix Scaling: It estimates a variance profile matrix and applies a diagonal scaling matrix $\Psi$ to make the variance matrix "doubly stochastic." This Sinkhorn-style scaling normalizes the noise across the network.
  • Spectral Stopping Rule: A test statistic is calculated based on the $(m+1)$-th largest eigenvalue of the normalized adjacency matrix. The process stops when this value falls below a universal threshold (typically $2 + \epsilon$), at which point $K$ is declared equal to $m$.

The authors mathematically prove that SVPS is consistent, meaning the probability of selecting the true $K$ approaches 1 as the network size increases, even in sparse conditions.

Key Results and Discussion

Superior Accuracy and Robustness

In extensive simulations, SVPS significantly outperformed standard selection criteria, such as the Corrected Bayesian Information Criterion (CBIC) and Integrated Classification Likelihood (ICL). As shown in Figure 1, SVPS maintains high accuracy rates even as the number of communities increases, whereas traditional methods often see a sharp decline in performance.

Accuracy of SVPS vs. standard criteria

Furthermore, the method demonstrates remarkable robustness to distributional mismatch. Even when the true data-generating process (e.g., Negative Binomial or Binomial) does not perfectly align with the assumed variance function, SVPS remains effective.

SVPS performance under Negative Binomial noise

Real-World Application: Les Misérables

The utility of SVPS was further validated using the Les Misérables social network. While unweighted methods typically suggest 3-4 communities, the weighted SVPS approach identified 6-7 communities. These additional groupings align more closely with the complex subplots and character arcs of the novel, demonstrating that weighted edges contain vital structural information that unweighted models often overlook.

Conclusion and Future Work

SVPS offers a powerful, distribution-free alternative for community selection in weighted networks. By leveraging matrix scaling to derive a universal threshold, it simplifies the selection process while maintaining high accuracy.

Future research directions include methods for estimating the variance-mean relationship $\nu(\cdot)$ directly from data and deriving the exact asymptotic null distribution of the test statistic to enable p-value assignments for the selection of $K$. Additionally, optimizing the computational efficiency for extremely large networks remains an area for further development.

Summary updated

BibTeX
@inproceedings{liu2025selecting,
  author = {Yucheng Liu and Xiaodong Li},
  title = {{Selecting the Number of Communities for Weighted Degree-Corrected Stochastic Block Models}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2025},
}
Figure