Optimal Estimation of the Number of Network Communities

DOI10.1080/01621459.2022.2035736MaRDI QIDQ6077596zbMATH OpenOpenAlexFDO

Authors Jiashun Jin, Zheng Tracy Ke, Shengming Luo

Publication date 18 October 2023

Published in Journal of the American Statistical Association (Search for Journal in Brave)

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

zbMATH Keywords

\(k\)-meanscommunity detectionlower boundnonsplitting property (NSP)over-fittingunder-fitting

Mathematics Subject Classification ID

Statistics (62-XX)

Abstract: In network analysis, how to estimate the number of communities $K$ is a fundamental problem. We consider a broad setting where we allow severe degree heterogeneity and a wide range of sparsity levels, and propose Stepwise Goodness-of-Fit (StGoF) as a new approach. This is a stepwise algorithm, where for $m=1,2,ldots$, we alternately use a community detection step and a goodness-of-fit (GoF) step. We adapt SCORE cite{SCORE} for community detection, and propose a new GoF metric. We show that at step $m$, the GoF metric diverges to $infty$ in probability for all $m<K$ and converges to $N(0,1)$ if $m=K$. This gives rise to a consistent estimate for $K$. Also, we discover the right way to define the signal-to-noise ratio (SNR) for our problem and show that consistent estimates for $K$ do not exist if $mathrmSNRgoto0$, and StGoF is uniformly consistent for $K$ if $mathrmSNRgotoinfty$. Therefore, StGoF achieves the optimal phase transition. Similar stepwise methods (e.g., cite{wang2017likelihood, ma2018determining}) are known to face analytical challenges. We overcome the challenges by using a different stepwise scheme in StGoF and by deriving sharp results that are not available before. The key to our analysis is to show that SCORE has the {it Non-Splitting Property (NSP)}. Primarily due to a non-tractable rotation of eigenvectors dictated by the Davis-Kahan $sin(heta)$ theorem, the NSP is non-trivial to prove and requires new techniques we develop.

Cites work

• A goodness-of-fit test for stochastic block models
• Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral estimator
• Coauthorship and citation networks for statisticians
• Community detection with dependent connectivity
• Community network auto-regression for high-dimensional time series
• Consistency of community detection in networks under degree-corrected stochastic block models
• Determining the number of communities in degree-corrected stochastic block models
• Eigen Selection in Spectral Clustering: A Theory-Guided Practice
• Estimating the number of communities by spectral methods
• Fast community detection by SCORE
• Feature screening for network autoregression model
• Global spectral clustering in dynamic networks
• Higher criticism for detecting sparse heterogeneous mixtures.
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• Large-Scale Simultaneous Hypothesis Testing
• Likelihood-based model selection for stochastic block models
• Matrix Analysis
• Mixed-effect time-varying network model and application in brain connectivity analysis
• Modularity based community detection in heterogeneous networks
• Network cross-validation by edge sampling
• Network cross-validation for determining the number of communities in network data
• Optimal adaptivity of signed-polygon statistics for network testing
• Phase transitions for high dimensional clustering and related problems
• Portal nodes screening for large scale social networks
• Power enhancement and phase transitions for global testing of the mixed membership stochastic block model
• Spectral clustering and the high-dimensional stochastic blockmodel
• The Rotation of Eigenvectors by a Perturbation. III
• Using Maximum Entry-Wise Deviation to Test the Goodness of Fit for Stochastic Block Models
• Variational Bayesian inference and complexity control for stochastic block models

Cited in

(18)

• Computing exact \(p\)-values for community detection
• Concentration and stability of community-detecting functions on random networks
• Identifying Community Structures from Network Data via Maximum Likelihood Methods
• scientific article; zbMATH DE number 5533285 (Why is no real title available?)
• Probabilistic Community Detection With Unknown Number of Communities
• StarTrek: combinatorial variable selection with false discovery rate control
• Applications of dual regularized Laplacian matrix for community detection
• A two-way heterogeneity model for dynamic networks
• Network Embedding-based Directed Community Detection with Unknown Community Number
• Optimally monitoring a network of sewage manholes in infectious disease surveillance
• Perfect spectral clustering with discrete covariates
• Network Goodness-of-Fit for the Block-Model Family
• Joint Spectral Clustering in Multilayer Degree-Corrected Stochastic Blockmodels
• Limit results for estimation of connectivity matrix in multi-layer stochastic block models
• On Inference for Modularity Statistics in Structured Networks
• Optimal Network Membership Estimation under Severe Degree Heterogeneity
• Subsampling-based modified Bayesian information criterion for large-scale stochastic block models
• Simultaneous Estimation of Connectivity and Dimensionality in Samples of Networks

This page was built for publication: Optimal Estimation of the Number of Network Communities

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