论文标题
随机块模型的确切相变和树上的重建
Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees
论文作者
论文摘要
在本文中，我们继续严格地确定统计物理学的突破性工作的预测，由卡尔萨卡拉，摩尔，兹德堡（Zdeborová，Zdeborová（2011））就块模型进行，尤其是$ q = 3 $和$ q = 4 $社区。 我们证明，对于$ q = 3 $和$ q = 4 $，如果平均度度超过一定的恒定度，则没有计算统计差距，从理论上讲是不可能检测到Kesten-Stigum Bound的信息。证明是基于表明，对于Galton-Watson树上的广播过程，如果平均度足够大，则不可能$ Q = 3 $和$ Q = 4 $重建。这改善了Sly（2009）的结果，后者证明了普通树的类似结果，价格为$ Q = 3 $。我们对关键案例$ q = 4 $的分析提供了详细的图片，表明在反铁磁案例中绑定的Kesten-Stigum的紧密度取决于树的平均程度。我们还证明，对于$ q \ geq 5 $，kestin-stigum Bound并不锋利。 我们的结果证明了减速器，Krzakala，Moore，Zdeborová（2011），Moore（2017），Abbe和Sandon（2018）以及Ricci-Tersenghi，Semerjian和Zdeborová（2019）的猜想。我们的证明是基于对树和图形过程的新一般耦合以及对树上广播过程的精致分析。
In this paper we continue to rigorously establish the predictions in ground breaking work in statistical physics by Decelle, Krzakala, Moore, Zdeborová (2011) regarding the block model, in particular in the case of $q=3$ and $q=4$ communities. We prove that for $q=3$ and $q=4$ there is no computational-statistical gap if the average degree is above some constant by showing it is information theoretically impossible to detect below the Kesten-Stigum bound. The proof is based on showing that for the broadcast process on Galton-Watson trees, reconstruction is impossible for $q=3$ and $q=4$ if the average degree is sufficiently large. This improves on the result of Sly (2009), who proved similar results for regular trees for $q=3$. Our analysis of the critical case $q=4$ provides a detailed picture showing that the tightness of the Kesten-Stigum bound in the antiferromagnetic case depends on the average degree of the tree. We also prove that for $q\geq 5$, the Kestin-Stigum bound is not sharp. Our results prove conjectures of Decelle, Krzakala, Moore, Zdeborová (2011), Moore (2017), Abbe and Sandon (2018) and Ricci-Tersenghi, Semerjian, and Zdeborová (2019). Our proofs are based on a new general coupling of the tree and graph processes and on a refined analysis of the broadcast process on the tree.
