Testing degree corrections in stochastic block models
From MaRDI portal
Abstract: We study sharp detection thresholds for degree corrections in Stochastic Block Models in the context of a goodness of fit problem, and explore the effect of the unknown community assignment (a high dimensional nuisance parameter) and the graph density on testing for degree corrections. When degree corrections are relatively dense, a simple test based on the total number of edges is asymptotically optimal. For sparse degree corrections, the results undergo several changes in behavior depending on density of the underlying Stochastic Block Model. For graphs which are not extremely sparse, optimal tests are based on Higher Criticism or Maximum Degree type tests based on a linear combination of within and across (estimated) community degrees. In the special case of balanced communities, a simple degree based Higher Criticism Test (Mukherjee, Mukherjee, Sen 2016) is optimal in case the graph is not completely dense, while the more complicated linear combination based procedure is required in the completely dense setting. The ``necessity" of the two step procedure is demonstrated for the case of balanced communities by the failure of the ordinary Maximum Degree Test in achieving sharp constants. Finally for extremely sparse graphs the optimal rates change, and a version of the maximum degree test with a different rejection region is shown to be optimal.
Recommendations
- Community detection in degree-corrected block models
- A spectral method for community detection in moderately sparse degree-corrected stochastic 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
- Corrected Bayesian information criterion for stochastic block models
Cites work
- scientific article; zbMATH DE number 52632 (Why is no real title available?)
- A goodness-of-fit test for stochastic block models
- A spectral method for community detection in moderately sparse degree-corrected stochastic block models
- Collective dynamics of `small-world' networks
- Community detection and stochastic block models: recent developments
- Community detection in degree-corrected block models
- Community detection in dense random networks
- Consistency of community detection in networks under degree-corrected stochastic block models
- Convexified modularity maximization for degree-corrected stochastic block models
- Detection boundary in sparse regression
- Detection thresholds for the \(\beta\)-model on sparse graphs
- Emergence of Scaling in Random Networks
- Estimation and prediction for stochastic blockmodels for graphs with latent block structure
- Fast community detection by SCORE
- Global testing under sparse alternatives: ANOVA, multiple comparisons and the higher criticism
- Higher criticism for detecting sparse heterogeneous mixtures.
- Hypothesis testing for high-dimensional sparse binary regression
- Innovated higher criticism for detecting sparse signals in correlated noise
- Nonparametric goodness-of-fit testing under Gaussian models
- The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
- The sparse Poisson means model
Cited in
(11)- Correction to the proof of consistency of community detection
- Detection thresholds for the \(\beta\)-model on sparse graphs
- An impossibility result for reconstruction in the degree-corrected stochastic block model
- Hypothesis testing in sparse weighted stochastic block model
- Using Maximum Entry-Wise Deviation to Test the Goodness of Fit for Stochastic Block Models
- Adjusted chi-square test for degree-corrected block models
- A likelihood-ratio type test for stochastic block models with bounded degrees
- Degree-based goodness-of-fit tests for heterogeneous random graph models: independent and exchangeable cases
- A goodness-of-fit test for stochastic block models
- Signal detection in degree corrected ERGMs
- Power enhancement and phase transitions for global testing of the mixed membership stochastic block model
This page was built for publication: Testing degree corrections in stochastic block models
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2077335)
