PERTURBING THE REGULAR TOPOLOGY OF CELLULAR AUTOMATA: IMPLICATIONS FOR THE DYNAMICS

The topology of Cellular Automata (CA) is that of regular graphs with high clustering coefficients and long characteristic path lengths. The introduction of some long range connections modifies the topology, and it may give rise to small world networks, with high clustering and short path lengths, modifying also the system dynamical properties (attractors, basins of attraction, transient duration). In order to investigate the effects on the dynamics of the introduction of long range connections it is appropriate to keep the number of connections per node constant, while the existing algorithms give rise to nodes with different connectivities. Here we present an algorithm able to re-direct the links without changing the connectivity degree of the nodes. We then analyze the effects of small topological perturbations of a regular lattice upon the system dynamical properties in the case where the transition function is the majority rule; we show that these effects are indeed important and discuss their characteristics.