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

Peter Chin, Anup Rao, Van Vu
Proceedings of The 28th Conference on Learning Theory, PMLR 40:391-423, 2015.

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 this Paper

BibTeX
@InProceedings{pmlr-v40-Chin15, 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 = {Proceedings of The 28th Conference on Learning Theory}, pages = {391--423}, year = {2015}, editor = {Grünwald, Peter and Hazan, Elad and Kale, Satyen}, volume = {40}, series = {Proceedings of Machine Learning Research}, address = {Paris, France}, month = {03--06 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v40/Chin15.pdf}, url = {https://proceedings.mlr.press/v40/Chin15.html}, 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.} }
Endnote
%0 Conference Paper %T Stochastic Block Model and Community Detection in Sparse Graphs: A spectral algorithm with optimal rate of recovery %A Peter Chin %A Anup Rao %A Van Vu %B Proceedings of The 28th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2015 %E Peter Grünwald %E Elad Hazan %E Satyen Kale %F pmlr-v40-Chin15 %I PMLR %P 391--423 %U https://proceedings.mlr.press/v40/Chin15.html %V 40 %X 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.
RIS
TY - CPAPER TI - Stochastic Block Model and Community Detection in Sparse Graphs: A spectral algorithm with optimal rate of recovery AU - Peter Chin AU - Anup Rao AU - Van Vu BT - Proceedings of The 28th Conference on Learning Theory DA - 2015/06/26 ED - Peter Grünwald ED - Elad Hazan ED - Satyen Kale ID - pmlr-v40-Chin15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 40 SP - 391 EP - 423 L1 - http://proceedings.mlr.press/v40/Chin15.pdf UR - https://proceedings.mlr.press/v40/Chin15.html AB - 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. ER -
APA
Chin, P., Rao, A. & Vu, V.. (2015). Stochastic Block Model and Community Detection in Sparse Graphs: A spectral algorithm with optimal rate of recovery. Proceedings of The 28th Conference on Learning Theory, in Proceedings of Machine Learning Research 40:391-423 Available from https://proceedings.mlr.press/v40/Chin15.html.

Related Material