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)- 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
- Computing eigenvalues of large scale sparse tensors arising from a hypergraph
- Optimal Estimation of the Number of Network Communities
- Exact recovery in the Ising blockmodel
- Matrix and discrepancy view of generalized random and quasirandom graphs
- Community detection for weighted networks with unknown number of communities
- A sparse completely positive relaxation of the modularity maximization for community detection
- Network modelling of topological domains using Hi-C data
- Spectral clustering via sparse graph structure learning with application to proteomic signaling networks in cancer
- Detecting structural changes in longitudinal network data
- Consistent structure estimation of exponential-family random graph models with block structure
- Consistency of modularity clustering on random geometric graphs
- Profile likelihood biclustering
- Nonparametric statistics of dynamic networks with distinguishable nodes
- Detection of structurally homogeneous subsets in graphs
- Optimization via low-rank approximation for community detection in networks
- Stochastic block models are a discrete surface tension
- Maximum likelihood estimation of sparse networks with missing observations
- Hypothesis testing for populations of networks
- Spectral method and regularized MLE are both optimal for top-\(K\) ranking
- Perturbation analysis for the normalized Laplacian matrices in the multiway spectral clustering method
- Statistical inference on random dot product graphs: a survey
- Analysis of spectral clustering algorithms for community detection: the general bipartite setting
- Convex programming based spectral clustering
- Maximum Likelihood Estimation and Graph Matching in Errorfully Observed Networks
- A variational approach to the consistency of spectral clustering
- scientific article; zbMATH DE number 7370580 (Why is no real title available?)
- A spectral method for community detection in moderately sparse degree-corrected stochastic block models
- Bayesian estimation of the latent dimension and communities in stochastic blockmodels
- Computing the \(p\)-spectral radii of uniform hypergraphs with applications
- Clustering High-Dimensional Data via Feature Selection
- Testing goodness of fit of random graph models
- Nonreconstruction of high-dimensional stochastic block model with bounded degree
- Theoretical and computational guarantees of mean field variational inference for community detection
- scientific article; zbMATH DE number 7307464 (Why is no real title available?)
- The expected adjacency and modularity matrices in the degree corrected stochastic block model
- Sparse exchangeable graphs and their limits via graphon processes
- Perturbation of linear forms of singular vectors under Gaussian noise
- The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
- Randomized Spectral Clustering in Large-Scale Stochastic Block Models
- 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
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)
