The Cavity Approach to Parallel Dynamics of Ising Spins on a Graph

Abstract

We use the cavity method to study parallel dynamics of disordered Ising models on a graph. In particular, we derive a set of recursive equations in single site probabilities of paths propagating along the edges of the graph. These equations are analogous to the cavity equations for equilibrium models and are exact on a tree. On graphs with exclusively directed edges we find an exact expression for the stationary distribution of the spins. We present the phase diagrams for an Ising model on an asymmetric Bethe lattice and for a neural network with Hebbian interactions on an asymmetric scale-free graph. For graphs with a nonzero fraction of symmetric edges the equations can be solved for a finite number of time steps. Theoretical predictions are confirmed by simulation results. Using a heuristic method, the cavity equations are extended to a set of equations that determine the marginals of the stationary distribution of Ising models on graphs with a nonzero fraction of symmetric edges. The results of this method are discussed and compared with simulations.

References in corpus (16)

• Scale-free brain functional networks
• The Bethe lattice spin glass revisited
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Percolation in Directed Scale-Free Networks
• Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
• Self-organized Networks of Competing Boolean Agents
• Parallel dynamics of disordered Ising spin systems on finitely connected random graphs
• Finite-connectivity systems as error-correcting codes
• Statistical Mechanics of Steiner trees
• Dynamical TAP approach to mean field glassy systems
• Analytic solution of attractor neural networks on scale-free graphs
• The Little-Hopfield model on a Random Graph
• Dynamical replica analysis of disordered Ising spin systems on finitely connected random graphs
• Computational core and fixed-point organisation in Boolean networks
• Dynamical replica analysis of processes on finitely connected random graphs I: vertex covering
• Dynamics of an Ising Spin Glass on the Bethe Lattice

Cited by in corpus (42)

• Inferring the origin of an epidemic with a dynamic message-passing algorithm
• Dynamic message-passing equations for models with unidirectional dynamics
• Spectral Theory of Sparse Non-Hermitian Random Matrices
• Large deviations of cascade processes on graphs
• Majority dynamics on trees and the dynamic cavity method
• Eigenvalue Outliers of non-Hermitian Random Matrices with a Local Tree Structure
• Dynamic mean-field and cavity methods for diluted Ising systems
• A message-passing scheme for non-equilibrium stationary states
• Inference of kinetic Ising model on sparse graphs
• Noisy Random Boolean Formulae - a Statistical Physics Perspective
• A Cavity Master Equation for the continuous time dynamics of discrete spins models
• Quasi-equilibrium in glassy dynamics: an algebraic view
• Belief-Propagation and replicas for inference and learning in a kinetic Ising model with hidden spins
• Dynamical Mean-Field Theory of Complex Systems on Sparse Directed Networks
• Variational approximations for stationary states of Ising-like models
• Causal analysis, Correlation-Response and Dynamic cavity
• Generalized mean field approximation for parallel dynamics of the Ising model
• Dynamics of asymmetric kinetic Ising systems revisited
• A simple analytical description of the non-stationary dynamics in Ising spin systems
• A matrix product algorithm for stochastic dynamics on networks, applied to non-equilibrium Glauber dynamics
• Dynamical Phase Transitions in Graph Cellular Automata
• Cluster approximations for the TASEP: stationary state and dynamical transition
• Backtracking Dynamical Cavity Method
• Matrix Product Belief Propagation for reweighted stochastic dynamics over graphs
• Quenches in the Sherrington-Kirkpatrick model
• Variational approximations for stochastic dynamics on graphs
• The matrix product approximation for the dynamic cavity method
• Nonequilibrium dynamics of the Ising model on heterogeneous networks with an arbitrary distribution of threshold noise
• Dynamics of sparse Boolean networks with multi-node and self-interactions
• Transfer operator analysis of the parallel dynamics of disordered Ising chains
• Small-Coupling Dynamic Cavity: a Bayesian mean-field framework for epidemic inference
• Multi-step relaxations in Glauber dynamics of a bond-diluted Ising model on a Bethe lattice
• Phase transitions and memory effects in the dynamics of Boolean networks
• A closure for the Master Equation starting from the Dynamic Cavity Method
• Connected components in networks with higher-order interactions
• Heat-Bath and Metropolis Dynamics in Ising-like Models on Directed Regular Random Graphs
• Overcoming the complexity barrier of the dynamic message-passing method in networks with fat-tailed degree distributions
• Dynamical Cavity Method for Hypergraphs and its Application to Quenches in the k-XOR-SAT Problem
• Minority Takeover in Majority Dynamics: Searching for Rare Initializations via the History Passing Algorithm
• Uncovering the non-equilibrium stationary properties in sparse Boolean networks
• Mean-field theory of vector spin models on networks with arbitrary degree distributions
• Nonequilibrium steady-state dynamics of Markov processes on graphs