Source Detection via Contact Tracing in the Presence of Asymptomatic Patients

Gergely Ódor, Jana Vuckovic, Miguel-Angel Sanchez Ndoye, Patrick ThiranarXiv 2021 · arXiv

Identifying the source of an epidemic, or "Patient Zero," is a critical task for public health agencies. However, traditional methods often assume complete knowledge of the contact network and struggle with asymptomatic spreaders who leave no temporal clues. This paper introduces the Source Detection via Contact Tracing Framework (SDCTF) and two local search algorithms, LS and LS+, which efficiently identify the source by adaptively querying the network, even when a significant portion of the population is asymptomatic.

The Challenge of Backward Tracing

Most contact tracing efforts are "forward-looking," aiming to identify and isolate individuals exposed to a known case. In contrast, "backward" tracing seeks to find the original source of an outbreak. This task is complicated by two real-world constraints:

  1. Unknown Networks: Most models assume the entire contact network is known. In reality, health agencies discover the network piece-by-piece through interviews.
  2. The Asymptomatic Gap: Standard algorithms rely on symptom onset times to reverse-engineer infection paths. Asymptomatic patients lack these timestamps, creating "dead ends" in the data.

The SDCTF Framework and Algorithms

The researchers propose the SDCTF, which begins its search only after the first hospitalization. The framework utilizes two types of adaptive queries: Contact Queries to map the local network and Test Queries to gather temporal data on infection status.

The paper introduces two primary algorithms:

  • LocalSearch (LS): A greedy algorithm that moves backward by selecting the neighbor with the earliest symptom onset time. While highly efficient, it can get "stuck" if it encounters an asymptomatic link.
  • LS+: An enhanced version designed for robustness. If LS+ hits an asymptomatic node, it queries that individual's household and contacts to find the symptomatic "missing link" further up the chain.
Evolution of an epidemic (a-c) and the subsequent backward tracing process (d-f) using local search iterations to identify the source.

Key Results and Insights

The algorithms were evaluated using synthetic models (DDE + HNM) and a high-fidelity COVID-19 simulator (DCS) based on real demographic data from Tübingen, Germany. Key findings include:

  • Superior Accuracy and Scalability: LS and LS+ consistently outperformed global baselines like Dynamic Message Passing (DMP). Because they are local, their runtime is independent of the total population size, unlike global methods with quadratic complexity.
  • Resilience to Asymptomatics: LS+ maintains high accuracy even when 40% of the population is asymptomatic by leveraging the "clique" nature of households to bypass gaps in the transmission chain.
  • Theoretical Validation: The authors developed a mathematical model using Random Exponential Recursive Trees (RERT) that accurately predicts the success probability of these heuristics, providing a solid theoretical foundation for the approach.

Conclusion

By focusing on local network exploration rather than global data, the SDCTF provides a scalable and effective solution for source detection. The robustness of LS+ to asymptomatic cases makes it particularly relevant for managing modern epidemics. Future research may explore decentralized, privacy-preserving implementations and the impact of non-compliant data reporting.

Summary updated

Abstract

Inferring the source of a diffusion in a large network of agents is a difficult but feasible task, if a few agents act as sensors revealing the time at which they got hit by the diffusion. A main limitation of current source detection algorithms is that they assume full knowledge of the contact network, which is rarely the case, especially for epidemics, where the source is called patient zero. Inspired by recent contact tracing algorithms, we propose a new framework, which we call Source Detection via Contact Tracing Framework (SDCTF). In the SDCTF, the source detection task starts at the time of the first hospitalization, and initially we have no knowledge about the contact network other than the identity of the first hospitalized agent. We may then explore the network by contact queries, and obtain symptom onset times by test queries in an adaptive way. We also assume that some of the agents may be asymptomatic, and therefore cannot reveal their symptom onset time. Our goal is to find patient zero with as few contact and test queries as possible. We propose two local search algorithms for the SDCTF: the LS algorithm is more data-efficient, but can fail to find the true source if many asymptomatic agents are present, whereas the LS+ algorithm is more robust to asymptomatic agents. By simulations we show that both LS and LS+ outperform state of the art adaptive and non-adaptive source detection algorithms adapted to the SDCTF, even though these baseline algorithms have full access to the contact network. Extending the theory of random exponential trees, we analytically approximate the probability of success of the LS/ LS+ algorithms, and we show that our analytic results match the simulations. Finally, we benchmark our algorithms on the Data-driven COVID-19 Simulator developed by Lorch et al., which is the first time source detection algorithms are tested on such a complex dataset.
BibTeX
@misc{odor2021source,
  author = {Gergely Ódor and Jana Vuckovic and Miguel-Angel Sanchez Ndoye and Patrick Thiran},
  title = {{Source Detection via Contact Tracing in the Presence of Asymptomatic Patients}},
  year = {2021},
  eprint = {2112.14530},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2112.14530},
}
Figure