Decelle–Krzakala–Moore–Zdeborová conjecture for the planted partition model
For , let be the planted partition model with two uniformly random labels in , and let
where and are fixed real numbers. A bisection is positively correlated with the original clusters if it agrees with their labels more often than chance.
Decelle–Krzakala–Moore–Zdeborová conjecture. If , one can almost surely find a bisection positively correlated with the original clusters; if , the reconstruction problem is not solvable. Moreover, there are no consistent estimators of and when , while consistent estimators exist whenever .
This conjecture describes the detectability threshold for the sparse two-community planted partition model.
References
Status
- Solved: Elchanan Mossel, Joe Neeman, Allan Sly, and Laurent Massoulié. A Proof Of The Block Model Threshold Conjecture (arXiv, 2014) https://arxiv.org/abs/1311.4115
Source: Debapratim Banerjee, “Contiguity and non-reconstruction results for planted partition models: the dense case”, arXiv:1609.02854 (2016).
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.