Consistency of spectral clustering in stochastic block models

DOI10.1214/14-AOS1274zbMath1308.62041arXiv1312.2050OpenAlexW3100144903MaRDI QIDQ2338925

Jing Lei, Alessandro Rinaldo

Publication date: 27 March 2015

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

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

zbMATH Keywords

sparsitynetwork dataspectral clusteringstochastic block model

Mathematics Subject Classification ID

Asymptotic properties of parametric estimators (62F12) Classification and discrimination; cluster analysis (statistical aspects) (62H30)

Related Items (only showing first 100 items - show all)

Estimating Mixed Memberships With Sharp Eigenvector Deviations ⋮ Overlapping community detection in networks via sparse spectral decomposition ⋮ The hierarchy of block models ⋮ The Bethe Hessian and information theoretic approaches for online change-point detection in network data ⋮ A Schatten-\(q\) low-rank matrix perturbation analysis via perturbation projection error bound ⋮ An impossibility result for reconstruction in the degree-corrected stochastic block model ⋮ Hierarchical Community Detection by Recursive Partitioning ⋮ Community Detection in Sparse Networks Using the Symmetrized Laplacian Inverse Matrix (SLIM) ⋮ Community detection via an efficient nonconvex optimization approach based on modularity ⋮ Large-scale estimation of random graph models with local dependence ⋮ Bayesian community detection ⋮ Sparse and smooth: improved guarantees for spectral clustering in the dynamic stochastic block model ⋮ Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral estimator ⋮ Uniform estimation in stochastic block models is slow ⋮ Optimal Bipartite Network Clustering ⋮ Randomized Spectral Clustering in Large-Scale Stochastic Block Models ⋮ Community detection by \(L_{0}\)-penalized graph Laplacian ⋮ Simultaneous Dimensionality and Complexity Model Selection for Spectral Graph Clustering ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Hypothesis testing in sparse weighted stochastic block model ⋮ Clustering sparse binary data with hierarchical Bayesian Bernoulli mixture model ⋮ A spectral algorithm with additive clustering for the recovery of overlapping communities in networks ⋮ Higher-order spectral clustering for geometric graphs ⋮ Model assisted variable clustering: minimax-optimal recovery and algorithms ⋮ Optimal rates for community estimation in the weighted stochastic block model ⋮ Spectral and matrix factorization methods for consistent community detection in multi-layer networks ⋮ Rate optimal Chernoff bound and application to community detection in the stochastic block models ⋮ Convexified modularity maximization for degree-corrected stochastic block models ⋮ Joint Community Detection and Rotational Synchronization via Semidefinite Programming ⋮ Test on stochastic block model: local smoothing and extreme value theory ⋮ Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering ⋮ Perturbation of Linear Forms of Singular Vectors Under Gaussian Noise ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A random effects stochastic block model for joint community detection in multiple networks with applications to neuroimaging ⋮ Entrywise eigenvector analysis of random matrices with low expected rank ⋮ Spectral norm bounds for block Markov chain random matrices ⋮ Core-periphery structure in networks: a statistical exposition ⋮ Non-backtracking spectra of weighted inhomogeneous random graphs ⋮ Bayesian estimation of the latent dimension and communities in stochastic blockmodels ⋮ A similarity measure for second order properties of non-stationary functional time series with applications to clustering and testing ⋮ Theoretical and computational guarantees of mean field variational inference for community detection ⋮ Exponential-family models of random graphs: inference in finite, super and infinite population scenarios ⋮ Approximating Spectral Clustering via Sampling: A Review ⋮ Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding ⋮ Uniform Bounds for Invariant Subspace Perturbations ⋮ Spectral clustering in the dynamic stochastic block model ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics ⋮ On semidefinite relaxations for the block model ⋮ Statistical inference on random dot product graphs: a survey ⋮ Consistency of the maximum likelihood and variational estimators in a dynamic stochastic block model ⋮ Adjusted chi-square test for degree-corrected block models ⋮ Unnamed Item ⋮ A goodness-of-fit test for stochastic block models ⋮ Optimization via low-rank approximation for community detection in networks ⋮ Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing ⋮ Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees ⋮ Convex optimization for the densest subgraph and densest submatrix problems ⋮ Community detection in sparse networks via Grothendieck's inequality ⋮ Community detection in degree-corrected block models ⋮ Limit theorems for eigenvectors of the normalized Laplacian for random graphs ⋮ Profile likelihood biclustering ⋮ On the estimation of latent distances using graph distances ⋮ Sparse random tensors: concentration, regularization and applications ⋮ Consistent structure estimation of exponential-family random graph models with block structure ⋮ Network Cross-Validation for Determining the Number of Communities in Network Data ⋮ Rate-optimal graphon estimation ⋮ Convex programming based spectral clustering ⋮ Consistent nonparametric estimation for heavy-tailed sparse graphs ⋮ Optimality of spectral clustering in the Gaussian mixture model ⋮ Node Features Adjusted Stochastic Block Model ⋮ A spectral method for community detection in moderately sparse degree-corrected stochastic block models ⋮ Exact Clustering of Weighted Graphs via Semidefinite Programming ⋮ Analysis of spectral clustering algorithms for community detection: the general bipartite setting ⋮ Computing Eigenvalues of Large Scale Sparse Tensors Arising from a Hypergraph ⋮ Partial recovery bounds for clustering with the relaxed \(K\)-means ⋮ Community detection on mixture multilayer networks via regularized tensor decomposition ⋮ Extended stochastic block models with application to criminal networks ⋮ The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics ⋮ The Interplay of Demographic Variables and Social Distancing Scores in Deep Prediction of U.S. COVID-19 Cases ⋮ A Performance Guarantee for Spectral Clustering ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Non-convex exact community recovery in stochastic block model ⋮ Consistency of spectral clustering in stochastic block models ⋮ Covariance-Based Sample Selection for Heterogeneous Data: Applications to Gene Expression and Autism Risk Gene Detection ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Robust and computationally feasible community detection in the presence of arbitrary outlier nodes ⋮ Blind Identification of Stochastic Block Models from Dynamical Observations ⋮ Using Maximum Entry-Wise Deviation to Test the Goodness of Fit for Stochastic Block Models

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pseudo-likelihood methods for community detection in large sparse networks
• Fast community detection by SCORE
• Belief propagation, robust reconstruction and optimal recovery of block models
• Spectra of edge-independent random graphs
• Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding
• On the spectra of general random graphs
• Spectral clustering and the high-dimensional stochastic blockmodel
• User-friendly tail bounds for sums of random matrices
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• Statistical analysis of network data. Methods and models
• NP-hardness of Euclidean sum-of-squares clustering
• Consistency of community detection in networks under degree-corrected stochastic block models
• Consistency of maximum-likelihood and variational estimators in the stochastic block model
• Classification and estimation in the stochastic blockmodel based on the empirical degrees
• Consistency of spectral clustering in stochastic block models
• Role of normalization in spectral clustering for stochastic blockmodels
• Minimax sparse principal subspace estimation in high dimensions
• A constant-factor approximation algorithm for the k -median problem (extended abstract)
• Stochastic blockmodels with a growing number of classes
• A nonparametric view of network models and Newman–Girvan and other modularities
• Spectral redemption in clustering sparse networks
• Improved Spectral-Norm Bounds for Clustering
• Graph Partitioning via Adaptive Spectral Techniques
• Community structure in social and biological networks
• A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
• A Survey of Statistical Network Models
• Consistent Adjacency-Spectral Partitioning for the Stochastic Block Model When the Model Parameters Are Unknown
• Spectral techniques applied to sparse random graphs
• Approximating k-median via pseudo-approximation
• Networks

This page was built for publication: Consistency of spectral clustering in stochastic block models