Common knowledge (CK) is a phenomenon where each individual within a group knows the same information and everyone knows that everyone knows the information, infinitely recursively. CK spreads information as a contagion through social networks in ways different from other models like susceptible-infectious-recovered (SIR) model. In a model of CK on Facebook, the biclique serves as the characterizing graph substructure for generating CK, as all nodes within a biclique share CK through their walls. To understand the effects of network structure on CK-based contagion, it is necessary to control the numbers and sizes of bicliques in networks. Thus, learning how to generate these CK networks (CKNs) is important. Consequently, we develop an exponential random graph model (ERGM) that constructs networks while controlling for bicliques. Our method offers powerful prediction and inference, reduces computational costs significantly, and has proven its merit in contagion dynamics through numerical experiments.

There are myriad real-life examples of contagion processes on human social networks, e.g., spread of viruses, information, and social unrest. Also, there are many methods to control or block contagion spread. In this work, we introduce a novel method of blocking contagions that uses nodes from dominating sets (DSs). To our knowledge, this is the first use of DS nodes to block contagions. Finding minimum dominating sets of graphs is an NP-Complete problem, so we generalize a well-known heuristic, enabling us to customize its execution. Our method produces a prioritized list of dominating nodes, which is, in turn, a prioritized list of blocking nodes. Thus, for a given network, we compute this list of blocking nodes and we use it to block contagions for all blocking node budgets, contagion seed sets, and parameter values of the contagion model. We report on computational experiments of the blocking efficacy of our approach using two mined networks. We also demonstrate the effectiveness of our approach by comparing blocking results with those from the high degree heuristic, which is a common standard in blocking studies.

Motivated by a wide range of applications, research on agent-based models of contagion propagation over networks has attracted a lot of attention in the literature. Many of the available software systems for simulating such agent-based models require users to download software, build the executable, and set up execution environments. Further, running the resulting executable may require access to high performance computing clusters. Our work describes an open access software system (NetSimS) that works under the “Modeling and Simulation as a Service” (MSaaS) paradigm. It enables users to run simulations by selecting models and parameter values, initial conditions, and networks through a web interface. The system supports a variety of models and networks with millions of nodes and edges. In addition to the simulator, the system includes components that enable users to choose initial conditions for simulations in a variety of ways, to analyze the data generated through simulations, and to produce plots from the data. We describe the components of NetSimS and carry out a performance evaluation of the system. We also discuss two case studies carried out on large networks using the system. NetSimS is a major component within net.science, a cyberinfrastructure for network science.

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.

Fear of reprisals such as violence and punishment can inhibit citizens from speaking out, or make them more reluctant to act, in opposition to a repressive regime. Protests are one form of opposition, and their growth has been successfully modeled as an inftuence-based contagion process within a social network (representing a population). In these models, an individual joins a protest if a sufficient number of her neighbors has already joined. This required number of neighbors is often called a “threshold.” In this study, we model a regime's ability to suppress protests by instilling fear in a subset of a population, and this fear is manifested by an increase in a person's threshold. We consider different social networks, numbers of seed nodes, and amounts of fear. Through simulations, we present several results. For example, we demonstrate that, for the objective of reducing the size of a protest, inducing fear can be more advantageous than removing nodes from a network.

Families separated by distance face the challenge of limited bonding, affecting their opportunities to connect and sustain their relationships. FamilySong is a domestic Media Space that fosters feelings of togetherness via synchronized music-listening. FamilySong was used in an experiment that ran for six months, with six distributed families. Detailed data collection, e.g. interaction routines and music sharing patterns, was gathered through the system. These data provide interesting insights into the social behavior of families separated by distance and how they connect over those distances. In this work, we built software to analyze the experiment's data. The procedures and insights described in this paper will be useful for other researchers and practitioners involved in Information and Communications Technologies projects, making the FamilySong analysis with this software an exemplar for efficient data analysis.

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.

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.

In this paper, we introduce homophily to a game-theoretic model of collective action (e.g., protests) on Facebook and study the effect of homophily in individuals' willingness to participate in collective action, i.e., their thresholds, on the emergence and spread of collective action. We use a real Facebook network and conduct computational experiments to study contagion dynamics (the size and the speed of diffusion) with respect to the level of homophily.

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.

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

Detecting and forecasting civil unrest events (protests, strikes, etc.) is of key interest to social scientists and policy makers because these events can lead to significant societal and cultural changes. We analyze protest dynamics in six countries of Latin America on a daily level, from November 2012 through August 2014, using multiple data sources that capture social, political and economic contexts within which civil unrest occurs. We use logistic regression models with Lasso to select a sparse feature set from our diverse datasets, in order to predict the probability of occurrence of civil unrest events in these countries. The models contain predictors extracted from social media sites (Twitter and blogs) and news sources, in addition to volume of requests to Tor, a widely-used anonymity network. Two political event databases and country-specific exchange rates are also used. Our forecasting models are evaluated using a Gold Standard Report (GSR), which is compiled by an independent group of social scientists and experts on Latin America. The experimental results, measured by F1-scores, are in the range 0.68 to 0.95, and demonstrate the efficacy of using a multi-source approach for predicting civil unrest. Case studies illustrate the insights into unrest events that are obtained with our methods.

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.

We describe the design, implementation, and evaluation of EMBERS, an automated, 24x7 continuous system for forecasting civil unrest across 10 countries of Latin America using open source indicators such as tweets, news sources, blogs, economic indicators, and other data sources. Unlike retrospective studies, EMBERS has been making forecasts into the future since Nov 2012 which have been (and continue to be) evaluated by an independent T&E team (MITRE). Of note, EMBERS has successfully forecast the June 2013 protests in Brazil and Feb 2014 violent protests in Venezuela. We outline the system architecture of EMBERS, individual models that leverage specific data sources, and a fusion and suppression engine that supports trading off specific evaluation criteria. EMBERS also provides an audit trail interface that enables the investigation of why specific predictions were made along with the data utilized for forecasting. Through numerous evaluations, we demonstrate the superiority of EMBERS over baserate methods and its capability to forecast significant societal happenings.

Simple diffusion processes on networks have been used to model, analyze and predict diverse phenomena such as spread of diseases, information and memes. More often than not, the underlying network data is noisy and sampled. This prompts the following natural question: how sensitive are the diffusion dynamics and subsequent conclusions to uncertainty in the network structure? In this paper, we consider two popular diffusion models: Independent cascade (IC) model and Linear threshold (LT) model. We study how the expected number of vertices that are influenced/infected, for particular initial conditions, are affected by network perturbations. Through rigorous analysis under the assumption of a reasonable perturbation model we establish the following main results. (1) For the IC model, we characterize the sensitivity to network perturbation in terms of the critical probability for phase transition of the network. We find that the expected number of infections is quite stable, unless the transmission probability is close to the critical probability. (2) We show that the standard LT model with uniform edge weights is relatively stable under network perturbations. (3) We study these sensitivity questions using extensive simulations on diverse real world networks and find that our theoretical predictions for both models match the observations quite closely. (4) Experimentally, the transient behavior, i.e., the time series of the number of infections, in both models appears to be more sensitive to network perturbations.

Simple diffusion processes on networks have been used to model, analyze and predict diverse phenomena such as spread of diseases, information and memes. More often than not, the underlying network data is noisy and sampled. This prompts the following natural question: how sensitive are the diffusion dynamics and subsequent conclusions to uncertainty in the network structure? In this paper, we consider two popular diffusion models: Independent cascades (IC) model and Linear threshold (LT) model. We study how the expected number of vertices that are influenced/infected, given some initial conditions, are affected by network perturbation. By rigorous analysis under the assumption of a reasonable perturbation model we establish the following main results. (1) For the IC model, we characterize the susceptibility to network perturbation in terms of the critical probability for phase transition of the network. We find the expected number of infections is quite stable, unless the the transmission probability is close to the critical probability. (2) We show that the standard LT model with uniform edge weights is relatively stable under network perturbations. (3) Empirically, the transient behavior, i.e., the time series of the number of infections, in both models appears to be more sensitive to network perturbations. We also study these questions using extensive simulations on diverse real world networks, and find that our theoretical predictions for both models match the empirical observations quite closely.

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.

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.