Adjusted chi-square test for degree-corrected block models

DOI10.48550/ARXIV.2012.15047MaRDI QIDQ90068zbMATH OpenOpenAlexFDO

Authors Linfan Zhang, Arash A. Amini, Arash A. Amini

Publication date 30 December 2020

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2012.15047, https://projecteuclid.org/journals/annals-of-statistics/volume-51/issue-6/Adjusted-chi-square-test-for-degree-corrected-block-models/10.1214/23-AOS2329.full

zbMATH Keywords

adjusted chi-square statisticcommunity detectiondegree-corrected stochastic block modelgoodness-of-fit testnonasymptotic

Mathematics Subject Classification ID

Asymptotic properties of nonparametric inference (62G20) Multivariate analysis (62H99) Approximations to statistical distributions (nonasymptotic) (62E17)

Abstract: We propose a goodness-of-fit test for degree-corrected stochastic block models (DCSBM). The test is based on an adjusted chi-square statistic for measuring equality of means among groups of $n$ multinomial distributions with $d_1,dots,d_n$ observations. In the context of network models, the number of multinomials, $n$, grows much faster than the number of observations, $d_i$, corresponding to the degree of node $i$, hence the setting deviates from classical asymptotics. We show that a simple adjustment allows the statistic to converge in distribution, under null, as long as the harmonic mean of $d_i$ grows to infinity. When applied sequentially, the test can also be used to determine the number of communities. The test operates on a compressed version of the adjacency matrix, conditional on the degrees, and as a result is highly scalable to large sparse networks. We incorporate a novel idea of compressing the rows based on a $(K+1)$-community assignment when testing for $K$ communities. This approach increases the power in sequential applications without sacrificing computational efficiency, and we prove its consistency in recovering the number of communities. Since the test statistic does not rely on a specific alternative, its utility goes beyond sequential testing and can be used to simultaneously test against a wide range of alternatives outside the DCSBM family. In particular, we prove that the test is consistent against a general family of latent-variable network models with community structure.

Recommendations

• A goodness-of-fit test for stochastic block models
• Using Maximum Entry-Wise Deviation to Test the Goodness of Fit for Stochastic Block Models
• Testing degree corrections in stochastic block models
• Two-sample test of stochastic block models
• Degree-based goodness-of-fit tests for heterogeneous random graph models: independent and exchangeable cases

Cites work

• scientific article; zbMATH DE number 7370586 (Why is no real title available?)
• scientific article; zbMATH DE number 7626732 (Why is no real title available?)
• A goodness-of-fit test for stochastic block models
• A likelihood-ratio type test for stochastic block models with bounded degrees
• A necessary and sufficient condition for edge universality of Wigner matrices
• Achieving optimal misclassification proportion in stochastic block models
• Assessment of model fit via network comparison methods based on subgraph counts
• Asymptotic Statistics
• Community detection and stochastic block models: recent developments
• Consistency of spectral clustering in stochastic block models
• Convexified modularity maximization for degree-corrected stochastic block models
• Corrected Bayesian information criterion for stochastic block models
• Estimating the number of communities by spectral methods
• General properties and estimation of conditional Bernoulli models
• Goodness of Fit of Social Network Models
• Hierarchical Community Detection by Recursive Partitioning
• Hypothesis testing for automated community detection in networks
• Likelihood-based model selection for stochastic block models
• Minimax rates of community detection in stochastic block models
• Network cross-validation by edge sampling
• Network cross-validation for determining the number of communities in network data
• Optimal bipartite network clustering
• Probabilistic Community Detection With Unknown Number of Communities
• Rigidity of eigenvalues of generalized Wigner matrices
• Statistical modeling: The two cultures. (With comments and a rejoinder).
• Stein's method and multinomial approximation
• Tailor-made tests for goodness of fit to semiparametric hypotheses
• The method of moments and degree distributions for network models

Cited in

(1)

• nett

This page was built for publication: Adjusted chi-square test for degree-corrected block models

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