Spectral clustering and the high-dimensional stochastic blockmodel

DOI10.1214/11-AOS887MaRDI QIDQ651016zbMATH OpenOpenAlexWikidataFDO

Authors Karl Rohe, Sourav Chatterjee, 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) Applications of graph theory (05C90) Social networks; opinion dynamics (91D30)

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.

Recommendations

• Spectral clustering in the dynamic stochastic block model
• Randomized Spectral Clustering in Large-Scale Stochastic Block Models
• A review on spectral clustering and stochastic block models
• Spectral clustering and block models: a review and a new algorithm
• Consistency of spectral clustering in stochastic block models
• Strong Consistency of Spectral Clustering for Stochastic Block Models
• Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models
• Sparse and smooth: improved guarantees for spectral clustering in the dynamic stochastic block model
• Latent structure blockmodels for Bayesian spectral graph clustering
• Role of normalization in spectral clustering for stochastic blockmodels

Cites work

• scientific article; zbMATH DE number 3129892 (Why is no real title available?)
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 46563 (Why is no real title available?)
• scientific article; zbMATH DE number 47363 (Why is no real title available?)
• scientific article; zbMATH DE number 1168330 (Why is no real title available?)
• scientific article; zbMATH DE number 1418276 (Why is no real title available?)
• scientific article; zbMATH DE number 3417498 (Why is no real title available?)
• p₂: a random effects model with covariates for directed graphs
• A nonparametric view of network models and Newman–Girvan and other modularities
• A survey of statistical network models
• An Exponential Family of Probability Distributions for Directed Graphs
• An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
• An improved spectral bisection algorithm and its application to dynamic load balancing
• Collective dynamics of `small-world' networks
• Community structure in social and biological networks
• Consistency of spectral clustering
• Drawing graphs by eigenvectors: theory and practice
• Emergence of Scaling in Random Networks
• Empirical graph Laplacian approximation of Laplace–Beltrami operators: Large sample results
• Estimation and Prediction for Stochastic Blockstructures
• 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
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• Latent Space Approaches to Social Network Analysis
• Learning Theory
• Lower Bounds for the Partitioning of Graphs
• Markov Graphs
• Mixed membership stochastic blockmodels
• On Finding Graph Clusterings with Maximum Modularity
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• Probabilistic Symmetries and Invariance Principles
• Singular vectors under random perturbation
• Spectral partitioning works: planar graphs and finite element meshes
• Statistical mechanics of complex networks
• Stochastic blockmodels with a growing number of classes
• Towards a theoretical foundation for Laplacian-based manifold methods
• Uniform Convergence of Adaptive Graph-Based Regularization

Cited in

(only showing first 100 items - show all)

• Euclidean Representation of Low-Rank Matrices and Its Geometric Properties
• Review of statistical network analysis: models, algorithms, and software
• Consistent Community Detection in Inter-Layer Dependent Multi-Layer Networks
• Sparse integrative clustering of multiple omics data sets
• Computational lower bounds for graphon estimation via low-degree polynomials
• Leave-one-out singular subspace perturbation analysis for spectral clustering
• Spectral clustering-based community detection using graph distance and node attributes
• Reconstruction and estimation in the planted partition model
• Spectral clustering revisited: information hidden in the Fiedler vector
• Community detection on mixture multilayer networks via regularized tensor decomposition
• A multiscale environment for learning by diffusion
• Optimal Estimation of the Number of Network Communities
• Estimating multivariate latent-structure models
• Limit theorems for eigenvectors of the normalized Laplacian for random graphs
• The method of moments and degree distributions for network models
• Spectral clustering in the dynamic stochastic block model
• Vertex nomination via seeded graph matching
• Confidence sets for network structure
• On consistent vertex nomination schemes
• Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering
• Consistency and asymptotic normality of stochastic block models estimators from sampled data
• Convex optimization for the densest subgraph and densest submatrix problems
• Fast community detection by SCORE
• Exact clustering of weighted graphs via semidefinite programming
• Simultaneous Dimensionality and Complexity Model Selection for Spectral Graph Clustering
• Efficient Estimation for Random Dot Product Graphs via a One-Step Procedure
• Extended stochastic block models with application to criminal networks
• scientific article; zbMATH DE number 7415085 (Why is no real title available?)
• Hierarchical Community Detection by Recursive Partitioning
• Community informed experimental design
• Large volatility matrix analysis using global and national factor models
• Vertex nomination, consistent estimation, and adversarial modification
• On a two-truths phenomenon in spectral graph clustering
• scientific article; zbMATH DE number 7307464 (Why is no real title available?)
• Guaranteed clustering and biclustering via semidefinite programming
• Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models
• Spectral clustering and block models: a review and a new algorithm
• Vertex nomination: the canonical sampling and the extended spectral nomination schemes
• Network cluster-robust inference
• Sparse exchangeable graphs and their limits via graphon processes
• A fast algorithm for integrative community detection of multi-layer networks
• Spectral analysis of networks with latent space dynamics and signs
• Maximum Likelihood Estimation and Graph Matching in Errorfully Observed Networks
• A spectral method for community detection in moderately sparse degree-corrected stochastic block models
• A similarity measure for second order properties of non-stationary functional time series with applications to clustering and testing
• Identifying latent group structures in nonlinear panels
• Community detection in sparse networks via Grothendieck's inequality
• Combinatorial statistics and the sciences
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Community detection with nodal information: likelihood and its variational approximation
• Statistical inference on group Rasch mixture network models
• Profile-pseudo likelihood methods for community detection of multilayer stochastic block models
• Special invited paper: the SCORE normalization, especially for heterogeneous network and text data
• Using Maximum Entry-Wise Deviation to Test the Goodness of Fit for Stochastic Block Models
• Community detection for weighted networks with unknown number of communities
• Asymptotic Theory of Eigenvectors for Random Matrices With Diverging Spikes
• Matched bipartite block model with covariates
• Covariate-assisted spectral clustering
• Contiguity and non-reconstruction results for planted partition models: the dense case
• On the question of effective sample size in network modeling: an asymptotic inquiry
• Consistent nonparametric estimation for heavy-tailed sparse graphs
• Two-sample test of stochastic block models
• scientific article; zbMATH DE number 7626779 (Why is no real title available?)
• Fast Network Community Detection With Profile-Pseudo Likelihood Methods
• Spectral clustering via sparse graph structure learning with application to proteomic signaling networks in cancer
• Analysis of multiview legislative networks with structured matrix factorization: does Twitter influence translate to the real world?
• A Time-Varying Network for Cryptocurrencies
• Asymptotic mutual information for the balanced binary stochastic block model
• A limit theorem for scaled eigenvectors of random dot product graphs
• Large-scale estimation of random graph models with local dependence
• Two sample tests for high-dimensional autocovariances
• Optimization via low-rank approximation for community detection in networks
• Numerical study of reciprocal recommendation with domain matching
• Universally consistent vertex classification for latent positions graphs
• 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
• Detecting structural changes in longitudinal network data
• Consistency of community detection in networks under degree-corrected stochastic block models
• Classification and estimation in the stochastic blockmodel based on the empirical degrees
• Consistency of maximum-likelihood and variational estimators in the stochastic block model
• Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding
• Exact recovery in the Ising blockmodel
• Optimal bipartite network clustering
• Consistency of the maximum likelihood and variational estimators in a dynamic stochastic block model
• Corrected Bayesian information criterion for stochastic block models
• Consistent model selection for the degree corrected stochastic blockmodel
• Testing Simultaneous Diagonalizability
• Co-clustering separately exchangeable network data
• A survey on theoretical advances of community detection in networks
• A review on spectral clustering and stochastic block models
• Latent structure blockmodels for Bayesian spectral graph clustering
• Sparse and smooth: improved guarantees for spectral clustering in the dynamic stochastic block model
• Mean-field theory of graph neural networks in graph partitioning
• Localization of dominant eigenpairs and planted communities by means of Frobenius inner products.
• Multiresolution Network Models
• Perturbation analysis for the normalized Laplacian matrices in the multiway spectral clustering method
• A review of dynamic network models with latent variables
• Convergence of the groups posterior distribution in latent or stochastic block models
• Fusing data depth with complex networks: community detection with prior information
• The interplay of demographic variables and social distancing scores in deep prediction of U.S. COVID-19 cases

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q651016)