Containing epidemic outbreaks by message-passing techniques
arXiv:1309.2805 · doi:10.1103/PhysRevX.4.021024
Abstract
The problem of targeted network immunization can be defined as the one of finding a subset of nodes in a network to immunize or vaccinate in order to minimize a tradeoff between the cost of vaccination and the final (stationary) expected infection under a given epidemic model. Although computing the expected infection is a hard computational problem, simple and efficient mean-field approximations have been put forward in the literature in recent years. The optimization problem can be recast into a constrained one in which the constraints enforce local mean-field equations describing the average stationary state of the epidemic process. For a wide class of epidemic models, including the susceptible-infected-removed and the susceptible-infected-susceptible models, we define a message-passing approach to network immunization that allows us to study the statistical properties of epidemic outbreaks in the presence of immunized nodes as well as to find (nearly) optimal immunization sets for a given choice of parameters and costs. The algorithm scales linearly with the size of the graph and it can be made efficient even on large networks. We compare its performance with topologically based heuristics, greedy methods, and simulated annealing.
References in corpus (25)
- Epidemic spreading in scale-free networks
- Cooperative Game Theory Approaches for Network Partitioning
- The spread of epidemic disease on networks
- Resilience of the Internet to random breakdowns
- Attack vulnerability of complex networks
- Epidemic dynamics and endemic states in complex networks
- Immunization of complex networks
- Efficient Immunization Strategies for Computer Networks and Populations
- What's in a crowd? Analysis of face-to-face behavioral networks
- Thresholds for epidemic spreading in networks
- A message passing approach for general epidemic models
- Localization and Spreading of Diseases in Complex Networks
- Efficient local strategies for vaccination and network attack
- Suppressing Epidemics with a Limited Amount of Immunization Units
- Finding undetected protein associations in cell signaling by belief propagation
- Identifying influential spreaders and efficiently estimating infection numbers in epidemic models: a walk counting approach
- Immunization of networks with community structure
- Optimizing spread dynamics on graphs by message passing
- Elusive Glassy Phase in the Random Field Ising Model
- Annealed and Mean-Field formulations of Disease Dynamics on Static and Adaptive Networks
- Large deviations of cascade processes on graphs
- Statistical Mechanics of Steiner trees
- The stochastic matching problem
- Stochastic optimization by message passing
- Inhomogeneous percolation models for spreading phenomena in random graphs
Cited by in corpus (39)
- Influence maximization in complex networks through optimal percolation
- Unification of theoretical approaches for epidemic spreading on complex networks
- Network dismantling
- Identifying optimal targets of network attack by belief propagation
- A message-passing approach for recurrent-state epidemic models on networks
- Optimal Deployment of Resources for Maximizing Impact in Spreading Processes
- Epidemic spreading and bond percolation in multilayer networks
- Rare events and discontinuous percolation transitions
- Model of Brain Activation Predicts the Neural Collective Influence Map of the Brain
- Fluctuations in percolation of sparse complex networks
- A message-passing approach to epidemic tracing and mitigation with apps
- Minimal contagious sets in random regular graphs
- Optimal Allocation of Resources for Suppressing Epidemic Spreading on Networks
- Contact-based model for epidemic spreading on temporal networks
- Underestimated cost of targeted attacks on complex networks
- Epidemic mitigation by statistical inference from contact tracing data
- Network reconstruction from infection cascades
- A centrality measure for quantifying spread on weighted, directed networks
- A Bayesian generative neural network framework for epidemic inference problems
- Impact of presymptomatic transmission on epidemic spreading in contact networks: A dynamic message-passing analysis
- A Max-Sum algorithm for training discrete neural networks
- Prediction and mitigation of nonlocal cascading failures using graph neural networks
- Competition, Collaboration, and Optimization in Multiple Interacting Spreading Processes
- Reactive immunization on complex networks
- Scalable Influence Estimation Without Sampling
- Heterogeneous message passing for heterogeneous networks
- Heterogeneous Population Dynamics and Scaling Laws near Epidemic Outbreaks
- Rank the spreading influence of nodes using dynamic Markov process
- Dismantling Efficiency and Network Fractality
- Contagion in an interacting economy
- Predicting epidemic evolution on contact networks from partial observations
- Spin-glass model for the C-dismantling problem
- Coordination problems on networks revisited: statics and dynamics
- Epidemic threshold and localization of the SIS model on directed complex networks
- Phase Transition in the Maximal Influence Problem: When Do We Need Optimization?
- On the Effectiveness of Tracking and Testing in SEIR Models
- On the accuracy of message-passing approaches to percolation in complex networks
- Dismantle a network efficiently during the entire process by a compound algorithm
- Efficient message passing for cascade size distributions on finite trees