An official website of the United States government
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
ComMit: Blind Community-based Early Mitigation Strategy against Viral Spread
In the early stages of a pandemic, epidemiological knowledge of the disease is limited and no vaccination is available. This poses the problem of determining an Early Mitigation Strategy. Previous studies have tackled this problem through finding globally influential nodes that contribute the most to the spread. These methods are often not practical due to their assumptions that (1) accessing the full contact social network is possible; (2) there is an unlimited budget for the mitigation strategy; (3) healthy individuals can be isolated for indefinite amount of time, which in practice can have serious mental health and economic consequences. In this work, we study the problem of developing an early mitigation strategy from a community perspective and propose a dynamic Community-based Mitigation strategy, ComMit. The distinguishing features of ComMit are: (1) It is agnostic to the dynamics of the spread; (2) does not require prior knowledge of contact network; (3) it works within a limited budget; and (4) it enforces bursts of short-term restriction on small communities instead of long-term isolation of healthy individuals. ComMit relies on updated data from test-trace reports and its strategy evolves over time. We have tested ComMit on several real-world social networks. The results of our experiments show that, within a small budget, ComMit can reduce the peak of infection by 73% and shorten the duration of infection by 90%, even for spreads that would reach a steady state of non-zero infections otherwise (e.g., SIS contagion model).
more »
« less
- Award ID(s):
- 1908048
- PAR ID:
- 10462517
- Date Published:
- Journal Name:
- 2022 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM)
- Page Range / eLocation ID:
- 26 to 33
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
Close contacts between individuals provide opportunities for the transmission of diseases, including COVID-19. While individuals take part in many different types of interactions, including those with classmates, co-workers and household members, it is the conglomeration of all of these interactions that produces the complex social contact network interconnecting individuals across the population. Thus, while an individual might decide their own risk tolerance in response to a threat of infection, the consequences of such decisions are rarely so confined, propagating far beyond any one person. We assess the effect of different population-level risk-tolerance regimes, population structure in the form of age and household-size distributions, and different interaction types on epidemic spread in plausible human contact networks to gain insight into how contact network structure affects pathogen spread through a population. In particular, we find that behavioural changes by vulnerable individuals in isolation are insufficient to reduce those individuals’ infection risk and that population structure can have varied and counteracting effects on epidemic outcomes. The relative impact of each interaction type was contingent on assumptions underlying contact network construction, stressing the importance of empirical validation. Taken together, these results promote a nuanced understanding of disease spread on contact networks, with implications for public health strategies.more » « less
-
Close contacts between individuals provide opportunities for the transmission of diseases, including COVID-19. While individuals take part in many different types of interactions, including those with classmates, co-workers and household members, it is the conglomeration of all of these interactions that produces the complex social contact network interconnecting individuals across the population. Thus, while an individual might decide their own risk tolerance in response to a threat of infection, the consequences of such decisions are rarely so confined, propagating far beyond any one person. We assess the effect of different population-level risk-tolerance regimes, population structure in the form of age and household-size distributions, and different interaction types on epidemic spread in plausible human contact networks to gain insight into how contact network structure affects pathogen spread through a population. In particular, we find that behavioural changes by vulnerable individuals in isolation are insufficient to reduce those individuals’ infection risk and that population structure can have varied and counteracting effects on epidemic outcomes. The relative impact of each interaction type was contingent on assumptions underlying contact network construction, stressing the importance of empirical validation. Taken together, these results promote a nuanced understanding of disease spread on contact networks, with implications for public health strategies.more » « less
-
Abstract Healthcare-associated infections (HAIs) are a major problem in hospital infection control. Although HAIs can be suppressed using contact precautions, such precautions are expensive, and we can only apply them to a small fraction of patients (i.e., a limited budget). In this work, we focus on two clinical problems arising from the limited budget: (a) choosing the best patients to be placed under precaution given a limited budget to minimize the spread (the isolation problem), and (b) choosing the best patients to release when limited budget requires some of the patients to be cleared from precaution (the clearance problem). A critical challenge in addressing them is that HAIs have multiple transmission pathways such that locations can also accumulate ‘load’ and spread the disease. One of the most common practices when placing patients under contact precautions is the regular clearance of pathogen loads. However, standard propagation models like independent cascade (IC)/susceptible-infectious-susceptible (SIS) cannot capture such mechanisms directly. Hence to account for this challenge, using non-linear system theory, we develop a novel spectral characterization of a recently proposed pathogen load based model,2-Mode-SISmodel, on people/location networks to capture spread dynamics of HAIs. We formulate the two clinical problems using this spectral characterization and develop effective and efficient algorithms for them. Our experiments show that our methods outperform several natural structural and clinical approaches on real-world hospital testbeds and pick meaningful solutions.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/ASONAM55673.2022.10068568
