Network Goodness-of-Fit for the block-model family

Jianshi Jin, Zheng Tracy Ke, Jiajun Tang, Jingming WangJournal of the American Statistical Association 2025 · arXiv

When researchers study social networks, protein interactions, or citation webs, they often reach for the Stochastic Block Model (SBM) or its more sophisticated cousins. But how do we know if these models actually "fit" the messy reality of a real-world network?

In a new paper titled "Network Goodness-of-Fit for the block-model family," Jiashun Jin and colleagues introduce a powerful new metric called GoF-MSCORE. This tool allows researchers to rigorously test whether a network model is adequate or if it’s missing the mark, providing a much-needed "sanity check" for the most complex models in the field.

TL;DR

The authors propose GoF-MSCORE, a goodness-of-fit test for the block-model family that converges to a standard normal distribution ($N(0,1)$) regardless of unknown parameters. Their analysis of 12 real-world networks reveals that the Degree-Corrected Mixed-Membership (DCMM) model is the "sweet spot"—broad enough to fit almost any network while remaining mathematically tractable and interpretable.

What Problem Does This Paper Address?

In network science, we group nodes into "communities." The block-model family offers four main ways to do this:

  1. SBM: The simplest version; nodes in the same group are identical.
  2. DCBM: Adds "degree correction" to account for the fact that some people are just more social (hubs) than others.
  3. MMSBM: Allows "mixed membership," where a node can belong to multiple communities.
  4. DCMM: The "kitchen sink" model that includes both degree correction and mixed membership.

The challenge is Goodness-of-Fit (GoF). If you assume a simple SBM but the data is actually a complex DCMM, your conclusions will be wrong. Conversely, if you use a model that is too complex, you might overfit.

Existing GoF tests usually only work for the simplest models (SBM). Testing the more realistic models (like DCMM) is notoriously difficult because they involve thousands of unknown parameters. Mathematically, this creates an "analytical hurdle": the distribution of your test statistic usually depends on those unknown parameters, making it impossible to set a reliable threshold for "good fit."

Methods

The authors overcome this hurdle using two clever ideas:

  1. Self-normalized Cycle Counts (SCC): Instead of looking at simple edges, the test counts triangles (cycles of length 3). Triangles capture the "clustering" behavior common in real networks. By "self-normalizing" these counts, the authors created a statistic that behaves predictably as the network grows.
  2. The "Net-Rounding" Scheme: To prove the theory, the model fitting must be a "simple" function of the data. Standard spectral methods (like SVD) are too mathematically "tangled." The authors used a technique called Mixed-SCORE combined with net-rounding—essentially discretizing the continuous membership estimates into a finite set of points. This "un-tangles" the math, allowing them to prove that the test statistic always converges to a standard normal distribution ($N(0,1)$) if the model is correct.

Datasets

The authors tested their metrics on 12 frequently-used real networks, including:

  • Social/Biological: Zachary’s Karate Club, Dolphin social network, and American College Football.
  • Large-scale/Technical: Political blogs (Weblogs), a large citation network (Citee2016), and a massive music streaming network (LastFM) with over 7,000 nodes.
  • Academic: Co-authorship networks of statisticians (CoAuthor, Fan).

Key Insights and Ideas

  • The Parameter-Free Null: This is the "Aha!" moment. Usually, a test's threshold changes depending on the network's sparsity or community structure. Because GoF-MSCORE always converges to $N(0,1)$, you can use a universal threshold (like 1.96 for 95% confidence) regardless of the network's specific parameters.
  • The Necessity of Complexity: The results show that for large networks, modeling only degree heterogeneity or only mixed membership isn't enough. You need both.
  • DCMM as the "Sweet Spot": The authors prove that DCMM is nearly as flexible as any "rank-K" network model but remains much easier to interpret than abstract mathematical models like Random Dot Product Graphs (RDPG).

Key Results

  • Theory: The authors proved that for all four models (SBM, DCBM, MMSBM, DCMM), the GoF statistic converges to $N(0,1)$ under the null hypothesis.
  • Real-World Performance:
    • For the Citee2016 network, the GoF for SBM was a staggering 759.2, and for MMSBM it was 405.3 (indicating a massive lack of fit).
  • However, the GoF for DCMM on the same network was only 3.687, falling within the "reasonably good fit" range (defined as < 5).
  • Model Selection: In the LastFM network, the test was sensitive enough to detect that $K=3$ communities provided a significantly better fit than $K=2$ or $K=4$.

Limitations and Future Work

  • Edge Independence: The current theory assumes that edges are independent given the latent variables. While they tested a "triadic closure" model (where edges are dependent) in simulations and found the test still worked, the formal theory for dependent edges remains for future work.
  • Outliers and Cliques: The block-model family doesn't explicitly account for outliers or very small, dense cliques. The authors suggest that cycle counts could be adapted to test for these specific features in the future.
  • Directed Networks: Most of the analysis focused on undirected networks. Extending this to directed graphs (where $A \neq A^T$) is a logical next step.

Paper Citation: Jin, J., Ke, Z. T., Tang, J., & Wang, J. (2025). Network Goodness-of-Fit for the block-model family. arXiv:2502.08609v1 [math.ST].

Summary updated

Abstract

The block-model family has four popular network models (SBM, DCBM, MMSBM, and DCMM). A fundamental problem is, how well each of these models fits with real networks. We propose GoF-MSCORE as a new Goodness-of-Fit (GoF) metric for DCMM (the broadest one among the four), with two main ideas. The first is to use cycle count statistics as a general recipe for GoF. The second is a novel network fitting scheme. GoF-MSCORE is a flexible GoF approach, and we further extend it to SBM, DCBM, and MMSBM. This gives rise to a series of GoF metrics covering each of the four models in the block-model family. We show that for each of the four models, if the assumed model is correct, then the corresponding GoF metric converges to $N(0, 1)$ as the network sizes diverge. We also analyze the powers and show that these metrics are optimal in many settings. In comparison, many other GoF ideas face challenges: they may lack a parameter-free limiting null, or are non-optimal in power, or face an analytical hurdle. Note that a parameter-free limiting null is especially desirable as many network models have a large number of unknown parameters. The limiting nulls of our GoF metrics are always $N(0,1)$, which are parameter-free as desired. For 12 frequently-used real networks, we use the proposed GoF metrics to show that DCMM fits well with almost all of them. We also show that SBM, DCBM, and MMSBM do not fit well with many of these networks, especially when the networks are relatively large. To complement with our study on GoF, we also show that the DCMM is nearly as broad as the rank-$K$ network model. Based on these results, we recommend the DCMM as a promising model for undirected networks.
BibTeX
@article{jin2025network,
  author = {Jianshi Jin and Zheng Tracy Ke and Jiajun Tang and Jingming Wang},
  title = {{Network Goodness-of-Fit for the block-model family}},
  journal = {Journal of the American Statistical Association},
  year = {2025},
}
Figure