Belief propagation on replica symmetric random factor graph models
Annales de l’Institut Henri Poincaré D, Tome 5 (2018) no. 2, pp. 211-249.

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
Classification : 05-XX, 82-XX
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://www.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://www.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://www.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://www.numdam.org/articles/10.4171/aihpd/53/

Cité par Sources :