Estimating the number of communities by spectral methods
From MaRDI portal
Publication:90067
DOI10.1214/21-EJS1971zbMATH Open1493.62313arXiv1507.00827OpenAlexW4285193794MaRDI QIDQ90067FDOQ90067
Can M. Le, Elizaveta Levina, Can M. Le, Can M. Le
Publication date: 1 January 2022
Published in: Electronic Journal of Statistics (Search for Journal in Brave)
Abstract: Community detection is a fundamental problem in network analysis with many methods available to estimate communities. Most of these methods assume that the number of communities is known, which is often not the case in practice. We study a simple and very fast method for estimating the number of communities based on the spectral properties of certain graph operators, such as the non-backtracking matrix and the Bethe Hessian matrix. We show that the method performs well under several models and a wide range of parameters, and is guaranteed to be consistent under several asymptotic regimes. We compare this method to several existing methods for estimating the number of communities and show that it is both more accurate and more computationally efficient.
Full work available at URL: https://arxiv.org/abs/1507.00827
Classification and discrimination; cluster analysis (statistical aspects) (62H30) Estimation in multivariate analysis (62H12)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A nonparametric view of network models and Newman–Girvan and other modularities
- Spectral clustering and the high-dimensional stochastic blockmodel
- Pseudo-likelihood methods for community detection in large sparse networks
- Likelihood-based model selection for stochastic block models
- Network cross-validation by edge sampling
- Network Cross-Validation for Determining the Number of Communities in Network Data
- A proof of the block model threshold conjecture
- Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
- Random matrices: universality of ESDs and the circular law
- Spectral radii of sparse random matrices
- Spectral redemption in clustering sparse networks
- Mixed membership stochastic blockmodels
- Belief propagation, robust reconstruction and optimal recovery of block models
- Community structure in social and biological networks
- Community Detection and Stochastic Block Models
- A Simple SVD Algorithm for Finding Hidden Partitions
- THE IHARA-SELBERG ZETA FUNCTION OF A TREE LATTICE
- Reconstruction and estimation in the planted partition model
- Corrected Bayesian Information Criterion for Stochastic Block Models
- Variational Bayesian inference and complexity control for stochastic block models
- The non-backtracking spectrum of the universal cover of a graph
- Community detection thresholds and the weak Ramanujan property
- Concentration and regularization of random graphs
- Hypothesis Testing for Automated Community Detection in Networks
- A goodness-of-fit test for stochastic block models
Cited In (15)
- Two-sample test of stochastic block models
- Universal rank inference via residual subsampling with application to large networks
- Consistent model selection for the degree corrected stochastic blockmodel
- Recent advances on mechanisms of network generation: community, exchangeability, and scale-free properties
- Hypothesis testing for equality of latent positions in random graphs
- Two-sample test of stochastic block models via the maximum sampling entry-wise deviation
- Title not available (Why is that?)
- nett
- Adjusted chi-square test for degree-corrected block models
- Optimal Estimation of the Number of Network Communities
- Applications of dual regularized Laplacian matrix for community detection
- Spectral clustering in the dynamic stochastic block model
- Extended stochastic block models with application to criminal networks
- randnet
- Estimating a network from multiple noisy realizations
This page was built for publication: Estimating the number of communities by spectral methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q90067)
