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)

• 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
• Consistent structure estimation of exponential-family random graph models with block structure
• Profile likelihood biclustering
• Maximum likelihood estimation of sparse networks with missing observations
• Convex programming based spectral clustering
• Perturbation of linear forms of singular vectors under Gaussian noise
• Near-optimal bounds for phase synchronization
• An \(\ell_{\infty}\) eigenvector perturbation bound and its application
• Convex relaxation methods for community detection
• Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
• Robust high-dimensional factor models with applications to statistical machine learning
• Clustering High-Dimensional Data via Feature Selection
• Hypothesis testing for populations of networks
• Detection of structurally homogeneous subsets in graphs
• Statistical inference on random dot product graphs: a survey
• Title not available (Why is that?)
• Theoretical and computational guarantees of mean field variational inference for community detection
• Network representation using graph root distributions
• Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees
• Estimating parameters of a probabilistic heterogeneous block model via the EM algorithm
• On the estimation of latent distances using graph distances
• Computing eigenvalues of large scale sparse tensors arising from a hypergraph
• Network modelling of topological domains using Hi-C data
• Testing goodness of fit of random graph models
• Nonparametric statistics of dynamic networks with distinguishable nodes
• A generalized Lieb's theorem and its applications to spectrum estimates for a sum of random matrices
• Spectral method and regularized MLE are both optimal for top-\(K\) ranking
• Randomized Spectral Clustering in Large-Scale Stochastic Block Models
• Matrix and discrepancy view of generalized random and quasirandom graphs
• Sparse integrative clustering of multiple omics data sets
• Optimal Estimation of the Number of Network Communities
• Limit theorems for eigenvectors of the normalized Laplacian for random graphs
• Title not available (Why is that?)
• Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models
• Sparse exchangeable graphs and their limits via graphon processes
• Maximum Likelihood Estimation and Graph Matching in Errorfully Observed Networks
• A spectral method for community detection in moderately sparse degree-corrected stochastic block models
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Covariate-assisted spectral clustering
• Community detection for weighted networks with unknown number of communities
• 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

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)