TY - GEN
T1 - Crossing the KS threshold in the stochastic block model with information theory
AU - Abbe, Emmanuel
AU - Sandon, Colin
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2016/8/10
Y1 - 2016/8/10
N2 - Decelle et al. conjectured that community detection in the symmetric stochastic block model has a computational threshold given by the so-called Kesten-Stigum (KS) threshold, and that information-theoretic methods can cross this threshold for a large enough number of communities (4 or 5 depending on the regime of the parameters). This paper shows that at k = 5, it is possible to cross the KS threshold in the disassortative regime with a non-efficient algorithm that samples a clustering having typical cluster volumes. Further, the gap between the KS and information-theoretic threshold is shown to be large in some cases. In the case where edges are drawn only across clusters with an average degree of b, and denoting by k the number of communities, the KS threshold reads b ≳ k2 whereas our information-theoretic bound reads b ≳ k ln(k).
AB - Decelle et al. conjectured that community detection in the symmetric stochastic block model has a computational threshold given by the so-called Kesten-Stigum (KS) threshold, and that information-theoretic methods can cross this threshold for a large enough number of communities (4 or 5 depending on the regime of the parameters). This paper shows that at k = 5, it is possible to cross the KS threshold in the disassortative regime with a non-efficient algorithm that samples a clustering having typical cluster volumes. Further, the gap between the KS and information-theoretic threshold is shown to be large in some cases. In the case where edges are drawn only across clusters with an average degree of b, and denoting by k the number of communities, the KS threshold reads b ≳ k2 whereas our information-theoretic bound reads b ≳ k ln(k).
UR - http://www.scopus.com/inward/record.url?scp=84985963116&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84985963116&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2016.7541417
DO - 10.1109/ISIT.2016.7541417
M3 - Conference contribution
AN - SCOPUS:84985963116
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 840
EP - 844
BT - Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2016 IEEE International Symposium on Information Theory, ISIT 2016
Y2 - 10 July 2016 through 15 July 2016
ER -