Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery

Peter Chin, Anup Rao, Van Vu

Type: Preprint

Publication Date: 2015-01-01

Citations: 109

DOI: https://doi.org/10.48550/arxiv.1501.05021

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery	2015	Peter Chin Anup Rao Van Vu
+	Community Detection and Stochastic Block Models	2017	Emmanuel Abbé
+	Community detection and stochastic block models: recent developments	2017	Emmanuel Abbé
+	Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms	2014	Se-Young Yun Alexandre Proutière
+	Partial Recovery Bounds for the Sparse Stochastic Block Model	2016	Jonathan Scarlett Volkan Cevher
+	Partial Recovery Bounds for the Sparse Stochastic Block Model	2016	Jonathan Scarlett Volkan Cevher
+	Recovery and rigidity in a regular stochastic block model	2016	Gerandy Brito Ioana Dumitriu Shirshendu Ganguly Christopher Hoffman Linh V. Tran
+ PDF Chat	Sparse and smooth: Improved guarantees for spectral clustering in the dynamic stochastic block model	2022	Nicolas Keriven Samuel Vaiter
+	Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms	2015	Emmanuel Abbé Colin Sandon
+	Sparse and Smooth: improved guarantees for Spectral Clustering in the Dynamic Stochastic Block Model	2020	Nicolas Keriven Samuel Vaiter
+	Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms.	2015	Emmanuel Abbé Colin Sandon
+ PDF Chat	Community detection in the sparse hypergraph stochastic block model	2021	Soumik Pal Yizhe Zhu
+	Exact recovery for the non-uniform Hypergraph Stochastic Block Model	2023	Ioana Dumitriu Hai‐Xiao Wang
+ PDF Chat	Partial recovery bounds for the sparse stochastic block model	2016	Jonathan Scarlett Volkan Cevher
+	Optimality of Spectral Algorithms for Community Detection in the Labeled Stochastic Block Model.	2015	Se-Young Yun Alexandre Proutière
+	Recovering communities in the general stochastic block model without knowing the parameters	2015	Emmanuel Abbé Colin Sandon
+	Recovering communities in the general stochastic block model without knowing the parameters	2015	Emmanuel Abbé Colin Sandon
+ PDF Chat	Exact Recovery in the Stochastic Block Model	2015	Emmanuel Abbé Afonso S. Bandeira Georgina Hall
+	Exact Recovery in the Stochastic Block Model	2014	Emmanuel Abbé Afonso S. Bandeira Georgina Hall
+	Exact Recovery in the Stochastic Block Model	2014	Emmanuel Abbé Afonso S. Bandeira Georgina Hall

Works That Cite This (84)

Action	Title	Year	Authors
+	Recovering the structure of random linear graphs	2018	Israel Rocha Jeannette Janssen Nauzer Kalyaniwalla
+	Learning big Gaussian Bayesian networks: partition, estimation, and fusion	2019	Jiaying Gu Qing Zhou
+	Theoretical and Computational Guarantees of Mean Field Variational Inference for Community Detection	2017	Anderson Y. Zhang Harrison H. Zhou
+	Unified $\ell_{2\rightarrow\infty}$ Eigenspace Perturbation Theory for Symmetric Random Matrices	2019	Lihua Lei
+	Exponential error rates of SDP for block models: Beyond Grothendieck's inequality	2017	Yingjie Fei Yudong Chen
+	Local-access generators for basic random graph models	2017	Amartya Shankha Biswas Ronitt Rubinfeld Anak Yodpinyanee
+	Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustly	2019	Yingjie Fei Yudong Chen
+	Achieving Optimal Misclassification Proportion in Stochastic Block Models	2017	Chao Gao Zongming Ma Anderson Y. Zhang Harrison H. Zhou
+	CHIP: A Hawkes Process Model for Continuous-time Networks with Scalable and Consistent Estimation	2019	Makan Arastuie Subhadeep Paul Kevin S. Xu
+	Optimal Recovery of Block Models with $q$ Communities	2020	Byron Chin Allan Sly

Works Cited by This (20)

Action	Title	Year	Authors
+	A simple SVD algorithm for finding hidden partitions	2014	Van Vu
+	Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms	2014	Se-Young Yun Alexandre Proutière
+	Exact Recovery in the Stochastic Block Model	2014	Emmanuel Abbé Afonso S. Bandeira Georgina Hall
+	Spectral partitioning of random graphs	2001	Frank McSherry
+	Stochastic Block Models and Reconstruction	2012	Elchanan Mossel Joe Neeman Allan Sly
+	A Proof Of The Block Model Threshold Conjecture	2013	Elchanan Mossel Joe Neeman Allan Sly
+ PDF Chat	Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications	2011	Aurélien Decelle Florent Krząkała Cristopher Moore Lenka Zdeborová
+	Spectral techniques applied to sparse random graphs	2005	Uriel Feige E. O. Ofek
+	On the second eigenvalue of random regular graphs	1989	Joel Friedman J. Kahn Endre Szemerédi
+	The rotation of eigenvectors by a perturbation	1963	Chandler Davis