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
WiFiTrace: Network-based Contact Tracing for Infectious Diseases Using Passive WiFi Sensing
Contact tracing is a well-established and effective approach for the containment of the spread of infectious diseases. While Bluetooth-based contact tracing method using phones has become popular recently, these approaches suffer from the need for a critical mass adoption to be effective. In this paper, we present WiFiTrace, a network-centric approach for contact tracing that relies on passive WiFi sensing with no client-side involvement. Our approach exploits WiFi network logs gathered by enterprise networks for performance and security monitoring, and utilizes them for reconstructing device trajectories for contact tracing. Our approach is specifically designed to enhance the efficacy of traditional methods, rather than to supplant them with new technology. We designed an efficient graph algorithm to scale our approach to large networks with tens of thousands of users. The graph-based approach outperforms an indexed PostgresSQL in memory by at least 4.5X without any index update overheads or blocking. We have implemented a full prototype of our system and deployed it on two large university campuses. We validated our approach and demonstrate its efficacy using case studies and detailed experiments using real-world WiFi datasets.
more »
« less
- NSF-PAR ID:
- 10314483
- Date Published:
- Journal Name:
- Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies
- Volume:
- 5
- Issue:
- 1
- ISSN:
- 2474-9567
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)We study allocation of COVID-19 vaccines to individuals based on the structural properties of their underlying social contact network. Even optimistic estimates suggest that most countries will likely take 6 to 24 months to vaccinate their citizens. These time estimates and the emergence of new viral strains urge us to find quick and effective ways to allocate the vaccines and contain the pandemic. While current approaches use combinations of age-based and occupation-based prioritizations, our strategy marks a departure from such largely aggregate vaccine allocation strategies. We propose a novel agent-based modeling approach motivated by recent advances in (i) science of real-world networks that point to efficacy of certain vaccination strategies and (ii) digital technologies that improve our ability to estimate some of these structural properties. Using a realistic representation of a social contact network for the Commonwealth of Virginia, combined with accurate surveillance data on spatio-temporal cases and currently accepted models of within- and between-host disease dynamics, we study how a limited number of vaccine doses can be strategically distributed to individuals to reduce the overall burden of the pandemic. We show that allocation of vaccines based on individuals' degree (number of social contacts) and total social proximity time is signi ficantly more effective than the currently used age-based allocation strategy in terms of number of infections, hospitalizations and deaths. Our results suggest that in just two months, by March 31, 2021, compared to age-based allocation, the proposed degree-based strategy can result in reducing an additional 56{110k infections, 3.2{5.4k hospitalizations, and 700{900 deaths just in the Commonwealth of Virginia. Extrapolating these results for the entire US, this strategy can lead to 3{6 million fewer infections, 181{306k fewer hospitalizations, and 51{62k fewer deaths compared to age-based allocation. The overall strategy is robust even: (i) if the social contacts are not estimated correctly; (ii) if the vaccine efficacy is lower than expected or only a single dose is given; (iii) if there is a delay in vaccine production and deployment; and (iv) whether or not non-pharmaceutical interventions continue as vaccines are deployed. For reasons of implementability, we have used degree, which is a simple structural measure and can be easily estimated using several methods, including the digital technology available today. These results are signi ficant, especially for resource-poor countries, where vaccines are less available, have lower efficacy, and are more slowly distributed.more » « less
-
Dovrolis, Constantine (Ed.)more » « less
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.
-
Demeniconi, C. ; Davidson, I (Ed.)Many irregular domains such as social networks, financial transactions, neuron connections, and natural language constructs are represented using graph structures. In recent years, a variety of graph neural networks (GNNs) have been successfully applied for representation learning and prediction on such graphs. In many of the real-world applications, the underlying graph changes over time, however, most of the existing GNNs are inadequate for handling such dynamic graphs. In this paper we propose a novel technique for learning embeddings of dynamic graphs using a tensor algebra framework. Our method extends the popular graph convolutional network (GCN) for learning representations of dynamic graphs using the recently proposed tensor M-product technique. Theoretical results presented establish a connection between the proposed tensor approach and spectral convolution of tensors. The proposed method TM-GCN is consistent with the Message Passing Neural Network (MPNN) framework, accounting for both spatial and temporal message passing. Numerical experiments on real-world datasets demonstrate the performance of the proposed method for edge classification and link prediction tasks on dynamic graphs. We also consider an application related to the COVID-19 pandemic, and show how our method can be used for early detection of infected individuals from contact tracing data.more » « less
-
The global and national response to the COVID-19 pandemic has been inadequate due to a collective lack of preparation and a shortage of available tools for responding to a large-scale pandemic. By applying lessons learned to create better preventative methods and speedier interventions, the harm of a future pandemic may be dramatically reduced. One potential measure is the widespread use of contact tracing apps. While such apps were designed to combat the COVID-19 pandemic, the time scale in which these apps were deployed proved a significant barrier to efficacy. Many companies and governments sprinted to deploy contact tracing apps that were not properly vetted for performance, privacy, or security issues. The hasty development of incomplete contact tracing apps undermined public trust and negatively influenced perceptions of app efficacy. As a result, many of these apps had poor voluntary public uptake, which greatly decreased the apps’ efficacy. Now, with lessons learned from this pandemic, groups can better design and test apps in preparation for the future. In this viewpoint, we outline common strategies employed for contact tracing apps, detail the successes and shortcomings of several prominent apps, and describe lessons learned that may be used to shape effective contact tracing apps for the present and future. Future app designers can keep these lessons in mind to create a version that is suitable for their local culture, especially with regard to local attitudes toward privacy-utility tradeoffs during public health crises.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1145/3448084
