Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding

DOI10.1214/14-EJS978zbMath1308.62131arXiv1310.0532MaRDI QIDQ485940

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

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

zbMATH Keywords

clustering; stochastic block model; degree corrected stochastic block model

Mathematics Subject Classification ID

62H30: Classification and discrimination; cluster analysis (statistical aspects)

05C80: Random graphs (graph-theoretic aspects)

Related Items

Unnamed Item, Statistical inference on random dot product graphs: a survey, Analysis of spectral clustering algorithms for community detection: the general bipartite setting, Unnamed Item, Unnamed Item, Empirical Bayes estimation for the stochastic blockmodel, Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding, Vertex nomination schemes for membership prediction, Estimating a network from multiple noisy realizations, Limit theorems for eigenvectors of the normalized Laplacian for random graphs, Vertex nomination, consistent estimation, and adversarial modification, Vertex nomination: the canonical sampling and the extended spectral nomination schemes, The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics, Consistency of spectral clustering in stochastic block models

Cites Work

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