skip to main content
Explore Scholarly Publications and Datasets in the NSF-PAR

  • Home
  • Search Results
  • Page 1 of 3

Search for: All records

Creators/Authors contains: "Marathe, Madhav"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. ; ; ; ; ; ; ( , 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 themore »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.« less
    Free, publicly-accessible full text available January 14, 2023
  2. ; ; ; ( , Scientific Reports)
    Abstract Infections produced by non-symptomatic (pre-symptomatic and asymptomatic) individuals have been identified as major drivers of COVID-19 transmission. Non-symptomatic individuals, unaware of the infection risk they pose to others, may perceive themselves—and be perceived by others—as not presenting a risk of infection. Yet, many epidemiological models currently in use do not include a behavioral component, and do not address the potential consequences of risk misperception. To study the impact of behavioral adaptations to the perceived infection risk, we use a mathematical model that incorporates the behavioral decisions of individuals, based on a projection of the system’s future state over amore »finite planning horizon. We found that individuals’ risk misperception in the presence of non-symptomatic individuals may increase or reduce the final epidemic size. Moreover, under behavioral response the impact of non-symptomatic infections is modulated by symptomatic individuals’ behavior. Finally, we found that there is an optimal planning horizon that minimizes the final epidemic size.« less
    Free, publicly-accessible full text available December 1, 2022
  3. ; ; ; ; ; ; ( , Proceedings of the National Academy of Sciences)
    The ongoing COVID-19 pandemic underscores the importance of developing reliable forecasts that would allow decision makers to devise appropriate response strategies. Despite much recent research on the topic, epidemic forecasting remains poorly understood. Researchers have attributed the difficulty of forecasting contagion dynamics to a multitude of factors, including complex behavioral responses, uncertainty in data, the stochastic nature of the underlying process, and the high sensitivity of the disease parameters to changes in the environment. We offer a rigorous explanation of the difficulty of short-term forecasting on networked populations using ideas from computational complexity. Specifically, we show that several forecasting problemsmore »(e.g., the probability that at least a given number of people will get infected at a given time and the probability that the number of infections will reach a peak at a given time) are computationally intractable. For instance, efficient solvability of such problems would imply that the number of satisfying assignments of an arbitrary Boolean formula in conjunctive normal form can be computed efficiently, violating a widely believed hypothesis in computational complexity. This intractability result holds even under the ideal situation, where all the disease parameters are known and are assumed to be insensitive to changes in the environment. From a computational complexity viewpoint, our results, which show that contagion dynamics become unpredictable for both macroscopic and individual properties, bring out some fundamental difficulties of predicting disease parameters. On the positive side, we develop efficient algorithms or approximation algorithms for restricted versions of forecasting problems.« less
    Free, publicly-accessible full text available January 25, 2023
  4. ; ; ; ; ; ; ; ; ; ; et al ( , Scientific Reports)
    Abstract This research measures the epidemiological and economic impact of COVID-19 spread in the US under different mitigation scenarios, comprising of non-pharmaceutical interventions. A detailed disease model of COVID-19 is combined with a model of the US economy to estimate the direct impact of labor supply shock to each sector arising from morbidity, mortality, and lockdown, as well as the indirect impact caused by the interdependencies between sectors. During a lockdown, estimates of jobs that are workable from home in each sector are used to modify the shock to labor supply. Results show trade-offs between economic losses, and lives savedmore »and infections averted are non-linear in compliance to social distancing and the duration of the lockdown. Sectors that are worst hit are not the labor-intensive sectors such as the Agriculture sector and the Construction sector, but the ones with high valued jobs such as the Professional Services, even after the teleworkability of jobs is accounted for. Additionally, the findings show that a low compliance to interventions can be overcome by a longer shutdown period and vice versa to arrive at similar epidemiological impact but their net effect on economic loss depends on the interplay between the marginal gains from averting infections and deaths, versus the marginal loss from having healthy workers stay at home during the shutdown.« less
    Free, publicly-accessible full text available December 1, 2022
  5. ; ; ; ; ; ; ; ; ; ; et al ( , IEEE International Conference on Big Data)
    We study the role of vaccine acceptance in controlling the spread of COVID-19 in the US using AI-driven agent-based models. Our study uses a 288 million node social contact network spanning all 50 US states plus Washington DC, comprised of 3300 counties, with 12.59 billion daily interactions. The highly-resolved agent-based models use realistic information about disease progression, vaccine uptake, production schedules, acceptance trends, prevalence, and social distancing guidelines. Developing a national model at this resolution that is driven by realistic data requires a complex scalable workflow, model calibration, simulation, and analytics components. Our workflow optimizes the total execution time andmore »helps in improving overall human productivity.This work develops a pipeline that can execute US-scale models and associated workflows that typically present significant big data challenges. Our results show that, when compared to faster and accelerating vaccinations, slower vaccination rates due to vaccine hesitancy cause averted infections to drop from 6.7M to 4.5M, and averted total deaths to drop from 39.4K to 28.2K nationwide. This occurs despite the fact that the final vaccine coverage is the same in both scenarios. Improving vaccine acceptance by 10% in all states increases averted infections from 4.5M to 4.7M (a 4.4% improvement) and total deaths from 28.2K to 29.9K (a 6% increase) nationwide. The analysis also reveals interesting spatio-temporal differences in COVID-19 dynamics as a result of vaccine acceptance. To our knowledge, this is the first national-scale analysis of the effect of vaccine acceptance on the spread of COVID-19, using detailed and realistic agent-based models.« less
    Free, publicly-accessible full text available December 15, 2022
  6. ; ; ; ( , Proceedings of the AAAI Conference on Artificial Intelligence)
    Discrete dynamical systems serve as useful formal models to study diffusion phenomena in social networks. Motivated by applications in systems biology, several recent papers have studied algorithmic and complexity aspects of diffusion problems for dynamical systems whose underlying graphs are directed, and may contain directed cycles. Such problems can be regarded as reachability problems in the phase space of the corresponding dynamical system. We show that computational intractability results for reachability problems hold even for dynamical systems on directed acyclic graphs (dags). We also show that for dynamical systems on dags where each local function is monotone, the reachability problemmore »can be solved efficiently.« less
    Accepted Manuscript Full Text Available
  7. ; ; ; ; ; ; ; ; ; ; et al ( , npj Digital Medicine)
    Abstract Privacy protection is paramount in conducting health research. However, studies often rely on data stored in a centralized repository, where analysis is done with full access to the sensitive underlying content. Recent advances in federated learning enable building complex machine-learned models that are trained in a distributed fashion. These techniques facilitate the calculation of research study endpoints such that private data never leaves a given device or healthcare system. We show—on a diverse set of single and multi-site health studies—that federated models can achieve similar accuracy, precision, and generalizability, and lead to the same interpretation as standard centralized statisticalmore »models while achieving considerably stronger privacy protections and without significantly raising computational costs. This work is the first to apply modern and general federated learning methods that explicitly incorporate differential privacy to clinical and epidemiological research—across a spectrum of units of federation, model architectures, complexity of learning tasks and diseases. As a result, it enables health research participants to remain in control of their data and still contribute to advancing science—aspects that used to be at odds with each other.« less
    Free, publicly-accessible full text available December 1, 2022
  8. ; ; ; ; ; ; ; ; ; ; et al ( , KDD '21: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining)
    Mobility restrictions have been a primary intervention for controlling the spread of COVID-19, but they also place a significant economic burden on individuals and businesses. To balance these competing demands, policymakers need analytical tools to assess the costs and benefits of different mobility reduction measures. In this paper, we present our work motivated by our interactions with the Virginia Department of Health on a decision-support tool that utilizes large-scale data and epidemiological modeling to quantify the impact of changes in mobility on infection rates. Our model captures the spread of COVID-19 by using a fine-grained, dynamic mobility network that encodesmore »the hourly movements of people from neighborhoods to individual places, with over 3 billion hourly edges. By perturbing the mobility network, we can simulate a wide variety of reopening plans and forecast their impact in terms of new infections and the loss in visits per sector. To deploy this model in practice, we built a robust computational infrastructure to support running millions of model realizations, and we worked with policymakers to develop an interactive dashboard that communicates our model's predictions for thousands of potential policies.« less
    Free, publicly-accessible full text available August 14, 2022
  9. ; ; ; ; ( , IEEE International Conference on Big Data)
    Abstract—Evacuation planning methods aim to design routes and schedules to relocate people to safety in the event of natural or man-made disasters. The primary goal is to minimize casualties which often requires the evacuation process to be completed as soon as possible. In this paper, we present QueST, an agent-based discrete event queuing network simulation system, and STEERS, an iterative routing algorithm that uses QueST for designing and evaluating large scale evacuation plans in terms of total egress time and congestion/bottlenecks occurring during evacuation. We use the Houston Metropolitan Area, which consists of nine US counties and spans an areamore »of 9,444 square miles as a case study, and compare the performance of STEERS with two existing route planning methods. We find that STEERS is either better or comparable to these methods in terms of total evacuation time and congestion faced by the evacuees. We also analyze the large volume of data generated by the simulation process to gain insights about the scenarios arising from following the evacuation routes prescribed by these methods.« less
    Full Text Available 
  10. ; ; ; ; ; ; ( , IEEE International Conference on Big Data)
    Abstract—It is well known that physical interdependencies exist between networked civil infrastructures such as transportation and power system networks. In order to analyze complex nonlinear correlations between such networks, datasets pertaining to such real infrastructures are required. However, such data are not readily available due to their proprietary nature. This work proposes a methodology to generate realistic synthetic power distribution networks for a given geographical region. A network generated in this manner is not the actual distribution system, but its functionality is very similar to the real distribution network. The synthetic network connects high voltage substations to individual residential consumersmore »through primary and secondary distribution networks. Here, the distribution network is generated by solving an optimization problem which minimizes the overall length of the network subject to structural and power flow constraints. This work also incorporates identification of long high voltage feeders originating from substations and connecting remotely situated customers in rural geographic locations while maintaining voltage regulation within acceptable limits. The proposed methodology is applied to the state of Virginia and creates synthetic distribution networks which are validated by comparing them to actual power distribution networks at the same location. Index Terms—synthetic distribution networks, radial networks, Mixed Integer Linear Programming« less
    Full Text Available