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

Abstract

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. © 2007 The American Physical Society.

Publication DOI: https://doi.org/10.1103/PhysRevE.76.011115
Divisions: College of Engineering & Physical Sciences > Systems analytics research institute (SARI)
Additional Information: © 2007 The American Physical Society.
Uncontrolled Keywords: Physics and Astronomy(all),Condensed Matter Physics,Statistical and Nonlinear Physics,Mathematical Physics
Publication ISSN: 1550-2376
Last Modified: 18 Mar 2024 08:10
Date Deposited: 29 Jul 2010 10:10
Full Text Link:
Related URLs: http://www.scop ... tnerID=8YFLogxK (Scopus URL)
http://pre.aps. ... /v76/i1/e011115 (Publisher URL)
PURE Output Type: Article
Published Date: 2007-07-20
Authors: Wong, K.Y. Michael
Saad, David (ORCID Profile 0000-0001-9821-2623)

Download

[img]

Version: Published Version


Export / Share Citation


Statistics

Additional statistics for this record