EXACT PHASE TRANSITIONS FOR STOCHASTIC BLOCK MODELS AND RECONSTRUCTION ON TREES

• 成果类型: Article
• 署名作者: Mossel, Elchanan; Sly, Allan; Sohn, Youngtak
• 署名单位: Massachusetts Institute of Technology (MIT); Princeton University
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/24-AOP1723
• 发表日期: 2025
• 页码: 967-1018
• 关键词: lattice spin-glass; ising-model; ferromagnetic bias; disordered state; external fields; INFORMATION; blockmodels; extremality

摘要

In this paper we continue to rigorously establish the predictions in ground breaking work in statistical physics by Decelle, Krzakala, Moore, Zdeborov & aacute; (Phys. Rev. E 84 (2011) 066106) 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 (Ann. Probab. 39 (2011) 1365-1406), 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. Our results prove conjectures of Decelle, Krzakala, Moore, Zdeborov & aacute; (Phys. Rev. E 84 (2011) 066106), Moore (Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 121 (2017) 26-61), Abbe and Sandon (Comm. Pure Appl. Math. 71 (2018) 1334-1406) and Ricci-Tersenghi, Semerjian, and Zdeborov & aacute; (Phys. Rev. E 99 (2019) 042109). 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.