Spectral clustering and the high-dimensional stochastic blockmodel

DOI10.1214/11-AOS887zbMATH Open1227.62042arXiv1007.1684OpenAlexW3104227803WikidataQ105584277 ScholiaQ105584277MaRDI QIDQ651016FDOQ651016

Authors: Karl Rohe, Sourav Chatterjee, Bin Yu 

Publication date: 8 December 2011

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

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.

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

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

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)

Cites Work

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

Cited In (only showing first 100 items - show all)

• Contiguity and non-reconstruction results for planted partition models: the dense case
• Fast Network Community Detection With Profile-Pseudo Likelihood Methods
• On the question of effective sample size in network modeling: an asymptotic inquiry
• Consistent nonparametric estimation for heavy-tailed sparse graphs
• Analysis of multiview legislative networks with structured matrix factorization: does Twitter influence translate to the real world?
• A limit theorem for scaled eigenvectors of random dot product graphs
• Universally consistent vertex classification for latent positions graphs
• Optimal bipartite network clustering
• Corrected Bayesian information criterion for stochastic block models
• 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
• Consistency of the maximum likelihood and variational estimators in a dynamic stochastic block model
• Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding
• Co-clustering separately exchangeable network data
• 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
• A review of dynamic network models with latent variables
• Convergence of the groups posterior distribution in latent or stochastic block models
• Exponential-family models of random graphs: inference in finite, super and infinite population scenarios
• On semidefinite relaxations for the block model
• Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics
• Review on statistical methods for gene network reconstruction using expression data
• Community detection in degree-corrected block models
• Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown
• Consistency of spectral clustering in stochastic block models
• Matrix estimation by universal singular value thresholding
• Universal latent space model fitting for large networks with edge covariates
• Covariate regularized community detection in sparse graphs
• Detecting overlapping communities in networks using spectral methods
• Convexified modularity maximization for degree-corrected stochastic block models
• Additive and multiplicative effects network models
• Identifiability of nonparametric mixture models and Bayes optimal clustering
• Structural similarity: spectral methods for relaxed blockmodeling
• Differential calculus on graphon space
• The topology of probability distributions on manifolds
• Spectral and matrix factorization methods for consistent community detection in multi-layer networks
• Entrywise eigenvector analysis of random matrices with low expected rank
• A critical threshold for design effects in network sampling
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Spectral redemption in clustering sparse networks
• Impact of regularization on spectral clustering
• Random matrix theory in statistics: a review
• Bayesian degree-corrected stochastic blockmodels for community detection
• Stochastic blockmodels with a growing number of classes
• Identifiability and parameter estimation of the overlapped stochastic co-block model
• Likelihood Inference for Large Scale Stochastic Blockmodels With Covariates Based on a Divide-and-Conquer Parallelizable Algorithm With Communication
• Clustering Social Networks
• The highest dimensional stochastic blockmodel with a regularized estimator
• Spectral clustering and biclustering. Learning large graphs and contingency tables
• Model-based clustering of multiple networks with a hierarchical algorithm
• Pseudo-likelihood methods for community detection in large sparse networks
• Local law and Tracy-Widom limit for sparse stochastic block models
• Title not available (Why is that?)
• Title not available (Why is that?)
• Estimating the number of communities by spectral methods
• Rate-optimal graphon estimation
• Probabilistic Community Detection With Unknown Number of Communities
• Empirical Bayes estimation for the stochastic blockmodel
• Role of normalization in spectral clustering for stochastic blockmodels
• Review of statistical network analysis: models, algorithms, and software
• Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
• Reconstruction and estimation in the planted partition model
• Vertex nomination via seeded graph matching
• Estimating multivariate latent-structure models
• The method of moments and degree distributions for network models
• Spectral clustering in the dynamic stochastic block model
• Hierarchical Community Detection by Recursive Partitioning
• Title not available (Why is that?)
• Convex optimization for the densest subgraph and densest submatrix problems
• Fast community detection by SCORE
• Spectral clustering and block models: a review and a new algorithm
• Guaranteed clustering and biclustering via semidefinite programming
• Asymptotic Theory of Eigenvectors for Random Matrices With Diverging Spikes
• Community detection in sparse networks via Grothendieck's inequality
• Asymptotic mutual information for the balanced binary stochastic block model
• Spectral clustering via sparse graph structure learning with application to proteomic signaling networks in cancer
• Optimization via low-rank approximation for community detection in networks
• Large-scale estimation of random graph models with local dependence
• Two sample tests for high-dimensional autocovariances
• Detecting structural changes in longitudinal network data
• Exact recovery in the Ising blockmodel
• Localization of dominant eigenpairs and planted communities by means of Frobenius inner products.
• Perturbation analysis for the normalized Laplacian matrices in the multiway spectral clustering method
• Fusing data depth with complex networks: community detection with prior information
• On the stability of network indices defined by means of matrix functions
• Consistency of modularity clustering on random geometric graphs
• Computing the \(p\)-spectral radii of uniform hypergraphs with applications
• Bayesian community detection
• Sparse graphs using exchangeable random measures
• A variational approach to the consistency of spectral clustering
• Community detection by \(L_{0}\)-penalized graph Laplacian
• Stochastic block models are a discrete surface tension
• The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
• A sparse completely positive relaxation of the modularity maximization for community detection
• Bayesian estimation of the latent dimension and communities in stochastic blockmodels
• Nonreconstruction of high-dimensional stochastic block model with bounded degree
• The expected adjacency and modularity matrices in the degree corrected stochastic block model
• Higher-order spectral clustering for geometric graphs

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)