Adjusted chi-square test for degree-corrected block models

DOI10.48550/ARXIV.2012.15047arXiv2012.15047OpenAlexW4390055394MaRDI QIDQ90068FDOQ90068

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)

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.

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

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)

Cites Work

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

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)