Large deviations of cascade processes on graphs
arXiv:1305.5745 · doi:10.1103/PhysRevE.87.062115
Abstract
Simple models of irreversible dynamical processes such as Bootstrap Percolation have been successfully applied to describe cascade processes in a large variety of different contexts. However, the problem of analyzing non-typical trajectories, which can be crucial for the understanding of the out-of-equilibrium phenomena, is still considered to be intractable in most cases. Here we introduce an efficient method to find and analyze optimized trajectories of cascade processes. We show that for a wide class of irreversible dynamical rules, this problem can be solved efficiently on large-scale systems.
References in corpus (25)
- The spread of epidemic disease on networks
- The large deviation approach to statistical mechanics
- The Bethe lattice spin glass revisited
- k-core organization of complex networks
- A message passing approach for general epidemic models
- High-accuracy approximation of binary-state dynamics on networks
- Jamming Percolation and Glass Transitions in Lattice Models
- Finding undetected protein associations in cell signaling by belief propagation
- Zero-temperature Hysteresis in Random-field Ising Model on a Bethe Lattice
- Facilitated spin models on Bethe lattice: bootstrap percolation, mode-coupling transition and glassy dynamics
- On the path integral representation for quantum spin models and its application to the quantum cavity method and to Monte Carlo simulations
- Cavity method for quantum spin glasses on the Bethe lattice
- Parallel dynamics of disordered Ising spin systems on finitely connected random graphs
- Majority dynamics on trees and the dynamic cavity method
- The Cavity Approach to Parallel Dynamics of Ising Spins on a Graph
- Dynamical replica analysis of disordered Ising spin systems on finitely connected random graphs
- Spreading dynamics on spatially constrained complex brain networks
- A message-passing scheme for non-equilibrium stationary states
- The stochastic matching problem
- Propagation on networks: an exact alternative perspective
- Inference and learning in sparse systems with multiple states
- A universal form of slow dynamics in zero-temperature random-field Ising model
- Stochastic optimization by message passing
- Dynamical replica analysis of processes on finitely connected random graphs I: vertex covering
- Dynamics of k-core percolation
Cited by in corpus (37)
- Vital nodes identification in complex networks
- Network dismantling
- Bayesian inference of epidemics on networks via Belief Propagation
- Containing epidemic outbreaks by message-passing techniques
- Optimal percolation on multiplex networks
- A message-passing approach for recurrent-state epidemic models on networks
- Optimizing spread dynamics on graphs by message passing
- Dynamic message-passing equations for models with unidirectional dynamics
- Efficient collective influence maximization in cascading processes with first-order transitions
- Fundamental difference between superblockers and superspreaders in networks
- Statistical Mechanics of the Minimum Dominating Set Problem
- Minimal contagious sets in random regular graphs
- The zero-patient problem with noisy observations
- Epidemic mitigation by statistical inference from contact tracing data
- Network reconstruction from infection cascades
- Large deviations of random walks on random graphs
- The large deviations of the whitening process in random constraint satisfaction problems
- On Minimal Sets to Destroy the -Core in Random Networks
- Competition, Collaboration, and Optimization in Multiple Interacting Spreading Processes
- A simple analytical description of the non-stationary dynamics in Ising spin systems
- Scalable Influence Estimation Without Sampling
- Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithm
- Dynamical Phase Transitions in Graph Cellular Automata
- Matrix Product Belief Propagation for reweighted stochastic dynamics over graphs
- Contagion in an interacting economy
- Predicting epidemic evolution on contact networks from partial observations
- Hierarchical cycle-tree packing model for -core attack problem
- Infection-induced Cascading Failures -- Impact and Mitigation
- A spin glass approach to the directed feedback vertex set problem
- The large connectivity limit of bootstrap percolation
- Coordination problems on networks revisited: statics and dynamics
- Small-Coupling Dynamic Cavity: a Bayesian mean-field framework for epidemic inference
- Large Deviations of the Finite-Time Magnetization of the Curie-Weiss Random Field Ising Model
- K-core attack, equilibrium K-core, and kinetically constrained spin system
- Nonequilibrium steady-state dynamics of Markov processes on graphs
- Dynamic message-passing approach for kinetic spin models with reversible dynamics
- A cavity approach to optimization and inverse dynamical problems