Containing epidemic outbreaks by message-passing techniques

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

• Cooperative Game Theory Approaches for Network Partitioning
• 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
• Efficient local strategies for vaccination and network attack
• 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
• 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

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