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

K.Y. Michael Wong, David Saad

    Research output: Contribution to journalArticlepeer-review


    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.

    Original languageEnglish
    Article number011115
    Pages (from-to)011115
    Number of pages1
    JournalPhysical Review E
    Issue number1
    Publication statusPublished - 20 Jul 2007

    Bibliographical note

    © 2007 The American Physical Society.


    Dive into the research topics of 'Inference and optimization of real edges on sparse graphs: A statistical physics perspective'. Together they form a unique fingerprint.

    Cite this