Spectral clustering and the high-dimensional stochastic blockmodel

DOI10.1214/11-AOS887zbMath1227.62042arXiv1007.1684OpenAlexW3104227803WikidataQ105584277 ScholiaQ105584277MaRDI QIDQ651016

Sourav Chatterjee, Karl Rohe, Bin Yu

Publication date: 8 December 2011

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

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

zbMATH Keywords

principal components analysisconvergence of eigenvectorslatent space model

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Social networks; opinion dynamics (91D30) Applications of graph theory (05C90)

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

Estimating Mixed Memberships With Sharp Eigenvector Deviations ⋮ Hierarchical Community Detection by Recursive Partitioning ⋮ Asymptotic Theory of Eigenvectors for Random Matrices With Diverging Spikes ⋮ A Maximum Principle Argument for the Uniform Convergence of Graph Laplacian Regressors ⋮ Community Detection in Sparse Networks Using the Symmetrized Laplacian Inverse Matrix (SLIM) ⋮ Optimal Bipartite Network Clustering ⋮ Randomized Spectral Clustering in Large-Scale Stochastic Block Models ⋮ Simultaneous Dimensionality and Complexity Model Selection for Spectral Graph Clustering ⋮ Maximum Likelihood Estimation and Graph Matching in Errorfully Observed Networks ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Improved Performance Guarantees for Orthogonal Group Synchronization via Generalized Power Method ⋮ Nonparametric statistics of dynamic networks with distinguishable nodes ⋮ Convexified modularity maximization for degree-corrected stochastic block models ⋮ An alternative class of models to position social network groups in latent spaces ⋮ Using Maximum Entry-Wise Deviation to Test the Goodness of Fit for Stochastic Block Models ⋮ Graphon estimation via nearest‐neighbour algorithm and two‐dimensional fused‐lasso denoising ⋮ A semiparametric Bayesian approach to epidemics, with application to the spread of the coronavirus MERS in South Korea in 2015 ⋮ Community informed experimental design ⋮ Subsampling spectral clustering for stochastic block models in large-scale networks ⋮ On the efficacy of higher-order spectral clustering under weighted stochastic block models ⋮ Perturbation of Linear Forms of Singular Vectors Under Gaussian Noise ⋮ Optimal Estimation of the Number of Network Communities ⋮ Clustering High-Dimensional Data via Feature Selection ⋮ A distributed community detection algorithm for large scale networks under stochastic block models ⋮ Efficient Estimation for Random Dot Product Graphs via a One-Step Procedure ⋮ Hypothesis testing for populations of networks ⋮ Community network auto-regression for high-dimensional time series ⋮ Large volatility matrix analysis using global and national factor models ⋮ Fast Network Community Detection With Profile-Pseudo Likelihood Methods ⋮ Combinatorial statistics and the sciences ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A survey on model-based co-clustering: high dimension and estimation challenges ⋮ Compressed spectral screening for large-scale differential correlation analysis with application in selecting glioblastoma gene modules ⋮ Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models ⋮ Asymptotic mutual information for the balanced binary stochastic block model ⋮ Sparse Graphs Using Exchangeable Random Measures ⋮ Co-clustering separately exchangeable network data ⋮ Random matrix theory in statistics: a review ⋮ Corrected Bayesian Information Criterion for Stochastic Block Models ⋮ Uniform Bounds for Invariant Subspace Perturbations ⋮ Near-Optimal Bounds for Phase Synchronization ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An $\ell_{\infty}$ Eigenvector Perturbation Bound and Its Application to Robust Covariance Estimation ⋮ Sparse exchangeable graphs and their limits via graphon processes ⋮ Statistical inference on random dot product graphs: a survey ⋮ Partitioning Well-Clustered Graphs: Spectral Clustering Works! ⋮ A Sparse Completely Positive Relaxation of the Modularity Maximization for Community Detection ⋮ Adjacency matrix comparison for stochastic block models ⋮ On the Stability of Network Indices Defined by Means of Matrix Functions ⋮ Optimization via low-rank approximation for community detection in networks ⋮ Bipartite communities via spectral partitioning ⋮ Consistent structure estimation of exponential-family random graph models with block structure ⋮ Detecting structural changes in longitudinal network data ⋮ Confidence sets for network structure ⋮ Review of statistical network analysis: models, algorithms, and software ⋮ Vertex nomination via seeded graph matching ⋮ Vertex nomination: the canonical sampling and the extended spectral nomination schemes ⋮ Unnamed Item ⋮ Multiresolution Network Models ⋮ Node Features Adjusted Stochastic Block Model ⋮ Likelihood Inference for Large Scale Stochastic Blockmodels With Covariates Based on a Divide-and-Conquer Parallelizable Algorithm With Communication ⋮ Localization of dominant eigenpairs and planted communities by means of Frobenius inner products ⋮ Exact recovery in the Ising blockmodel ⋮ Spectral method and regularized MLE are both optimal for top-\(K\) ranking ⋮ Probabilistic Community Detection With Unknown Number of Communities ⋮ 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 ⋮ 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 ⋮ Covariate Regularized Community Detection in Sparse Graphs ⋮ A Performance Guarantee for Spectral Clustering ⋮ Unnamed Item ⋮ Numerical study of reciprocal recommendation with domain matching ⋮ Mean-field theory of graph neural networks in graph partitioning ⋮ Matrix estimation by universal singular value thresholding ⋮ Consistency of spectral clustering in stochastic block models ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The topology of probability distributions on manifolds ⋮ Convergence of the groups posterior distribution in latent or stochastic block models ⋮ Differential calculus on graphon space ⋮ Role of normalization in spectral clustering for stochastic blockmodels ⋮ Robust and computationally feasible community detection in the presence of arbitrary outlier nodes ⋮ Detecting Overlapping Communities in Networks Using Spectral Methods ⋮ Blind Identification of Stochastic Block Models from Dynamical Observations ⋮ Stock co-jump networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improved spectral bisection algorithm and its application to dynamic load balancing
• Drawing graphs by eigenvectors: theory and practice
• Spectral partitioning works: planar graphs and finite element meshes
• Towards a theoretical foundation for Laplacian-based manifold methods
• Estimation and prediction for stochastic blockmodels for graphs with latent block structure
• Graph drawing. 11th international symposium, GD 2003, Perugia, Italy, September 21--24, 2003. Revised papers
• Consistency of spectral clustering
• Stochastic blockmodels with a growing number of classes
• A nonparametric view of network models and Newman–Girvan and other modularities
• Statistical mechanics of complex networks
• Mixed membership stochastic blockmodels
• Emergence of Scaling in Random Networks
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• On Finding Graph Clusterings with Maximum Modularity
• Empirical graph Laplacian approximation of Laplace–Beltrami operators: Large sample results
• Markov Graphs
• An Exponential Family of Probability Distributions for Directed Graphs
• Estimation and Prediction for Stochastic Blockstructures
• Latent Space Approaches to Social Network Analysis
• Community structure in social and biological networks
• An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• p₂: a random effects model with covariates for directed graphs
• A Survey of Statistical Network Models
• Uniform Convergence of Adaptive Graph-Based Regularization
• Collective dynamics of ‘small-world’ networks
• Singular vectors under random perturbation
• Learning Theory
• Lower Bounds for the Partitioning of Graphs
• Probabilistic Symmetries and Invariance Principles

This page was built for publication: Spectral clustering and the high-dimensional stochastic blockmodel