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:

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 set K which typically is finite. 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 manner in which the vertex functions are applied to the vertex states. This induces a discrete dynamical system given by a map of the form 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 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 = (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_w : Kⁿ → Kⁿ is the function composition

F_w = F_w(m) o F_w(m-1 ) o ··· o F_w(2) o 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 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.

People

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

Chris Barrett (Virginia Tech)
Bill Chen (Nankai University)
Henryk Fuks (Brock University)
Abdul S. Jarrah (Virginia Tech)
Reinhard Laubenbacher (Virginia Tech)
Matt Macauley (Clemson University)
Madhav V. Marathe (Virginia Tech)
Jon McCammond (UCSB)
Bodo Pareigis (University of Munich)
Christian M. Reidys (Nankai University)

Publications

Please note that access to some articles will require a subscription with the respective publisher. Journal articles:

[J13] M. Macauley, and H.S. Mortveit, Update sequence stability in graph dynamical systems. Discrete and Continuous Dynamical Systems S., 4(6):1533-1541, 2011. (Preprint available at math.DS/0909.1723.)
[J12] M. Macauley, J. McCammond, and H. S. Mortveit. Dynamics groups of asynchronous cellular automata. Journal of Algebraic Combinatorics, 33(1):11-35, 2011 (Preprint available at math.DS/0909.1723.)
[J11] M. Macauley and H.S. Mortveit. Cycle Equivalence of Graph Dynamical Systems. Nonlinearity, 22(2):421-436, 2009. (Preprint available at math.DS/0802.4412.)
[J10] 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.)
[J9] M. Macauley and H.S. Mortveit, On Enumeration of Conjugacy Classes of Coxeter Elements. Proceedings of the American Mathematical Society, 136:4157-4165, 2008. (Preprint available at http://arxiv.org/abs/0711.1140.)
[J8] A.A. Hansson, H.S. Mortveit and C.M. Reidys, On Asynchronous Cellular Automata. Advances in Complex Systems, 8(4):521-538, 2005.
[J7] 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.
[J6] H.S. Mortveit and C.M. Reidys. Reduction of Discrete Dynamical Systems over Graphs. Advances in Complex Systems, 7(1):1-20, 2004.
[J5] 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.
[J4] H.S. Mortveit and C.M. Reidys. Towards a calculus of biological networks Z. Phys. Chem. 216(2):235-247, 2002.
[J3] 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.
[J2] H.S. Mortveit and C.M. Reidys. Discrete, Sequential Dynamical Systems. Discrete Mathematics, 226(1-3):281-295, 2001.
[J1] 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.

Papers in conference proceedings:

[P9] M. Macauley and H. S. Mortveit. Coxeter groups and asynchronous cellular automata, 2010. In Proceedings of the 9th International Conference on Cellular Automata for Research and Industry (ACRI). Lecture Notes in Computer Science, pages 409-418, Heidelberg, 2010, Springer.
[P8] V. S. A. Kumar, M. Macauley, and H. S. Mortveit. Limit set reachability in asynchronous graph dynamical systems. In Reachability Problems (RP) 2009, volume 5797 of Lecture Notes in Computer Science, pages 217-232, Berlin/Heidelberg, 2009. Springer.
[P7] A. D. Blumer, H. [S.] Mortveit, and C. D. Patterson. Formal modeling of process migration. In 2007 International Conference on Field Programmable Logic and Applications, Amsterdam, The Netherlands, pages 104-110, 2007.
[P6] J. L. Tripp, A. AA. Hansson, M. Gokhale, and H. S. Mortveit. Partitioning hardware and software for reconfigurable supercomputing applications: A case study. In Proceedings of the 2005 ACM/IEEE Conference on Supercomputing (SC|05), September 2005.
[P5] A. AA. Hansson, H. S. Mortveit, J. L. Tripp, and M. Gokhale. Urban traffic simulation modeling for reconfigurable hardware. In Proceedings of Industrial Simulation Conference 2005 (ISC'05), pages 291-298, June 2005.
[P4] J. L. Tripp, H. S. Mortveit, A. AA. Hansson, and M. Gokhale. Metropolitan road traffic simulation on fpgas. In Proceedings of the 13th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'05), pages 117-126, April 2005.
[P3] J. L. Tripp, H. S. Mortveit, M. S. Nassr, A. AA. Hansson, and Maya Gokhale. Acceleration of traffic simulation on reconfigurable hardware. In Proceedings of MAPLD04, September 2004. Accepted for inclusion.
[P-e] C. L. Barrett, H. S. Mortveit, and C. M. Reidys. Sequential dynamical systems. In Artificial Life and Robotics, Proceedings of the Sixth International Symposium on Artificial Life and Robotics, Tokyo, January 15-17, 2001, volume 6, pages 167-169, 2002.
[P2] C. L. Barrett, S. Eubank, M. V. Marathe, H. S. Mortveit, and C. M. Reidys. Science and engineering of large scale socio-technical simulations. In Proceedings of the 1st International Conference on Grand Challenges in Simulations, held as part of the Western Simulation Conference, 2002. LA-UR-01-6623.
[P1] C. L. Barrett, B. W. Bush, S. Kopp, H. S. Mortveit, and C. M. Reidys. Sequential dynamical systems and applications to simulations. In 33rd Annual Simulation Symposium, pages 245-252, April 2000.

Books/thesis:

[B2] H.S. Mortveit and C.M. Reidys, An Introduction to Sequential Dynamical Systems, Springer Verlag (Universitext), 2007.
[B1] H. S. Mortveit. Sequential Dynamical Systems. PhD thesis, Norwegian University of Science and Technology, 2000.

Book chapters (peer reviewed):

[BC3] C. L. Barrett, K. Bisset, J. Chen, S. Eubank, B. Lewis, V. S. A. Kumar, M. V. Marathe, and H. S. Mortveit. Interactions Among Human Behavior, Social Networks, and Societal Infrastructures: A Case Study in Computational Epidemiology, pages 477-507. Springer Verlag, 2009. Printed in the UK.
[BC2] R. Laubenbacher, A.S. Jarrah, H.S. Mortveit and S.S. Ravi, A mathematical formalism for agent-based modeling. In Encyclopedia of Complexity and System Science, Springer, 2009. (Preprint available at http://arxiv.org/abs/0801.0249.)
[BC1] C. L. Barrett, K. Bisset, S. Eubank, V. S. A. Kumar, M. V. Marathe, and H. S. Mortveit. Modeling and Simulation of Large Biological, Information and Socio-Technical Systems: An Interaction-Based Approach, volume 64 of Proceedings of Symposia in Applied Mathematics, pages 101-148. American Mathematical Society, 2007.

Technical perspectives (peer reviewed):

[TP1] K. Atkins, C. Barrett, R. Beckman, K. Bisset, J. Chen, S. Eubank, A. Feng, X. Feng, S. Harris, B. Lewis, A. Kumar, M. Marathe, A. Marathe, H. Mortveit, and Stretz P. An interaction based composable architecture for building scalable models of large social, biological, information and technical systems. CT Watch, 4:46-53, 2008.

In preparation/under review:

[IP3] M. Macauley and H.S. Mortveit, Combinatorial Characterizations of Admissible Coxeter Sequences and Their Applications. In preparation, 2010. (Preprint available at http://arxiv.org/abs/0910.4376v1.)
[IP2] V.S. Anil Kumar, M. Macauley, and H. S. Mortveit. Update Order Instability in Graph Dynamical Systems. preprint, 2010.
[IP1] M. Macauley and H. S. Mortveit. Morphisms of sequential dynamical systems. In preparation, 2010.

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