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.
Accepté le :
Publié le :
DOI : 10.4171/aihpd/53
Publié le :
DOI : 10.4171/aihpd/53
Classification :
05-XX, 82-XX
Mots-clés : Random graphs, Gibbs measures, belief propagation, Bethe formula, cavity method
Mots-clés : Random graphs, Gibbs measures, belief propagation, Bethe formula, cavity method
@article{AIHPD_2018__5_2_211_0, author = {Coja-Oghlan, Amin and Perkins, Will}, title = {Belief propagation on replica symmetric random factor graph models}, journal = {Annales de l{\textquoteright}Institut Henri Poincar\'e D}, pages = {211--249}, volume = {5}, number = {2}, year = {2018}, doi = {10.4171/aihpd/53}, mrnumber = {3813215}, zbl = {1390.05213}, language = {en}, url = {http://archive.numdam.org/articles/10.4171/aihpd/53/} }
TY - JOUR AU - Coja-Oghlan, Amin AU - Perkins, Will TI - Belief propagation on replica symmetric random factor graph models JO - Annales de l’Institut Henri Poincaré D PY - 2018 SP - 211 EP - 249 VL - 5 IS - 2 UR - http://archive.numdam.org/articles/10.4171/aihpd/53/ DO - 10.4171/aihpd/53 LA - en ID - AIHPD_2018__5_2_211_0 ER -
%0 Journal Article %A Coja-Oghlan, Amin %A Perkins, Will %T Belief propagation on replica symmetric random factor graph models %J Annales de l’Institut Henri Poincaré D %D 2018 %P 211-249 %V 5 %N 2 %U http://archive.numdam.org/articles/10.4171/aihpd/53/ %R 10.4171/aihpd/53 %G en %F AIHPD_2018__5_2_211_0
Coja-Oghlan, Amin; Perkins, Will. Belief propagation on replica symmetric random factor graph models. Annales de l’Institut Henri Poincaré D, Tome 5 (2018) no. 2, pp. 211-249. doi : 10.4171/aihpd/53. http://archive.numdam.org/articles/10.4171/aihpd/53/
Cité par Sources :