Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic BP, and the information-computation gap
作者： Colin Sandon , Emmanuel Abbe
DOI:
关键词:
摘要: … guess its community membership at random, and running BP works. However, no method is … clustering (ie, a clustering having the right proportions of edges inside and across clusters). …
arxiv.org
harvard.edu参考文章(64)
Laurent Massoulié, Marc Lelarge, Jiaming Xu, Edge Label Inference in Generalized Stochastic Block Models: from Spectral Theory to Impossibility Results arXiv: Statistics Theory. ,(2014)
Colin Sandon, Emmanuel Abbe, Recovering communities in the general stochastic block model without knowing the parameters arXiv: Probability. ,(2015)
Anne Condon, Richard M. Karp, Algorithms for Graph Partitioning on the Planted Partition Model Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques. pp. 221- 232 ,(1999) , 10.1007/978-3-540-48413-4_23
Van Vu, A simple SVD algorithm for finding hidden partitions arXiv: Combinatorics. ,(2014)
Alexandre Proutière, Se-Young Yun, Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms. arXiv: Social and Information Networks. ,(2014)
Yair Weiss, Kevin P. Murphy, Michael I. Jordan, Loopy belief propagation for approximate inference: an empirical study uncertainty in artificial intelligence. pp. 467- 475 ,(1999)
Afonso S. Bandeira, Random Laplacian matrices and convex relaxations arXiv: Probability. ,(2015)
Laurent Massoulié, Marc Lelarge, Simon Heimlicher, Community Detection in the Labelled Stochastic Block Model arXiv: Social and Information Networks. ,(2012)
Andrea Montanari, Finding One Community in a Sparse Graph arXiv: Machine Learning. ,(2015) , 10.1007/S10955-015-1338-2
Joe Neeman, Praneeth Netrapalli, Non-Reconstructability in the Stochastic Block Model arXiv: Probability. ,(2014)