Information Technology Reference
In-Depth Information
Perturbing the Regular Topology of Cellular Automata:
Implications for the Dynamics
Roberto Serra and Marco Villani
Centro Ricerche Ambientali Montecatini, via Ciro Menotti 48
I-48023 Marina di Ravenna (RA)
Abstract. 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.
1 Introduction
Major features of cellular automata (CA) include the locality of the interactions and
the regularity of the topology, which make them well suited to deal e.g. with spatially
extended systems. The CA approach has been used also to model systems (like e.g.
interacting companies in an economy [1] and genetic networks in a cell [2]) where the
topological constraints appear to be somewhat artificial. In these cases, an alternative
approach is that of random networks, where each element (node) is influenced by a
number of other elements chosen at random [3][4][5][6].
Recent researches [7][8][9][10][11] highlighted that several networks of interest
(ranging from biochemical interaction networks to the Internet, from friendship
relations to the World Wide Web, from scientist collaboration to electric power
distribution) show an odd combination of the features of the above systems, i.e. they
have short characteristic path lengths (like random graphs) yet their clustering
coefficients are much higher than those of the random graphs. Theoretical models of
these "small world" networks have also been proposed and their properties have been
investigated. In particular, the Watts-Strogatz (WS) [12] and the scale-free (SF) [13]
models have been the focus of many researches.
Search WWH ::




Custom Search