Inferring the origin of an epidemy with dynamic message-passing algorithm

Andrey Y. Lokhov, Marc Mézard, Hiroki Ohta, Lenka ZdeborováarXiv 2013 · arXiv

Introduction

Identifying the source of an epidemic—the "Patient Zero"—is a critical task in public health, cybersecurity, and social science. Whether tracking a biological virus, a computer worm, or the spread of misinformation, knowing where an outbreak began allows for targeted interventions and a better understanding of transmission dynamics. However, this task is complicated by the stochastic nature of spreading processes and the fact that observers often only have access to a partial "snapshot" of the network's state at a single point in time.

A snapshot of an epidemic on a network. Nodes are labeled as Susceptible (S), Infected (I), or Recovered (R). The algorithm aims to identify the most likely source node (P).

The Dynamic Message-Passing Approach

Traditional methods for source identification often rely on graph centrality measures, such as Jordan centrality, which identify the "geometric center" of the infected cluster. These heuristics frequently fail because they ignore the temporal dynamics of the infection and the valuable information provided by nodes that remain uninfected.

To address these limitations, researchers have developed a Dynamic Message-Passing (DMP) algorithm. This approach leverages the physics of the Susceptible-Infected-Recovered (SIR) model. Unlike standard Belief Propagation, which seeks a steady state, DMP equations track the actual time-steps of the epidemic. By calculating the marginal probability of each node being in a specific state at any given time, the algorithm can use Bayesian inference to rank every node in the network by the likelihood that it was the original source.

Experimental Results

The DMP algorithm was evaluated across various network topologies, including Random Regular, Erdős-Rényi, and Scale-Free graphs, as well as real-world data from the U.S. West-Coast Power Grid.

Comparison of source identification accuracy. The bar chart shows the frequency of the true source appearing at a specific rank. DMP (dark red) correctly identifies the source (rank 0) in nearly 90% of cases, vastly outperforming centrality-based methods.

A key finding is the algorithm's robustness to incomplete data. Even when the health status of a large majority of the population is unknown, DMP effectively utilizes "negative information"—the presence of susceptible nodes—to narrow down the source's location. Furthermore, the algorithm can accurately estimate the time elapsed since the start of the outbreak by maximizing a partition function.

Discussion and Limitations

While DMP shows superior performance, it does encounter a "hard" regime. When the infection rate $\lambda$ is extremely high, the epidemic spreads so rapidly that the network effectively "forgets" its origin, making inference difficult for any method. Additionally, while highly effective on sparse networks, the algorithm's accuracy may decrease in "cliquey" networks where the assumption of uncorrelated marginals is less valid.

Conclusion

The Dynamic Message-Passing algorithm represents a significant advancement in epidemic source inference. By incorporating the underlying dynamics of the SIR model and utilizing the full information available in a snapshot, it provides a more accurate and robust solution than traditional graph-theoretic heuristics. Future work will explore extending this framework to handle multiple sources and dynamic network structures.

Summary updated

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.
BibTeX
@misc{lokhov2013inferring,
  author = {Andrey Y. Lokhov and Marc Mézard and Hiroki Ohta and Lenka Zdeborová},
  title = {{Inferring the origin of an epidemy with dynamic message-passing algorithm}},
  year = {2013},
  eprint = {1303.5315},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1303.5315},
}
Figure