Dynamical replica analysis of processes on finitely connected random graphs I: vertex covering

Abstract

We study the stochastic dynamics of Ising spin models with random bonds, interacting on finitely connected Poissonnian random graphs. We use the dynamical replica method to derive closed dynamical equations for the joint spin-field probability distribution, and solve these within the replica symmetry ansatz. Although the theory is developed in a general setting, with a view to future applications in various other fields, in this paper we apply it mainly to the dynamics of the Glauber algorithm (extended with cooling schedules) when running on the so-called vertex cover optimization problem. Our theoretical predictions are tested against both Monte Carlo simulations and known results from equilibrium studies. In contrast to previous dynamical analyses based on deriving closed equations for only a small numbers of scalar order parameters, the agreement between theory and experiment in the present study is nearly perfect.

26 pages LaTeX, 5 figures

References in corpus (23)

• The Bethe lattice spin glass revisited
• Phase Transitions in the Coloring of Random Graphs
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• Coloring random graphs
• The Entropy of the K-Satisfiability Problem
• Optimisation problems and replica symmetry breaking in finite connectivity spin-glasses
• Core percolation in random graphs: a critical phenomena analysis
• Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
• Parallel dynamics of disordered Ising spin systems on finitely connected random graphs
• Vertex cover problem studied by cavity method: Analytics and population dynamics
• Message passing for vertex covers
• Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs
• Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem
• Finitely connected vector spin systems with random matrix interactions
• On the stochastic dynamics of disordered spin models
• Approximation schemes for the dynamics of diluted spin models: the Ising ferromagnet on a Bethe lattice
• Order Parameter Flow in the SK Spin-Glass I: Replica Symmetry
• Order-Parameter Flow in the SK Spin-Glass II: Inclusion of Microscopic Memory Effects
• Dynamical replica analysis of disordered Ising spin systems on finitely connected random graphs
• Finitely coordinated models for low-temperature phases of amorphous systems
• Dynamics of dilute disordered models: a solvable case
• Dynamics of heuristic optimization algorithms on random graphs
• Statics and dynamics of the Lebwohl-Lasher model in the Bethe approximation

Cited by in corpus (14)

• Large deviations of cascade processes on graphs
• The Cavity Approach to Parallel Dynamics of Ising Spins on a Graph
• Maximum-entropy moment-closure for stochastic systems on networks
• Parallel dynamics of disordered Ising spin systems on finitely connected directed random graphs with arbitrary degree distributions
• A message-passing scheme for non-equilibrium stationary states
• A Cavity Master Equation for the continuous time dynamics of discrete spins models
• Dynamical replica analysis of processes on finitely connected random graphs II: Dynamics in the Griffiths phase of the diluted Ising ferromagnet
• Spin models on random graphs with controlled topologies beyond degree constraints
• Exploring the diluted ferromagnetic p-spin model with a Cavity Master Equation
• The matrix product approximation for the dynamic cavity method
• Perturbative large deviation analysis of non-equilibrium dynamics
• Nonequilibrium dynamics of the Ising model on heterogeneous networks with an arbitrary distribution of threshold noise
• Improved mean-field dynamical equations are able to detect the two-steps relaxation in glassy dynamics at low temperatures
• From random point processes to hierarchical Cavity Master Equations for the stochastic dynamics of disordered systems in Random Graphs: Ising models and epidemics