The scope of these lecture notes is to provide an introduction to modern statistical physics mean-field methods for the study of phase transitions and optimization problems over random structures. We first give a brief introduction to the field using as tutorial example the percolation problem in random graphs. Next we describe the so called cavity method and the related message-passing algorithms (Belief Propagation and variants) which can be used to analyze and solve optimization problems over random structures.
Statistical physics and network optimization problems
BALDASSI, CARLO;ZECCHINA, RICCARDO
2015
Abstract
The scope of these lecture notes is to provide an introduction to modern statistical physics mean-field methods for the study of phase transitions and optimization problems over random structures. We first give a brief introduction to the field using as tutorial example the percolation problem in random graphs. Next we describe the so called cavity method and the related message-passing algorithms (Belief Propagation and variants) which can be used to analyze and solve optimization problems over random structures.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
