Graph dynamical system

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.

As such, the research typically involves techniques from, e.g., graph theory, combinatorics, algebra, and dynamical systems rather than differential geometry.

The structure of the phase space is governed by the properties of the graph Y, the vertex functions (fi)i, and the update scheme.

The research in this area seeks to infer phase space properties based on the structure of the system constituents.

If, for example, the update scheme consists of applying the vertex functions synchronously one obtains the class of generalized cellular automata (CA).

[2] In this case it is convenient to introduce the Y-local maps Fi constructed from the vertex functions by The SDS map F = [FY , w] : Kn → Kn is the function composition If the update sequence is a permutation one frequently speaks of a permutation SDS to emphasize this point.

From, e.g., the point of view of applications it is interesting to consider the case where one or more of the components of a GDS contains stochastic elements.

Motivating applications could include processes that are not fully understood (e.g. dynamics within a cell) and where certain aspects for all practical purposes seem to behave according to some probability distribution.

There are also applications governed by deterministic principles whose description is so complex or unwieldy that it makes sense to consider probabilistic approximations.

A natural object to study in this regard is the Markov chain on state space induced by this collection of SDS maps.

This specific example with stochastic update sequence illustrates two general facts for such systems: when passing to a stochastic graph dynamical system one is generally led to (1) a study of Markov chains (with specific structure governed by the constituents of the GDS), and (2) the resulting Markov chains tend to be large having an exponential number of states.

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.