A wide variety of phenomena, such as the spread of diseases, opinions, attitudes and beliefs in social and communication networks can be modeled as a contagion process on a network. As the recent Ebola and Zika outbreaks have shown, understanding how such processes spread, and how to control them are problems of great societal importance. However, despite their ubiquity, and the widespread appreciation of the importance of contagion processes over complex networks, there has been an outstanding need for a systematic and rigorous computational approach for understanding them. For instance, though it was known that the structure of the underlying network has a significant impact on the dynamics, the specific mechanisms were poorly understood. The overall goal of our project was to explore the mathematical and computational foundations of contagions over large social, communication, and organization networks. The specific objectives included analyzing and computing dynamical properties of such system, developing fast algorithms for generating networks and computing their properties, and designing interventions to control the dynamics, e.g., spread of epidemics. We have made significant strides on all of these objectives, as discussed below.

1. As a unifying mathematical framework, we developed the theory of graph dynamical systems, which is able to capture a variety of contagion processes. Our results lead to novel characterizations of the dynamics in terms of network structure for both simple and complex contagions. We have also developed novel models of complex contagion, including a bi-threshold model, which captures phenomena where nodes might revert back to their original states, e.g., in the case of spread of smoking. We have also obtained new results on the sensitivity of dynamics to initial conditions and changes in the network structure.

2. Highly scalable simulation tools for general class of dynamical systems: we have developed novel parallel algorithms to simulate complex and generalized contagion over large complex networks. Turn-around times on the order of 1 to 4 hours are routinely realized for networks with 100,000 nodes and million+ edges. This compares favorably with the several weeks, if not months, generally required to alter and validate a focused simulator for a different diffusion process. These tools are now being made available through CINET, a cyber-infrastructure for network science.

3. Generating and computing properties of massive networks: we have made significant advances in generating massive instances from various random graph models with heterogeneous degree distributions. We have also developed novel algorithms for computing properties such as the number of triangles, trees and other subgraphs, and community detection in networks with billions of edges. Our results often give either the first parallel algorithms for some of these problems, or the first ones to scale to such sizes. Additionally, we have explored different kinds of parallel computing paradigms, and find that the best models depend on the specific problem.

4. Developing interventions to control dynamics: these problems arise in the context of policy planning, and we have developed new rigorous and practical results for a number of models, arising from different application domains. In the context of epidemic spread, we have used a combination of network models and agent based simulations for the first rigorous evaluation of specific policies being discussed in the public health literature, such as paid sick leave. Our results are based on the insights from the impact of the network structure on the dynamics, specifically, properties such as spectral radius and core decomposition. We have also studied game-theoretical aspects, which arise when individual compliance depends on their utilities and incentives.

In addition, our project has had significant broader impacts.

1. NetSE has supported 9 postdoctoral associates including 2 women and 26 graduate students including 6 women from computer science, economics, public health, industrial and systems engineering, mathematics, statistics, and physics, which reflects the multi-disciplinary nature of the project. 

2. Developing tools to support the response to the 2014 Ebola outbreak: we played a crucial role in supporting the outbreak response by the US Department of Defense. Some of the theoretical advances from this project were used in this response. Some of the big challenges during this outbreak were the lack of data and impact of individual and community level behavioral changes. We used the insights from this project to refine our high performance computing based simulations to improve, calibrate and forecast the epidemic spread, and evaluate policies for providing healthcare resources.

3. We have developed a hands-on science exhibit called VirusTracker, where the spread of an epidemic is illustrated using wristbands (a mobile app has also been developed). Players with the wristband are “infected”, and can spread the infection to others by distributing wristbands. This has been deployed at a number of science based events, including the “USA Science and Engineering Festival” (USASEF) in 2010, 2012, 2014 and 2016.

Last Modified: 11/10/2016
Modified by: Madhav V Marathe