Complexity Classification Of Cellular Automata Based On Complex Network Analysis

Cellular automata(CA)is a discrete dynamical system and abundant dynamical behaviors axe emerged from its simpler components and interaction laws.According to Wolfram classification,CA rules can be classified as stable,periodic,chaotic and complex.In recent years,the rise of complex network provides a new idea for describing the complex relationship between individuals and multiple individuals.To obtain the complexity classification of CA,we describe CA as a state space network(SSN)and study the local and global properties of network that correspond to the dynamical behaviors of CA by theoretical derivations,experimental simulations and quantitative analysis.Our approach apparently is different from the common methods such as the definitions of complexity and statistical observations of space-time evolution patterns.The main work and conclusions of this thesis are as follows:1.This thesis analyzed the scaling behavior of the maximum degree of SSNs for 88 independent rules as a function of network size.The data analysis showed that power values were related to the spectrum of transition matrix and could not separate simple dynamics from the more complex behaviors.Besides,applied the network proposed by Kayama to distinguish the dynamical behaviors of the CA rule.2.Some properties of the degree and degree distribution for Rule 4 were given.Then,the degree distribution fitting method and the exact calculation method of Rule 4 were deduced.Besides,we analyzed the scaling behaviors of path diversity of state space network for 88 independent rules as a function of network size.The data analysis showed that the power exponents were close to 0.9718 except for rules 30,45,106 and 154.3.The experimental simulations and theoretical derivations indicated that the co-appearance of non-trivial scaling in both hub size and path diversity could not characterize the dynamical complexity.Two important mesoscale parameters for representing the topological characteristics of SSNs were presented:average path length and average ring cycle of attraction.Our quantitative classification results were consistent with Wolfram classification,and could be regarded as a complement to Wolfram classification.