Spectral clustering and the high-dimensional stochastic blockmodel
From MaRDI portal
(Redirected from Publication:651016)
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?)
- p2: 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)- Sparse and smooth: improved guarantees for spectral clustering in the dynamic stochastic block model
- Model-based clustering of multiple networks with a hierarchical algorithm
- Spectral clustering and biclustering. Learning large graphs and contingency tables
- Stochastic blockmodels with a growing number of classes
- Clustering Social Networks
- scientific article; zbMATH DE number 7415085 (Why is no real title available?)
- Convexified modularity maximization for degree-corrected stochastic block models
- A limit theorem for scaled eigenvectors of random dot product graphs
- Classification and estimation in the stochastic blockmodel based on the empirical degrees
- Consistency of maximum-likelihood and variational estimators in the stochastic block model
- Local law and Tracy-Widom limit for sparse stochastic block models
- Pseudo-likelihood methods for community detection in large sparse networks
- scientific article; zbMATH DE number 7255138 (Why is no real title available?)
- scientific article; zbMATH DE number 7370586 (Why is no real title available?)
- Contiguity and non-reconstruction results for planted partition models: the dense case
- Structural similarity: spectral methods for relaxed blockmodeling
- Fast Network Community Detection With Profile-Pseudo Likelihood Methods
- A critical threshold for design effects in network sampling
- Identifiability and parameter estimation of the overlapped stochastic co-block model
- Convex optimization for the densest subgraph and densest submatrix problems
- Fast community detection by SCORE
- Exponential-family models of random graphs: inference in finite, super and infinite population scenarios
- Reconstruction and estimation in the planted partition model
- Consistency of spectral clustering in stochastic block models
- Matrix estimation by universal singular value thresholding
- Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
- On semidefinite relaxations for the block model
- Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics
- Estimating multivariate latent-structure models
- Review of statistical network analysis: models, algorithms, and software
- The method of moments and degree distributions for network models
- Estimating the number of communities by spectral methods
- Consistency of the maximum likelihood and variational estimators in a dynamic stochastic block model
- Spectral clustering in the dynamic stochastic block model
- Rate-optimal graphon estimation
- Spectral redemption in clustering sparse networks
- On the question of effective sample size in network modeling: an asymptotic inquiry
- Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
- Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding
- Additive and multiplicative effects network models
- Likelihood Inference for Large Scale Stochastic Blockmodels With Covariates Based on a Divide-and-Conquer Parallelizable Algorithm With Communication
- Impact of regularization on spectral clustering
- Review on statistical methods for gene network reconstruction using expression data
- Universally consistent vertex classification for latent positions graphs
- Bayesian degree-corrected stochastic blockmodels for community detection
- Consistent nonparametric estimation for heavy-tailed sparse graphs
- Empirical Bayes estimation for the stochastic blockmodel
- Differential calculus on graphon space
- The topology of probability distributions on manifolds
- Vertex nomination via seeded graph matching
- Probabilistic Community Detection With Unknown Number of Communities
- Universal latent space model fitting for large networks with edge covariates
- Co-clustering separately exchangeable network data
- A review of dynamic network models with latent variables
- Spectral and matrix factorization methods for consistent community detection in multi-layer networks
- Asymptotic Theory of Eigenvectors for Random Matrices With Diverging Spikes
- Analysis of multiview legislative networks with structured matrix factorization: does Twitter influence translate to the real world?
- The highest dimensional stochastic blockmodel with a regularized estimator
- Role of normalization in spectral clustering for stochastic blockmodels
- Identifiability of nonparametric mixture models and Bayes optimal clustering
- Covariate regularized community detection in sparse graphs
- Community detection in degree-corrected block models
- Community detection in sparse networks via Grothendieck's inequality
- Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown
- Optimal bipartite network clustering
- Detecting overlapping communities in networks using spectral methods
- Random matrix theory in statistics: a review
- A review on spectral clustering and stochastic block models
- Latent structure blockmodels for Bayesian spectral graph clustering
- Corrected Bayesian information criterion for stochastic block models
- Hierarchical Community Detection by Recursive Partitioning
- Convergence of the groups posterior distribution in latent or stochastic block models
- Consistency of community detection in networks under degree-corrected stochastic block models
- Spectral clustering and block models: a review and a new algorithm
- Guaranteed clustering and biclustering via semidefinite programming
- Entrywise eigenvector analysis of random matrices with low expected rank
- Higher-order spectral clustering for geometric graphs
- Sparse integrative clustering of multiple omics data sets
- Community detection by \(L_{0}\)-penalized graph Laplacian
- On the stability of network indices defined by means of matrix functions
- Sparse graphs using exchangeable random measures
- Bayesian community detection
- Near-optimal bounds for phase synchronization
- Localization of dominant eigenpairs and planted communities by means of Frobenius inner products.
- Network representation using graph root distributions
- Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models
- 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
- A generalized Lieb's theorem and its applications to spectrum estimates for a sum of random matrices
- Limit theorems for eigenvectors of the normalized Laplacian for random graphs
- On the estimation of latent distances using graph distances
- Fusing data depth with complex networks: community detection with prior information
- Asymptotic mutual information for the balanced binary stochastic block model
- Large-scale estimation of random graph models with local dependence
- Two sample tests for high-dimensional autocovariances
- An \(\ell_{\infty}\) eigenvector perturbation bound and its application
- Covariate-assisted spectral clustering
- 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
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)
