Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding

DOI10.1214/14-EJS978MaRDI QIDQ485940zbMATH OpenOpenAlexFDO

Authors Vince Lyzinski, Carey E. Priebe, Daniel L. Sussman, Minh Tang, Avanti Athreya

Publication date 14 January 2015

Published in Electronic Journal of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.0532, https://projecteuclid.org/euclid.ejs/1420815881

zbMATH Keywords

clusteringstochastic block modeldegree corrected stochastic block model

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Vertex clustering in a stochastic blockmodel graph has wide applicability and has been the subject of extensive research. In thispaper, we provide a short proof that the adjacency spectral embedding can be used to obtain perfect clustering for the stochastic blockmodel and the degree-corrected stochastic blockmodel. We also show an analogous result for the more general random dot product graph model.

Recommendations

• A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
• Consistency of spectral clustering in stochastic block models
• Spectral clustering and the high-dimensional stochastic blockmodel
• Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown
• Spectral clustering and block models: a review and a new algorithm

Cites work

• A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
• A limit theorem for scaled eigenvectors of random dot product graphs
• A nonparametric view of network models and Newman–Girvan and other modularities
• Belief propagation, robust reconstruction and optimal recovery of block models
• Co-clustering separately exchangeable network data
• Consistency of spectral clustering in stochastic block models
• Empirical Bayes estimation for the stochastic blockmodel
• Estimation and prediction for stochastic blockmodels for graphs with latent block structure
• Freedman's inequality for matrix martingales
• Latent Space Approaches to Social Network Analysis
• Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding
• Random Dot Product Graph Models for Social Networks
• Spectral clustering and the high-dimensional stochastic blockmodel
• Stochastic blockmodels with a growing number of classes
• Strong consistency of k-means clustering
• The method of moments and degree distributions for network models
• Universally consistent vertex classification for latent positions graphs

Cited in

(32)

• scientific article; zbMATH DE number 7415085 (Why is no real title available?)
• Overlapping community detection in networks via sparse spectral decomposition
• Limit theorems for eigenvectors of the normalized Laplacian for random graphs
• Robust Recommendation via Social Network Enhanced Matrix Completion
• scientific article; zbMATH DE number 7370586 (Why is no real title available?)
• Spectral graph clustering via the expectation-solution algorithm
• Valid two-sample graph testing via optimal transport procrustes and multiscale graph correlation with applications in connectomics
• Vertex nomination: the canonical sampling and the extended spectral nomination schemes
• Community detection in complex networks: from statistical foundations to data science applications
• Vertex nomination schemes for membership prediction
• Vertex nomination, consistent estimation, and adversarial modification
• Consistency of spectral clustering in stochastic block models
• Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral estimator
• Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals
• Statistical inference on random dot product graphs: a survey
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding
• Spectral analysis of networks with latent space dynamics and signs
• Empirical Bayes estimation for the stochastic blockmodel
• On estimation and inference in latent structure random graphs
• Improved spectral community detection in large heterogeneous networks
• On a two-truths phenomenon in spectral graph clustering
• scientific article; zbMATH DE number 7626709 (Why is no real title available?)
• scientific article; zbMATH DE number 7625156 (Why is no real title available?)
• Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown
• A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
• Latent structure blockmodels for Bayesian spectral graph clustering
• The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
• A note on the orthogonal Procrustes problem and norm-dependent optimality
• Randomized Spectral Clustering in Large-Scale Stochastic Block Models
• Estimating a network from multiple noisy realizations
• On consistent vertex nomination schemes

This page was built for publication: Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q485940)