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)- 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
- scientific article; zbMATH DE number 7255095 (Why is no real title available?)
- Synergistic graph fusion via encoder embedding
- On semidefinite relaxations for the block model
- Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics
- Exponential-family models of random graphs: inference in finite, super and infinite population scenarios
- Review on statistical methods for gene network reconstruction using expression data
- Stock co-jump networks
- Learning Coefficient Heterogeneity over Networks: A Distributed Spanning-Tree-Based Fused-Lasso Regression
- Community detection in degree-corrected block models
- scientific article; zbMATH DE number 7626708 (Why is no real title available?)
- Consistency of modularity clustering on random geometric graphs
- Consistency of spectral clustering in stochastic block models
- Matrix estimation by universal singular value thresholding
- Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown
- On the stability of network indices defined by means of matrix functions
- Computing the \(p\)-spectral radii of uniform hypergraphs with applications
- Bayesian community detection
- Estimation of the parameters in an expanding dynamic network model
- Null models and community detection in multi-layer networks
- Overlapping community detection in networks via sparse spectral decomposition
- Scalable estimation of epidemic thresholds via node sampling
- Detecting groups in large vector autoregressions
- Convexified modularity maximization for degree-corrected stochastic block models
- 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
- Additive and multiplicative effects network models
- Structural similarity: spectral methods for relaxed blockmodeling
- Identifiability of nonparametric mixture models and Bayes optimal clustering
- Smoothing graphons for modelling exchangeable relational data
- A stochastic block Ising model for multi-layer networks with inter-layer dependence
- 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
- scientific article; zbMATH DE number 7415089 (Why is no real title available?)
- A variational approach to the consistency of spectral clustering
- Sparse graphs using exchangeable random measures
- Community detection by \(L_{0}\)-penalized graph Laplacian
- A semiparametric Bayesian approach to epidemics, with application to the spread of the coronavirus MERS in South Korea in 2015
- A critical threshold for design effects in network sampling
- Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral estimator
- Stochastic block models are a discrete surface tension
- Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
- Spectral redemption in clustering sparse networks
- The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
- A maximum principle argument for the uniform convergence of graph Laplacian regressors
- Network Estimation by Mixing: Adaptivity and More
- Co-clustering of nonsmooth graphons
- Learning sparse graphons and the generalized Kesten-Stigum threshold
- Impact of regularization on spectral clustering
- Bayesian estimation of the latent dimension and communities in stochastic blockmodels
- The expected adjacency and modularity matrices in the degree corrected stochastic block model
- A sparse completely positive relaxation of the modularity maximization for community detection
- Nonreconstruction of high-dimensional stochastic block model with bounded degree
- Nonparametric identification and estimation of stochastic block models from many small networks
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)
