Dynamic message-passing equations for models with unidirectional dynamics

Abstract

Understanding and quantifying the dynamics of disordered out-of-equilibrium models is an important problem in many branches of science. Using the dynamic cavity method on time trajectories, we construct a general procedure for deriving the dynamic message-passing equations for a large class of models with unidirectional dynamics, which includes the zero-temperature random field Ising model, the susceptible-infected-recovered model, and rumor spreading models. We show that unidirectionality of the dynamics is the key ingredient that makes the problem solvable. These equations are applicable to single instances of the corresponding problems with arbitrary initial conditions, and are asymptotically exact for problems defined on locally tree-like graphs. When applied to real-world networks, they generically provide a good analytic approximation of the real dynamics.

Final version

References in corpus (19)

• Cooperative Game Theory Approaches for Network Partitioning
• The Bethe lattice spin glass revisited
• A message passing approach for general epidemic models
• Inferring the origin of an epidemic with a dynamic message-passing algorithm
• Edge-Based Compartmental Modeling for Infectious Disease Spread Part I: An Overview
• Zero-temperature Hysteresis in Random-field Ising Model on a Bethe Lattice
• Modelling diffusion of innovations in a social network
• Optimizing spread dynamics on graphs by message passing
• Parallel dynamics of disordered Ising spin systems on finitely connected random graphs
• Majority dynamics on trees and the dynamic cavity method
• Large deviations of cascade processes on graphs
• A message-passing approach for threshold models of behavior in networks
• The Cavity Approach to Parallel Dynamics of Ising Spins on a Graph
• Nonequilibrium phase transition in a model for the propagation of innovations among economic agents
• Parallel dynamics of disordered Ising spin systems on finitely connected directed random graphs with arbitrary degree distributions
• Dynamical replica analysis of disordered Ising spin systems on finitely connected random graphs
• Spreading dynamics on spatially constrained complex brain networks
• Dynamical replica analysis of processes on finitely connected random graphs II: Dynamics in the Griffiths phase of the diluted Ising ferromagnet
• A universal form of slow dynamics in zero-temperature random-field Ising model

Cited by in corpus (37)

• A message-passing approach for recurrent-state epidemic models on networks
• Optimal Deployment of Resources for Maximizing Impact in Spreading Processes
• Predicting the epidemic threshold of the susceptible-infected-recovered model
• Identifying an influential spreader from a single seed in complex networks via a message-passing approach
• Recovery rate affects the effective epidemic threshold with synchronous updating
• Epidemic mitigation by statistical inference from contact tracing data
• Impact of presymptomatic transmission on epidemic spreading in contact networks: A dynamic message-passing analysis
• Message-Passing Methods for Complex Contagions
• Causal analysis, Correlation-Response and Dynamic cavity
• Reconstructing parameters of spreading models from partial observations
• Competition, Collaboration, and Optimization in Multiple Interacting Spreading Processes
• A simple analytical description of the non-stationary dynamics in Ising spin systems
• Heterogeneous message passing for heterogeneous networks
• On the number of limit cycles in diluted neural networks
• A matrix product algorithm for stochastic dynamics on networks, applied to non-equilibrium Glauber dynamics
• Scalable Influence Estimation Without Sampling
• Cluster approximations for the TASEP: stationary state and dynamical transition
• Dynamical Phase Transitions in Graph Cellular Automata
• Backtracking Dynamical Cavity Method
• Contagion in an interacting economy
• The matrix product approximation for the dynamic cavity method
• Infection-induced Cascading Failures -- Impact and Mitigation
• Coordination problems on networks revisited: statics and dynamics
• Analysis of the susceptible-infected-susceptible epidemic dynamics in networks via the non-backtracking matrix
• Epidemic threshold and localization of the SIS model on directed complex networks
• Small-Coupling Dynamic Cavity: a Bayesian mean-field framework for epidemic inference
• Exact analytical solution of irreversible binary dynamics on networks
• Network infection source identification under the SIRI model
• Stochasticity of infectious outbreaks and consequences for optimal interventions
• Identifying the structure patterns to govern the performance of localization in regulating innovation diffusion
• Combinatorial approach to spreading processes on networks
• On the accuracy of message-passing approaches to percolation in complex networks
• Uncovering the non-equilibrium stationary properties in sparse Boolean networks
• Dynamic message-passing approach for kinetic spin models with reversible dynamics
• 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
• Overcoming the complexity barrier of the dynamic message-passing method in networks with fat-tailed degree distributions