A matrix product algorithm for stochastic dynamics on networks, applied to non-equilibrium Glauber dynamics

Abstract

We introduce and apply a novel efficient method for the precise simulation of stochastic dynamical processes on locally tree-like graphs. Networks with cycles are treated in the framework of the cavity method. Such models correspond, for example, to spin-glass systems, Boolean networks, neural networks, or other technological, biological, and social networks. Building upon ideas from quantum many-body theory, the new approach is based on a matrix product approximation of the so-called edge messages -- conditional probabilities of vertex variable trajectories. Computation costs and accuracy can be tuned by controlling the matrix dimensions of the matrix product edge messages (MPEM) in truncations. In contrast to Monte Carlo simulations, the algorithm has a better error scaling and works for both, single instances as well as the thermodynamic limit. We employ it to examine prototypical non-equilibrium Glauber dynamics in the kinetic Ising model. Because of the absence of cancellation effects, observables with small expectation values can be evaluated accurately, allowing for the study of decay processes and temporal correlations.

5 pages, 3 figures; minor improvements, published version

References in corpus (10)

• The density-matrix renormalization group in the age of matrix product states
• A message passing approach for general epidemic models
• Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
• Dynamic message-passing equations for models with unidirectional dynamics
• Dynamical TAP equations for non-equilibrium Ising spin glasses
• A message-passing approach for threshold models of behavior in networks
• Inference of kinetic Ising model on sparse graphs
• Variational perturbation and extended Plefka approaches to dynamics on random networks: the case of the kinetic Ising model
• A simple analytical description of the non-stationary dynamics in Ising spin systems
• Variational approximations for stochastic dynamics on graphs

Cited by in corpus (8)

• A theory of non-equilibrium local search on random satisfaction problems
• Dynamical Phase Transitions in Graph Cellular Automata
• Backtracking Dynamical Cavity Method
• Matrix Product Belief Propagation for reweighted stochastic dynamics over graphs
• The matrix product approximation for the dynamic cavity method
• A closure for the Master Equation starting from the Dynamic Cavity Method
• Scaling of contraction costs for entanglement renormalization algorithms including tensor Trotterization and variational Monte Carlo
• Nonequilibrium steady-state dynamics of Markov processes on graphs