Unsolved
Exact Recovery Threshold in Multi-Community SBM
§ Problem Statement
§ Discussion
Loading discussion…
§ Significance & Implications
§ Known Partial Results
§ References
[1]
Exact recovery in the stochastic block model
Emmanuel Abbe, Afonso Bandeira, Georgina Hall (2016)
IEEE Transactions on Information Theory
📍 Section 6 (Open problems), the multi-community symmetric SBM exact-recovery threshold discussion (the open question on the threshold as $k$ grows).
[2]
[3]
Reconstruction and estimation in the planted partition model
Elchanan Mossel, Joe Neeman, Allan Sly (2015)
Probability Theory and Related Fields
📍 Section 1 (Introduction), Theorem 1.1 (information-theoretic threshold for exact recovery in 2-community SBM), p. 433.