BELIEF PROPAGATION, ROBUST RECONSTRUCTION AND OPTIMAL RECOVERY OF BLOCK MODELS

• 成果类型: Article
• 署名作者: Mossel, Elchanan; Neeman, Joe; Sly, Allan
• 署名单位: University of Pennsylvania; University of California System; University of California Berkeley; University of Bonn; University of Texas System; University of Texas Austin; Australian National University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/15-AAP1145
• 发表日期: 2016
• 页码: 2211-2256
• 关键词: stochastic blockmodels; coloring random; algorithms; trees

摘要

We consider the problem of reconstructing sparse symmetric block models with two blocks and connection probabilities a/n and b/n for inter- and intra-block edge probabilities, respectively. It was recently shown that one can do better than a random guess if and only if (a - b)(2) > 2(a b). Using a variant of belief propagation, we give a reconstruction algorithm that is optimal in the sense that if (a - b)(2) > C (a b) for some constant C then our algorithm maximizes the fraction of the nodes labeled correctly. Ours is the only algorithm proven to achieve the optimal fraction of nodes labeled correctly. Along the way, we prove some results of independent interest regarding robust reconstruction for the Ising model on regular and Poisson trees.