An official website of the United States government
Traditional contact tracing tests the direct contacts of those who test positive. But, by the time an infected individual is tested, the infection starting from the person may have infected a chain of individuals. Hence, why should the testing stop at direct contacts, and not test secondary, tertiary contacts or even contacts further down? One deterrent in testing long chains of individuals right away may be that it substantially increases the testing load, or does it? We investigate the costs and benefits of such multi-hop contact tracing for different number of hops. Considering diverse contact networks, we show that the cost–benefit trade-off can be characterized in terms of a single measurable attribute, the initial epidemic growth rate . Once this growth rate crosses a threshold, multi-hop contact tracing substantially reduces the outbreak size compared with traditional tracing. Multi-hop even incurs a lower cost compared with the traditional tracing for a large range of values of the growth rate. The cost–benefit trade-offs can be classified into three phases depending on the value of the growth rate. The need for choosing a larger number of hops becomes greater as the growth rate increases or the environment becomes less conducive toward containing the disease.
more »
« less
Capturing COVID-19 spread and interplay with multi-hop contact tracing intervention
A preemptive multi-hop contact tracing scheme that tracks not only the direct contacts of those who tested positive for COVID-19, but also secondary or tertiary contacts has been proposed and deployed in practice with some success. We propose a mathematical methodology for evaluating this preemptive contact tracing strategy that combines the contact tracing dynamics and the virus transmission mechanism in a single framework using microscopic Markov Chain approach (MMCA). We perform Monte Carlo (MC) simulations to validate our model and show that the output of our model provides a reasonable match with the result of MC simulations. Utilizing the formulation under a human contact network generated from real-world data, we show that the cost-benefit tradeoff can be significantly enhanced through an implementation of the multi-hop contact tracing as compared to traditional contact tracing. We further shed light on the mechanisms behind the effectiveness of the multi-hop testing strategy using the framework. We show that our mathematical framework allows significantly faster computation of key attributes for multi-hop contact tracing as compared to MC simulations. This in turn enables the investigation of these attributes for large contact networks, and constitutes a significant strength of our approach as the contact networks that arise in practice are typically large.
more »
« less
- Award ID(s):
- 2047482
- PAR ID:
- 10500182
- Editor(s):
- Dovrolis, Constantine
- Publisher / Repository:
- ncbi.nlm.nih.gov
- Date Published:
- Journal Name:
- PLOS ONE
- Volume:
- 18
- Issue:
- 7
- ISSN:
- 1932-6203
- Page Range / eLocation ID:
- e0288394
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Efficient contact tracing and isolation is an effective strategy to control epidemics, as seen in the Ebola epidemic and COVID-19 pandemic. An important consideration in contact tracing is the budget on the number of individuals asked to quarantine—the budget is limited for socioeconomic reasons (e.g., having a limited number of contact tracers). Here, we present a Markov Decision Process (MDP) framework to formulate the problem of using contact tracing to reduce the size of an outbreak while limiting the number of people quarantined. We formulate each step of the MDP as a combinatorial problem, MinExposed, which we demonstrate is NP-Hard. Next, we develop two approximation algorithms, one based on rounding the solutions of a linear program and another (greedy algorithm) based on choosing nodes with a high (weighted) degree. A key feature of the greedy algorithm is that it does not need complete information of the underlying social contact network, making it implementable in practice. Using simulations over realistic networks, we show how the algorithms can help in bending the epidemic curve with a limited number of isolated individuals.more » « less
-
ABSTRACT Efficient contact tracing and isolation is an effective strategy to control epidemics, as seen in the Ebola epidemic and COVID-19 pandemic. An important consideration in contact tracing is the budget on the number of individuals asked to quarantine—the budget is limited for socioeconomic reasons (e.g., having a limited number of contact tracers). Here, we present a Markov Decision Process (MDP) framework to formulate the problem of using contact tracing to reduce the size of an outbreak while limiting the number of people quarantined. We formulate each step of the MDP as a combinatorial problem, MinExposed, which we demonstrate is NP-Hard. Next, we develop two approximation algorithms, one based on rounding the solutions of a linear program and another (greedy algorithm) based on choosing nodes with a high (weighted) degree. A key feature of the greedy algorithm is that it does not need complete information of the underlying social contact network, making it implementable in practice. Using simulations over realistic networks, we show how the algorithms can help in bending the epidemic curve with a limited number of isolated individuals.more » « less
-
Efficient contact tracing and isolation is an effective strategy to control epidemics. It was used effectively during the Ebola epidemic and successfully implemented in several parts of the world during the ongoing COVID-19 pandemic. An important consideration in contact tracing is the budget on the number of individuals asked to quarantine -- the budget is limited for socioeconomic reasons. In this paper, we present a Markov Decision Process (MDP) framework to formulate the problem of using contact tracing to reduce the size of an outbreak while asking a limited number of people to quarantine. We formulate each step of the MDP as a combinatorial problem, MinExposed, which we demonstrate is NP-Hard; as a result, we develop an LP-based approximation algorithm. Though this algorithm directly solves MinExposed, it is often impractical in the real world due to information constraints. To this end, we develop a greedy approach based on insights from the analysis of the previous algorithm, which we show is more interpretable. A key feature of the greedy algorithm is that it does not need complete information of the underlying social contact network. This makes the heuristic implementable in practice and is an important consideration. Finally, we carry out experiments on simulations of the MDP run on real-world networks, and show how the algorithms can help in bending the epidemic curve while limiting the number of isolated individuals. Our experimental results demonstrate that the greedy algorithm and its variants are especially effective, robust, and practical in a variety of realistic scenarios, such as when the contact graph and specific transmission probabilities are not known. All code can be found in our GitHub repository: this https URL.more » « less
-
Interference alignment (IA) is widely regarded as a promising interference management technique for wireless networks and its potential is most profound in interference-intensive environments. This motivates us to study IA for multicast communications in multi-hop MIMO networks, which are rich in interference by nature. We develop a set of linear constraints that can characterize a feasible design space of IA for multicast communications. The set of linear constraints constitutes a simple mathematical model of IA that allows us to conduct cross-layer multicast throughput optimization in multi-hop MIMO networks, but without getting involved into the onerous signal design at the physical layer. Based on the mathematical model of IA, we formulate a multicast throughput maximization problem and develop an approximation solution that can achieve (1−ϵ)-optimality. Simulation results show that the use of IA can significantly increase the multicast throughput in multi-hop MIMO networks and the throughput gain increases with the volume of multicast traffic and the number of antennas.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1371/journal.pone.0288394
