Henning S. Mortveit: Research

[Graph Dynamical Systems | Publications | People | Main Page ]

Graph Dynamical Systems

The term Graph Dynamical Systems (GDS) covers many classes of dynamical systems. Several of these are constructed from the following common structural elements: If, for example, all the vertex maps are applied synchronously one obtains the class of generalized cellular automata  (CA). In this case, the global map F : K nK n is given by

F (x )v = fv (x [v ])  .

This class is referred to as generalized  CA since classical cellular automata are typically defined and studied over regular graphs or grids. If the vertex functions are applied asynchronously in the order specified by some word w = (w1, w2, … , wm) or permutation π = ( π1, π2, … , π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 Fi  constructed from the vertex functions by

Fi (x ) = (x1, x2, … , xi-1 , fi (x []), xi+1 , …, xn).

The SDS map FwK nK n is the function composition

Fw = Fw(m) o Fw(m-1 ) o ··· o Fw(2) o Fw(1)  .

The phase space associated to a dynamical system with with map F : K nK n is the finite (since K  is finite) directed graph with vertex set K n and edges ( x(x ) ). The structure of the phase space is governed by the properties of the graph Y, the vertex functions (fi )i , and the permutation or word specifying the composition order.

The research in this area uses techniques from abstract algebra, combinatorics, graph theory, probability theory and other areas of mathematics to infer phase space properties based on the structure of the system constituents. A common theme in the research is to derive global system properties based on collections of local structural properties.

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.


An alphabetical list of collaborators and some of the people that are or have been involved in this area:


Please note that access to some articles will require a subscription with the respective publisher. Journal articles: Papers in conference proceedings: Books/thesis: Book chapters (peer reviewed): Technical perspectives (peer reviewed): In preparation/under review:

Last updated: Mon Oct 1 12:45:44 EDT 2007