Spectral clustering and the high-dimensional stochastic blockmodel
arXiv:1007.1684 · doi:10.1214/11-AOS887
Abstract
Networks or graphs can easily represent a diverse set of data sources that are characterized by interacting units or actors. Social networks, representing people who communicate with each other, are one example. Communities or clusters of highly connected actors form an essential feature in the structure of several empirical networks. Spectral clustering is a popular and computationally feasible method to discover these communities. The stochastic blockmodel [Social Networks 5 (1983) 109--137] is a social network model with well-defined communities; each node is a member of one community. For a network generated from the Stochastic Blockmodel, we bound the number of nodes "misclustered" by spectral clustering. The asymptotic results in this paper are the first clustering results that allow the number of clusters in the model to grow with the number of nodes, hence the name high-dimensional. In order to study spectral clustering under the stochastic blockmodel, we first show that under the more general latent space model, the eigenvectors of the normalized graph Laplacian asymptotically converge to the eigenvectors of a "population" normalized graph Laplacian. Aside from the implication for spectral clustering, this provides insight into a graph visualization technique. Our method of studying the eigenvectors of random matrices is original.
Published in at http://dx.doi.org/10.1214/11-AOS887 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)
References in corpus (2)
Cited by in corpus (91)
- Matrix estimation by Universal Singular Value Thresholding
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- Consistency of spectral clustering in stochastic block models
- Fast community detection by SCORE
- Consistency of community detection in networks under degree-corrected stochastic block models
- Pseudo-likelihood methods for community detection in large sparse networks
- Dynamic stochastic blockmodels for time-evolving social networks
- Stochastic blockmodels with growing number of classes
- A Review of Stochastic Block Models and Extensions for Graph Clustering
- Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
- Rate-optimal graphon estimation
- Sparse integrative clustering of multiple omics data sets
- The method of moments and degree distributions for network models
- Network histograms and universality of blockmodel approximation
- Near-optimal bounds for phase synchronization
- Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
- Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
- Exponential-Family Models of Random Graphs: Inference in Finite-, Super-, and Infinite Population Scenarios
- On the Question of Effective Sample Size in Network Modeling: An Asymptotic Inquiry
- Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
- On a 'Two Truths' Phenomenon in Spectral Graph Clustering
- Spectral Method and Regularized MLE Are Both Optimal for Top- Ranking
- Guaranteed clustering and biclustering via semidefinite programming
- A User Guide to Low-Pass Graph Signal Processing and its Applications
- Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
- Structural and Functional Discovery in Dynamic Networks with Non-negative Matrix Factorization
- Universally consistent vertex classification for latent positions graphs
- Role of normalization in spectral clustering for stochastic blockmodels
- A Survey on Theoretical Advances of Community Detection in Networks
- Improved Graph Clustering
- Co-clustering separately exchangeable network data
- One-Hot Graph Encoder Embedding
- Graphon Signal Processing
- Detecting Dynamic Community Structure in Functional Brain Networks Across Individuals: A Multilayer Approach
- Estimating multivariate latent-structure models
- Convergence of the groups posterior distribution in latent or stochastic block models
- Mean-field theory of graph neural networks in graph partitioning
- Blind identification of stochastic block models from dynamical observations
- Exact Blind Community Detection from Signals on Multiple Graphs
- Unsupervised Diffusion and Volume Maximization-Based Clustering of Hyperspectral Images
- Algorithmic detectability threshold of the stochastic block model
- Consistent structure estimation of exponential-family random graph models with block structure
- Large-scale estimation of random graph models with local dependence
- Differential Calculus on Graphon Space
- Laplacian Eigenmaps from Sparse, Noisy Similarity Measurements
- Bayesian estimation of the latent dimension and communities in stochastic blockmodels
- Confidence sets for network structure
- Community detection for weighted bipartite networks
- Robust Vertex Classification
- Discovering Communication Pattern Shifts in Large-Scale Labeled Networks using Encoder Embedding and Vertex Dynamics
- Graph Encoder Ensemble for Simultaneous Vertex Embedding and Community Detection
- Joint Network Topology Inference via a Shared Graphon Model
- A generalized hypothesis test for community structure in networks
- Novel Sampling Design for Respondent-driven Sampling
- Targeted sampling from massive block model graphs with personalized PageRank
- Pairwise Covariates-adjusted Block Model for Community Detection
- Synergistic Graph Fusion via Encoder Embedding
- Analysis of multiview legislative networks with structured matrix factorization: Does Twitter influence translate to the real world?
- A useful criterion on studying consistent estimation in community detection
- Profile Likelihood Biclustering
- Entrograms and coarse graining of dynamics on complex networks
- Detectability thresholds of general modular graphs
- Strong Consistency of Spectral Clustering for the Sparse Degree-Corrected Hypergraph Stochastic Block Model
- Structured networks and coarse-grained descriptions: a dynamical perspective
- Consistency of the maximum likelihood and variational estimators in a dynamic stochastic block model
- Non Parametric Statistics of Dynamic Networks with distinguishable nodes
- Group fairness without demographics using social networks
- Estimating the number of communities in weighted networks
- Convex Programming Based Spectral Clustering
- Comparing Graph Spectra of Adjacency and Laplacian Matrices
- Network Dependence Testing via Diffusion Maps and Distance-Based Correlations
- Multiple Support Recovery Using Very Few Measurements Per Sample
- How social networks influence human behavior: An integrated latent space approach for differential social influence
- Encoder Embedding for General Graph and Node Classification
- Refined Graph Encoder Embedding via Self-Training and Latent Community Recovery
- Fast and Scalable Multi-Kernel Encoder Classifier
- Improving Disease Comorbidity Prediction Based on Human Interactome with Biologically Supervised Graph Embedding
- Latent structure blockmodels for Bayesian spectral graph clustering
- Network modelling of topological domains using Hi-C data
- Linking Datasets on Organizations Using Half A Billion Open-Collaborated Records
- On role extraction for digraphs via neighbourhood pattern similarity
- Efficient Graph Encoder Embedding for Large Sparse Graphs in Python
- A Generative Framework for Predictive Modeling of Multiple Chronic Conditions Using Graph Variational Autoencoder and Bandit-Optimized Graph Neural Network
- Spectral goodness-of-fit tests for complete and partial network data
- Distributed Pseudo-Likelihood Method for Community Detection in Large-Scale Networks
- Testing Simultaneous Diagonalizability
- Overlapping community detection in networks via sparse spectral decomposition
- Consistent model selection for the Degree Corrected Stochastic Blockmodel
- Overlapping community detection in weighted networks
- A Unified Framework for Community Detection and Model Selection in Blockmodels
- Clustering as Approximation by Constrained Projectors: Theory and Guarantees