GDSCalc: A Web-Based Application for Evaluating Discrete Graph Dynamical Systems

Abstract

Discrete dynamical systems are used to model various realistic systems in network science, from social unrest in human populations to regulation in biological networks. A common approach is to model the agents of a system as vertices of a graph, and the pairwise interactions between agents as edges. Agents are in one of a finite set of states at each discrete time step and are assigned functions that describe how their states change based on neighborhood relations. Full characterization of state transitions of one system can give insights into fundamental behaviors of other dynamical systems. In this paper, we describe a discrete graph dynamical systems (GDSs) application called GDSCalc for computing and characterizing system dynamics. It is an open access system that is used through a web interface. We provide an overview of GDS theory. This theory is the basis of the web application; i.e., an understanding of GDS provides an understanding of the software features, while abstracting away implementation details. We present a set of illustrative examples to demonstrate its use in education and research. Finally, we compare GDSCalc with other discrete dynamical system software tools. Our perspective is that no single software tool will perform all computations that may be required by all users; tools typically have particular features that are more suitable for some tasks. We situate GDSCalc within this space of software tools.

Fig 1. Phase spaces for three GDSs.

The bidirected graph X = Circle₄ (top), and the phase spaces of the synchronous GDS; a sequential GDS with update permutation π = (1,2,3,4); and a block sequential GDS with block permutation π _B = ([1, 2],3,4). All vertices use the nor function.

Fig 2. Sequence of high-level user activities to run an analysis in GDSC.

Fig 3. Experimental results generated with GDSC showing the maximum cycle length versus number of graph vertices when the condition Δ = k ₁₀ − k ₀₁ ≤ 1 is minimally violated.

The goal is to produce GDSs that generate larger limit cycles than fixed points. The three tree structures on the left were found experimentally, and results were used to prove that there exist graphs with particular structures that produce limit cycles of any specified size for sequential update (see plot at right). Functional forms of these relationships are given in [8]. These structures differ in the smallest limit cycles they can produce and in the maximum cycle size for a given number of vertices. Data for the sequential update scheme are presented as solid lines; limit cycle size increases without bound for increasing graph size. Data for synchronous update, for all graph structures, is the dashed black curve.

Fig 4. A 3-vertex-state, multi-threshold system where each vertex state transition is governed by a distinct threshold.

Threshold k _ij governs the transition from state i to j.

Fig 5. Results that guided proofs of bifurcations in r-state sequential GDS maps.

When the threshold vector is k = (k ₀₁, k ₁₀, k ₁₂, k ₂₁, k ₀₂, k ₂₀) = (2,3,6,6,4,5), the maximum cycle size ℓ = 1 is fixed for all n of Circle_n because the fixed point conditions do not depend on n. When k ₀₁ is reduced from 2 to 1, the maximum cycle length increases with number of vertices in Circle_n graphs as ℓ = n − 1.

Fig 6. Phase space for a bithreshold sequential GDS and an ergodic set for the attractor graph.

A bithreshold sequential GDS with (k ₀₁, k ₁₀) = (1,3) and permutation π = (1,2,4,3). The four basins of attraction in the phase space are highlighted (top). The resulting attractor graph (bottom) forms an ergodic set (i.e., a strongly connected component) of size 4.

Fig 7. Representative results on ergodic sets generated with the help of GDSC.

The 49-vertex graph X on the left has n _s = 3 subgraphs X _i, 1 ≤ i ≤ n _s, shown in blue, orange, and maroon. There are three results implied by experiments on smaller graphs and theory-based extensions to larger graphs; see text for details. All three of these results significantly extend characterizations of ergodic sets.

Fig 8. Biological network from [5] modeled by GDSC.

Edge weights are given next to edges, and vertex thresholds are specified inside the vertices.