Search for: All records

Abstract Human mobility is a primary driver of infectious disease spread. However, existing data is limited in availability, coverage, granularity, and timeliness. Data-driven forecasts of disease dynamics are crucial for decision-making by health officials and private citizens alike. In this work, we focus on a machine-learned anonymized mobility map (hereon referred to as AMM) aggregated over hundreds of millions of smartphones and evaluate its utility in forecasting epidemics. We factor AMM into a metapopulation model to retrospectively forecast influenza in the USA and Australia. We show that the AMM model performs on-par with those based on commuter surveys, which are sparsely available and expensive. We also compare it with gravity and radiation based models of mobility, and find that the radiation model’s performance is quite similar to AMM and commuter flows. Additionally, we demonstrate our model’s ability to predict disease spread even across state boundaries. Our work contributes towards developing timely infectious disease forecasting at a global scale using human mobility datasets expanding their applications in the area of infectious disease epidemiology. 

Discrete dynamical systems serve as useful formal models to study diffusion phenomena in social networks. Several recent articles have studied the algorithmic and complexity aspects of some decision problems on synchronous Boolean networks, which are discrete 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. Previous work has shown that some of these decision problems become efficiently solvable for systems on directed acyclic graphs (DAGs). Motivated by this line of work, we investigate a number of decision problems for dynamical systems whose underlying graphs are DAGs. We show that computational intractability (i.e.,PSPACE-completeness) results for reachability problems hold even for dynamical systems on DAGs. We also identify some restricted versions of dynamical systems on DAGs for which reachability problem can be solved efficiently. In addition, we show that a decision problem (namely, Convergence), which is efficiently solvable for dynamical systems on DAGs, becomesPSPACE-complete for Quasi-DAGs (i.e., graphs that become DAGs by the removal of asingleedge). In the process of establishing the above results, we also develop several structural properties of the phase spaces of dynamical systems on DAGs. 

Abstract Efficient energy consumption is crucial for achieving sustainable energy goals in the era of climate change and grid modernization. Thus, it is vital to understand how energy is consumed at finer resolutions such as household in order to plan demand-response events or analyze impacts of weather, electricity prices, electric vehicles, solar, and occupancy schedules on energy consumption. However, availability and access to detailed energy-use data, which would enable detailed studies, has been rare. In this paper, we release a unique, large-scale, digital-twin of residential energy-use dataset for the residential sector across the contiguous United States covering millions of households. The data comprise of hourly energy use profiles for synthetic households, disaggregated into Thermostatically Controlled Loads (TCL) and appliance use. The underlying framework is constructed using a bottom-up approach. Diverse open-source surveys and first principles models are used for end-use modeling. Extensive validation of the synthetic dataset has been conducted through comparisons with reported energy-use data. We present a detailed, open, high resolution, residential energy-use dataset for the United States. 

Abstract We consider the simultaneous propagation of two contagions over a social network. We assume a threshold model for the propagation of the two contagions and use the formal framework of discrete dynamical systems. In particular, we study an optimization problem where the goal is to minimize the total number of new infections subject to a budget constraint on the total number of available vaccinations for the contagions. While this problem has been considered in the literature for a single contagion, our work considers the simultaneous propagation of two contagions. This optimization problem is NP-hard. We present two main solution approaches for the problem, namely an integer linear programming (ILP) formulation to obtain optimal solutions and a heuristic based on a generalization of the set cover problem. We carry out a comprehensive experimental evaluation of our solution approaches using many real-world networks. The experimental results show that our heuristic algorithm produces solutions that are close to the optimal solution and runs several orders of magnitude faster than the ILP-based approach for obtaining optimal solutions. We also carry out sensitivity studies of our heuristic algorithm. 

Developing techniques to infer the behavior of networked social systems has attracted a lot of attention in the literature. Using a discrete dynamical system to model a networked social system, the problem of inferring the behavior of the system can be formulated as the problem of learning the local functions of the dynamical system. We investigate the problem assuming an active form of interaction with the system through queries. We consider two classes of local functions (namely, symmetric and threshold functions) and two interaction modes, namely batch (where all the queries must be submitted together) and adaptive (where the set of queries submitted at a stage may rely on the answers to previous queries). We establish bounds on the number of queries under both batch and adaptive query modes using vertex coloring and probabilistic methods. Our results show that a small number of appropriately chosen queries are provably sufficient to correctly learn all the local functions. We develop complexity results which suggest that, in general, the problem of generating query sets of minimum size is computationally intractable. We present efficient heuristics that produce query sets under both batch and adaptive query modes. Also, we present a query compaction algorithm that identifies and removes redundant queries from a given query set. Our algorithms were evaluated through experiments on over 20 well-known networks. 

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 problems (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. 

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 problem can be solved efficiently. 

Data from surveys administered after Hurricane Sandy provide a wealth of information that can be used to develop models of evacuation decision-making. We use a model based on survey data for predicting whether or not a family will evacuate. The model uses 26 features for each household including its neighborhood characteristics. We augment a 1.7 million node household-level synthetic social network of Miami, Florida with public data for the requisite model features so that our population is consistent with the survey-based model. Results show that household features that drive hurricane evacuations dominate the eects of specifying large numbers of families as "early evacuators" in a contagion process, and also dominate effects of peer influence to evacuate. There is a strong network-based evacuation suppression effect from the fear of looting. We also study spatial factors aecting evacuation rates as well as policy interventions to encourage evacuation. 

Neighborhood eects have an important role in evacuation decision-making by a family. Owing to peer influence, neighbors evacuating can motivate a family to evacuate. Paradoxically, if a lot of neighbors evacuate, then the likelihood of an individual or family deciding to evacuate decreases, for fear of crime and looting. Such behavior cannot be captured using standard models of contagion spread on networks, e.g., threshold, independent cascade, and linear threshold models. Here, we propose a new threshold-based graph dynamical system model, 2mode-threshold, which captures this dichotomy. We study theoretically the dynamical properties of 2mode-threshold in different networks, and fi nd signi ficant differences from a standard threshold model. We build and characterize small world networks of Virginia Beach, VA, where nodes are geolocated families (households) in the city and edges are interactions between pairs of families. We demonstrate the utility of our behavioral model through agent-based simulations on these small world networks. We use it to understand evacuation rates in this region, and to evaluate the effects of modeling parameters on evacuation decision dynamics. Speci fically, we quantify the effects of (i) network generation parameters, (ii) stochasticity in the social network generation process, (iii) model types (2mode-threshold vs. stan- dard threshold models), (iv) 2mode-threshold model parameters, (v) and initial conditions, on computed evacuation rates and their variability. An illustrative example result shows that the absence of looting eect can overpredict evacuation rates by as much as 50%. 

We study evacuation dynamics in a major urban region (Mi- ami, FL) using a combination of a realistic population and social contact network, and an agent-based model of evacuation behavior that takes into account peer influence and concerns of looting. These factors have been shown to be important in prior work, and have been modeled as a threshold-based network dynamical systems model (2mode-threshold), which involves two threshold parameters - for a family's decision to evacuate and to remain in place for looting and crime concerns - based on the fraction of neighbors who have evacuated. The dynamics of such models are not well understood, and we observe that the threshold parameters have a signifi cant impact on the evacuation dynamics. We also observe counter-intuitive effects of increasing the evacuation threshold on the evacuated fraction in some regimes of the model parameter space, which suggests that the details of realistic networks matter in designing policies.