More Like this

1. Theoretical Models and Preliminary Results for Contact Tracing and Isolation

   Li, G.Z.; Haddadan, A.; Li, A.; Marathe, M.; Srinivasan, A.; Vullikanti, A.; Zhao, Z. (May 2022, Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems)

   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
2. A Markov Decision Process Framework for Efficient and Implementable Contact Tracing and Isolation

   Li, George; Haddadan, Arash; Li, Ann; Marathe, Madhav; Srinivasan, Aravind; Vullikanti, Anil; Zhao, Zeyu (January 2022, ArXivorg)

   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
3. Solving Markov decision processes for network-level post-hazard recovery via simulation optimization and rollout

   Sarkale, Y.; Nozhati, S.; Chong, E. K.; Ellingwood, B. R.; Mahmoud, H. (August 2019, 2018 IEEE 14th International Conference on Automation Science and Engineering (CASE))

   Computation of optimal recovery decisions for community resilience assurance post-hazard is a combinatorial decision-making problem under uncertainty. It involves solving a large-scale optimization problem, which is significantly aggravated by the introduction of uncertainty. In this paper, we draw upon established tools from multiple research communities to provide an effective solution to this challenging problem. We provide a stochastic model of damage to the water network (WN) within a testbed community following a severe earthquake and compute near-optimal recovery actions for restoration of the water network. We formulate this stochastic decision-making problem as a Markov Decision Process (MDP), and solve it using a popular class of heuristic algorithms known as rollout. A simulation-based representation of MDPs is utilized in conjunction with rollout and the Optimal Computing Budget Allocation (OCBA) algorithm to address the resulting stochastic simulation optimization problem. Our method employs non-myopic planning with efficient use of simulation budget. We show, through simulation results, that rollout fused with OCBA performs competitively with respect to rollout with total equal allocation (TEA) at a meagre simulation budget of 5-10% of rollout with TEA, which is a crucial step towards addressing large-scale community recovery problems following natural disasters. 

   more » « less
4. Detecting and quantifying heterogeneity in susceptibility using contact tracing data

   https://doi.org/10.1371/journal.pcbi.1012310  

   Tuschhoff, Beth M; Kennedy, David A (July 2024, PLOS Computational Biology)

   Lau, Eric HY (Ed.)

   The presence of heterogeneity in susceptibility, differences between hosts in their likelihood of becoming infected, can fundamentally alter disease dynamics and public health responses, for example, by changing the final epidemic size, the duration of an epidemic, and even the vaccination threshold required to achieve herd immunity. Yet, heterogeneity in susceptibility is notoriously difficult to detect and measure, especially early in an epidemic. Here we develop a method that can be used to detect and estimate heterogeneity in susceptibility given contact by using contact tracing data, which are typically collected early in the course of an outbreak. This approach provides the capability, given sufficient data, to estimate and account for the effects of this heterogeneity before they become apparent during an epidemic. It additionally provides the capability to analyze the wealth of contact tracing data available for previous epidemics and estimate heterogeneity in susceptibility for disease systems in which it has never been estimated previously. The premise of our approach is that highly susceptible individuals become infected more often than less susceptible individuals, and so individuals not infected after appearing in contact networks should be less susceptible than average. This change in susceptibility can be detected and quantified when individuals show up in a second contact network after not being infected in the first. To develop our method, we simulated contact tracing data from artificial populations with known levels of heterogeneity in susceptibility according to underlying discrete or continuous distributions of susceptibilities. We analyzed these data to determine the parameter space under which we are able to detect heterogeneity and the accuracy with which we are able to estimate it. We found that our power to detect heterogeneity increases with larger sample sizes, greater heterogeneity, and intermediate fractions of contacts becoming infected in the discrete case or greater fractions of contacts becoming infected in the continuous case. We also found that we are able to reliably estimate heterogeneity and disease dynamics. Ultimately, this means that contact tracing data alone are sufficient to detect and quantify heterogeneity in susceptibility. 

   more » « less
5. Tracing and testing multiple generations of contacts to COVID-19 cases: cost–benefit trade-offs

   https://doi.org/10.1098/rsos.211927  

   Kim, Jungyeol; Chen, Xingran; Nikpey, Hesam; Rubin, Harvey; Saeedi Bidokhti, Shirin; Sarkar, Saswati (October 2022, Royal Society Open Science)

   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