Source-linked AI summary
Inferring the origin of an epidemic with a dynamic message-passing algorithm
Andrey Y. Lokhov, Marc Mézard, Hiroki Ohta, Lenka Zdeborová
TL;DR
The paper asks how to identify patient zero from a contact network and an epidemic snapshot, despite stochastic spread and ambiguous origins. It develops an approximate Bayesian inference algorithm using dynamic message passing to estimate observation probabilities for candidate sources. The method generally improves on existing approaches and remains effective when only part of the network is observed.
Problem
Identifying patient zero from a contact network and epidemic snapshot is difficult because stochastic propagation allows different origins to yield the same observed configuration.
Method
The algorithm uses dynamic message passing to estimate node-state probabilities for each candidate source, then applies a mean-field-like approximation to rank origins by observation probability.
Results
The algorithm generally improves source estimation over existing approaches and outperforms both Jordan and distance centralities on tested network types, including incomplete snapshots.
Takeaways & Limitations
The approach uses information about nodes where the epidemic did not spread and remains robust when only a fraction of node states is observed.
Takeaways & Limitations
Performance can be suboptimal because message passing may err on loopy graphs and the joint observation likelihood uses a mean-field-like approximation.
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
The paper frames epidemic-source estimation as identifying patient zero from a contact network and an observed snapshot, a difficult task because stochastic spread makes origins ambiguous. It introduces dynamic message passing for efficient SIR-source inference and reports improved performance, including with partial observations.
- Motivation: Estimating patient zero from a contact network and epidemic snapshot is important for mitigating or preventing future outbreaks.The problem applies to infectious diseases, computer viruses, and rumors in social media.
- Problem: Stochastic infection propagation makes source estimation intrinsically hard because different initial conditions can produce the same observed configuration.Finding the most probable origin is generally computationally intractable except on special networks such as lines or regular trees.
- Approach: The paper introduces an SIR-source algorithm that uses dynamic message passing to estimate node-state probabilities for every possible epidemic origin.A mean-field-like approximation is then used to estimate the observation probability and rank candidate origins.
- Approach: DMP generalizes belief propagation to dynamic problems and exploits irreversible SIR trajectories, which can be parametrized by a few flipping times.Unlike BP, DMP iteration time directly corresponds to real epidemic time and it is exact on tree contact networks.
- Evaluation: Tests on synthetic spreading data show better performance than existing approaches except in a special parameter region where the Jordan center is better.The method remains efficient when only a fraction of node states is observed and identifies parameter regions where source estimation is easy or hard.
A. Spreading model
The paper adopts the susceptible-infected-recovered model on a contact graph, with node-specific transmission and recovery probabilities treated as known. SIR captures irreversible recovery and depletion of susceptible agents, unlike SIS dynamics.
- Model definition: SIR infection cannot persist indefinitely because susceptible agents are depleted.The model typically focuses on the fraction of the population touched by the epidemic.
- Assumptions: Common SIR-network studies often assume uniform infection and recovery probabilities and mass-action mixing, which ignores the physical contact topology.These assumptions support simple mean-field equations for qualitative epidemic mechanisms and thresholds.
- Model definition: The SIR model represents epidemic spreading on a connected undirected graph whose nodes are susceptible, infected, or recovered.Recovered nodes do not change state.
- Assumptions: The model assumes known graph structure and transmission parameters λij and recovery parameters µi.The paper states that these quantities are known or have already been inferred.
B. Dynamic message-passing equations
The DMP equations track cavity probabilities for SIR infection signals and node states over time. They are exact on trees and provide an efficient approximation for sparse loopy networks.
- Properties: DMP gives exact marginal probabilities on tree graphs for every initial condition and realization of transmission and recovery probabilities.For a given vertex, its algorithmic complexity is O(tNc), where c is the graph’s average degree.
- Cavity construction: DMP models epidemic spreading as infection signals transmitted along network edges and uses cavity dynamics to separate graph branches on trees.An auxiliary dynamics fixes one node susceptible, preventing infection from propagating through it and making branches independent.
- Message definitions: The message θk→i(t) is the probability that node k has not transmitted an infection signal to node i by time t.The related message φk→i(t) tracks non-transmission together with node k being infected at time t.
- Message updates: The cavity updates account for transmission, recovery, and newly acquired infection, with a compensation term preventing double-counting simultaneous transmission and recovery.The equations are iterated from initial cavity-message conditions.
- Node marginals: The marginal probabilities for susceptible, infected, and recovered states are obtained by including all neighbors in the message-passing expression.These marginals sum to one and provide the node-state probabilities used by the algorithm.
- Relation to prior work: The paper derives a graph-specific, initial-condition-specific iterative DMP form for constant transmission and recovery rates, extending earlier averaged formulations.The earlier general non-exponential model lacked an easily tractable Markovian DMP form.
III. INFERENCE OF EPIDEMIC ORIGIN AND DMP ALGORITHM
The inference problem estimates patient zero from observed epidemic states after t0 time steps, using dynamic message passing to rank possible origins. The method combines state probabilities with an energy-based likelihood approximation and can estimate unknown observation time.
- Problem: The task is to locate patient zero from the observed states of a node set O after t0 time steps, with t0 potentially unknown.The observation set may be a subset of the network, rather than all nodes.
- Benchmarks: Distance, rumor, and Jordan centrality measures serve as benchmark methods, including a distance measure defined on the component containing infected and recovered nodes.The described benchmark setup includes a recovery-dependent factor in the distance centrality measure, while prior implementations differed in their use of observed states.
- DMP algorithm: For each candidate origin, DMP estimates the probabilities that every node is susceptible, infected, or recovered.These marginal state probabilities are computed for a specified patient zero and time.
- DMP algorithm: The algorithm assigns each candidate an energy E(i) = −log P(O|i), so lower-energy nodes are more likely epidemic sources.The observation likelihood is approximated as a product of DMP-provided marginal probabilities because the exact joint probability is intractable.
- DMP algorithm: Unknown observation time is estimated by evaluating E(i,t) across possible times and choosing the time that maximizes the partition function Z(t).This extends the inference procedure beyond the case where t0 is known.
- DMP algorithm: The computational complexity for computing one vertex’s energy is O(t0Nc), where c is the graph’s average degree.The energy determines the corresponding probability that the vertex is the epidemic origin.
IV. PERFORMANCE OF INFERENCE ALGORITHMS
Across random regular, Erdős–Rényi, scale-free, incomplete-snapshot, and real-network tests, DMP generally outperforms centrality-based estimators. The method remains effective when observations are incomplete and on a nonrandom power-grid network, while approximate Bayesian inference introduces potential sub-optimality on real networks.
- Experimental setup: The experiments use uniform transmission and recovery probabilities on random regular graphs before extending evaluation to other network families.Random regular graphs are drawn uniformly from graphs in which every node has degree c.
- Random-network evaluations: DMP inference considerably outperforms distance, rumor, and Jordan centralities at comparable computational cost.Performance is evaluated using the normalized rank of the true epidemic origin among observed infected or recovered nodes.
- Random-network evaluations: DMP considerably outperforms Jordan and distance centralities on Erdős–Rényi and scale-free networks.The Erdős–Rényi and scale-free evaluations use networks of size approximately 1000; averages use 1000 and 3000 instances, respectively.
- Incomplete snapshots: With incomplete snapshots, DMP outperforms both generalized centralities, including cases where Jordan centrality performs better for complete snapshots.Here, a fraction ξ of nodes is unobserved.
- Nonrandom network: On the U.S. West-Coast power-grid network, DMP gives better prediction than the alternatives across the full infection-rate range.The network contains N = 4941 nodes, mean degree ⟨c⟩ = 2.67, maximum degree 19, and clustering coefficient C = 0.08.
- Methodological caveat: Approximate Bayesian inference can be sub-optimal because message-passing errors arise on loopy graphs and the joint-probability approximation may be imperfect.Including two-point correlations did not improve the reported results, motivating searches for better likelihood approximations on general graphs.
V. CONCLUSION
The DMP-based probabilistic algorithm improves epidemic-source estimation over existing approaches in most tested settings, including incomplete snapshots, and supports several extensions.
- The DMP algorithm generally improves source estimates over existing algorithms, except in a narrow parameter region where the Jordan center performs better.It also uses information about nodes where the epidemic did not spread.
- With incomplete snapshots, DMP inference remains effective when only a fraction of node states is observed and outperforms both generalized centralities.Figure 6 evaluates random contact networks with N = 1000, degree c = 4, t0 = 10, and λ = 0.5 or λ = 0.7.
- DMP inference outperforms distance and Jordan centralities on the U.S. West-Coast power-grid network across the tested transmission probabilities.The experiment uses recovery probability µ = 0.5, observes all nodes, and evaluates the normalized rank of the true origin.
- The approach can be generalized to time-evolving contact networks by encoding network dynamics in time-dependent transmission probabilities λij(t).The paper also discusses extensions to multiple infection sources and incomplete network knowledge.
Appendix A: The centrality algorithms for incomplete snapshots
For incomplete snapshots, the centrality baselines incorporate observed infected, recovered, and unknown nodes into a connected component, while the experiments compare their source-ranking performance with DMP.
- Incomplete snapshots: When a fraction ξ of nodes is unobserved, the snapshot contains observed S, I, and R states plus randomly located unknown X nodes.The observed fraction is 1 −ξ, and the unknown fraction is ξ.
- Incomplete snapshots: The generalized centrality algorithms construct a connected component from I and R nodes plus X clusters not completely surrounded by S nodes.Distance and Jordan centralities are then applied to this component.
- Performance comparison: 60% of cases place the true source within the top 10% of relevant nodes when ξ = 0.The relevant nodes are those situated in the constructed graph G.