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 = {Peter Chin and Anup Rao and Van Vu}, booktitle = {Proceedings of The 28th Conference on Learning Theory}, pages = {391--423}, year = {2015}, editor = {Peter Grünwald and Elad Hazan and Satyen Kale}, 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 = {http://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 %J Proceedings of Machine Learning Research %P 391--423 %U http://proceedings.mlr.press %V 40 %W PMLR %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 PY - 2015/06/26 DA - 2015/06/26 ED - Peter Grünwald ED - Elad Hazan ED - Satyen Kale ID - pmlr-v40-Chin15 PB - PMLR SP - 391 DP - PMLR EP - 423 L1 - http://proceedings.mlr.press/v40/Chin15.pdf UR - http://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 PMLR 40:391-423

Related Material