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

DOI10.1088/1751-8113/41/11/115003zbMATH Open1142.82020arXiv0712.1139OpenAlexW3100410822MaRDI QIDQ5456532FDOQ5456532

A. C. C. Coolen, Alexander Mozeika

Publication date: 8 April 2008

Published in: Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/0712.1139

zbMATH Keywords

random graphdynamicsvertex coveringprocessreplica analysis

Mathematics Subject Classification ID

Dynamics of disordered systems (random Ising systems, etc.) in time-dependent statistical mechanics (82C44)

Cited In (7)

• The matrix product approximation for the dynamic cavity method
• Title not available (Why is that?)
• Heterogeneous mean-field analysis of the generalized Lotka-Volterra model on a network
• Improved mean-field dynamical equations are able to detect the two-step relaxation in glassy dynamics at low temperatures
• The cavity master equation: average and fixed point of the ferromagnetic model in random graphs
• Dynamical replica analysis of processes on finitely connected random graphs: II. Dynamics in the Griffiths phase of the diluted Ising ferromagnet
• Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs

   Recommendations

• Dynamical replica analysis of processes on finitely connected random graphs: II. Dynamics in the Griffiths phase of the diluted Ising ferromagnet 👍 👎
• Zero-temperature dynamics for the ferromagnetic Ising model on random graphs 👍 👎
• Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs 👍 👎
• Replica bounds for optimization problems and diluted spin systems 👍 👎
• Statistical mechanics of the vertex-cover problem 👍 👎

This page was built for publication: Dynamical replica analysis of processes on finitely connected random graphs: I. Vertex covering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5456532)