Decelle et al.'s partial-recovery threshold conjecture for the stochastic block model
Throughout, let be the two-community stochastic block model with two roughly equal-sized communities, within-community connection probability , between-community connection probability , sparse parameters , and . Decelle et al.'s threshold conjecture. If
then partial recovery in is possible, whereas if
then partial recovery is information-theoretically impossible.
References
Status
- Solved: Elchanan Mossel, Joe Neeman, and Allan Sly. A Proof Of The Block Model Threshold Conjecture (Combinatorica, 2016) https://ar5iv.labs.arxiv.org/html/1311.4115
Source: Ankur Moitra, William Perry and Alexander S. Wein, “How Robust are Reconstruction Thresholds for Community Detection?”, arXiv:1511.01473 (2016).
Progress summary
Never refreshed
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.