{
  "id": "enwiki-001330771905",
  "slug": "graph-dynamical-system",
  "title": "Graph dynamical system",
  "qid": "",
  "lead": "In mathematics, the concept of graph dynamical systems can be used to capture a wide range of processes taking place on graphs or networks. A major theme in the mathematical and computational analysis of GDSs is to relate their structural properties (e.g. the network connectivity) and the global dynamics that result. The work on GDSs considers finite graphs and finite state spaces. As such, the research typically involves techniques from, e.g., graph theory, combinatorics, algebra, and dynamical systems rather than differential geometry. In principle, one could define and study GDSs over an infinite graph (e.g. cellular automata or probabilistic cellular automata over \\mathbb{Z}^k or interacting particle systems when some randomness is included), as well as GDSs with infinite state space (e.g. \\mathbb{R} as in coupled map lattices); see, for example, Wu. In the following, everything is implicitly assumed to be finite unless stated otherwise.",
  "body": "In mathematics, the concept of graph dynamical systems can be used to capture a wide range of processes taking place on graphs or networks. A major theme in the mathematical and computational analysis of GDSs is to relate their structural properties (e.g. the network connectivity) and the global dynamics that result. The work on GDSs considers finite graphs and finite state spaces. As such, the research typically involves techniques from, e.g., graph theory, combinatorics, algebra, and dynamical systems rather than differential geometry. In principle, one could define and study GDSs over an infinite graph (e.g. cellular automata or probabilistic cellular automata over \\mathbb{Z}^k or interacting particle systems when some randomness is included), as well as GDSs with infinite state space (e.g. \\mathbb{R} as in coupled map lattices); see, for example, Wu. In the following, everything is implicitly assumed to be finite unless stated otherwise. ==Formal definition== A graph dynamical system is constructed from the following components: A finite graph Y with vertex set v[Y] = {1,2, ... , n}. Depending on the context the graph can be directed or undirected. A state x v for each vertex v of Y taken from a finite set K. The system state is the n-tuple x = (x 1 , x 2 , ... , x n ), and x[v] is the tuple consisting of the states associated to the vertices in the 1-neighborhood of v in Y (in some fixed order). A vertex function f v for each vertex v. The vertex function maps the state of vertex v at time t to the vertex state at time t&nbsp;+&nbsp;1 based on the states associated to the 1-neighborhood of v in Y. An update scheme specifying the mechanism by which the mapping of individual vertex states is carried out so as to induce a discrete dynamical system with map F: K n → K n . The phase space associated to a dynamical system with map F: K n → K n is the finite directed graph with vertex set K n and directed edges (x, F(x)). The structure of the phase space is governed by the properties of the graph Y, the vertex functions (f i ) i , and the update scheme. The research in this area seeks to infer phase space properties based on the structure of the system constituents. The analysis has a local-to-global character. F(x)_v = f_v(x[v]) \\;. This class is referred to as generalized cellular automata since the classical or standard cellular automata are typically defined and studied over regular graphs or grids, and the vertex functions are typically assumed to be identical. Example: Let Y be the circle graph on vertices {1,2,3,4} with edges {1,2}, {2,3}, {3,4} and {1,4}, denoted Circ 4 . Let K = {0,1} be the state space for each vertex and use the function nor 3 : K 3 → K defined by nor 3 (x,y,z)&nbsp;=&nbsp;(1&nbsp;+&nbsp;x)(1&nbsp;+&nbsp;y)(1&nbsp;+&nbsp;z) with arithmetic modulo 2 for all vertex functions. Then for example the system state (0,1,0,0) is mapped to (0,&nbsp;0,&nbsp;0,&nbsp;1) using a synchronous update. All the transitions are shown in the phase space below. If the vertex functions are applied asynchronously in the sequence specified by a word w = (w 1 , w 2 , ... , w m ) or permutation \\pi = ( \\pi_1 , \\pi_2,\\dots,\\pi_n ) of v[Y] one obtains the class of Sequential dynamical systems (SDS). In this case it is convenient to introduce the Y-local maps F i constructed from the vertex functions by F_i (x) = (x_1, x_2,\\ldots, x_{i-1}, f_i(x[i]), x_{i+1}, \\ldots , x_n) \\;. The SDS map F = [F Y , w] : K n → K n is the function composition [F_Y ,w] = F_{w(m)} \\circ F_{w(m-1)} \\circ \\cdots \\circ F_{w(2)} \\circ F_{w(1)} \\;. If the update sequence is a permutation one frequently speaks of a permutation SDS to emphasize this point. Example: Let Y be the circle graph on vertices {1,2,3,4} with edges {1,2}, {2,3}, {3,4} and {1,4}, denoted Circ 4 . Let K={0,1} be the state space for each vertex and use the function nor 3 : K 3 → K defined by nor 3 (x,&nbsp;y,&nbsp;z) = (1&nbsp;+&nbsp;x)(1&nbsp;+&nbsp;y)(1&nbsp;+&nbsp;z) with arithmetic modulo 2 for all vertex functions. Using the update sequence (1,2,3,4) then the system state (0,&nbsp;1,&nbsp;0,&nbsp;0) is mapped to (0,&nbsp;0,&nbsp;1,&nbsp;0). All the system state transitions for this sequential dynamical system are shown in the phase space below. One may also consider the case where the vertex functions are stochastic, i.e., function stochastic GDS. For example, Random Boolean networks are examples of function stochastic GDS using a synchronous update scheme and where the state space is K = {0,&nbsp;1}. Finite probabilistic cellular automata (PCA) is another example of function stochastic GDS. In principle the class of Interacting particle systems (IPS) covers finite and infinite PCA, but in practice the work on IPS is largely concerned with the infinite case since this allows one to introduce more interesting topologies on state space. ==Applications== Graph dynamical systems constitute a natural framework for capturing distributed systems such as biological networks and epidemics over social networks, many of which are frequently referred to as complex systems. ==See also== Chemical reaction network theory Dynamic network analysis (a social science topic) Finite-state machine Hopfield network Petri net ==References== ==Further reading== ==External links== Graph Dynamical Systems – A Mathematical Framework for Interaction-Based Systems, Their Analysis and Simulations by Henning Mortveit",
  "categories": [
    "20226755",
    "20350275",
    "23374303"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1330771905",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1767353406.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001330771905",
    "type": "webpage",
    "title": "Graph dynamical system",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/graph-dynamical-system",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          17
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          17
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001330771905",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1330771905",
    "note": "Immutable snapshot enwiki-001330771905"
  }
}