TY - JOUR
T1 - A likelihood-ratio type test for stochastic block models with bounded degrees
AU - Yuan, Mingao
AU - Feng, Yang
AU - Shang, Zuofeng
N1 - Funding Information:
Supported by NSF CAREER, United States Grant DMS-1554804.Supported by NSF, United StatesDMS-1764280.
Publisher Copyright:
© 2021 Elsevier B.V.
PY - 2022/7
Y1 - 2022/7
N2 - 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).
AB - 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).
KW - Bounded degrees
KW - Contiguity theory
KW - Hypothesis testing
KW - Likelihood ratio
KW - Stochastic block model
UR - http://www.scopus.com/inward/record.url?scp=85121626990&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85121626990&partnerID=8YFLogxK
U2 - 10.1016/j.jspi.2021.12.005
DO - 10.1016/j.jspi.2021.12.005
M3 - Article
AN - SCOPUS:85121626990
SN - 0378-3758
VL - 219
SP - 98
EP - 119
JO - Journal of Statistical Planning and Inference
JF - Journal of Statistical Planning and Inference
ER -