Stochastic Block Model and Community Detection in Sparse Graphs: A Spectral Algorithm with Optimal Rate of Recovery
Abstract
In this paper, we present and analyze a simple and robust spectral algorithm for the stochastic block model with $k$ blocks, for any $k$ fixed. Our algorithm works with graphs having constant edge density, under an optimal condition on the gap between the density inside a block and the density between the blocks. As a co-product, we settle an open question posed by Abbe et. al. concerning censor block models.
Cite
Text
Chin et al. "Stochastic Block Model and Community Detection in Sparse Graphs: A Spectral Algorithm with Optimal Rate of Recovery." Annual Conference on Computational Learning Theory, 2015.Markdown
[Chin et al. "Stochastic Block Model and Community Detection in Sparse Graphs: A Spectral Algorithm with Optimal Rate of Recovery." Annual Conference on Computational Learning Theory, 2015.](https://mlanthology.org/colt/2015/chin2015colt-stochastic/)BibTeX
@inproceedings{chin2015colt-stochastic,
title = {{Stochastic Block Model and Community Detection in Sparse Graphs: A Spectral Algorithm with Optimal Rate of Recovery}},
author = {Chin, Peter and Rao, Anup and Vu, Van},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2015},
pages = {391-423},
url = {https://mlanthology.org/colt/2015/chin2015colt-stochastic/}
}