Coastal flooding poses increasing threats to communities worldwide, necessitating accurate and hyper-local inundation forecasting for effective emergency response. However, real-world deployment of forecasting systems is often constrained by sparse sensor networks, where only a limited subset of locations may have sensors due to budget constraints. To approach this challenge, we present Diff-Sparse, a masked conditional diffusion model designed for probabilistic coastal inundation forecasting from sparse sensor observations. Diff-Sparse primarily utilizes the inundation history of a location and its neighboring locations from a context time window as spatiotemporal context. The fundamental challenge of spatiotemporal prediction based on sparse observations in the context window is addressed by introducing a novel masking strategy during training. Digital elevation data and temporal co-variates are utilized as additional spatial and temporal contexts, respectively. A convolutional neural network and a conditional UNet architecture with cross-attention mechanism are employed to capture the spatiotemporal dynamics in the data. We trained and tested Diff-Sparse on coastal inundation data from the Eastern Shore of Virginia and systematically assessed the performance of Diff-Sparse across different sparsity levels (0%, 50%, 95% missing observations). Our experiment results show that Diff-Sparse achieves upto 62% improvement in terms of two forecasting performance metrics compared to existing methods, at 95% sparsity level. Moreover, our ablation studies reveal that digital elevation data becomes more useful at high sparsity levels compared to temporal co-variates.

Estimating the true prevalence of an epidemic outbreak is a key public health problem. This is challenging because surveillance is usually resource intensive and biased. In the network setting, prior work on cost sensitive disease surveillance has focused on choosing a subset of individuals (or nodes) to minimize objectives such as probability of outbreak detection. Such methods do not give insights into the outbreak size distribution which, despite being complex and multi-modal, is very useful in public health planning. We introduce TESTPREV, a problem of choosing a subset of nodes which maximizes the mutual information with disease prevalence, which directly provides information about the outbreak size distribution. We show that, under the independent cascade (IC) model, solutions computed by all prior disease surveillance approaches are highly sub-optimal for TESTPREV in general. We also show that TESTPREV is hard to even approximate. While this mutual information objective is computationally challenging for general networks, we show that it can be computed efficiently for various network classes. We present a greedy strategy, called GREEDYMI, that uses estimates of mutual information from cascade simulations and thus can be applied on any network and disease model. We find that GREEDYMI does better than natural baselines in terms of maximizing the mutual information as well as reducing the expected variance in outbreak size, under the IC model.

Bibliometric and science-of-science studies have yielded valuable insights into co-authorship and citation networks, yet most analyses rely on static datasets and limited relation types. We introduce a multi-agent AI architecture that orchestrates specialized large language model (LLM) agents (ingestion, extraction, disambiguation, integration, and analysis) to build and query a comprehensive knowledge graph. Ingestion agents unify data from diverse sources such as OpenAlex, ORCID, ROR, USPTO, and custom web scrapers. Extraction agents harness LLMs to parse unstructured text. Disambiguation agents combine rule-based heuristics with LLM reasoning to resolve ambiguous authors and institutions. Integration agents assemble and cache a provenance-rich graph. An analysis agent translates natural language questions into graph queries and interprets results. This end-to-end pipeline produces a rich graph schema spanning authors, institutions, publications, patents, grants, topics, and temporal relations. Researcher mobility and knowledge diffusion are then modeled as timed automata, where each researcher node’s institutional transitions and accumulated attributes (such as publications, collaborators, and topic expertise) enable dynamic temporal reasoning. Results show that our multi-agent, graph-based system consistently outperforms standalone LLMs and research agents on complex temporal queries, entity disambiguation accuracy, and cross-entity reasoning while maintaining competitive efficiency. These capabilities position the system as a foundation for real-time, LLM-assisted knowledge analysis platforms that can support science policy, research evaluation, and meta-scientific inquiry.

Large-scale livestock operations pose significant risks to human health and the environment, while also being vulnerable to threats such as infectious diseases and extreme weather events. As the number of such operations continues to grow, accurate and scalable mapping has become increasingly important. In this work, we present an infrastructure-first, explainable pipeline for identifying and characterizing Concentrated Animal Feeding Operations (CAFOs) from aerial and satellite imagery. Our method (i) detects candidate infrastructure (e.g., barns, feedlots, manure lagoons, silos) with a domain-tuned YOLOv8 detector, then derives SAM2 masks from these boxes and filters component-specific criteria; (ii) extracts structured descriptors (e.g., counts, areas, orientations, and spatial relations) and fuses them with deep visual features using a lightweight spatial cross-attention classifier; and (iii) outputs both CAFO type predictions and mask-level attributions that link decisions to visible infrastructure. Through comprehensive evaluation, we show that our approach achieves state-of-the-art performance, with Swin-B+PRISM-CAFO surpassing the best performing baseline by up to 15%. Beyond strong predictive performance across diverse U.S. regions, we run systematic gradient–activation analyses that quantify the impact of domain priors and show how specific infrastructure (e.g., barns, lagoons) shapes classification decisions. We release code, infrastructure masks, and descriptors to support transparent, scalable monitoring of livestock infrastructure, enabling risk modeling, change detection, and targeted regulatory action. Github: https://github.com/Nibir088/PRISM-CAFO.

Coastal flooding poses significant risks to communities, necessitating fast and accurate forecasting methods to mitigate potential damage. To approach this problem, we present Diff-Flood, a probabilistic spatiotemporal forecasting method designed based on denoising diffusion models. Diff-Flood predicts inundation level at a location by taking spatiotemporal context into account. It utilizes inundation levels at neighboring locations and digital elevation data as spatial context. Inundation history from a context time window, together with additional co-variates are used as temporal context. Convolutional neural networks and cross-attention mechanism are then employed to capture the spatiotemporal dynamics in the data. We trained and tested Diff-Flood on coastal inundation data from the Eastern Shore of Virginia, a region highly impacted by coastal flooding. Our results show that, Diff-Flood outperforms existing forecasting methods in terms of prediction performance (6% to 64% improvement in terms of two performance metrics) and scalability.

We study exascale parallel algorithms for the selection of intervention or monitoring strategies in massive realistic socio-technical networks through scalable Influence Maximization (InfMax) algorithms.We employ novel techniques to enable efficient scaling on up to 8k nodes of OLCF Frontier, with 65k AMD GPUs and 458k AMD CPU cores.Current state-of-the-art InfMax tools are limited to networks with only a few million actors (vertices) and a few hundred million interactions (edges).By overcoming these limitations, ICS '25, June 08-11, 2025, Salt Lake City, UT, USA Minutoli et al.we show that our approach is capable of processing a realistic social contact network of the United States with 285 million nodes and about 8 billion edges.This two ordersof-magnitude improvement over the previous state-of-theart is obtained by leveraging algorithmic advancements for the InfMax problem and designing several problem-specific approaches to overlap communication with computation, improve GPU efficiency, and lower the application's memory requirements.We evaluate strong scaling for computing 10k most influential seeds using up to 8k nodes of an exascale system, and weak scaling from 128 to 8k system nodes for seed sets ranging from 625 to 40k seeds.We achieve the fastest-known runtime of 25 minutes while performing 48 million diffusion simulations totaling 2.31 petabytes to identify 40k influential seeds using 8k nodes, and take 5.75 minutes to identify 10k seeds while using 4k nodes.

Accurate canal network mapping is essential for water management, including irrigation planning and infrastructure maintenance. State-of-the-art semantic segmentation models for infrastructure mapping, such as roads, rely on large, well-annotated remote sensing datasets. However, incomplete or inadequate ground truth can hinder these learning approaches. Many infrastructure networks have graph-level properties such as reachability to a source (like canals) or connectivity (roads) that can be leveraged to improve these existing ground truth. This paper develops a novel iterative framework IGraSS, combining a semantic segmentation module—incorporating RGB and additional modalities (NDWI, DEM)—with a graph-based ground-truth refinement module. The segmentation module processes satellite imagery patches, while the refinement module operates on the entire data viewing the infrastructure network as a graph. Experiments show that IGraSS reduces unreachable canal segments from ~18% to ~3%, and training with refined ground truth significantly improves canal identification. IGraSS serves as a robust framework for both refining noisy ground truth and mapping canal networks from remote sensing imagery. We also demonstrate the effectiveness and generalizability of IGraSS using road networks as an example, applying a different graph-theoretic constraint to complete road networks.

Accurate mapping of irrigation methods is crucial for sustainable agricultural practices and food systems. However, existing models that rely solely on spectral features from satellite imagery are ineffective due to the complexity of agricultural landscapes and limited training data, making this a challenging problem. We present Knowledge-Informed Irrigation Mapping (KIIM), a novel Swin-Transformer based approach that uses (i) a specialized projection matrix to encode crop to irrigation probability, (ii) a spatial attention map to identify agricultural lands from non-agricultural lands, (iii) bi-directional cross-attention to focus complementary information from different modalities, and (iv) a weighted ensemble for combining predictions from images and crop information. Our experimentation on five states in the US shows up to 22.9% (IoU) improvement over baseline with a 71.4% (IoU) improvement for hard-to-classify drip irrigation. In addition, we propose a two-phase transfer learning approach to enhance cross-state irrigation mapping, achieving a 51% IoU boost in a state with limited labeled data. The ability to achieve baseline performance with only 40% of the training data highlights its efficiency, reducing the dependency on extensive manual labeling efforts and making large-scale, automated irrigation mapping more feasible and cost-effective. Code: https://github.com/Nibir088/KIIM

The Russian invasion of Ukraine in February 2022 has led to the largest forced migration crisis in Europe since World War II, with millions displaced both internally and internationally. Among the displaced, approximately 4.2 million individuals have returned, highlighting the significance of return migration as a critical phase in the migration continuum. Existing studies on return migration are limited in scope, relying on survey-based approaches that suffer from demographic bias, lack of validation against ground truth, and inability to account for uncertainty. We propose a novel computational framework for modeling the return of conflict-induced migrants, using agent-based models (ABMs) and their surrogates. These models are grounded in hazard functions and account for sociopolitical contexts. Our proposed ABMs outperform baseline methods in estimating return migration from Poland to Ukraine by at least 42% and by as much as 57% in terms of normalized root mean squared error (NRMSE). Further, to illustrate the utility of such models for policymakers, we conduct two case studies that estimate the duration of displacement and characterize the demographic breakdown among the returnees.

Preventing the spread of infectious diseases requires implementing interventions at various levels of government and evaluating the potential impact and efficacy of those preemptive measures. Agent-based modeling can be used for detailed studies of the spread of such diseases in the presence of possible interventions. The computational cost of modeling epidemic diffusion through large social contact networks necessitates the use of parallel algorithms and resources in order to achieve quick turnaround times. In this work, we present Loimos, a scalable parallel framework for simulating epidemic diffusion. Loimos uses a hybrid of time-stepping and discrete event simulation to model disease spread, and is implemented on top of Charm++, an asynchronous, many-task runtime that enables over-decomposition and adaptive overlap of computation and communication. We demonstrate that Loimos is able to achieve significant speedups while scaling to large core counts. In particular, Loimos is able to simulate 200 days of a COVID19 outbreak on a digital twin of California in about 42 seconds, for an average of 4.6 billion traversed edges per second (TEPS), using 4096 cores on Perlmutter at NERSC.

We introduce IrrMap, the first large-scale dataset (1.1 million patches) for irrigation method mapping across regions. IrrMap consists of multi-resolution satellite imagery from LandSat and Sentinel, along with key auxiliary data such as crop type, land use, and vegetation indices. The dataset spans 1,668,899 farms and 11,443,492 acres across multiple western U.S. states from 2013 to 2023, providing a rich and diverse foundation for irrigation analysis and ensuring geospatial alignment and quality control. The dataset is ML-ready, with standardized 224×224 GeoTIFF patches, the multiple input modalities, carefully chosen train-test-split data, and accompanying dataloaders for seamless deep learning model training and benchmarking in irrigation mapping. The dataset is also accompanied by a complete pipeline for dataset generation, enabling researchers to extend IrrMap to new regions for irrigation data collection or adapt it with minimal effort for other similar applications in agricultural and geospatial analysis. We also analyze the irrigation method distribution across crop groups, spatial irrigation patterns (using Shannon diversity indices), and irrigated area variations for both LandSat and Sentinel, providing insights into regional and resolution-based differences. To promote further exploration, we openly release IrrMap, along with the derived datasets, benchmark models, and pipeline code, through a GitHub repository: https://github.com/Nibir088/IrrMap and Data repository: https://huggingface.co/Nibir/IrrMap, providing comprehensive documentation and implementation details.

The lack of fine-grained, large-scale datasets on water availability presents a critical barrier to applying machine learning (ML) for agricultural water management. Since there are multiple natural and anthropogenic factors that influence water availability, incorporating diverse multimodal features can significantly improve modeling performance. However, integrating such heterogeneous data is challenging due to spatial misalignments, inconsistent formats, semantic label ambiguities, and class imbalances. To address these challenges, we introduce IRRISIGHT, a large-scale, multimodal dataset spanning 20 U.S. states. It consists of 1.4 million pixel-aligned 224×224 patches that fuse satellite imagery with rich environmental attributes. We develop a robust geospatial fusion pipeline that aligns raster, vector, and point-based data on a unified 10m grid, and employ domain-informed structured prompts to convert tabular attributes into natural language. With irrigation type classification as a representative problem, the dataset is AI-ready, offering a spatially disjoint train/test split and extensive benchmarking with both vision and vision–language models. Our results demonstrate that multimodal representations substantially improve model performance, establishing a foundation for future research on water availability.https://github.com/Nibir088/IRRISIGHThttps://huggingface.co/datasets/OBH30/IRRISIGHT

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.

Discrete dynamical systems are commonly used to model the spread of contagions on real-world networks. Under the PAC framework, existing research has studied the problem of learning the behavior of a system, assuming that the underlying network is known. In this work, we focus on a more challenging setting: to learn both the behavior and the underlying topology of a black-box system. We show that, in general, this learning problem is computationally intractable. On the positive side, we present efficient learning methods under the PAC model when the underlying graph of the dynamical system belongs to certain classes. Further, we examine a relaxed setting where the topology of an unknown system is partially observed. For this case, we develop an efficient PAC learner to infer the system and establish the sample complexity. Lastly, we present a formal analysis of the expressive power of the hypothesis class of dynamical systems where both the topology and behavior are unknown, using the well-known Natarajan dimension formalism. Our results provide a theoretical foundation for learning both the topology and behavior of discrete dynamical systems.

Causal effect estimation on a graph of connected units is often complicated by entangled treatments, where the treatment assignment is not independent for each individual. This presents multiple challenges: accurately modeling treatment assignment mechanisms, adjusting for both observed and unobserved confounders to mitigate confounding bias, and constructing instrumental variables to adjust unobserved confounders within a graph structure. Prior research on estimating the causal effects of entangled treatments either assumed no unobserved confounders or relied on the manual selection of IVs, leading to gaps in the methodology. To bridge these gaps and build upon previous work, we introduce the Graph-Disentanglement Instrumental Variable (GDIV) model, a novel approach employing both Graph Neural Networks (GNNs) and Adversarial Networks to assess the causal effects on nodes in a graph, considering observed/unobserved confounders and the intricacies of treatment entanglement. Our GDIV estimator is validated through extensive experiments across synthetic and semisynthetic datasets, demonstrating its better performance over state-of-the-art methods. The ablation studies and robustness experiments verify the benefits of leveraging adversarial networks to generate IVs that satisfy the required assumptions.

Evacuation planning is an essential part of disaster management where the goal is to relocate people under imminent danger to safety. However, finding jointly optimal evacuation routes and a schedule that minimizes the average evacuation time or evacuation completion time, is a computationally hard problem. As a result, large-scale evacuation routing and scheduling continues to be a challenge. In this paper, we present a game-theoretic approach to tackle this problem. We start by formulating a strategic routing and scheduling game, named the Evacuation Game: Routing and Scheduling (EGRES), where players choose their route and time of departure. We show that: (i) every instance of EGRES has at least one pure strategy Nash equilibrium, and (ii) an optimal outcome in an instance will always be an equilibrium in that instance. We then provide bounds on how bad an equilibrium can be compared to an optimal outcome. Additionally, we present a polynomial-time algorithm, the Sequential Action Algorithm (SAA), for finding equilibria in a given instance under a special condition. We use Virginia Beach City in Virginia, and Harris County in Houston, Texas as study areas and construct two EGRES instances. Our results show that, by utilizing SAA, we can efficiently find equilibria in these instances that have social objective close to the optimal value.

Networked dynamical systems are widely used as formal models of real-world cascading phenomena, such as the spread of diseases and information. Prior research has addressed the problem of learning the behavior of an unknown dynamical system when the underlying network has a single layer. In this work, we study the learnability of dynamical systems over multilayer networks, which are more realistic and challenging. First, we present an efficient PAC learning algorithm with provable guarantees to show that the learner only requires a small number of training examples to infer an unknown system. We further provide a tight analysis of the Natarajan dimension which measures the model complexity. Asymptotically, our bound on the Nararajan dimension is tight for almost all multilayer graphs. The techniques and insights from our work provide the theoretical foundations for future investigations of learning problems for multilayer dynamical systems.

During the COVID-19 pandemic, forecasting COVID-19 trends to support planning and response was a priority for scientists and decision makers alike. In the United States, COVID-19 forecasting was coordinated by a large group of universities, companies, and government entities led by the Centers for Disease Control and Prevention and the US COVID-19 Forecast Hub (https://covid19forecasthub.org). We evaluated approximately 9.7 million forecasts of weekly state-level COVID-19 cases for predictions 1-4 weeks into the future submitted by 24 teams from August 2020 to December 2021. We assessed coverage of central prediction intervals and weighted interval scores (WIS), adjusting for missing forecasts relative to a baseline forecast, and used a Gaussian generalized estimating equation (GEE) model to evaluate differences in skill across epidemic phases that were defined by the effective reproduction number. Overall, we found high variation in skill across individual models, with ensemble-based forecasts outperforming other approaches. Forecast skill relative to the baseline was generally higher for larger jurisdictions (e.g., states compared to counties). Over time, forecasts generally performed worst in periods of rapid changes in reported cases (either in increasing or decreasing epidemic phases) with 95% prediction interval coverage dropping below 50% during the growth phases of the winter 2020, Delta, and Omicron waves. Ideally, case forecasts could serve as a leading indicator of changes in transmission dynamics. However, while most COVID-19 case forecasts outperformed a naïve baseline model, even the most accurate case forecasts were unreliable in key phases. Further research could improve forecasts of leading indicators, like COVID-19 cases, by leveraging additional real-time data, addressing performance across phases, improving the characterization of forecast confidence, and ensuring that forecasts were coherent across spatial scales. In the meantime, it is critical for forecast users to appreciate current limitations and use a broad set of indicators to inform pandemic-related decision making.

The SARS-CoV-2 pandemic has generated a considerable number of infections and associated morbidity and mortality across the world. Recovery from these infections, combined with the onset of large-scale vaccination, have led to rapidly-changing population-level immunological landscapes. In turn, these complexities have highlighted a number of important unknowns related to the breadth and strength of immunity following recovery or vaccination. Using simple mathematical models, we investigate the medium-term impacts of waning immunity against severe disease on immuno-epidemiological dynamics. We find that uncertainties in the duration of severity-blocking immunity (imparted by either infection or vaccination) can lead to a large range of medium-term population-level outcomes (i.e. infection characteristics and immune landscapes). Furthermore, we show that epidemiological dynamics are sensitive to the strength and duration of underlying host immune responses; this implies that determining infection levels from hospitalizations requires accurate estimates of these immune parameters. More durable vaccines both reduce these uncertainties and alleviate the burden of SARS-CoV-2 in pessimistic outcomes. However, heterogeneity in vaccine uptake drastically changes immune landscapes toward larger fractions of individuals with waned severity-blocking immunity. In particular, if hesitancy is substantial, more robust vaccines have almost no effects on population-level immuno-epidemiology, even if vaccination rates are compensatorily high among vaccine-adopters. This pessimistic scenario for vaccination heterogeneity arises because those few individuals that are vaccine-adopters are so readily re-vaccinated that the duration of vaccinal immunity has no appreciable consequences on their immune status. Furthermore, we find that this effect is heightened if vaccine-hesitants have increased transmissibility (e.g. due to riskier behavior). Overall, our results illustrate the necessity to characterize both transmission-blocking and severity-blocking immune time scales. Our findings also underline the importance of developing robust next-generation vaccines with equitable mass vaccine deployment.

Despite hundreds of methods published in the literature, forecasting epidemic dynamics remains challenging yet important. The challenges stem from multiple sources, including: the need for timely data, co-evolution of epidemic dynamics with behavioral and immunological adaptations, and the evolution of new pathogen strains. The ongoing COVID-19 pandemic highlighted these challenges; in an important article, Reich et al. did a comprehensive analysis highlighting many of these challenges. In this paper, we take another step in critically evaluating existing epidemic forecasting methods. Our methods are based on a simple yet crucial observation - epidemic dynamics go through a number of phases (waves). Armed with this understanding, we propose a modification to our deployed Bayesian ensembling case time series forecasting framework. We show that ensembling methods employing the phase information and using different weighting schemes for each phase can produce improved forecasts. We evaluate our proposed method with both the currently deployed model and the COVID-19 forecasthub models. The overall performance of the proposed model is consistent across the pandemic but more importantly, it is ranked third and first during two critical rapid growth phases in cases, regimes where the performance of most models from the CDC forecasting hub dropped significantly.

Evolutionary anti-coordination games on networks capture real-world strategic situations such as traffic routing and market competition. Two key problems concerning evolutionary games are the existence of a pure Nash equilibrium (NE) and the convergence time. In this work, we study these two problems for anti-coordination games under sequential and synchronous update schemes. For each update scheme, we examine two decision modes based on whether an agent considers its own previous action (self essential) or not (self non-essential) in choosing its next action. Using a relationship between games and dynamical systems, we show that for both update schemes, finding an NE can be done efficiently under the self non-essential mode but is computationally intractable under the self essential mode. We then identify special cases for which an NE can be obtained efficiently. For convergence time, we show that the dynamics converges in a polynomial number of steps under the synchronous scheme; for the sequential scheme, the convergence time is polynomial only under the self non-essential mode. Through experiments, we empirically examine the convergence time and the equilibria for both synthetic and real-world networks.

Transitioning to clean and low-carbon energy is becoming a crucial goal for many entities in the energy systems sector such as governments, power utilities, and policymakers. This shift to clean energy is supported by a diverse portfolio of data products such as satellite data, smart meter data, power networks, green energy datasets (e.g., solar installations & electric vehicles), microgrid networks, and building stock data. Among these, network datasets are becoming increasingly common in addressing a wide array of issues in residential energy, especially in applications that focus on social good. Thus, streamlining the process of generating different types of networks will be helpful. In this work, we propose a versatile network synthesis and analytics pipeline developed using software design principles that make it modular, scalable, and extensible. Three case studies are presented to illustrate the significance of network data in sustainable energy applications.

Vaccines have proven to be extremely effective in preventing the spread of COVID-19 and potentially ending the pandemic. Lack of access caused many people not getting vaccinated early, so states such as Virginia deployed mobile vaccination sites in order to distribute vaccines across the state. Here we study the problem of deciding where these facilities should be placed and moved over time in order to minimize the distance each person needs to travel in order to be vaccinated. Traditional facility location models for this problem fail to incorporate the fact that our facilities are mobile (i.e., they can move over time). To this end, we instead model vaccine distribution as the Dynamic k-Supplier problem and give the first approximation algorithms for this problem. We then run extensive simulations on real world datasets to show the efficacy of our methods. In particular, we find that natural baselines for Dynamic k-Supplier cannot take advantage of the mobility of the facilities, and perform worse than non-mobile k-Supplier algorithms.

Evacuation planning is a crucial part of disaster management. However, joint optimization of its two essential components, routing and scheduling, with objectives such as minimizing average evacuation time or evacuation completion time, is a computationally hard problem. To approach it, we present MIP-LNS, a scalable optimization method that utilizes heuristic search with mathematical optimization and can optimize a variety of objective functions. We also present the method MIP-LNS-SIM, where we combine agent-based simulation with MIP-LNS to estimate delays due to congestion, as well as, find optimized plans considering such delays. We use Harris County in Houston, Texas, as our study area. We show that, within a given time limit, MIP-LNS finds better solutions than existing methods in terms of three different metrics. However, when congestion dependent delay is considered, MIP-LNS-SIM outperforms MIP-LNS in multiple performance metrics. In addition, MIP-LNS-SIM has a significantly lower percent error in estimated evacuation completion time compared to MIP-LNS.

Compared to previous epidemics, COVID-19 spreads much faster in people gatherings. Thus, we need not only more accurate epidemic spread prediction considering the people gatherings but also more time-efficient prediction for taking actions (e.g., allocating medical equipments) in time. Motivated by this, we analyzed a time-varying people mobility graph of the United States (US) for one year and the effectiveness of previous methods in handling time-varying graphs. We identified several factors that influence COVID-19 spread and observed that some graph changes are transient, which degrades the effectiveness of the previous graph repartitioning and replication methods in distributed graph processing since they generate more time overhead than saved time. Based on the analysis, we propose an accurate and time-efficient Distributed Epidemic Spread Prediction system (DESP). First, DESP incorporates the factors into a previous prediction model to increase the prediction accuracy. Second, DESP conducts repartitioning and replication only when a graph change is stable for a certain time period (predicted using machine learning) to ensure the operation improves time-efficiency. We conducted extensive experiments on Amazon AWS based on real people movement datasets. Experimental results show DESP reduces communication time by up to 52%, while enhancing accuracy by up to 24% compared to existing methods.

We consider the setting of cascades that result from contagion dynamics on large realistic contact networks. We address the question of whether the structural properties of a (partially) observed cascade can characterize the contagion scenario and identify the interventions that might be in effect. Using epidemic spread as a concrete example, we study how social interventions such as compliance in social distancing, extent (and efficacy) of vaccination, and the transmissibility of disease can be inferred. The techniques developed are more generally applicable to other contagions as well.

Infectious disease forecasting has been a key focus in the recent past owing to the COVID-19 pandemic and has proved to be an important tool in controlling the pandemic. With the advent of reliable spatiotemporal data, graph neural network models have been able to successfully model the inter-relation between the cross-region signals to produce quality forecasts, but like most deep-learning models they do not explicitly incorporate the underlying causal mechanisms. In this work, we employ a causal mechanistic model to guide the learning of the graph embeddings and propose a novel learning framework -- Causal-based Graph Neural Network (CausalGNN) that learns spatiotemporal embedding in a latent space where graph input features and epidemiological context are combined via a mutually learning mechanism using graph-based non-linear transformations. We design an attention-based dynamic GNN module to capture spatial and temporal disease dynamics. A causal module is added to the framework to provide epidemiological context for node embedding via ordinary differential equations. Extensive experiments on forecasting daily new cases of COVID-19 at global, US state, and US county levels show that the proposed method outperforms a broad range of baselines. The learned model which incorporates epidemiological context organizes the embedding in an efficient way by keeping the parameter size small leading to robust and accurate forecasting performance across various datasets.

The deployment of vaccines across the US provides significant defense against serious illness and death from COVID-19. Over 70% of vaccine-eligible Americans are at least partially vaccinated, but there are pockets of the population that are under-vaccinated, such as in rural areas and some demographic groups (e.g. age, race, ethnicity). These pockets are extremely susceptible to the Delta variant, exacerbating the healthcare crisis and increasing the risk of new variants. In this paper, we describe a data-driven model that provides real-time support to Virginia public health officials by recommending mobile vaccination site placement in order to target under-vaccinated populations. Our strategy uses fine-grained mobility data, along with US Census and vaccination uptake data, to identify locations that are most likely to be visited by unvaccinated individuals. We further extend our model to choose locations that maximize vaccine uptake among hesitant groups. We show that the top recommended sites vary substantially across some demographics, demonstrating the value of developing customized recommendation models that integrate fine-grained, heterogeneous data sources. We also validate our recommendations by analyzing the success rates of deployed vaccine sites, and show that sites placed closer to our recommended areas administered higher numbers of doses. Our model is the first of its kind to consider evolving mobility patterns in real-time for suggesting placement strategies customized for different targeted demographic groups.

Networked discrete dynamical systems are often used to model the spread of contagions and decision-making by agents in coordination games. Fixed points of such dynamical systems represent configurations to which the system converges. In the dissemination of undesirable contagions (such as rumors and misinformation), convergence to fixed points with a small number of affected nodes is a desirable goal. Motivated by such considerations, we formulate a novel optimization problem of finding a nontrivial fixed point of the system with the minimum number of affected nodes. We establish that, unless P = NP, there is no polynomial-time algorithm for approximating a solution to this problem to within the factor n^(1 - epsilon) for any constant epsilon > 0. To cope with this computational intractability, we identify several special cases for which the problem can be solved efficiently. Further, we introduce an integer linear program to address the problem for networks of reasonable sizes. For solving the problem on larger networks, we propose a general heuristic framework along with greedy selection methods. Extensive experimental results on real-world networks demonstrate the effectiveness of the proposed heuristics. A full version of the manuscript, source code and data are available at: https://github.com/bridgelessqiu/NMIN-FPE

Real-time forecasting of non-stationary time series is a challenging problem, especially when the time series evolves rapidly. For such cases, it has been observed that ensemble models consisting of a diverse set of model classes can perform consistently better than individual models. In order to account for the nonstationarity of the data and the lack of availability of training examples, the models are retrained in real-time using the most recent observed data samples. Motivated by the robust performance properties of ensemble models, we developed a Bayesian model averaging ensemble technique consisting of statistical, deep learning, and compartmental models for fore-casting epidemiological signals, specifically, COVID-19 signals. We observed the epidemic dynamics go through several phases (waves). In our ensemble model, we observed that different model classes performed differently during the various phases. Armed with this understanding, in this paper, we propose a modification to the ensembling method to employ this phase information and use different weighting schemes for each phase to produce improved forecasts. However, predicting the phases of such time series is a significant challenge, especially when behavioral and immunological adaptations govern the evolution of the time series. We explore multiple datasets that can serve as leading indicators of trend changes and employ transfer entropy techniques to capture the relevant indicator. We propose a phase prediction algorithm to estimate the phases using the leading indicators. Using the knowledge of the estimated phase, we selectively sample the training data from similar phases. We evaluate our proposed methodology on our currently deployed COVID-19 forecasting model and the COVID-19 ForecastHub models. The overall performance of the proposed model is consistent across the pandemic. More importantly, it is ranked second during two critical rapid growth phases in cases, regimes where the performance of most models from the ForecastHub dropped significantly.

Synthetic data is gaining rapid importance in many application domains due to privacy issues, bias, lack, or simply unavailability of real data. It is important that the synthetic data be a good representation of real data for successfully completing the task at hand. Thus, devising characteristic validation metrics is crucial and remains an open problem in many domains (e.g., image generation). Good validation metrics must be able to disentangle the differences between the quality and the variability coverage of the synthetic data. We propose to use a 3-dimensional metric (precision α, recall β, coverage γ) to describe the fidelity and diversity of the synthetic data. In this paper, we improve on existing definitions of precision, recall, and coverage to extend to large scale time series data. Traditional nearest neighbor manifolds from the literature are replaced by unsupervised learning techniques such as clustering to deal with large scale fine resolution time series while computing the validation metrics. The proposed metrics are employed to validate synthetic data in the domain of residential energy demand. In addition, we extend these definitions to datasets that have a natural hierarchical structure. We propose a hierarchical data-tree model in which precision, recall, and coverage can be computed at multiple inherent (and/or custom) levels of groupings of the data.

Evacuation planning is an essential part of disaster management where the goal is to relocate people in a safe and orderly manner. Existing research has shown that such problems are hard to approximate and current methods are difficult to scale to real-life applications. We introduce a notion of fairness and two related objectives while studying evacuation planning, namely: minimizing maximum inconvenience and minimizing average inconvenience. We show that both problems are not just NP-hard to solve exactly, but in fact are NP-hard to approximate. On the positive side, we present a heuristic optimization method MIP-LNS, based on the well-known Large Neighborhood Search framework, that can find good approximate solutions in reasonable amount of time. We also consider a multi-objective problem where the goal is to minimize both objectives and solve it using MIP-LNS. We use real-world road network and population data from Harris County in Houston, Texas (a region that needed large-scale evacuations in the past), and apply MIP-LNS to calculate evacuation plans for the area. We compare the quality of the plans in terms of evacuation efficiency and fairness. We find that the solutions to the multi-objective problem are superior in both of these aspects. We also perform statistical tests to show that the solutions are significantly different.

Using a discrete dynamical system model, many papers have addressed the problem of learning the behavior (i.e., the local function at each node) of a networked system through active queries, assuming that the network topology is known. We address the problem of inferring both the topology of the network and the behavior of a discrete dynamical system through active queries. We consider two query models studied in the literature, namely the batch model (where all the queries must be submitted together) and the adaptive model (where responses to previous queries can be used in formulating a new query). Our results are for systems where the state of each node is from {0,1} and the local functions are Boolean. We present algorithms to learn the topology and the behavior under both batch and adaptive query models for several classes of dynamical systems. These algorithms use only a polynomial number of queries. We also present experimental results obtained by running our query generation algorithms on synthetic and real-world networks.

Residential consumers have become active participants in the power distribution network after being equipped with residential EV charging provisions. This creates a challenge for the network operator tasked with dispatching electric power to the residential consumers through the existing distribution network infrastructure in a reliable manner. In this paper, we address the problem of scheduling residential EV charging for multiple consumers while maintaining network reliability. An additional challenge is the restricted exchange of information: where the consumers do not have access to network information and the network operator does not have access to consumer load parameters. We propose a distributed framework which generates an optimal EV charging schedule for individual residential consumers based on their preferences and iteratively updates it until the network reliability constraints set by the operator are satisfied. We validate the proposed approach for different EV adoption levels in a synthetically created digital twin of an actual power distribution network. The results demonstrate that the new approach can achieve a higher level of network reliability compared to the case where residential consumers charge EVs based solely on their individual preferences, thus providing a solution for the existing grid to keep up with increased adoption rates without significant investments in increasing grid capacity.

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.

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.

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.

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.

Timely, high-resolution forecasts of infectious disease incidence are useful for policy makers in deciding intervention measures and estimating healthcare resource burden. In this paper, we consider the task of forecasting COVID-19 confirmed cases at the county level for the United States. Although multiple methods have been explored for this task, their performance has varied across space and time due to noisy data and the inherent dynamic nature of the pandemic. We present a forecasting pipeline which incorporates probabilistic forecasts from multiple statistical, machine learning and mechanistic methods through a Bayesian ensembling scheme, and has been operational for nearly 6 months serving local, state and federal policymakers in the United States. While showing that the Bayesian ensemble is at least as good as the individual methods, we also show that each individual method contributes significantly for different spatial regions and time points. We compare our model's performance with other similar models being integrated into CDC-initiated COVID-19 Forecast Hub, and show better performance at longer forecast horizons. Finally, we also describe how such forecasts are used to increase lead time for training mechanistic scenario projections. Our work demonstrates that such a real-time high resolution forecasting pipeline can be developed by integrating multiple methods within a performance-based ensemble to support pandemic response.

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

The COVID-19 pandemic represents the most significant public health disaster since the 1918 influenza pandemic. During pandemics such as COVID-19, timely and reliable spatio-temporal forecasting of epidemic dynamics is crucial. Deep learning-based time series models for forecasting have recently gained popularity and have been successfully used for epidemic forecasting. Here we focus on the design and analysis of deep learning-based models for COVID-19 forecasting. We implement multiple recurrent neural network-based deep learning models and combine them using the stacking ensemble technique. In order to incorporate the effects of multiple factors in COVID-19 spread, we consider multiple sources such as COVID-19 confirmed and death case count data and testing data for better predictions. To overcome the sparsity of training data and to address the dynamic correlation of the disease, we propose clustering-based training for high-resolution forecasting. The methods help us to identify the similar trends of certain groups of regions due to various spatio-temporal effects. We examine the proposed method for forecasting weekly COVID-19 new confirmed cases at county-, state-, and country-level. A comprehensive comparison between different time series models in COVID-19 context is conducted and analyzed. The results show that simple deep learning models can achieve comparable or better performance when compared with more complicated models. We are currently integrating our methods as a part of our weekly forecasts that we provide state and federal authorities.

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

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

The COVID-19 pandemic brought to the forefront an unprecedented need for experts, as well as citizens, to visualize spatio-temporal disease surveillance data. Web application dashboards were quickly developed to fill t his g ap, b ut a ll of these dashboards supported a particular niche view of the pandemic (ie, current status or specific r egions). I n t his paper, we describe our work developing our COVID-19 Surveillance Dashboard, which offers a unique view of the pandemic while also allowing users to focus on the details that interest them. From the beginning, our goal was to provide a simple visual tool for comparing, organizing, and tracking near-real-time surveillance data as the pandemic progresses. In developing this dashboard, we also identified 6 key metrics which we propose as a standard for the design and evaluation of real-time epidemic science dashboards. Our dashboard was one of the first released to the public, and continues to be actively visited. Our own group uses it to support federal, state and local public health authorities, and it is used by individuals worldwide to track the evolution of the COVID-19 pandemic, build their own dashboards, and support their organizations as they plan their responses to the pandemic.

Deep learning classifiers are assisting humans in making decisions and hence the user's trust in these models is of paramount importance. Trust is often a function of constant behavior. From an AI model perspective it means given the same input the user would expect the same output, especially for correct outputs, or in other words consistently correct outputs. This paper studies a model behavior in the context of periodic retraining of deployed models where the outputs from successive generations of the models might not agree on the correct labels assigned to the same input. We formally define consistency and correct-consistency of a learning model. We prove that consistency and correct-consistency of an ensemble learner is not less than the average consistency and correct-consistency of individual learners and correct-consistency can be improved with a probability by combining learners with accuracy not less than the average accuracy of ensemble component learners. To validate the theory using three datasets and two state-of-the-art deep learning classifiers we also propose an efficient dynamic snapshot ensemble method and demonstrate its value. Code for our algorithm is available at https://github.com/christa60/dynens.

The COVID-19 pandemic represents an unprecedented global crisis and serves as a reminder of the social, economic and health burden of infectious diseases. The ongoing trends towards urbanization, global travel, climate change and a generally older and immuno-compromised population continue to make epidemic planning and control challenging. Recent advances in computing, AI, and bigdata have created new opportunities for realizing the vision of real-time epidemic science.

Big graphs (networks) arising in numerous application areas pose significant challengesfor graph analysts as these graphs grow to billions of nodes and edges and are prohibitively large to fit in the main memory. Finding the number of triangles in a graph is an important problem in the mining and analysis of graphs. In this article, we present two efficient MPI-based distributed memory parallel algorithms for counting triangles in big graphs. The first algorithm employs overlapping partitioning and efficient load balancing schemes to provide a very fast parallel algorithm. The algorithm scales well to networks with billions of nodes and can compute the exact number of triangles in a network with 10 billion edges in 16 minutes. The second algorithm divides the network into non-overlapping partitions leading to a space-efficient algorithm. Our results on both artificial and real-world networks demonstrate a significant space saving with this algorithm. We also present a novel approach that reduces communication cost drastically leading the algorithm to both a space- and runtime-efficient algorithm. Further, we demonstrate how our algorithms can be used to list all triangles in a graph and compute clustering coefficients of nodes. Our algorithm can also be adapted to a parallel approximation algorithm using an edge sparsification method.

Influenza-like illness (ILI) is among the most common diseases worldwide. Producing timely, well-informed, and reliable forecasts for ILI is crucial for preparedness and optimal interventions. In this work, we focus on short-term but highresolution forecasting and propose DEFSI (Deep Learning Based Epidemic Forecasting with Synthetic Information), an epidemic forecasting framework that integrates the strengths of artificial neural networks and causal methods. In DEFSI, we build a two-branch neural network structure to take both within-season observations and between-season observations as features. The model is trained on geographically highresolution synthetic data. It enables detailed forecasting when high-resolution surveillance data is not available. Furthermore, the model is provided with better generalizability and physical consistency. Our method achieves comparable/better performance than state-of-the-art methods for short-term ILI forecasting at the state level. For high-resolution forecasting at the county level, DEFSI significantly outperforms the other methods.

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.

Subgraph counting aims to count occurrences of a template T in a given network G (V, E). It is a powerful graph analysis tool and has found real-world applications in diverse domains. Scaling subgraph counting problems is known to be memory bounded and computationally challenging with exponential complexity. Although scalable parallel algorithms are known for several graph problems such as Triangle Counting and PageRank, this is not common for counting complex subgraphs. Here we address this challenge and study connected acyclic graphs or trees. We propose a novel vectorized subgraph counting algorithm, named SUBGRAPH2VEC, as well as both shared memory and distributed implementations: 1) reducing algorithmic complexity by minimizing neighbor traversal; 2) achieving a highly-vectorized implementation upon linear algebra kernels to significantly improve performance and hardware utilization. 3) SUBGRAPH2VEC improves the overall performance over the state-of-the-art work by orders of magnitude and up to 660x on a single node. 4) SUBGRAPH2VEC in distributed mode can scale up the template size to 20 and maintain good strong scalability. 5) enabling portability to both CPU and GPU.

We consider the PAC learnability of the local functions at the vertices of a discrete networked dynamical system, assuming that the underlying network is known. Our focus is on the learnability of threshold functions. We show that several variants of threshold functions are PAC learnable and provide tight bounds on the sample complexity. In general, when the input consists of positive and negative examples, we show that the concept class of threshold functions is not efficiently PAC learnable, unless NP = RP. Using a dynamic programming approach, we show efficient PAC learnability when the number of negative examples is small. We also present an efficient learner which is consistent with all the positive examples and at least (1-1/e) fraction of the negative examples. This algorithm is based on maximizing a submodular function under matroid constraints. By performing experiments on both synthetic and real-world networks, we study how the network structure and sample complexity influence the quality of the inferred system.

Dengue and influenza-like illness (ILI) are two of the leading causes of viral infection in the world and it is estimated that more than half the world's population is at risk for developing these infections. It is therefore important to develop accurate methods for forecasting dengue and ILI incidences. Since data from multiple sources (such as dengue and ILI case counts, electronic health records and frequency of multiple internet search terms from Google Trends) can improve forecasts, standard time series analysis methods are inadequate to estimate all the parameter values from the limited amount of data available if we use multiple sources. In this paper, we use a computationally efficient implementation of the known variable selection method that we call the Autoregressive Likelihood Ratio (ARLR) method. This method combines sparse representation of time series data, electronic health records data (for ILI) and Google Trends data to forecast dengue and ILI incidences. This sparse representation method uses an algorithm that maximizes an appropriate likelihood ratio at every step. Using numerical experiments, we demonstrate that our method recovers the underlying sparse model much more accurately than the lasso method. We apply our method to dengue case count data from five countries/states: Brazil, Mexico, Singapore, Taiwan, and Thailand and to ILI case count data from the United States. Numerical experiments show that our method outperforms existing time series forecasting methods in forecasting the dengue and ILI case counts. In particular, our method gives a 18 percent forecast error reduction over a leading method that also uses data from multiple sources. It also performs better than other methods in predicting the peak value of the case count and the peak time.

Prophylactic interventions such as vaccine allocation are some of the most effective public health policy planning tools. The supply of vaccines, however, is limited and an important challenge is to optimally allocate the vaccines to minimize epidemic impact. This resource allocation question (which we refer to as VaccIntDesign) has multiple dimensions: when, where, to whom, etc. Most of the existing literature in this topic deals with the latter (to whom), proposing policies that prioritize individuals by age and disease risk. However, since seasonal influenza spread has a typical spatial trend, and due to the temporal constraints enforced by the availability schedule, the when and where problems become equally, if not more, relevant. In this paper, we study the VaccIntDesign problem in the context of seasonal influenza spread in the United States. We develop a national scale metapopulation model for influenza that integrates both short and long distance human mobility, along with realistic data on vaccine uptake. We also design GreedyAlloc, a greedy algorithm for allocating the vaccine supply at the state level under temporal constraints and show that such a strategy improves over the current baseline of pro-rata allocation, and the improvement is more pronounced for higher vaccine efficacy and moderate flu season intensity. Further, the resulting strategy resembles a ring vaccination applied spatiallyacross the US.

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.

The problem of inferring unknown parameters of a networked social system is of considerable practical importance. We consider this problem for the independent cascade model using an active query framework. More specifically, given a network whose edge probabilities are unknown, the goal is to infer the probability value on each edge by querying the system. The optimization objective is to use as few queries as possible in carrying out the inference. We present approximation algorithms that provide provably good estimates of edge probabilities. We also present results from an experimental evaluation of our algorithms on several real-world networks.

BACKGROUND: Visualization plays an important role in epidemic time series analysis and forecasting. Viewing time series data plotted on a graph can help researchers identify anomalies and unexpected trends that could be overlooked if the data were reviewed in tabular form; these details can influence a researcher's recommended course of action or choice of simulation models. However, there are challenges in reviewing data sets from multiple data sources - data can be aggregated in different ways (e.g., incidence vs. cumulative), measure different criteria (e.g., infection counts, hospitalizations, and deaths), or represent different geographical scales (e.g., nation, HHS Regions, or states), which can make a direct comparison between time series difficult. In the face of an emerging epidemic, the ability to visualize time series from various sources and organizations and to reconcile these datasets based on different criteria could be key in developing accurate forecasts and identifying effective interventions. Many tools have been developed for visualizing temporal data; however, none yet supports all the functionality needed for easy collaborative visualization and analysis of epidemic data. RESULTS: In this paper, we present EpiViewer, a time series exploration dashboard where users can upload epidemiological time series data from a variety of sources and compare, organize, and track how data evolves as an epidemic progresses. EpiViewer provides an easy-to-use web interface for visualizing temporal datasets either as line charts or bar charts. The application provides enhanced features for visual analysis, such as hierarchical categorization, zooming, and filtering, to enable detailed inspection and comparison of multiple time series on a single canvas. Finally, EpiViewer provides several built-in statistical Epi-features to help users interpret the epidemiological curves. CONCLUSION: EpiViewer is a single page web application that provides a framework for exploring, comparing, and organizing temporal datasets. It offers a variety of features for convenient filtering and analysis of epicurves based on meta-attribute tagging. EpiViewer also provides a platform for sharing data between groups for better comparison and analysis. Our user study demonstrated that EpiViewer is easy to use and fills a particular niche in the toolspace for visualization and exploration of epidemiological data.

Accurate and timely influenza (flu) forecasting has gained significant traction in recent times. If done well, such forecasting can aid in deploying effective public health measures. Unlike other statistical or machine learning problems, however, flu forecasting brings unique challenges and considerations stemming from the nature of the surveillance apparatus and the end utility of forecasts. This article presents a set of considerations for flu forecasters to take into account prior to applying forecasting algorithms.

Random graphs (or networks) have gained a significant increase of interest due to its popularity in modeling and simulating many complex real-world systems. Degree sequence is one of the most important aspects of these systems. Random graphs with a given degree sequence can capture many characteristics like dependent edges and non-binomial degree distribution that are absent in many classical random graph models such as the Erdöos-Rényi graph model. In addition, they have important applications in uniform sampling of random graphs, counting the number of graphs having the same degree sequence, as well as in string theory, random matrix theory, and matching theory. In this paper, we present an OpenMP-based shared-memory parallel algorithm for generating a random graph with a prescribed degree sequence, which achieves a speedup of 20.4 with 32 cores. We also present a comparative study of several structural properties of the random graphs generated by our algorithm with that of the real-world graphs and random graphs generated by other popular methods. One of the steps in our parallel algorithm requires checking the Erdöos-Gallai characterization, i.e., whether there exists a graph obeying the given degree sequence, in parallel. This paper presents a non-trivial parallel algorithm for checking the Erdöos-Gallai characterization, which achieves a speedup of 23 with 32 cores.

We develop a general data-driven methodology that yields network representations of agricultural flows pertaining to the spread of invasive species. The methodology synthesizes sparse, diverse, noisy and incomplete data that is typically available to build realistic spatiotemporal network representations. We illustrate the methodology by modeling the seasonal flow of the tomato crop in Nepal between major domestic markets. Through dynamical analysis of the network, we study its role in the spread of a major pest of tomato, Tuta absoluta, an emerging outbreak in this country. In the absence of high-resolution pest distribution data, we apply a novel ranking-based inference approach to establish that tomato trade is a driving factor in the rapid spread of this pest.

Controlling the spread of infectious diseases in large populations is an important societal challenge. Mathematically, the problem is best captured as a certain class of reaction-diffusion processes (referred to as contagion processes) over appropriate synthesized interaction networks. Agent-based models have been successfully used in the recent past to study such contagion processes. We describe EpiSimdemics, a highly scalable, parallel code written in Charm++ that uses agent-based modeling to simulate disease spreads over large, realistic, co-evolving interaction networks. We present a new parallel implementation of EpiSimdemics that achieves unprecedented strong and weak scaling on different architectures - Blue Waters, Cori and Mira. EpiSimdemics achieves five times greater speedup than the second fastest parallel code in this field. This unprecedented scaling is an important step to support the long term vision of realtime epidemic science. Finally, we demonstrate the capabilities of EpiSimdemics by simulating the spread of influenza over a realistic synthetic social contact network spanning the continental United States (~280 million nodes and 5.8 billion social contacts).

Over the past decades, numerous techniques have been developed to forecast the temporal evolution of epidemic outbreaks. This paper proposes an approach that combines high resolution agent-based models using realistic social contact networks for simulating epidemic evolution with a particle filter based method for assimilation based forecasting. Agent-based modeling using realistic social contact networks provides two key advantages: (i) they capture the causal processes underlying the epidemic and hence are useful to understand the role of interventions on the course of the epidemics - typically time series models cannot capture this and as a result often do not perform well in such situations; (ii) they provide detailed forecast information - this allows us to produce forecast at high levels of temporal, spatial and social granularity. We also propose a new variation of particle filter technique called beam search particle filtering. The modification allows us to more efficiently search the parameter space which is necessitated by the fact that agent-based techniques are computationally expensive. We illustrate our methodology on the synthetic dataset of Ebola provided as a part of the NSF/NIH Ebola forecasting challenge. Our results show the efficacy of the proposed approach and suggest that agent-based causal models can be combined with filtering techniques to yield a new class of assimilation models for infectious disease forecasting.

Real-time monitoring and responses to emerging public health threats rely on the availability of timely surveillance data. During the early stages of an epidemic, the ready availability of line lists with detailed tabular information about laboratory-confirmed cases can assist epidemiologists in making reliable inferences and forecasts. Such inferences are crucial to understand the epidemiology of a specific disease early enough to stop or control the outbreak. However, construction of such line lists requires considerable human supervision and therefore, difficult to generate in real-time. In this paper, we motivate Guided Epidemiological Line List (GELL), the first tool for building automated line lists (in near real-time) from open source reports of emerging disease outbreaks. Specifically, we focus on deriving epidemiological characteristics of an emerging disease and the affected population from reports of illness. GELL uses distributed vector representations (ala word2vec) to discover a set of indicators for each line list feature. This discovery of indicators is followed by the use of dependency parsing based techniques for final extraction in tabular form. We evaluate the performance of GELL against a human annotated line list provided by HealthMap corresponding to MERS outbreaks in Saudi Arabia. We demonstrate that GELL extracts line list features with increased accuracy compared to a baseline method. We further show how these automatically extracted line list features can be used for making epidemiological inferences, such as inferring demographics and symptoms-to-hospitalization period of affected individuals.

Many real-world systems and networks are modeled and analyzed using various random graph models. These models must incorporate relevant properties such as degree distribution and clustering coefficient. Many models, such as the Chung-Lu (CL), stochastic Kronecker, stochastic block model (SBM), and block two-level Erdős-Rényi (BTER) models have been devised to capture those properties. However, the generative algorithms for these models are mostly sequential and take prohibitively long time to generate large-scale graphs. In this paper, we present a novel time and space efficient algorithmic method to generate random graphs using CL, BTER, and SBM models. First, we present an efficient sequential algorithm and an efficient distributed-memory parallel algorithm for the CL model. Our sequential algorithm takes O(m) time and O(Λ) space, where m and Λ are the number of edges and distinct degrees, and our parallel algorithm takes O (m/p + Λ + P) time w.h.p. and O(Λ) space using P processors. These algorithms are almost time optimal since any sequential and parallel algorithms need at least Ω(m) and Ω(m/p) time, respectively. Our algorithms outperform the best known previous algorithms by a significant margin in terms of both time and space. Experimental results on various large-scale networks show that both of our sequential and parallel algorithms require 400–15000 times less memory than the existing sequential and parallel algorithms, respectively, making our algorithms suitable for generating very large-scale networks. Moreover, both of our algorithms are about 3–4 times faster than the existing sequential and parallel algorithms. Finally, we show how our algorithmic method also leads to efficient parallel and sequential algorithms for the SBM and BTER models.

Finding the number of triangles in a graph (network) is an important problem in graph analysis. The number of triangles also has important applications in graph mining. Big graphs emerging from numerous application areas pose a significant challenge for the analysis and mining since these graphs consist of millions, or even billions, of nodes and edges. Graphs of such scale necessitate the development of efficient parallel algorithms. Existing distributed memory parallel algorithms for counting exact triangles are either Map-Reduce or message passing interface (MPI) based. Map-Reduce based algorithms generate prohibitively large intermediate data and do not demonstrate reasonably good runtime efficiency. The MPI based algorithms offer fast computation of the number of triangles. However, the partitioning and load balancing schemes these algorithms employ are static in nature - the partitions are precomputed based on some estimations. In this paper, we present an efficient MPI-based parallel algorithm for counting triangles in large graph. We consider the case where the main memory of each compute node is large enough to contain the entire graph. We observe that for such a case, computation load can be balanced dynamically and present a dynamic load balancing scheme which improves the performance of the algorithm significantly. Our algorithm demonstrates very good speedups and scales to a large number of processors. The algorithm computes the exact number of triangles in a network with 1 billion edges in 2 minutes with only 100 processors. Our results demonstrate that the algorithm is significantly faster than the related algorithms with static partitioning. In fact, for the real-world networks we experimented on, our algorithm achieves at least 2 times runtime efficiency over the fastest algorithm with static load balancing.

Summary form only given, as follows. The H1N1 pandemic of 2009 and the ongoing Ebola outbreak in West Africa serve as a reminder of the social, economic and health burden of infectious diseases. The ongoing trends towards urbanization, global travel, climate change and a generally older and immuno-compromised population continue to make epidemic planning and control challenging. Recent quantitative changes in high performance pervasive computing have created new opportunities for collecting, integrating, analyzing and accessing information related to large urban social systems, disease surveillance and global logistics and supply chains. The advances in network and information science that build on this new capability provide entirely new ways for reasoning and controlling epidemics. In this talk I will overview of the state of the art in computational networked epidemiology with an emphasis on computational thinking and on the development of high performance computing oriented decision-support environments for planning and response in the event of epidemics. I will describe how such systems can be used to support near real-time planning and response during the 2009 H1N1 swine flu and the recent Ebola Outbreak in West Africa. Computational challenges and directions for future research will be discussed.

Cost estimation is crucial in the performance modeling of parallel algorithms and allocation of computational resources on distributed systems. This paper presents a novel methodology for estimating the cost of constrained producer-consumer (CPC) algorithms. In CPC algorithms, the computation is performed by classes of nodes (tasks), separated in time. The methodology combines data flow analysis with communication latencies to determine the production and consumption of data on different processors, which helps in determining the amount of computations and communication. The cost metric that we develop in this paper uses computational imbalances and communication load, and determines a single cost value. The resulting metric is unique, as it provides the first model that targets CPC algorithms. It has wide application in Genetic Algorithms, molecular dynamics, scheduling schemes and computational epidemiology. We provide a general method for determining the application-specific constants of the cost metric. As an example, we extract the constants for EpiSimdemics (a highly scalable contagion simulator), and give guidelines for applying the procedure to other CPC algorithms. Our evaluations show that the cost metric estimated the execution times of a contagion simulator with less than a 6.5% error. The metric can be used in optimal assignment of computational resources.

Cost estimation is crucial for optimizing the performance of parallel algorithms on distributed systems. This paper performs load analysis and cost estimation of constrained producer-consumer (CPC) parallel algorithms. In CPC algorithms, the computation is performed by classes of nodes (tasks), separated in time. For any given CPC problem, the cost can be modelled as a linear combination of computational imbalance components and a communication load. These components can be determined from analysis of the inter-task communication of the algorithm.

Analysis of structural properties and dynamics of networks is currently a central topic in many disciplines including Social Sciences, Biology and Business. CINET, a cyber infrastructure for such studies, introduced the concept of supporting network analysis as a service. The basic idea is to allow experts in various disciplines to focus on obtaining domain-specific insights from the results of network analyses instead of worrying about programming details and allocation of computational resources needed to carry out the analyses. A basic version of CINET was released in May 2012. This paper discusses CINET 2.0, a significantly enhanced version that supports complex network analyses through a web portal. CINET 2.0 has already been used for teaching courses related to Network Science at several US universities. In this paper, we discuss how CINET 2.0 significantly extends CINET 1.0 through enhancements to some components and the addition of new components.

An edge switch is an operation on a network (graph) where two edges are selected randomly and one of their end vertices are swapped with each other. Usually, a sequence of these operations are performed to generate network perturbations having the same degree sequence of the original network. Edge switch operations have important applications in graph theory and network analysis, such as in generating random networks with a given degree sequence, modeling and analyzing dynamic networks (e.g., peer-to-peer networks), studying various dynamic phenomena over a network (e.g., disease dynamics over a social contact network). The growth of real-world networks motivates the need to develop efficient parallel algorithms for performing a large sequence of edge switch operations. The dependencies among successive edge switch operations and the requirement of keeping the graph simple (i.e., no self-loops or parallel edges) as the edges are switched lead to significant challenges in designing a parallel algorithm. Addressing these challenges requires complex synchronization and communication among the processors. In this paper, we present a distributed memory parallel algorithm for switching edges in massive networks (networks with billions of edges) and achieve a speedup factor of 85 with 1024 processors. One of the steps in our edge switch algorithm requires the computation of multinomial random variables in parallel. The paper presents the first non-trivial parallel algorithm for the problem. The algorithm achieves a speedup of 925 using 1024 processors.

Modeling dynamical systems represents an important application class covering a wide range of disciplines including but not limited to biology, chemistry, finance, national security, and health care. Such applications typically involve large-scale, irregular graph processing, which makes them difficult to scale due to the evolutionary nature of their workload, irregular communication and load imbalance. EpiSimdemics is such an application simulating epidemic diffusion in extremely large and realistic social contact networks. It implements a graph-based system that captures dynamics among co-evolving entities. This paper presents an implementation of EpiSimdemics in Charm++ that enables future research by social, biological and computational scientists at unprecedented data and system scales. We present new methods for application-specific processing of graph data and demonstrate the effectiveness of these methods on a Cray XE6, specifically NCSA's Blue Waters system.

We describe ISIS, a high-performance-computing-based application to support computational epidemiology of infectious diseases. ISIS has been developed over the last seven years in close coordination with public health and policy experts. It has been used in a number of important federal planning and response exercises. ISIS grew out of years of experience in developing and using HPC-oriented models of complex socially coupled systems. This identified the guiding principle that complex models will be used by domain experts only if they can do realistic analysis without becoming computing experts.

As recent pandemics such as SARS and the Swine Flu outbreak have shown, diseases spread very fast in today's interconnected world, making public health an important research area. Some of the basic questions are: How can an outbreak be contained before it becomes an epidemic, and what disease surveillance strategies should be implemented? These problems have been studied traditionally using differential equation methods, which are amenable to analysis and closed form solutions. However, these models are based on complete mixing assumptions, which do not hold for realistic populations, thereby limiting their utility.

Modern epidemiological forecasts of common illnesses, such as the flu, rely on both traditional surveillance sources as well as digital surveillance data. However, most published studies have been retrospective. Concurrently, the reports about flu activity generally lags by several weeks and even when published are revised for several weeks more. We posit that effectively handling this uncertainty is one of the key challenges for a real-time prediction system in this sphere. In this paper, we present a detailed prospective analysis on the generation of robust quantitative predictions about temporal trends of flu activity, using several surrogate data sources for 15 Latin American countries. We present our findings about the limitations and possible advantages of correcting the uncertainty associated with official flu estimates. We also compare the prediction accuracy between model-level fusion of different surrogate data sources against data-level fusion. Finally, we present a novel matrix factorization approach using neighborhood embedding to predict flu case counts. Comparing our proposed ensemble method against several baseline methods helps us demarcate the importance of different data sources for the countries under consideration.

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.

Massive networks arising in numerous application areas poses significant challenges for network analysts as these networks grow to billions of nodes and are prohibitively large to fit in the main memory. Finding the number of triangles in a network is an important problem in the analysis of complex networks. Several interesting graph mining applications depend on the number of triangles in the graph. In this paper, we present an efficient MPI-based distributed memory parallel algorithm, called PATRIC, for counting triangles in massive networks. PATRIC scales well to networks with billions of nodes and can compute the exact number of triangles in a network with one billion nodes and 10 billion edges in 16 minutes. Balancing computational loads among processors for a graph problem like counting triangles is a challenging issue. We present and analyze several schemes for balancing load among processors for the triangle counting problem. These schemes achieve very good load balancing. We also show how our parallel algorithm can adapt an existing edge sparsification technique to approximate the number of triangles with very high accuracy. This modification allows us to count triangles in even larger networks.

Eliminating interactions among individuals is an important means of blocking contagion spread, e.g., closing schools during an epidemic or shutting down electronic communication channels during social unrest. We study contagion blocking in networked populations by identifying edges to remove from a network, thus blocking contagion transmission pathways. We formulate various problems to minimize contagion spread and show that some are efficiently solvable while others are formally hard. We also compare our hardness results to those from node blocking problems and show interesting differences between the two. Our main problem is not only hard, but also has no approximation guarantee, unless P=NP. Therefore, we devise a heuristic for the problem and compare its performance to state-of-the-art heuristics from the literature. We show, through results of 12 (network, heuristic) combinations on three real social networks, that our method offers considerable improvement in the ability to block contagions in weighted and unweighted networks. We also conduct a parametric study to understand the limitations of our approach.

Recently, there has been substantial interest in the study of various random networks as mathematical models of complex systems. As these complex systems grow larger, the ability to generate progressively large random networks becomes all the more important. This motivates the need for efficient parallel algorithms for generating such networks. Naive parallelization of the sequential algorithms for generating random networks may not work due to the dependencies among the edges and the possibility of creating duplicate (parallel) edges. In this paper, we present MPI-based distributed memory parallel algorithms for generating random scale-free networks using the preferential-attachment model. Our algorithms scale very well to a large number of processors and provide almost linear speedups. The algorithms can generate scale-free networks with 50 billion edges in 123 seconds using 768 processors.

We describe a first principles based integrated modeling environment to study urban socio-communication networks which represent not just the physical cellular communication network, but also urban populations carrying digital devices interacting with the cellular network. The modeling environment is designed specifically to understand spectrum demand and dynamic cellular network traffic. One of its key features is its ability to support individual-based models at highly resolved spatial and temporal scales. We have instantiated the modeling environment by developing detailed models of population mobility, device ownership, calling patterns and call network. By composing these models using an appropriate in-built workflow, we obtain an integrated model that represents a dynamic socio-communication network for an entire urban region. In contrast with earlier papers that typically use proprietary data, these models use open source and commercial data sets. The dynamic model represents for a normative day, every individual in an entire region, with detailed demographics, a minute-by-minute schedule of each person's activities, the locations where these activities take place, and calling behavior of every individual. As an illustration of the applicability of the modeling environment, we have developed such a dynamic model for Portland, Oregon comprising of approximately 1.6 million individuals. We highlight the unique features of the models and the modeling environment by describing three realistic case studies.

Differentiation of CD4+ T cells into effector or regulatory phenotypes is tightly controlled by the cytokine milieu, complex intracellular signaling networks and numerous transcriptional regulators. We combined experimental approaches and computational modeling to investigate the mechanisms controlling differentiation and plasticity of CD4+ T cells in the gut of mice. Our computational model encompasses the major intracellular pathways involved in CD4+ T cell differentiation into T helper 1 (Th1), Th2, Th17 and induced regulatory T cells (iTreg). Our modeling efforts predicted a critical role for peroxisome proliferator-activated receptor gamma (PPARγ) in modulating plasticity between Th17 and iTreg cells. PPARγ regulates differentiation, activation and cytokine production, thereby controlling the induction of effector and regulatory responses, and is a promising therapeutic target for dysregulated immune responses and inflammation. Our modeling efforts predict that following PPARγ activation, Th17 cells undergo phenotype switch and become iTreg cells. This prediction was validated by results of adoptive transfer studies showing an increase of colonic iTreg and a decrease of Th17 cells in the gut mucosa of mice with colitis following pharmacological activation of PPARγ. Deletion of PPARγ in CD4+ T cells impaired mucosal iTreg and enhanced colitogenic Th17 responses in mice with CD4+ T cell-induced colitis. Thus, for the first time we provide novel molecular evidence in vivo demonstrating that PPARγ in addition to regulating CD4+ T cell differentiation also plays a major role controlling Th17 and iTreg plasticity in the gut mucosa.

This paper presents ENISI Visual, an agent-based simulator for modeling gut immunity to enteric pathogens. Gastrointestinal systems are important for in-taking food and other nutritions and gut immunity is an important part of human immune system. ENISI Visual provides quality visualizations and users can control initial cell concentrations and the simulation speed, take snapshots, and record videos. The cells are represented with different icons and the icons change colors as their states change. Users can observe real-time immune responses, including cell recruitment, cytokine and chemokine secretion and dissipation, random or chemotactic movement, cell-cell interactions, and state changes. The case study clearly shows that users can use ENISI Visual to develop models and run novel and insightful in silico experiments.

Networks are an effective abstraction for representing real systems. Consequently, network science is increasingly used in academia and industry to solve problems in many fields. Computations that determine structure properties and dynamical behaviors of networks are useful because they give insights into the characteristics of real systems. We introduce a newly built and deployed cyberinfrastructure for network science (CINET) that performs such computations, with the following features: (i) it offers realistic networks from the literature and various random and deterministic network generators; (ii) it provides many algorithmic modules and measures to study and characterize networks; (iii) it is designed for efficient execution of complex algorithms on distributed high performance computers so that they scale to large networks; and (iv) it is hosted with web interfaces so that those without direct access to high performance computing resources and those who are not computing experts can still reap the system benefits. It is a combination of application design and cyberinfrastructure that makes these features possible. To our knowledge, these capabilities collectively make CINET novel. We describe the system and illustrative use cases, with a focus on the CINET user.

Here we present the ENteric Immunity Simulator (ENISI), a modeling system for the inflammatory and regulatory immune pathways triggered by microbe-immune cell interactions in the gut. With ENISI, immunologists and infectious disease experts can test and generate hypotheses for enteric disease pathology and propose interventions through experimental infection of an in silico gut. ENISI is an agent based simulator, in which individual cells move through the simulated tissues, and engage in context-dependent interactions with the other cells with which they are in contact. The scale of ENISI is unprecedented in this domain, with the ability to simulate $10^7$ cells for 250 simulated days on 576 cores in one and a half hours, with the potential to scale to even larger hardware and problem sizes. In this paper we describe the ENISI simulator for modeling mucosal immune responses to gastrointestinal pathogens. We then demonstrate the utility of ENISI by recreating an experimental infection of a mouse with Helicobacter pylori 26695. The results identify specific processes by which bacterial virulence factors do and do not contribute to pathogenesis associated with H. pylori strain 26695. These modeling results inform general intervention strategies by indicating immunomodulatory mechanisms such as those used in inflammatory bowel disease may be more appropriate therapeutically than directly targeting specific microbial populations through vaccination or by using antimicrobials.

Relational sub graph analysis, e.g. finding labeled sub graphs in a network, which are isomorphic to a template, is a key problem in many graph related applications. It is computationally challenging for large networks and complex templates. In this paper, we develop SAHAD, an algorithm for relational sub graph analysis using Hadoop, in which the sub graph is in the form of a tree. SAHAD is able to solve a variety of problems closely related with sub graph isomorphism, including counting labeled/unlabeled sub graphs, finding supervised motifs, and computing graph let frequency distribution. We prove that the worst case work complexity for SAHAD is asymptotically very close to that of the best sequential algorithm. On a mid-size cluster with about 40 compute nodes, SAHAD scales to networks with up to 9 million nodes and a quarter billion edges, and templates with up to 12 nodes. To the best of our knowledge, SAHAD is the first such Hadoop based subgraph/subtree analysis algorithm, and performs significantly better than prior approaches for very large graphs and templates. Another unique aspect is that SAHAD is also amenable to running quite easily on Amazon EC2, without needs for any system level optimization.

In this paper we advocate the study of discrete models of social dynamics underadversarial scheduling. The approach we propose forms part of a foundational basis for agenerative approach to social science(Epstein 2007). We highlight the feasibility of the adversarial scheduling approach by using it to study thePrisoners's Dilemma Game with Pavlov update, a dynamics that has already been investigated under random update in Kittock (1994), Dyeret al. (2002), Mossel and Roch (2006) and Dyer and Velumailum (2011). The model is specified by letting players at the nodes of an underlying graphGrepeatedly play the Prisoner's Dilemma against their neighbours. The players adapt their strategies based on the past behaviour of their opponents by applying the so-called win–stay lose–shift strategy. With random scheduling, starting from any initial configuration, the system reaches the fixed point in which all players cooperate with high probability. On the other hand, under adversarial scheduling the following results hold: — A scheduler that can selectbothgame participants can preclude the system from reaching the unique fixed point on most graph topologies. — A non-adaptive scheduler that is only allowed to chooseoneof the participants is no more powerful than a random scheduler. With this restriction, even an adaptive scheduler is not significantly more powerful than the random scheduler, provided it is ‘reasonably fair’.

3G networks are currently overloaded, due to the increasing popularity of various applications for smartphones. Offloading mobile data traffic through opportunistic communications is a promising solution to partially solve this problem, because there is almost no monetary cost for it. We propose to exploit opportunistic communications to facilitate information dissemination in the emerging Mobile Social Networks (MoSoNets) and thus reduce the amount of mobile data traffic. As a case study, we investigate the target-set selection problem for information delivery. In particular, we study how to select the target set with only k users, such that we can minimize the mobile data traffic over cellular networks. We propose three algorithms, called Greedy, Heuristic, and Random, for this problem and evaluate their performance through an extensive trace-driven simulation study. Our simulation results verify the efficiency of these algorithms for both synthetic and real-world mobility traces. For example, the Heuristic algorithm can offload mobile data traffic by up to 73.66 percent for a real-world mobility trace. Moreover, to investigate the feasibility of opportunistic communications for mobile phones, we implement a proof-of-concept prototype, called Opp-off, on Nokia N900 smartphones, which utilizes their Bluetooth interface for device/service discovery and content transfer.

Clinical symptoms of gastrointestinal (GI) infections are often caused by the inflammatory response elicited to eliminate the invading microbe. Here we present ENISI, a simulator of GI immune mechanisms in response to resident commensal bacteria as well as invading pathogens and the effect on host clinical symptoms. ENISI is a tool for identifying treatment strategies that reduce inflammation-induced damage and, at the same time, ensure pathogen removal by allowing one to test plausibility of in vitro observed behavior as explanations for observations in vivo, propose behaviors not yet tested in vitro that could explain these tissue-level observations, and conduct low-cost, preliminary experiments of proposed interventions/ treatments. An example of such application is shown in which we simulate dysentery resulting from B. hyodysenteriae infection and identify aspects of the host immune pathways that lead to continued inflammation-induced tissue damage even after pathogen elimination.

Modeling environments to study epidemic outbreaks can be used as decision support tools by decision makers to support public health policies. However, although the current high performance simulation engines have become adept at rapidly simulating disease diffusion, computational environments for exploring complex mitigation strategies are fairly rudimentary. Interactive simulations provide a natural way to study the complicated co-evolution of disease dynamics and public policies. In this paper, we formalize the problem of interactive simulations and present experimental results based on an interactive simulation platform that we have recently developed.

Large scale realistic simulations of malware on mobile wireless networks have recently become an increasingly important application of high-performance computing. We propose EpiCure - an individual-based, scalable high performance computing oriented modeling environment to study malware propagation over realistic mobile networks. It is designed specifically to work on commodity cluster architectures. EpiCure runs extremely fast for realistic instances that involve: (i) large time-varying networks consisting of millions of heterogeneous individuals with time varying interaction neighborhoods, (ii) dynamic interactions between disease propagation, device behavior, and the exogenous interventions, and (iii) large number of replicated runs necessary for statistically sound estimates about the stochastic epidemic evolution. We find that EpiCure runs several orders of magnitude faster than another comparable simulation tool while delivering similar results. Beyond simple compute speed, EpiCure has been designed so that analysts can easily represent a range of interventions leading to improved human productivity and ease of use. This is an increasingly important metric in high performance computing. We illustrate EpiCure using three case studies that bring out the novel features of EpiCure.

Identifying motifs (or commonly occurring subgraphs/templates) has been found to be useful in a number of applications, such as biological and social networks; they have been used to identify building blocks and functional properties, as well as to characterize the underlying networks. Enumerating subgraphs is a challenging computational problem, and all prior results have considered networks with a few thousand nodes. In this paper, we develop a parallel subgraph enumeration algorithm, ParSE, that scales to networks with millions of nodes. Our algorithm is a randomized approximation scheme, that estimates the subgraph frequency to any desired level of accuracy, and allows enumeration of a class of motifs that extends those considered in prior work. Our approach is based on parallelization of an approach called color coding, combined with a stream based partitioning. We also show that ParSE scales well with the number of processors, over a large range.

To respond to the serious threat of pandemics (e.g. 2009 H1N1 influenza) to human society, we developed Indemics (Interactive Epidemic Simulation), an interactive, data intensive, high performance modeling environment for realtime pandemic planning, situation assessment, and course of action analysis. Indemics was built upon a model of interactive data intensive scientific computation, supporting online interactions between users and simulations and enabling epidemic simulations over detailed social contact networks and realistic representations of complex public policies and intervention strategies.

Large scale realistic epidemic simulations have recently become an increasingly important application of high-performance computing. We propose a parallel algorithm, EpiFast, based on a novel interpretation of the stochastic disease propagation in a contact network. We implement it using a master-slave computation model which allows scalability on distributed memory systems.

Equipping wireless nodes with multiple radios can significantly increase the capacity of wireless networks, by making these radios simultaneously transmit over multiple non-overlapping channels. However, due to the limited number of radios and available orthogonal channels, designing efficient channel assignment and scheduling algorithms in such networks is a major challenge. In this paper, we present provably-good distributed algorithms for simultaneous channel allocation of individual links and packet-scheduling, in software-defined radio (SDR) wireless networks. Our distributed algorithms are very simple to implement, and do not require any coordination even among neighboring nodes. A novel access hash function or random oracle methodology is one of the key drivers of our results. With this access hash function, each radio can know the transmitters' decisions for links in its interference set for each time slot without introducing any extra communication overhead between them. Further, by utilizing the inductive-scheduling technique, each radio can also backoff appropriately to avoid collisions. Extensive simulations demonstrate that our bounds are valid in practice.

Topology control in ad hoc networks is a multi-criteria optimization problem involving (contradictory) objectives of connectivity, interference, and power minimization. Additionally, nodes can be unreliable, which adds another dimension to an already challenging problem. In this paper, we study topology control problems in ad hoc networks under node failures for arbitrary node distributions. We consider a simple and natural stochastic failure model, in which each node can fail independently with a given probability. The topology control problem under stochastic failures is to choose a power level for each node and a subset of edges such that the residual graph (i.e., the graph formed by the nodes which have not failed) is connected and can be scheduled efficiently, with high probability. We develop provably efficient bi-criteria approximation algorithms for this problem that simultaneously minimize power, reduce interference, and ensure that the surviving graph is connected with high probability. Our algorithms can be implemented efficiently in a distributed manner.

We develop a single rounding algorithm for scheduling on unrelated parallel machines; this algorithm works well with the known linear programming-, quadratic programming-, and convex programming-relaxations for scheduling to minimize completion time, makespan, and other well-studied objective functions. This algorithm leads to the following applications for the general setting of unrelated parallel machines: (i) a bicriteria algorithm for a schedule whose weighted completion-time and makespan simultaneously exhibit the current-best individual approximations for these criteria; (ii) better-than-two approximation guarantees for scheduling to minimize the L p norm of the vector of machine-loads, for all 1 < p < ∞; and (iii) the first constant-factor multicriteria approximation algorithms that can handle the weighted completion-time and any given collection of integer L p norms. Our algorithm has a natural interpretation as a melding of linear-algebraic and probabilistic approaches. Via this view, it yields a common generalization of rounding theorems due to Karp et al. [1987] and Shmoys & Tardos [1993], and leads to improved approximation algorithms for the problem of scheduling with resource-dependent processing times introduced by Grigoriev et al. [2007].

We study the problem of total throughput maximization in arbitrary multi-hop wireless networks, with constraints on the total power usage (denoted by PETM), when nodes have the capability to adaptively choose their power levels, which is the case with software defined radio devices. The underlying interference graph changes when power levels change, making PETM a complex cross-layer optimization problem. We develop a linear programming formulation for this problem, that leads to a constant factor approximation to the total throughput rate, for any given bound on the total power usage. Our result is a rigorously provable worst case approximation guarantee, which holds for any instance. Our formulation is generic and can accommodate different interference models and objective functions. We complement our theoretical analysis with simulations and compute the explicit tradeoffs between fairness, total throughput and power usage.

A fundamental problem in wireless networks is to estimate its throughput capacity - given a set of wireless nodes, and a set of connections, what is the maximum rate at which data can be sent on these connections. Most of the research in this direction has focused on either random distributions of points, or has assumed simple graph-based models for wireless interference. In this paper, we study capacity estimation problem using the more general Signal to Interference Plus Noise Ratio (SINR) model for interference, on arbitrary wireless networks. The problem becomes much harder in this setting, because of the non-locality of the SINR model. Recent work by Moscibroda et al. (2006) has shown that the throughput in this model can differ from graph based models significantly. We develop polynomial time algorithms to provably approximate the total throughput in this setting.

We study the throughput capacity of wireless networks which employ (asynchronous) random-access scheduling as opposed to deterministic scheduling. The central question we answer is: how should we set the channel-access probability for each link in the network so that the network operates close to its optimal throughput capacity? We design simple and distributed channel-access strategies for random-access networks which are provably competitive with respect to the optimal scheduling strategy, which is deterministic, centralized, and computationally infeasible. We show that the competitiveness of our strategies are nearly the best achievable via random-access scheduling, thus establishing fundamental limits on the performance of random- access. A notable outcome of our work is that random access compares well with deterministic scheduling when link transmission durations differ by small factors, and much worse otherwise. The distinguishing aspects of our work include modeling and rigorous analysis of asynchronous communication, asymmetry in link transmission durations, and hidden terminals under arbitrary link-conflict based wireless interference models.

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.

The idea of the cognitive network, drawn from previous research in cognitive radios and cross-layer design, is an attempt to address issues of complexity and scalability by allowing the network to self-adapt and reach end-to-end goals. This paper identifies three critical design decisions that must be considered when creating a cognitive network: the behavior of the decision-making elements, amount of computational state available to these elements, and the degree of control they have. To measure the effect of these design tradeoffs, we develop and define a metric called the "price of a feature." This metric is used to quantify the effect of these properties on a cognitive network with the objective of maximizing the lifetime of a multicast flow in a wireless environment. For this cognitive network, we show that the price of selfish behavior and partial control are more significant than the price of ignorance.

Recently, there has been substantial interest in the design of cross-layer protocols for wireless networks. These protocols optimize certain performance metric(s) of interest (e.g. latency, energy, rate) by jointly optimizing the performance of multiple layers of the protocol stack. Algorithm designers often use geometric-graph-theoretic models for radio interference to design such cross-layer protocols. In this paper we study the problem of designing cross-layer protocols for multi-hop wireless networks using a more realistic Signal to Interference plus Noise Ratio (SINR) model for radio interference. The following cross-layer latency minimization problem is studied: Given a set V of transceivers, and a set of source-destination pairs, (i) choose power levels for all the transceivers, (ii) choose routes for all connections, and (iii) construct an end-to-end schedule such that the SINR constraints are satisfied at each time step so as to minimize the make-span of the schedule (the time by which all packets have reached their respective destinations). We present a polynomial-time algorithm with provable worst-case performance guarantee for this cross-layer latency minimization problem. As corollaries of the algorithmic technique we show that a number of variants of the cross-layer latency minimization problem can also be approximated efficiently in polynomial time. Our work extends the results of Kumar et al. (Proc. SODA, 2004) and Moscibroda et al. (Proc. MOBIHOC, 2006). Although our algorithm considers multiple layers of the protocol stack, it can naturally be viewed as compositions of tasks specific to each layer --- this allows us to improve the overall performance while preserving the modularity of the layered structure.

Using shortest paths, the Internet scales very poorly with respect to congestion [2]. Two main reasons for using shortest paths are dilation (or delay) and size of routing tables. As the Internet grows, the small size of routing tables is important for scaling, but it does not require shortest paths. As long as the paths are confluent, the routing table size is unchanged. In this paper we study the confluent capacity of the Internet. We use the preferential attachment model [5] for the Internet, and all-pair uniform demand for the traffic pattern. Our main theoretical result is that the confluent congestion1 is within a logarithmic factor of the optimal splittable congestion and can be achieved using a simple randomized and distributed scheme called Locally Independent Rounding Algorithm (LIRA). We reinforce this result experimentally by employing simulations to demonstrate that for almost all instances the confluent congestion is (nearly) equal to the splittable congestion. Thus we conclude that the Internet scales well using confluent paths. We combine known results on expanders and the expansion properties of the preferential attachment model to show that for almost all Internet-like networks, we can find a confluent flow that simultaneously achieves O(log n)- approximate congestion and O(1)-approximate dilation. We confirm, using simulations, the intuition that confluence does not come at the cost of dilation.

We develop a single rounding algorithm for scheduling on unrelated parallel machines; this algorithm works well with the known linear programming, quadratic programming, and convex programming-relaxations for scheduling to minimize completion time, makespan, and other well-studied objective functions. We obtain the following applications for the general setting of unrelated parallel machines: (i) a bicriteria algorithm for a schedule whose weighted completion-time and makespan simultaneously exhibit the current-best individual approximations for these criteria (3/2 and 2, respectively); (ii) better-than-two approximation guarantees for scheduling under the L/sub p/ norm for all 1 < p < /spl infin/, improving on the 2-approximation algorithms of Azar & Epstein; and (iii) the first constant-factor multicriteria approximation algorithms that handle the weighted completion-time and any given collection of integer L/sub p/ norms. Our algorithm yields a common generalization of rounding theorems due to Karp et al and Shmoys & Tardos; among other applications, this yields an improved approximation for scheduling with resource-dependent processing times studied by Grigoriev et al.

This paper considers two inter-related questions: (i) Given a wireless ad-hoc network and a collection of source-destination pairs {(si,ti)}, what is the maximum throughput capacity of the network, i.e. the rate at which data from the sources to their corresponding destinations can be transferred in the network? (ii) Can network protocols be designed that jointly route the packets and schedule transmissions at rates close to the maximum throughput capacity? Much of the earlier work focused on random instances and proved analytical lower and upper bounds on the maximum throughput capacity. Here, in contrast, we consider arbitrary wireless networks. Further, we study the algorithmic aspects of the above questions: the goal is to design provably good algorithms for arbitrary instances. We develop analytical performance evaluation models and distributed algorithms for routing and scheduling which incorporate fairness, energy and dilation (path-length) requirements and provide a unified framework for utilizing the network close to its maximum throughput capacity.Motivated by certain popular wireless protocols used in practice, we also explore "shortest-path like" path selection strategies which maximize the network throughput. The theoretical results naturally suggest an interesting class of congestion aware link metrics which can be directly plugged into several existing routing protocols such as AODV, DSR, etc. We complement the theoretical analysis with extensive simulations. The results indicate that routes obtained using our congestion aware link metrics consistently yield higher throughput than hop-count based shortest path metrics.

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:

Topology control problems are concerned with the assignment of power values to the nodes of an ad hoc network so that the power assignment leads to a graph topology satisfying some specified properties. This paper considers such problems under several optimization objectives, including minimizing the maximum power and minimizing the total power. A general approach leading to a polynomial algorithm is presented for minimizing maximum power for a class of graph properties called textbf monotone properties. The difficulty of generalizing the approach to properties that are not monotone is discussed. Problems involving the minimization of total power are known to be bf NP -complete even for simple graph properties. A general approach that leads to an approximation algorithm for minimizing the total power for some monotone properties is presented. Using this approach, a new approximation algorithm for the problem of minimizing the total power for obtaining a 2-node-connected graph is obtained. It is shown that this algorithm provides a constant performance guarantee. Experimental results from an implementation of the approximation algorithm are also presented.

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.

We demonstrate how the concepts of algebraic representability and strongly-local reductions developed here and in [20] can be used to characterize the computational complexity/efficient approximability of a number of basic problems and their variants, on various abstract algebraic structures F. These problems include the following:

Motivated by applications in cartography and computer graphics, we study a version of the map-labeling problem that we call the k-Position Map-Labeling Problem: given a set of points in the plane and, for each point, a set of up to k allowable positions, place uniform and nonintersecting labels of maximum size at each point in one of the allowable positions.This version combines an aesthetic criterion and a legibility criterion and comes close to actual practice while generalizing the fixed-point and slider models found in the literature.We then extend our approach to arbitrary positions, obtaining an algorithm that is easy to implement and also dramatically improves the best approximation bounds.We present a general heuristic which runs in time O(n log n+ nlogR*) , where R* is the size of the optimal label, and which guarantees a fixed-ratio approximation for any regular labels.For circular labels, our technique yields a 3.6approximation, a dramatic improvement in the case of arbitrary placement over the previous bound of 19.35 given by Strijk and Wolff [11].Our technique combines several geometric and combinatorial properties, which might be of independent interest.

We conduct an experimental analysis to identify the most computational time consuming fragments of software and hardware that will likely be an integral part of power exchanges in a deregulated environment. The empirical analysis provides insights into the scalability of the system as a function of branch congestion, excess/scarcity of power, average size of multi-lateral contracts, and topology and size of networks. Additionally they yield insights into the reliability, security and stability of electrical networks.

We conduct an experimental analysis of a distributed, randomized algorithm for edge coloring simple undirected graphs. The algorithm is extremely simple, yet, according to the probabilistic analysis, it computes nearly optimal colorings very quickly [12]. We test the algorithm on a number of random as well as non-random graph families.

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.

We study the complexity and the efficient approximability of graph and satisfiability problems when specified using various kinds of periodic specifications studied previously. We obtain two general results. First, we characterize the complexities of several basic generalized CNF satisfiability problems SAT(S), when instances are specified using various kinds of 1- and 2-dimensional periodic specifications. We outline how this characterization can be used to prove a number of new hardness results for periodically specified problems for various complexity classes. As one corollary, we show that a number of basic NP-hard problems become EXPSPACE-hard when inputs are represented using 1-dimensional infinite periodic wide specifications, thereby answering an open question. Second, we outline a simple yet a general technique to devise approximation algorithms with provable worst case performance guarantees for a number of combinatorial problems specified periodically. Our efficient approximation algorithms and schemes are based on extensions of the previous ideas. They provide the first nontrivial collection of natural NEXPTIME-hard problems that have an /spl epsiv/-approximation (or PTAS).

We prove the #P-hardness of the counting problems associated with various satisfiability, graph, and combinatorial problems, when restricted to planar instances. These problems include 3Sat, 1-3Sat, 1-Ex3Sat, Minimum Vertex Cover, Minimum Dominating Set, Minimum Feedback Vertex Set, X3C, Partition Into Triangles, and Clique Cover. We also prove the NP-completeness of the Ambiguous Satisfiability} problems [J. B. Saxe, Two Papers on Graph Embedding Problems, Tech. Report CMU-CS-80-102, Dept. of Computer Science, Carnegie Mellon Univ., Pittsburgh, PA, 1980] and the D P -completeness (with respect to random polynomial reducibility) of the unique satisfiability problems [L. G. Valiant and V. V. Vazirani, NP is as easy as detecting unique solutions, in Proc. 17th ACM Symp. on Theory of Computing, 1985, pp. 458--463] associated with several of the above problems, when restricted to planar instances. Previously, very few #P}-hardness results, no {\sf NP}-hardness results, and no D P -completeness results were known for counting problems, ambiguous satisfiability problems, and unique satisfiability problems, respectively, when restricted to planar instances. Assuming {\sf P \neq $ NP}, one corollary of the above results is that there are no $\epsilon$-approximation algorithms for the problems of maximizing or minimizing a linear objective function subject to a planar system of linear inequality constraints over the integers.

We study the efficient approximability of basic graph and logic problems in the literature when instances are specified hierarchically as in [T. Lengauer, J. Assoc. Comput. Mach., 36(1989), pp. 474--509] or are specified by one-dimensional finite narrow periodic specifications as in [E. Wanke, Paths and cycles in finite periodic graphs, in Lecture Notes in Comp. Sci. 711, Springer-Verlag, New York, 1993, pp. 751--760]. We show that, for most of the problems $\Pi$ considered when specified using k-level-restricted hierarchical specifications or k-narrow periodic specifications, the following hold. Let $\rho$ be any performance guarantee of a polynomial time approximation algorithm for $\Pi$, when instances are specified using standard specifications. Then $\forall \epsilon > 0$, $ \Pi$ has a polynomial time approximation algorithm with performance guarantee $(1 + \epsilon) \rho$. $\Pi$ has a polynomial time approximation scheme when restricted to planar instances. These are the first polynomial time approximation schemes for PSPACE-hard hierarchically or periodically specified problems. Since several of the problems considered are PSPACE-hard, our results provide the first examples of natural PSPACE-hard optimization problems that have polynomial time approximation schemes. This answers an open question in Condon et al. [Chicago J. Theoret. Comput. Sci., 1995, Article 4].

We study the problem of finding small trees. Classical network design problems are considered with the additional constraint that only a specified number k of nodes are required to be connected in the solution. A prototypical example is the kMST problem in which we require a tree of minimum weight spanning at least k nodes in an edge-weighted graph. We show that the kMST problem is NP-hard even for points in the Euclidean plane. We provide approximation algorithms with performance ratio $2\sqrt{k} $ for the general edge-weighted case and $O(k^{1/4} )$ for the case of points in the plane. Polynomial-time exact solutions are also presented for the class of treewidth-bounded graphs, which includes trees, series-parallel graphs, and bounded bandwidth graphs, and for points on the boundary of a convex region in the Euclidean plane. We also investigate the problem of finding short trees and, more generally, that of finding networks with minimum diameter. A simple technique is used to provide a polynomial-time solution for finding k-trees of minimum diameter. We identify easy and hard problems arising in finding short networks using a framework due to T. C. Hu.

Abstract Unit disk graphs are intersection graphs of circles of unit radius in the plane. We present simple and provably good heuristics for a number of classical NP‐hard optimization problems on unit disk graphs. The problems considered include maximum independent set, minimum vertex cover, minimum coloring, and minimum dominating set. We also present an on‐line coloring heuristic which achieves a competitive ratio of 6 for unit disk graphs. Our heuristics do not need a geometric representation of unit disk graphs. Geometric representations are used only in establishing the performance guarantees of the heuristics. Several of our approximation algorithms can be extended to intersection graphs of circles of arbitrary radii in the plane, intersection graphs of regular polygons, and intersection graphs of higher dimensional regular objects.

We study network-design problems with multiple design objectives.In particular, we look at two cost NY 12222.

Abstract We present an O(n2) time‐optimal algorithm for solving the unweighted all‐pair shortest path problem on interval graphs, an important subclass of perfect graphs. An interesting structure called the neighborhood tree is studied and used in the algorithm. This tree is formed by identifying the successive neighborhoods of the vertex labeled last in the graph according to the IG‐ordering.

Ethernet -like local area network links have been studied by a number of researchers. Most of these studies have involved extensive simulation models operating at the level of individual packets. However, as we begin building models of systems built around such links, detailed simulation models are neither necessary, nor cost-effective. Instead, a simple analytical model of the medium should be adequate as a component of the higher level system models. This paper discusses a number of analytical models and identifies a last-in-first-out M/G/1 model with slightly increased service time as one which adequately captures both the mean and the coefficient of variation of the response time. Given any offered load, this model can be used to predict the mean waiting time and its coefficient of variation. These two can be used to construct a suitable 2 stage hyperexponential distribution. Random numbers can then be drawn from this distribution for use as waiting times of individual packets.