Information Technology Reference
In-Depth Information
Since these networks represent the backbone of dynamical interacting systems, it is
very important to investigate how the topology affects the dynamics (for a review see
[14]). It is worth stressing, however, that until now the algorithms for generating a
small world network give rise to a distribution of connectivities.
The presence of long range connections and that of a distribution of connectivities
may both influence the dynamical properties; therefore, in order to disentangle their
roles, in this paper we introduce an algorithm for generating a small world network
from a regular lattice leaving the number of connections for each node unchanged; we
can then leave also the transition function of each node unchanged, and test the effects
of the modification of the topology on the dynamical properties.
We consider here a well-known CA rule, the majority rule (although in this case an
obvious generalization exists when the number of connections changes, this is not so
in general). This rule has been chosen because it has been extensively studied in the
literature on cellular automata and genetic algorithms [15, 16, 17] therefore allowing
comparison with known results for regular lattices.
Among the interesting aspects, let us remark that the small world character
becomes apparent when just a small fraction of long range interactions has been
added, and that the introduction of such interactions affects the number of attractors
and the size of their basins. Moreover, it also affects the duration of the transients,
which may be very important in some open systems.
The outline of the paper is as follows. In Section 2 a short review of definitions and
properties of graphs is given. In Section 3 our algorithm for perturbing a regular
lattice is described, and it is shown that it gives indeed rise to a small world network.
The dynamical properties of the majority rule are analyzed in section 4 as a function
of the number of redirected links. This is only the beginning of a wide research
program, yet it already provides some interesting observations. We do not know the
degree of generality of these observations, which will be the subject of further work.
A brief comment on this is the subject of section 5.
2 Graphs and Cellular Automata: Characteristic Path Length and
Clustering Coefficient
A graph G={V,E} is defined by a set of labelled nodes V={v| v=1 … n} and a set of
edges E
{(a,b)|a=1…n, b= 1…n, b#a}, where an edge is defined as a pair of nodes
(a,b). If the pair is ordered, then the graph is ordered. In the following we will
consider unordered graphs, most generalizations to the case of ordered graphs being
straightforward. An edge (a,b) is said to connect the nodes a and b. Synonyms are
often used, i.e. "vertex" instead of node and "link" instead of edge. Two vertices are
adjacent if there is a link connecting them.
For a recent review on regular, random and small-world graphs, we refer the reader
to [9]. In order to provide a gross characterisation of the topological properties of
different graphs, three quantities play a major role: the average connectivity per node
(k), the characteristic path length (L) and the clustering coefficient (C). Although this
