An empirical analysis of loopy belief propagation in three topologies: Grids, small-world networks and random graphs

Download: PDF.

“An empirical analysis of loopy belief propagation in three topologies: Grids, small-world networks and random graphs” by R. Santana, A. Mendiburu, and J. A. Lozano. In Proceedings of the Fourth European Workshop on Probabilistic Graphical Models (PGM-2008), (Manfred Jaeger and Thomas D. Nielsen, eds.), 2008, pp. 249-256.

Abstract

Recently, much research has been devoted to the study of loopy belief propagation algorithm. However, little attention has been paid to the change of its behavior in relation with the problem graph topology. In this paper we empirically study the behavior of loopy belief propagation on different network topologies which include grids, small-world networks and random graphs. In our experiments, several descriptors of the algorithm are collected in order to analyze its behavior. We show that the performance of the algorithm is highly sensitive to changes in the topologies. Furthermore, evidence is given showing that the addition of shortcuts to grids can determine important changes in the dynamics of the algorithm.

Download: PDF.

BibTeX entry:

@inproceedings{Santana_et_al:2008g,
   author = {R. Santana and A. Mendiburu and J. A. Lozano},
   editor = {Manfred Jaeger and Thomas D. Nielsen},
   title = {An empirical analysis of loopy belief propagation in three
	topologies: {G}rids, small-world networks and random graphs},
   booktitle = {Proceedings of the Fourth European Workshop on
	Probabilistic Graphical Models (PGM-2008)},
   pages = {249--256},
   year = {2008}
}

(This webpage was created with bibtex2web.)

Back to Roberto Santana publications.