Please use this identifier to cite or link to this item:

Inference and optimization of real edges on sparse graphs: A statistical physics perspective

Authors Wong, Michael K.Y. View this author's profile
Saad, David
Issue Date 2007
Source Physical Review E , v. 76, (1), 2007, July, article number 011115
Summary Inference and optimization of real-value edge variables in sparse graphs are studied using the Bethe approximation and replica method of statistical physics. Equilibrium states of general energy functions involving a large set of real edge variables that interact at the network nodes are obtained in various cases. When applied to the representative problem of network resource allocation, efficient distributed algorithms are also devised. Scaling properties with respect to the network connectivity and the resource availability are found, and links to probabilistic Bayesian approximation methods are established. Different cost measures are considered and algorithmic solutions in the various cases are devised and examined numerically. Simulation results are in full agreement with the theory.
ISSN 1539-3755
Rights © 2007 American Physical Society
Language English
Format Article
Access View full-text via DOI
View full-text via Web of Science
View full-text via Scopus
Files in this item:
File Description Size Format
PhysRevE.76.011115.pdf Published version 484422 B Adobe PDF