Large-scale population displacements arising from conflict-induced forced migration generate uncertainty and introduce several policy challenges. Addressing these concerns requires an interdisciplinary approach that integrates knowledge from both computational modeling and social sciences. We propose a generalized computational agent-based modeling framework grounded by Theory of Planned Behavior to model conflict-induced migration outflows within Ukraine during the start of that conflict in 2022. Existing migration modeling frameworks that attempt to address policy implications primarily focus on destination while leaving absent a generalized computational framework grounded by social theory focused on the conflict-induced region. We propose an agent-based framework utilizing a spatiotemporal gravity model and a Bi-threshold model over a Graph Dynamical System to update migration status of agents in conflict-induced regions at fine temporal and spatial granularity. This approach significantly outperforms previous work when examining the case of Russian invasion in Ukraine. Policy implications of the proposed framework are demonstrated by modeling the migration behavior of Ukrainian civilians attempting to flee from regions encircled by Russian forces. We also showcase the generalizability of the model by simulating a past conflict in Burundi, an alternative conflict setting. Results demonstrate the utility of the framework for assessing conflict-induced migration in varied settings as well as identifying vulnerable civilian populations.

We study allocation of COVID-19 vaccines to individuals based on the structural properties of their underlying social contact network. Using a realistic representation of a social contact network for the Commonwealth of Virginia, 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 significantly more effective than the usually used age-based allocation strategy in reducing the number of infections, hospitalizations and deaths. 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 significant, especially for resource-poor countries, where vaccines are less available, have lower efficacy, and are more slowly distributed.

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 and 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.

The COVID-19 global outbreak represents the most significant epidemic event since the 1918 influenza pandemic. Simulations have played a crucial role in supporting COVID-19 planning and response efforts. Developing scalable workflows to provide policymakers quick responses to important questions pertaining to logistics, resource allocation, epidemic forecasts and intervention analysis remains a challenging computational problem. In this work, we present scalable high performance computing-enabled workflows for COVID-19 pandemic planning and response. The scalability of our methodology allows us to run fine-grained simulations daily, and to generate county-level forecasts and other counterfactual analysis for each of the 50 states (and DC), 3140 counties across the USA. Our workflows use a hybrid cloud/cluster system utilizing a combination of local and remote cluster computing facilities, and using over 20,000 CPU cores running for 6-9 hours every day to meet this objective. Our state (Virginia), state hospital network, our university, the DOD and the CDC use our models to guide their COVID-19 planning and response efforts. We began executing these pipelines March 25, 2020, and have delivered and briefed weekly updates to these stakeholders for over 30 weeks without interruption.

In anagram games, players are provided with letters for forming as many words as possible over a specified time duration. Anagram games have been used in controlled experiments to study problems such as collective identity, effects of goal-setting, internal-external attributions, test anxiety, and others. The majority of work on anagram games involves individual players. Recently, work has expanded to group anagram games where players cooperate by sharing letters. In this work, we analyze experimental data from online social networked experiments of group anagram games. We develop mechanistic and data-driven models of human decision-making to predict detailed game player actions (e.g., what word to form next). With these results, we develop a composite agent-based modeling and simulation platform that incorporates the models from data analysis. We compare model predictions against experimental data, which enables us to provide explanations of human decision-making and behavior. Finally, we provide illustrative case studies using agent-based simulations to demonstrate the efficacy of models to provide insights that are beyond those from experiments alone.

Abduction is an inference approach that uses data and observations to identify plausible (and preferably, best) explanations for phenomena. Applications of abduction (e.g., robotics, genetics, image understanding) have largely been devoid of human behavior. Here, we devise and execute an iterative abductive analysis process that is driven by the social sciences: behaviors and interactions among groups of human subjects. One goal is to understand intra-group cooperation and its effect on fostering collective identity. We build an online game platform; perform and analyze controlled laboratory experiments; form hypotheses; build, exercise, and evaluate network-based agent-based models; and evaluate the hypotheses in multiple abductive iterations, improving our understanding as the process unfolds. While the experimental results are of interest, the paper's thrust is methodological, and indeed establishes the potential of iterative abductive looping for the (computational) social sciences.

Motivation: DNA data is transcribed into single-stranded RNA, which folds into specific molecular structures. In this paper we pose the question to what extent sequence- and structure-information correlate. We view this correlation as structural semantics of sequence data that allows for a different interpretation than conventional sequence alignment. Structural semantics could enable us to identify more general embedded ‘patterns’ in DNA and RNA sequences. Results: We compute the partition function of sequences with respect to a fixed structure and connect this computation to the mutual information of a sequence–structure pair for RNA secondary structures. We present a Boltzmann sampler and obtain the a priori probability of specific sequence patterns. We present a detailed analysis for the three PDB-structures, 2JXV (hairpin), 2N3R (3-branch multi-loop) and 1EHZ (tRNA). We localize specific sequence patterns, contrast the energy spectrum of the Boltzmann sampled sequences versus those sequences that refold into the same structure and derive a criterion to identify native structures. We illustrate that there are multiple sequences in the partition function of a fixed structure, each having nearly the same mutual information, that are nevertheless poorly aligned. This indicates the possibility of the existence of relevant patterns embedded in the sequences that are not discoverable using alignments. Availability and Implementation: The source code is freely available at http://staff.vbi.vt.edu/fenixh/Sampler.zip Contact: [email protected] Supplimentary Information: Supplementary data are available at Bioinformatics online.

Socially coupled systems are comprised of interdependent social, organizational, economic, infrastructure and physical networks. Today's urban regions serve as an excellent example of such systems. People and institutions confront the implications of the increasing scale of information becoming available due to a combination of advances in pervasive computing, data acquisition systems as well as high performance computing. Integrated modeling and decision making environments are necessary to support planning, analysis and counter factual experiments to study these complex systems. Here, we describe SIMFRASTRUCTURE - a flexible coordination middleware that supports high performance computing oriented decision and analytics environments to study socially coupled systems. Simfrastructure provides a multiplexing mechanism by which simple and intuitive user-interfaces can be plugged in as front-end systems, and high-end computing resources can be plugged in as back-end systems for execution. This makes the computational complexity of the simulations completely transparent to the users. The decoupling of user interfaces and data repository from simulation execution allows users to access simulation results asynchronously and enables them to add new datasets and simulation models dynamically. Simfrastructure enables implementation of a simple yet powerful modeling environment with built-in analytics-as-a service platform, which provides seamless access to high end computational resources, through an intuitive interface for studying socially coupled systems. We illustrate the applicability of Simfrastructure in the context of an integrated modeling environment to study public health epidemiology.

Preventing and controlling outbreaks of infectious diseases such as pandemic influenza is a top public health priority. We describe EpiSimdemics - a scalable parallel algorithm to simulate the spread of contagion in large, realistic social contact networks using individual-based models. EpiSimdemics is an interaction-based simulation of a certain class of stochastic reaction-diffusion processes. Straightforward simulations of such process do not scale well, limiting the use of individual-based models to very small populations. EpiSimdemics is specifically designed to scale to social networks with 100 million individuals. The scaling is obtained by exploiting the semantics of disease evolution and disease propagation in large networks. We evaluate an MPI-based parallel implementation of EpiSimdemics on a mid-sized HPC system, demonstrating that EpiSimdemics scales well. EpiSimdemics has been used in numerous sponsor defined case studies targeted at policy planning and course of action analysis, demonstrating the usefulness of EpiSimdemics in practical situations.

There has recently been renewed interest among various research communities in understanding the structure of social and infrastructure networks. Motivated by this line of research, we conduct an in-depth structural analysis of large ad hoc networks derived by placing nodes randomly as well as by placing them in realistic urban environments, a scenario that is rapidly gaining interest (K. Jain, et al, 2003). We use structural analysis in two illustrative settings. First, we use it to study the performance of network protocols. Our results indicate that structural analysis of interference graphs that model ad hoc networks can yield a good first order prediction of the overall protocol performance. Second, we study the robustness of a network to random node and edge failures. This study is important in the context of ad hoc networks wherein one expects nodes/edges to fail due various natural or system dependent reasons. The experimental results presented in this paper show the following: (i) structural properties of ad hoc networks depend crucially on the spatial distribution of the nodes. (ii) Structural properties of the network significantly affect the performance of protocols. (iii) Graph theoretic measures can provide good first order insights into the network protocol performance. (iv) The measures are also useful in characterizing the robustness of such networks.

We consider the problem of determining the maximum capacity of the media access (MAC) layer in wireless ad hoc networks. Due to spatial contention for the shared wireless medium, not all nodes can concurrently transmit packets to each other in these networks. The maximum number of possible concurrent transmissions is, therefore, an estimate of the maximum network capacity, and depends on the MAC protocol being used. We show that for a large class of MAC protocols based on virtual carrier sensing using RTS/CTS messages, which includes the popular IEEE 802.11 standard, this problem may be modeled as a maximum Distance-2 matching ( D2EMIS) in the underlying wireless network: Given a graph G(V,E), find a set of edges E'/spl sube/E such that no two edges in E' are connected by another edge in E. D2EMIS is NP-complete. Our primary goal is to show that it can be approximated efficiently in networks that arise in practice. We do this by focusing on an admittedly simplistic, yet natural, graph-theoretic model for ad hoc wireless networks based on disk graphs, where a node can reach all other nodes within some distance (nodes may have unequal reach distances). We show that our approximation yields good capacity bounds. Our work is the first attempt at characterizing an important "maximum" measure of wireless network capacity, and can be used to shed light on previous topology formation protocols like Span and GAF that attempt to produce "good" or "capacity-preserving" topologies, while allowing nodes to alternate between sleep and awake states. Our work shows an efficient way to compute an upper bound on maximum wireless network capacity, thereby allowing topology formation algorithms to determine how close they are to optimal. We also outline a distributed algorithm for the problem for unit disk graphs, and briefly discuss extensions of our results to: 1) different node interference models; 2) directional antennas; and 3) other transceiver connectivity structures besides disk graphs.

We study the interaction between communication protocols, network topology and packet traffic in wireless static radio networks. A particular interest is to empirically characterize the effect of interaction between the routing layer and the MAC layer on overall system performance. Three well-known MAC protocols: 802.11, CSMA and MACA are considered. Similarly three recently proposed routing protocols: AODV, DSR and LAR scheme 1 are considered. The performance of the protocols is measured with regard to three important parameters: (i) number of packets received, (ii) average latency of each packet and (iii) long term fairness. We use a simple statistical technique based on ANOVA (analysis of variance), to characterize the effect of interaction between protocols and various input parameters on network performance. This technique is of independent interest and can be utilized in other simulation studies. Using our methodology, we conclude that different combinations of routing and MAC protocols yield varying performance under varying network topology and traffic situations. Our results show that no combination of routing protocol and MAC protocol is the best over all situations. An important implication of the study is that the performance analysis of protocols at a given level in the protocol stack needs to be studied not locally in isolation but as a part of the complete protocol stack.

We empirically study the effect of mobility and interaction between various input parameters on the performance of protocols designed for wireless ad-hoc networks. An important objective is to study the interaction of the routing and MAC layer protocols under different mobility parameters. We use three basic mobility models: grid mobility model, random waypoint model, and exponential correlated random model. The performance of protocols is measured in terms of various quality of service measures including (i) latency, (ii) throughput, (iii) number of packets received and (iv) long term fairness. Three different commonly studied routing protocols are used: AODV, DSR and LAR scheme 1. Similarly three well known MAC protocols are used: MACA, 802.11 and CSMA.Our main contribution is simulation based experiments coupled with emph rigorous statistical analysis to characterize the emph interaction between the above stated parameters. Such methods allow us to analyze complicated experiments with large input space in a systematic manner. From our results, we conclude the following:

We conduct a comparative experimental analysis of three well known media access protocols: 802.11, CSMA, and MACA for wireless radio networks. Both fixed and ad-hoc networks are considered. The experimental analysis was carried out using GloMoSim: a tool for simulating wireless networks. The main focus of experiments was to study how (i) the size of the network, (ii) number of open connections, (iii) the spatial location of individual connections, (iv) speed with which individual nodes move and (v) protocols higher up in the protocol stack (e,g. routing layer) affect the performance of the media access sublayer protocols. The performance of the protocols was measured w.r.t. three important parameters: (1) number of received packets, (2) average latency of each packet, and (3) throughput. The following general qualitative conclusions were obtained; some of the conclusions reinforce the earlier claims by other researchers. (1) Although 802.11 performs better than the other two protocols with respect to fairness of transmission, packets dropped, and latency, its performance is found to (i) show a lot of variance with changing input parameters and (ii) the overall performance still leaves a lot of room for improvement. (2) CSMA does not perform too well under the fairness criteria, however, was the best in terms of the latency criteria. (3) MACA also shows fairness problems and has poor performance at high packet injection rates. (4) Protocols in the higher level of the protocol stack affect the MAC layer performance. The main general implications of our work is two folds: (1) No single protocol dominated the other protocols across various measures of efficiency. This motivates the design of a new class of parameterized protocols that adapt to changes in the network connectivity and loads. We refer to these class of protocols as parameterized dynamically adaptive efficient protocols and as a first step suggest key design requirements for such a class of protocols. (2) Performance analysis of protocols at a given level in the protocol stack need to be studied not locally in isolation but as a part of the complete protocol stack. The results suggest that in order to improve the performance of a communication network, it will be important to study the entire protocol stuck as a single algorithmic construct; optimizing individual layers in the 7 layer OSI stack will not yield performance improvements beyond a point.

Given an alphabet $\Sigma$, a (directed) graph G whose edges are weighted and $\Sigma$-labeled, and a formal language $L\subseteq\Sigma^*$, the formal-language-constrained shortest/simple path problem consists of finding a shortest (simple) path p in G complying with the additional constraint that l(p) \in L$. Here l(p) denotes the unique word obtained by concatenating the $\Sigma$-labels of the edges along the path p. The main contributions of this paper include the following: We show that the formal-language-constrained shortest path problem is solvable efficiently in polynomial time when L is restricted to be a context-free language (CFL). When L is specified as a regular language we provide algorithms with improved space and time bounds. In contrast, we show that the problem of finding a simple path between a source and a given destination is NP-hard, even when L is restricted to fixed simple regular languages and to very simple classes of graphs (e.g., complete grids). For the class of treewidth-bounded graphs, we show that (i) the problem of finding a regular-language-constrained simple path between source and destination is solvable in polynomial time and (ii) the extension to finding CFL-constrained simple paths is NP-complete. Our results extend the previous results in [SIAM J. Comput., 24 (1995), pp. 1235--1258; Proceedings of the 76th Annual Meeting of the Transportation Research Board, 1997; and Proceedings of the 9th ACM SIGACT-SIGMOD-SIGART Symposium on Database Systems, 1990, pp. 230--242]. Several additional extensions and applications of our results in the context of transportation problems are presented. For instance, as a corollary of our results, we obtain a polynomial-time algorithm for the best k-similar path problem studied in Proceedings of the 76th Annual Meeting of the Transportation Reasearch Board, 1997]. The previous best algorithm was given by [ Proceedings of the 76th Annual Meeting of the Transportation Research Board, 1997] and takes exponential time in the worst case.