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:
- Unknown Networks: Most models assume the entire contact network is known. In reality, health agencies discover the network piece-by-piece through interviews.
- 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.
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