TL;DR
This paper introduces a new framework, the Source Identification via Contact Tracing Framework (SICTF), to pinpoint the origin of an epidemic when some infected individuals are asymptomatic. They propose two algorithms, LS and LS+, that efficiently identify the "patient zero" by adaptively querying contacts and symptom onset times, outperforming existing methods even without full network knowledge.
What Problem Does This Paper Address?
Identifying the initial source of an epidemic (patient zero) is crucial for effective containment and response. Traditional methods often assume complete knowledge of the contact network, which is rarely available in real-world scenarios, especially during the early stages of an outbreak. Furthermore, the presence of asymptomatic individuals, who don't reveal their symptom onset times, significantly complicates source identification. Existing algorithms struggle with this lack of information and the challenge posed by asymptomatic cases. This paper addresses the need for a practical and robust source identification method that can operate with limited network information and effectively handle asymptomatic infections.
Methods
The authors propose the Source Identification via Contact Tracing Framework (SICTF). This framework models a scenario where an agency learns about an outbreak upon the first hospitalization and can then perform two types of queries:
- Household queries: Reveal individuals within the same household.
- Contact queries: Reveal direct contacts within a specific time window.
- Test queries: Reveal symptom onset times for symptomatic individuals.
The key innovation is the adaptive nature of these queries, meaning they can depend on previous outcomes. They introduce two algorithms within this framework:
- LocalSearch (LS): A greedy algorithm that traces back from the first hospitalized patient, updating its candidate source based on the earliest reported symptom onset times. It's efficient but can be misled by asymptomatic individuals.
- LS+: An improved version of LS that specifically addresses asymptomatic cases by extending its search to include backward contacts of asymptomatic individuals and household members of any asymptomatic node. This makes it more robust.
The paper also develops theoretical models (Red-Blue trees, Deterministic Exponential Trees) to analytically approximate the performance of LS and LS+, allowing for rigorous analysis of their source identification probabilities.
Datasets
The authors validate their algorithms using:
- The Data-driven COVID-19 Simulator (DCS): A complex, realistic simulator developed by Lorch et al. (2022) that uses aggregate data to generate synthetic mobility traces and simulate epidemic processes. This serves as a benchmark for their methods in a highly realistic setting.
- Synthetic epidemic and mobility models: Including the Deterministically Developing Epidemic (DDE) model combined with the Household Network Model (HNM) and the Tubingen mobility model (TU). These simplified models are used for theoretical analysis and to understand the impact of various parameters.
Key Insights and Ideas
- Asymptomatic patients are a major hurdle: The presence of asymptomatic individuals significantly degrades the accuracy of source identification algorithms, as they don't provide crucial temporal information.
- Adaptive querying is key: The ability to adaptively choose which contacts to query and which individuals to test based on previous results dramatically improves efficiency and accuracy.
- Household structure matters for robustness: The LS+ algorithm's ability to leverage household information makes it more resilient to asymptomatic cases compared to LS.
- Theoretical analysis on simplified models is crucial: While complex simulators are valuable for validation, analytical tractability is achieved by simplifying the network and epidemic models (e.g., to tree structures), allowing for rigorous proofs and deeper understanding of performance drivers.
- "Low-tech" approach has practical appeal: The design of LS/LS+ algorithms, focusing on adaptive querying and local search, makes them potentially easier to implement in real-world contact tracing scenarios.
Key Results
- Both LS and LS+ algorithms outperform existing baseline algorithms (random+DMP, SG) in source identification accuracy, even when baselines have full network access.
- LS+ is more robust than LS, especially in the presence of asymptomatic patients.
- The number of queries (tests and contacts) used by LS and LS+ is independent of the network size, depending only on the local neighborhood of the source, making them scalable.
- Theoretical analysis closely matches simulation results, providing confidence in the models and predictions.
- The algorithms demonstrate robustness to changes in epidemic and mobility parameters.
Limitations and Future Work
- Theoretical analysis on loopy graphs: The theoretical results are derived on tree approximations of the network. Quantifying the tightness of these approximations or developing direct theoretical results for loopy graphs is a future direction.
- Imprecise reporting and multiple variants: The current framework assumes perfect reporting and doesn't account for multiple disease variants. Investigating robustness to these factors is suggested.
- Real-world data limitations: The authors acknowledge the challenge of finding publicly available individual-level mobility and epidemiological datasets due to privacy concerns.
- Computational complexity: While LS/LS+ are efficient, some baseline algorithms (like DMP) can become computationally expensive, especially for larger networks or longer timeframes.
- "Low-tech" implementation: The authors highlight the potential for real-world implementation of their algorithms, suggesting this as a practical advantage.
Summary updated