A likelihood-ratio type test for stochastic block models with bounded degrees

Mingao Yuan, Yang Feng, Zuofeng Shang

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


A fundamental problem in network data analysis is to test Erdös–Rényi model [Formula presented] versus a bisection stochastic block model [Formula presented], where a,b>0 are constants that represent the expected degrees of the graphs and n denotes the number of nodes. This problem serves as the foundation of many other problems such as testing-based methods for determining the number of communities (Bickel and Sarkar, 2016; Lei, 2016) and community detection (Montanari and Sen, 2016). Existing work has been focusing on growing-degree regime a,b→∞ (Bickel and Sarkar, 2016; Lei, 2016; Montanari and Sen, 2016; Banerjee and Ma, 2017; Banerjee, 2018; Gao and Lafferty, 2017a,b) while leaving the bounded-degree regime untreated. In this paper, we propose a likelihood-ratio (LR) type procedure based on regularization to test stochastic block models with bounded degrees. We derive the limit distributions as power Poisson laws under both null and alternative hypotheses, based on which the limit power of the test is carefully analyzed. We also examine a Monte-Carlo method that partly resolves the computational cost issue. The proposed procedures are examined by both simulated and real-world data. The proof depends on a contiguity theory developed by Janson (1995).

Original languageEnglish (US)
Pages (from-to)98-119
Number of pages22
JournalJournal of Statistical Planning and Inference
StatePublished - Jul 2022

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty
  • Applied Mathematics


  • Bounded degrees
  • Contiguity theory
  • Hypothesis testing
  • Likelihood ratio
  • Stochastic block model


Dive into the research topics of 'A likelihood-ratio type test for stochastic block models with bounded degrees'. Together they form a unique fingerprint.

Cite this