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

DOI10.1016/J.JSPI.2021.12.005zbMATH Open1484.62052arXiv1807.04426OpenAlexW2856071244MaRDI QIDQ2123258FDOQ2123258

Authors: Mingao Yuan, Yang Feng, Zuofeng Shang 

Publication date: 8 April 2022

Published in: Journal of Statistical Planning and Inference (Search for Journal in Brave)

Abstract: A fundamental problem in network data analysis is to test Erd"{o}s-R'{e}nyi model $mathcalGleft(n,fraca+b2night)$ versus a bisection stochastic block model $mathcalGleft(n,fracan,fracbnight)$, 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 (cite{BS16,L16}) and community detection (cite{MS16}). Existing work has been focusing on growing-degree regime $a,boinfty$ (cite{BS16,L16,MS16,BM17,B18,GL17a,GL17b}) 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 cite{J95}.

Full work available at URL: https://arxiv.org/abs/1807.04426

Recommendations

• A goodness-of-fit test for stochastic block models
• Testing degree corrections in stochastic block models
• Hypothesis testing in sparse weighted stochastic block model
• Bayesian testing for exogenous partition structures in stochastic block models
• Classification and estimation in the stochastic blockmodel based on the empirical degrees
• Goodness-of-fit test for latent block models
• Test on stochastic block model: local smoothing and extreme value theory
• Likelihood-based model selection for stochastic block models
• Using Maximum Entry-Wise Deviation to Test the Goodness of Fit for Stochastic Block Models
• Nonreconstruction of high-dimensional stochastic block model with bounded degree

zbMATH Keywords

stochastic block modelhypothesis testinglikelihood ratiobounded degreescontiguity theory

Mathematics Subject Classification ID

Nonparametric hypothesis testing (62G10) Random graphs (graph-theoretic aspects) (05C80)

Cites Work

• A nonparametric view of network models and Newman–Girvan and other modularities
• Pseudo-likelihood methods for community detection in large sparse networks
• Consistency of community detection in networks under degree-corrected stochastic block models
• Community detection and stochastic block models: recent developments
• Reconstruction and estimation in the planted partition model
• Hypothesis Testing for Automated Community Detection in Networks
• A goodness-of-fit test for stochastic block models
• On semidefinite relaxations for the block model
• Exploring complex networks
• Testing and modeling dependencies between a network and nodal attributes
• Paths in graphs
• Title not available (Why is that?)
• Role of normalization in spectral clustering for stochastic blockmodels
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• Contiguity and non-reconstruction results for planted partition models: the dense case
• Proof of the achievability conjectures for the general stochastic block model
• Semidefinite programs on sparse random graphs and their application to community detection
• Universality of the mean-field for the Potts model

Cited In (8)

• Two-sample test of stochastic block models
• Hypothesis testing in sparse weighted stochastic block model
• Asymptotic uncertainty quantification for communities in sparse planted bi-section models
• Nonreconstruction of high-dimensional stochastic block model with bounded degree
• Power enhancement and phase transitions for global testing of the mixed membership stochastic block model
• Adjusted chi-square test for degree-corrected block models
• A goodness-of-fit test for stochastic block models
• Using Maximum Entry-Wise Deviation to Test the Goodness of Fit for Stochastic Block Models

This page was built for publication: A likelihood-ratio type test for stochastic block models with bounded degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2123258)