TY - JOUR
T1 - Dynamical replica analysis of processes on finitely connected random graphs
T2 - I. Vertex covering
AU - Mozeika, A.
AU - Coolen, A. C C
PY - 2008/3/4
Y1 - 2008/3/4
N2 - We study the stochastic dynamics of Ising spin models with random bonds, interacting on finitely connected Poissonian 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 number of scalar order parameters, the agreement between theory and experiment in the present study is nearly perfect.
AB - We study the stochastic dynamics of Ising spin models with random bonds, interacting on finitely connected Poissonian 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 number of scalar order parameters, the agreement between theory and experiment in the present study is nearly perfect.
UR - http://www.scopus.com/inward/record.url?scp=41149116097&partnerID=8YFLogxK
U2 - 10.1088/1751-8113/41/11/115003
DO - 10.1088/1751-8113/41/11/115003
M3 - Article
AN - SCOPUS:41149116097
SN - 1751-8113
VL - 41
JO - Journal of Physics A: Mathematical and Theoretical
JF - Journal of Physics A: Mathematical and Theoretical
IS - 11
M1 - 115003
ER -