Annales de l’Institut Henri Poincaré D

Full-Text PDF (399 KB) | Metadata | Table of Contents | AIHPD summary
Volume 5, Issue 2, 2018, pp. 211–249
DOI: 10.4171/AIHPD/53

Published online: 2018-06-04

Belief propagation on replica symmetric random factor graph models

Amin Coja-Oghlan[1] and Will Perkins[2]

(1) Goethe University, Frankfurt, Germany
(2) University of Birmingham, UK

According to physics predictions, the free energy of random factor graph models that satisfy a certain “static replica symmetry” condition can be calculated via the Belief Propagation message passing scheme [Krzakala et al., PNAS 2007]. Here we prove this conjecture for two general classes of random factor graph models, namely Poisson random factor graphs and random regular factor graphs. Specifically, we show that the messages constructed just as in the case of acyclic factor graphs asymptotically satisfy the Belief Propagation equations and that the free energy density is given by the Bethe free energy formula.

Keywords: Random graphs, Gibbs measures, belief propagation, Bethe formula, cavity method

Coja-Oghlan Amin, Perkins Will: Belief propagation on replica symmetric random factor graph models. Ann. Inst. Henri Poincaré Comb. Phys. Interact. 5 (2018), 211-249. doi: 10.4171/AIHPD/53