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

DOI10.1016/J.JSPI.2021.12.005MaRDI QIDQ2123258zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

stochastic block modelhypothesis testinglikelihood ratiobounded degreescontiguity theory

Mathematics Subject Classification ID

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

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}.

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

Cites work

• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• A goodness-of-fit test for stochastic block models
• A nonparametric view of network models and Newman–Girvan and other modularities
• Community detection and stochastic block models: recent developments
• Consistency of community detection in networks under degree-corrected stochastic block models
• Contiguity and non-reconstruction results for planted partition models: the dense case
• Exploring complex networks
• Hypothesis testing for automated community detection in networks
• On semidefinite relaxations for the block model
• Paths in graphs
• Proof of the achievability conjectures for the general stochastic block model
• Pseudo-likelihood methods for community detection in large sparse networks
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• Reconstruction and estimation in the planted partition model
• Role of normalization in spectral clustering for stochastic blockmodels
• Semidefinite programs on sparse random graphs and their application to community detection
• Testing and modeling dependencies between a network and nodal attributes
• 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)