Estimating the number of communities by spectral methods
From MaRDI portal
(Redirected from Publication:90067)
DOI10.1214/21-EJS1971zbMATH Open1493.62313OpenAlexW4285193794MaRDI QIDQ90067FDOQ90067
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.
Recommendations
- Spectral clustering for community detection
- Detecting overlapping communities in networks using spectral methods
- Overlapping community detection in networks via sparse spectral decomposition
- Bayesian estimation of the latent dimension and communities in stochastic blockmodels
- Consistency of spectral clustering in stochastic block models
Cites work
- scientific article; zbMATH DE number 4165188 (Why is no real title available?)
- scientific article; zbMATH DE number 5296054 (Why is no real title available?)
- scientific article; zbMATH DE number 7370586 (Why is no real title available?)
- scientific article; zbMATH DE number 967931 (Why is no real title available?)
- A Simple SVD Algorithm for Finding Hidden Partitions
- A goodness-of-fit test for stochastic block models
- A nonparametric view of network models and Newman–Girvan and other modularities
- A proof of the block model threshold conjecture
- Belief propagation, robust reconstruction and optimal recovery of block models
- Community detection and stochastic block models: recent developments
- Community detection thresholds and the weak Ramanujan property
- Community structure in social and biological networks
- Concentration and regularization of random graphs
- Corrected Bayesian information criterion for stochastic block models
- Hypothesis testing for automated community detection in networks
- Likelihood-based model selection for stochastic block models
- Mixed membership stochastic blockmodels
- Network cross-validation by edge sampling
- Network cross-validation for determining the number of communities in network data
- Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
- Pseudo-likelihood methods for community detection in large sparse networks
- Random matrices: universality of ESDs and the circular law
- Reconstruction and estimation in the planted partition model
- Spectral clustering and the high-dimensional stochastic blockmodel
- Spectral radii of sparse random matrices
- Spectral redemption in clustering sparse networks
- THE IHARA-SELBERG ZETA FUNCTION OF A TREE LATTICE
- The non-backtracking spectrum of the universal cover of a graph
- Variational Bayesian inference and complexity control for stochastic block models
Cited in
(18)- 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
- Overlapping community detection in networks via sparse spectral decomposition
- Spectral clustering for community detection
- Recent advances on mechanisms of network generation: community, exchangeability, and scale-free properties
- Consistent Estimation of the Number of Communities via Regularized Network Embedding
- 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 no real title available?)
- 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)
