Inferring the origin of an epidemic with a dynamic message-passing algorithm

Abstract

We study the problem of estimating the origin of an epidemic outbreak -- given a contact network and a snapshot of epidemic spread at a certain time, determine the infection source. Finding the source is important in different contexts of computer or social networks. We assume that the epidemic spread follows the most commonly used susceptible-infected-recovered model. We introduce an inference algorithm based on dynamic message-passing equations, and we show that it leads to significant improvement of performance compared to existing approaches. Importantly, this algorithm remains efficient in the case where one knows the state of only a fraction of nodes.

9 pages, 8 figures. Revised version, new figures added

References in corpus (2)

• A message passing approach for general epidemic models
• Information Source Detection in the SIR Model: A Sample Path Based Approach

Cited by in corpus (72)

• Epidemic processes in complex networks
• Bayesian inference of epidemics on networks via Belief Propagation
• Locating the source of diffusion in complex networks by time-reversal backward spreading
• Identification of Patient Zero in Static and Temporal Networks - Robustness and Limitations
• Estimating network structure from unreliable measurements
• A message-passing approach for recurrent-state epidemic models on networks
• Optimal Deployment of Resources for Maximizing Impact in Spreading Processes
• Dynamic message-passing equations for models with unidirectional dynamics
• Identifying an influential spreader from a single seed in complex networks via a message-passing approach
• A message-passing approach to epidemic tracing and mitigation with apps
• Minimal contagious sets in random regular graphs
• Phase transition in the recoverability of network history
• Optimizing sensors placement in complex networks for localization of hidden signal source: A review
• Message-passing theory for cooperative epidemics
• Contact-based model for epidemic spreading on temporal networks
• Assessing node risk and vulnerability in epidemics on networks
• The zero-patient problem with noisy observations
• Epidemic mitigation by statistical inference from contact tracing data
• Network reconstruction from infection cascades
• Finding Patient Zero: Learning Contagion Source with Graph Neural Networks
• On the Universality of Jordan Centers for Estimating Infection Sources in Tree Networks
• Anonymity Properties of the Bitcoin P2P Network
• Contagion Source Detection in Epidemic and Infodemic Outbreaks: Mathematical Analysis and Network Algorithms
• A Bayesian generative neural network framework for epidemic inference problems
• Detecting the Influence of Spreading in Social Networks with Excitable Sensor Networks
• Impact of presymptomatic transmission on epidemic spreading in contact networks: A dynamic message-passing analysis
• On the Properties of Gromov Matrices and their Applications in Network Inference
• Simulating SIR processes on networks using weighted shortest paths
• Time evolution of predictability of epidemics on networks
• Dandelion: Redesigning the Bitcoin Network for Anonymity
• Competition, Collaboration, and Optimization in Multiple Interacting Spreading Processes
• Scalable Influence Estimation Without Sampling
• Heterogeneous message passing for heterogeneous networks
• Source Localization in Networks: Trees and Beyond
• Sensor-based localization of epidemic sources on human mobility networks
• Inferring propagation paths for sparsely observed perturbations on complex networks
• Contagion in an interacting economy
• Predicting Infectiousness for Proactive Contact Tracing
• The matrix product approximation for the dynamic cavity method
• Bayes-optimal inference for spreading processes on random networks
• Infection-induced Cascading Failures -- Impact and Mitigation
• Locating Contagion Sources in Networks with Partial Timestamps
• Multiple Infection Sources Identification with Provable Guarantees
• Coordination problems on networks revisited: statics and dynamics
• Small-Coupling Dynamic Cavity: a Bayesian mean-field framework for epidemic inference
• The big bang of an epidemic
• Epidemic threshold and localization of the SIS model on directed complex networks
• Locating the Source of Large-scale Diffusion of Foodborne Contamination
• Estimating Infection Sources in Networks Using Partial Timestamps
• Morphological Inversion of Complex Diffusion
• A Robust Information Source Estimator with Sparse Observations
• Network infection source identification under the SIRI model
• On the accuracy of message-passing approaches to percolation in complex networks
• Combinatorial approach to spreading processes on networks
• A closure for the Master Equation starting from the Dynamic Cavity Method
• Stochasticity of infectious outbreaks and consequences for optimal interventions
• Identifying the structure patterns to govern the performance of localization in regulating innovation diffusion
• Tensor product algorithms for inference of contact network from epidemiological data
• Locating the source of interacting signal in complex networks
• Network Topology Inference Using Information Cascades with Limited Statistical Knowledge
• Source location on multilayer networks
• A privacy-preserving tests optimization algorithm for epidemics containment
• Dynamics of epidemic models from cavity master equations
• Dynamic message-passing approach for kinetic spin models with reversible dynamics
• Contamination source inference in water distribution networks
• Uncovering the non-equilibrium stationary properties in sparse Boolean networks
• Back to the Source: an Online Approach for Sensor Placement and Source Localization
• Universality classes in the time evolution of epidemic outbreaks on complex networks
• Social Diffusion Sources Can Escape Detection
• Inference in Spreading Processes with Neural-Network Priors
• Overcoming the complexity barrier of the dynamic message-passing method in networks with fat-tailed degree distributions
• Reconstruction of Worm Propagation Path Using a Trace-back Approach