Shreim, Grassberger (2007)

Authors: Amer Shreim, Peter Grassberger, Walter Nadler, Björn Samuelsson, Joshua E.S. Socolar, and Maya Paczuski
Published in: Physical Review Letters 98, 198701 (May 8, 2007)
More: PDF | arXiv

In this paper we study the dynamics of discrete systems in their state space and explore the relationship between the network topology of the state space and the complexity of dynamics e.g. as classified by Wolfram. The state space of a discrete dynamical system is a directed network where dynamical states are represented as nodes, the nodes are then connected by drawing links (directed) between each node to its image under the dynamical rule. We start our exploration by studying one dimensional cellular automata and found some new and surprising results for the networks of their state spaces. to characterize the networks we looked two measures: (1) the degree of a node (state) which a local measure and (2) a global measure of the heterogeneity of the paths to the attractors -- what we call the "path diversity." For complex dynamics, both exhibit scaling behavior with respect to the system size whereas for simple dynamics one or the other (or both) does not scale. It turns out that a certain critical exponent (the scaling of the maximal hub with network size) can be calculated exactly for each model, even though it is generally irrational.

We study networks representing the dynamics of elementary 1-d cellular automata (CA) on finite lattices. We analyze scaling behaviors of both local and global network properties as a function of system size. The scaling of the largest node in-degree is obtained analytically for a variety of CA including rules 22, 54 and 110. We further define the path diversity as a global network measure. The co-appearance of non-trivial scaling in both hub size and path diversity separates simple dynamics from the more complex behaviors typically found in Wolfram's Class IV and some Class III CA.

@article{shreim2007nas,
title={{Network Analysis of the State Space of Discrete Dynamical Systems}},
author={Shreim, A. and Grassberger, P. and Nadler, W. and Samuelsson, B. and Socolar, J.E.S. and Paczuski, M.},
journal={Physical Review Letters},
volume={98},
number={19},
pages={198701},
year={2007},
publisher={APS}
}