Skip to main content

# BELIEF PROPAGATION, ROBUST RECONSTRUCTION AND OPTIMAL RECOVERY OF BLOCK MODELS

## Author(s): Mossel, Elchanan; Neeman, Joe; Sly, Allan M.

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1fd5t
 Abstract: 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. Publication Date: Aug-2016 Citation: Mossel, Elchanan, Neeman, Joe, Sly, Allan. (2016). BELIEF PROPAGATION, ROBUST RECONSTRUCTION AND OPTIMAL RECOVERY OF BLOCK MODELS. ANNALS OF APPLIED PROBABILITY, 26 (2211 - 2256. doi:10.1214/15-AAP1145 DOI: doi:10.1214/15-AAP1145 ISSN: 1050-5164 Pages: 2211 - 2256 Language: English Type of Material: Journal Article Journal/Proceeding Title: ANNALS OF APPLIED PROBABILITY Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.