Belief propagation, robust reconstruction and optimal recovery of block models

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.

Published at http://dx.doi.org/10.1214/15-AAP1145 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• Spectral redemption: clustering sparse networks

Cited by in corpus (13)

• Typology of phase transitions in Bayesian inference problems
• Hierarchical community structure in networks
• Consistency Thresholds for the Planted Bisection Model
• Fluctuation results for general block spin Ising models
• Community detection in the sparse hypergraph stochastic block model
• Multi-group Binary Choice with Social Interaction and a Random Communication Structure -- a Random Graph Approach
• Aligning random graphs with a sub-tree similarity message-passing algorithm
• Correlation detection in trees for planted graph alignment
• An Information-Percolation Bound for Spin Synchronization on General Graphs
• Efficient inference in stochastic block models with vertex labels
• Broadcasting induced colourings of random recursive trees and preferential attachment trees
• Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model
• Faster algorithms for the alignment of sparse correlated Erdös-Rényi random graphs