Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding

DOI10.1214/14-EJS978zbMATH Open1308.62131arXiv1310.0532OpenAlexW2963582232MaRDI QIDQ485940FDOQ485940

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)

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.

Full work available at URL: https://arxiv.org/abs/1310.0532

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

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)

Cites Work

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

Cited In (32)

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

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)