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.

21 pages, 10 figures, major changes: Sections IV to VII updated, Figs. 1 to 3 replaced

References in corpus (3)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Cavity approach for real variables on diluted graphs and application to synchronization in small-world lattices
• Equilibration through local information exchange in networks

Cited by in corpus (9)

• Networking - A Statistical Physics Perspective
• Minimizing Unsatisfaction in Colourful Neighbourhoods
• Optimal Resource Allocation in Random Networks with Transportation Bandwidths
• Optimal Location of Sources in Transportation Networks
• The network source location problem: ground state energy, entropy and effects of freezing
• Self-Organization of Balanced Nodes in Random Networks with Transportation Bandwidths
• Bilevel optimization in flow networks: A message-passing approach
• Belief propagation for supply networks: Efficient clustering of their factor graphs
• Bandwidth Allocation and Resource Adjustment for Stability Enhancement in Complex Networks