Henning S. Mortveit: Research

[Graph Dynamical Systems | Publications | 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:

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₁, x₂, …,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+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 synchronized so as to induce a discrete dynamical system with map F: Kⁿ → Kⁿ.

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ⁿ → Kⁿ is given by

F(x)_v = f_v(x[v]) .
This class is referred to as generalized CA since 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 = (w₁, w₂, … , w_m) or permutation π = ( π₁, π₂, … π_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₁, x₂, …, x_i-1, f_i(x[i]), x_i+1, …, x_n).
The SDS map F = [F_Y , w] : Kⁿ → Kⁿ is the function composition

[F_Y ,w] = F_w(m) ° F_w(m-1) ° ··· ° F_w(2) ° F_w(1) .
The phase space associated to a dynamical system with with map F: Kⁿ → Kⁿ is the finite (since K is finite) directed graph with vertex set Kⁿ and 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 permutation or word specifying the composition order. The research in this area uses techniques from, e.g. abstract algebra, combinatorics and probability theory to infer phase space properties based on the structure of the system constituents.

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.

Publications

M. Macauley and H.S. Mortveit, On Enumeration of Conjugacy Classes of Coxeter Elements. Proceedings of the American Mathematical Society. In press, February, 2008. (Preprint available at http://arxiv.org/abs/0711.1140.)
M. Macauley and H.S. Mortveit, Cycle Equivalence of Graph Dynamical Systems. February 2008. (Preprint available at http://arxiv.org/abs/0802.4412.)
M. Macauley and H.S. Mortveit, Equivalences on Acyclic Orientations. February 2008. (Preprint available at http://arxiv.org/abs/0709.0291.)
M. Macauley, J. McCammond and H.S. Mortveit, Order Independence in Asynchronous Cellular Automata, Journal of Cellular Automata, 3(1):37-56, 2008. (Preprint available at http://arxiv.org/abs/0707.2360.)
R. Laubenbacher, A.S. Jarrah, H.S. Mortveit and S.S. Ravi, A mathematical formalism for agent-based modeling. February 2008. Accepted for the Encyclopedia of Complexity and System Science, Springer. (Preprint available at http://arxiv.org/abs/0801.0249.)
H.S. Mortveit and C.M. Reidys, An Introduction to Sequential Dynamical Systems, Springer Verlag (Universitext), 2007.
C.L. Barrett, K. Bissett, S. Eubank, M.V. Marathe, V.S.A. Kumar, H.S. Mortveit, Modeling and simulation of large biological, information and socio-technical systems: An interaction-based approach, in Modeling and Simulation of Biological Networks, Proceedings of Symposia in Applied Mathematics, Volume 64, American Mathematical Society, 2007.
A.A. Hansson, H.S. Mortveit and C.M. Reidys, On Asynchronous Cellular Automata. Advances in Complex Systems, 8(4):521-538, 2005.
J. Tripp, A. Hansson, M. Gokhale and H.S. Mortveit, Partitioning hardware and software for reconfigurable supercomputing applications: A case study. Proceedings of the 2005 ACM/IEEE Conference on Supercomputing '05 Industrial, 27-38, 2005.
J. Tripp, A. Hansson, H.S. Mortveit and M. Gokhale, Metropolitan road traffic simulation on FPGAs, IEEE Symposium on Field-Programmable Custom Computing, Machines, 117-126, 2005.
H.S. Mortveit and C.M. Reidys. Reduction of Discrete Dynamical Systems over Graphs. Advances in Complex Systems, 7(1):1-20, 2004.
H.S. Mortveit and C.M. Reidys. Neutral Evolution and Mutation Rates of Sequential Dynamical Systems. Advances in Complex Systems, 7(3-4):395-418, 2004.
C.L. Barrett, H.S. Mortveit, and C.M. Reidys. ETS IV: Sequential Dynamical Systems: fixed points, invertibility and equivalence. Appl. Math. and Comput., 134(1):153-171, 2003.
H.S. Mortveit and C.M. Reidys. Towards a calculus of biological networks Z. Phys. Chem. 216(2):235-247, 2002.
H.S. Mortveit and C.M. Reidys. Discrete, Sequential Dynamical Systems. Discrete Mathematics, 226(1-3):281-295, 2001.
C.L. Barrett, H.S. Mortveit, and C.M. Reidys. Elements of a Theory of Simulation III: Equivalence of SDS. Appl. Math. and Comput., 122(3):325-340, 2001.
C.L. Barrett, H.S. Mortveit and C.M. Reidys. Elements of a Theory of Simulation II: Sequential Dynamical Systems. Appl. Math. and Comput., 107(2-3):121-136, 2000.

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