Information Technology Reference
In-Depth Information
while L is small with respect to the values they take in case of large f values (which
corresponds to a high degree of randomness).
Fig. 1.
The characteristic path length
L
and the clustering coefficient
C
vs. the fraction of
redirected links f (on the right, a magnification of the small world region). n=1000; k=10; each
point is the average of the values obtained from 10 different networks
4 The Dynamical Properties
In order to study the effects of the topological properties upon the system dynamics
we considered a particular case, i.e. boolean automata whose transition function obeys
the majority rule. The state of cell i at time t+1 equals the state of the majority of its
neighbours at the previous time step. If the number of neighbours is even, then the
state is left unchanged in case of parity. This rule or similar ones have been
extensively studied in the cellular automata literature [15]. It is also related to the so-
called majority problem, which stimulated many researches on the effectiveness of
genetic algorithms [16] and on computational mechanics [17].
It should be made precise that in the following simulations
cell i itself is excluded from the counting, i.e. there is no self-coupling in the
graph
asynchronous updating is always adopted, with a random choice at each time step
of the cell to be updated
the regular topology we start from is that of a 1D ring with k/2 connections on
each side of cell i
At this stage we cannot claim any generality of the results which follow, and we
limit to report the results of the perturbation of the topology on this specific rule.
It is known that, in regular CA, the majority rule with asynchronous updating
admits several fixed point attractors, which can be loosely described as arising from a
division of the cellular space into homogeneous domains [15]. As k is increased, the
size of the domains expands, and their number is reduced. Starting from an initial
