Overview

Why GDS

Agent-based simulations are used to understand disease transmission, the spread of social unrest, and the propagation a host of other contagions such as fads, rumors, and influence. Contagions may be spread, for example, by face-to-face interaction and/or electronic means (e.g., social media).

Simulation is an effective way to study these dynamics of contagion spread. Often simulations are carried out on populations that are represented as networks, where vertices represent agents (e.g., people) and edges represent their interactions. Typically, populations are composed of thousands, millions, or even billions of agents, with the result that only a small fraction of the possible dynamics can be evaluated.

53b315e6fc6ea3a2638d3ea2_examples.png

Understanding of system dynamics, provides insights on how to control them. Examples include: How to minimize the spread of epidemics. How to increase the probability that a marketing campaign goes viral. How to spread safety tips among drug users. How to encourage healthy youth behavior (e.g., avoid smoking, excessive drinking).

We model populations of (human) agents and their interactions. Translation from reality to model:

53b31ae4fc6ea3a2638d3ed7_gds%20reality%20to%20model.png

Elements of GDS

Graph of nodes, each has a state. Vertex Functions quantifies when a node changes state, and to what state, based on its neighborhood. Update Scheme defines the ordering of execution the functions. Update Scheme can be sequential: Nodes update one-at-a-time in a prescribed order. Synchronous: Nodes update simultaneously. Block sequential:  generalizes the other two. A primary use:  compute phase space. Set of all state transitions for all possible system states.

GDSCalc Features

The Graph Dynamical Systems Calculator (GDSCalc) is a web-based application within the CINET suite. Unlike most simulators, GDSCalc computes all of the dynamics for a given system, which are represented as a phase space. Consequently, it operates on much smaller networks. GDSCalc provides a user interface to select or create networks, assign models to vertices that describe their behavior, and specify the order in which the dynamics are processed; it also manages data and jobs across users. A computational engine performs the calculations on a cluster, and results are displayed textually and graphically. One of the primary uses of GDSCalc is experimental mathematics, where computed behaviors for smaller networks provide direction for theoretical characterizations of systems in general, even systems with billions of agents.

Videos

Learn how to use GDSCalc using this collection of videos

Video 1: Creating Graphs in list view


Video 2: Drawing graphs


Video 3: Assign model (vertex function) for each node


Video 4: Defining the update scheme, the order in which dynamics are processed


Video 5: Defining the nodes initial states


Video 6: Viewing results


Video 7: Loading existing analysis


Video 8: Using the admin tab for regression testing

Anatomy

53b44127deed0b7164b85f59_GDSC%20architecture%20new.png

Docs  

  • GDSCalc manual (Last updated 4/5/2014) (PDF)
  • GDSCalc: A Web-Based Graph Dynamical Systems Calculator      
    (Presentation for NDSSL Graduate Seminar 4/25/2014)  (PDF) (PPT)
  • GDSCalc: A Web-Based Application for Discrete Graph Dynamical Systems
    (NDSSL Technical Report 14-061  5/24/2014) (PDF)

Publications  

Korkmaz G, Kuhlman C, Marathe A, Marathe M, Vega-Redondo F (2014) Collective Action Through Common Knowledge Using A Facebook Model. In Proceedings of The Thirteenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS). Paris, France, May 5-9 2014.

Kuhlman C, VS Anil Kumar, Marathe M, Ravi SS, Rosenkrantz D (2014) Inhibiting Diffusion of Complex Contagions in Social Networks: Theoretical and Experimental Results, Journal Data Mining and Knowledge Discovery.

Adiga A, Kuhlman C, Mortveit H, Kumar V (2013) Sensitivity of Diffusion Dynamics to Network Uncertainty. In Proceedings of the AAAI-2013. Bellevue, Washington, USA, July 14-18, 2013. (Honorable Mention, Best Paper).

Barrett C, Bisset K, Chandan S, Chen J, Chungbaek Y, Eubank S, Evrenosoglu Y, Lewis B, Lum K, Marathe A, Marathe M, Mortveit H, Parikh N, Phadke A, Reed J, Rivers C, Saha S, Stretz P, Swarup S, Thorpe J, Vullikanti A, Xie D (2013) Planning and Response in the Aftermath of a Large Crisis: An Agent-based Informatics Framework. In Proceedings of the 2013 Winter Simulation Conference. Washington DC, December 8-11, 2013.

Kuhlman C, Kumar VS Anil, Marathe M, Ravi S, Rosenkrantz D, Stearns R (2013) Analysis Problems for Special Classes of Bi-threshold Dynamical Systems. In The 12th International Conference on Autonomous Agents and Multiagent Systems (AA-MAS 2013). Saint Paul, Minnesota, May, 6-10.

Kuhlman C, V. S. Anil Kumar, Ravi SS (2013) Controlling Opinion Propagation in Online Networks, Journal of Computer Networks, Vol. 57, pp. 2121-2132.Kuhlman C, Tuli G, Swarup S, Marathe M, Ravi S (2013) Blocking Simple and Complex Contagion By Edge Removal. In Proceedings of the IEEE International Conference on Data Mining. Dallas, TX, Dec 7-10, 2013.

Mortveit H, Macauley M (2013) An atlas of limit set dynamics for asynchronous elementary cellular automata. Theoretical Computer Science, 504 26-37.Abdelhamid S, Alo R, Arifuzzaman S, Beckman P, Bhuiyan M, Bisset K, Fox E, Fox G, Hall K, Hasan S, Joshi A, Khan M, Kuhlman C, Lee S, Leidig J, Makkapati H, Marathe M, Mortveit H, Qiu J, Ravi S, Shams Z, Sirisaengtaksin O, Subbiah R, Swarup S, Trebon N, Vullikanti A, Zhao Z (2012) CINET: A CyberInfrastructure for Network Science. In The 8th IEEE International Conference on eScience, 2012. Chicago, IL, October 8-12, 2012.

Bisset K, Chen J, Kuhlman C, Kumar V, Marathe M (2011) Interaction-based HPC modeling of social, biological and economic contagions over large networks. In Winter Simulation Conference. Phoenix, AZ, December 2011.

Kuhlman C, Kumar VS Anil, Marathe M, Mortveit H, Swarup S, Tuli G, Ravi S, Rosenkrantz D (2011) A general-purpose graph dynamical system modeling framework. In Proceedings of the 2011 Winter Simulation Conference. Phoenix, Arizona, December 11-14, 2011.

Mortveit H, Murrugarra D, Kuhlman C, Kumar VS Anil (2011) Bifurcations in Boolean Networks. In Discrete Mathematics and Theoretical Computer Science, AP 29-46. Santiago, Chile.

Macauley M, Mortveit H (2010) Update sequence stability in graph dynamical systems. Discrete and Continuous Dynamical Systems S., 4(6): 1533-1541.

Kumar VS Anil, Macauley M, Mortveit H (2009) Limit set reachability in asynchronous graph dynamical systems, Lecture Notes in Computer Science. In Reachability Problems, 5797 217-232.

Macauley M, Mortveit H (2009) Cycle equivalence of graph dynamical systems. Nonlinearity, 22(2): 421-436.

Barrett C, III Hunt H, Marathe M, Ravi S, Rosenkrantz D, Stearns R, Thakur M (2007) Predecessor existence problems for finite discrete dynamical systems. Theoretical Computer Science, 386(1-2): 3-37.

CL Barrett, KR Bisset, SG Eubank, X Feng, MV Marathe EpiSimdemics: an efficient algorithm for simulating the spread of infectious disease over large realistic social networks Proceedings of the 2008 ACM/IEEE conference on Supercomputing, 37

KR Bisset, J Chen, X Feng, VS Kumar, MV Marathe EpiFast: a fast algorithm for large scale realistic epidemic simulations on distributed memory systems Proceedings of the 23rd international conference on Supercomputing, 430-439

S Eubank, VSA Kumar, MV Marathe, A Srinivasan, N Wang Structure of social contact networks and their impact on epidemics DIMACS Series in Discrete Mathematics and Theoretical Computer Science 70, 181

C Barrett, S Eubank, M Marathe Modeling and simulation of large biological, information and socio-technical systems: an interaction based approach Interactive Computation, 353-392

Contact

Thank you!

Your submission has been received!

Oops! Something went wrong while submitting the form :(