The Kesten–Stigum conjecture for symmetric stochastic block models
Let be drawn from the symmetric stochastic block model with communities, probability inside the communities and across. Define
Kesten–Stigum conjecture. For any , if , it is possible to detect communities in polynomial time. If , it is possible to detect communities information-theoretically for some strictly below .
This conjecture predicts both the algorithmic threshold at the Kesten–Stigum threshold and an information-theoretic transition below it for sufficiently many communities. The source notes that is necessary under the constraint , whereas suffices in general, and that the second transition is more precise for while has a single threshold.
References
Status
- Solved: Emmanuel Abbe and Colin Sandon. Proof of the Achievability Conjectures for the General Stochastic Block Model (Communications on Pure and Applied Mathematics, 2018) https://doi.org/10.1002/cpa.21719
Source: Emmanuel Abbe, “Community Detection and Stochastic Block Models”, arXiv:1703.10146 (2023).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.