The network source location problem: ground state energy, entropy and effects of freezing
arXiv:1209.4134 · doi:10.1007/s10955-014-1002-2
Abstract
Ground state entropy of the network source location problem is evaluated at both the replica symmetric level and one-step replica symmetry breaking level using the entropic cavity method. The regime that is a focus of this study, is closely related to the vertex cover problem with randomly quenched covered nodes. The resulting entropic message passing inspired decimation and reinforcement algorithms are used to identify the optimal location of sources in single instances of transportation networks. The conventional belief propagation without taking the entropic effect into account is also compared. We find that in the glassy phase the entropic message passing inspired decimation yields a lower ground state energy compared to the belief propagation without taking the entropic effect. Using the extremal optimization algorithm, we study the ground state energy and the fraction of frozen hubs, and extend the algorithm to collect statistics of the entropy. The theoretical results are compared with the extremal optimization results.
arXiv comment26 pages, 11 figures, Journal of Statistical Physics (in press)
References in corpus (34)
- The Bethe lattice spin glass revisited
- The structural glass transition and the entropy of the metastable states
- Optimization with Extremal Dynamics
- Phase Transitions in the Coloring of Random Graphs
- Lattice Glass Models
- Glass models on Bethe lattices
- Extremal Optimization for Graph Partitioning
- Clusters of solutions and replica symmetry breaking in random k-satisfiability
- Structure, Scaling and Phase Transition in the Optimal Transport Network
- Instability of one-step replica-symmetry-broken phase in satisfiability problems
- Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation
- Landscape of solutions in constraint satisfaction problems
- Extremal Optimization at the Phase Transition of the 3-Coloring Problem
- Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
- Survey-propagation decimation through distributed local computations
- Message passing for vertex covers
- Constraint satisfaction problems with isolated solutions are hard
- Numerical Results for Ground States of Mean-Field Spin Glasses at low Connectivities
- Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem
- The Competition for Shortest Paths on Sparse Graphs
- Numerical Results for Ground States of Spin Glasses on Bethe Lattices
- Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
- Equilibration through local information exchange in networks
- Inference and Optimization of Real Edges on Sparse Graphs - A Statistical Physics Perspective
- Local field distributions in spin glasses
- Long range frustration in finite connectivity spin glasses: A mean field theory and its application to the random -satisfiability problem
- Ground-State Entropy of the Random Vertex-Cover Problem
- mean-field population dynamics approach for the random 3-satisfiability problem
- Determining the Solution Space of Vertex-Cover by Interactions and Backbones
- Statistical mechanics of budget-constrained auctions
- Cavity approach to the Sourlas code system
- Colouring random graphs and maximising local diversity
- Next nearest neighbour Ising models on random graphs
- Optimal Location of Sources in Transportation Networks