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.
2015
9783319169668
9783319169675
Fagnani, Fabio; Fosson Sophie M.; Ravazzi Chiara
Mathematical foundations of complex networked information systems
Baldassi, Carlo; Braunstein, Alfredo; Ramezanpour, Abolfazl; Zecchina, Riccardo
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11565/3996622
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 4
social impact