Large deviations of cascade processes on graphs

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 (8)

• The large deviation approach to statistical mechanics
• A message passing approach for general epidemic models
• Finding undetected protein associations in cell signaling by belief propagation
• 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
• Spreading dynamics on spatially constrained complex brain networks
• Dynamical replica analysis of processes on finitely connected random graphs I: vertex covering
• Dynamics of k-core percolation

Cited by in corpus (36)

• 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
• 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 $k$-Core in Random Networks
• A simple analytical description of the non-stationary dynamics in Ising spin systems
• Competition, Collaboration, and Optimization in Multiple Interacting Spreading Processes
• 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 $K$-core attack problem
• Infection-induced Cascading Failures -- Impact and Mitigation
• The large connectivity limit of bootstrap percolation
• A spin glass approach to the directed feedback vertex set problem
• Coordination problems on networks revisited: statics and dynamics
• Large Deviations of the Finite-Time Magnetization of the Curie-Weiss Random Field Ising Model
• Small-Coupling Dynamic Cavity: a Bayesian mean-field framework for epidemic inference
• 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