Network Analysis of the State Space of Discrete Dynamical Systems

We study networks representing the dynamics of elementary 1D 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 coappearance of nontrivial scaling in both the hub size and the path diversity separates simple dynamics from the more complex behaviors typically found in Wolfram’s class IV and some class III CA.

Figure 1

One connected cluster out of each state space network for different CA, plotted with the program Pajek [21]. All arrows point from leaves towards the center. Sizes are $L=10–13$. For rule 4, the network heterogeneity resides entirely in the size distribution of the different clusters making the state space network.

Figure 2

The largest in-degree $k_{\max }$ as a function of $N=2^L$. Except for class III rules 30, 45, and 150, all CA shown here exhibit clear scaling of the largest hub size $k_{\max }$ with the total number of nodes in the network $N$. Rule 160 is class I, 4 and 50 are class II, and 110 is class IV. Rules 18, 22, and 54 are between III and IV, as they have large structures masked by small-scale chaos (18 and 22) or structures on intermediate scales (54). The analytic values of $\nu$ are 0.8114, 0.6942, 0.5515, 0.4057, 0.3471, 0.4057, and 0.6942 for rules 4, 18, 22, 50, 54, 110, and 160, respectively. These values are in perfect agreement with the numerical results.

Figure 3

Walks on the graph shown on the left generate all preimages of the hub state $\mathcal{H}$ for rule 18. Each step corresponds to an element of the matrix $\mathbf{T}$ shown on the right, with rows and columns labeled in the order 00, 01, 10, 11.

Figure 4

In-degree distribution functions collapsed for simple and complex rules using a multiscaling ansatz for rules 4, 22, and 110 for different system sizes. The black solid line is Eq. (7). The distributions were shifted by 0.5 units each for clarity. Rule 22 is consistent with a power law $P(k)\sim k^{-\gamma }$, with $\gamma \approx 2.8$.

Figure 5

The path diversity $\mathcal{D}$ of different CA. Straight lines indicate scaling $\mathcal{D}\sim N^{\delta }$. Fitted values of $\delta$ are 0.88, 0.88, 0.85, 0.75, and 0.72 for rules 110, 22, 54, 18, and 30, respectively.