Information Technology Reference
In-Depth Information
3 The Algorithm of Minimal Perturbation
The best known models which account for the small world phenomenon are those of
Watts and Strogatz (WS) [12] and the scale free (SF) [13] model. These different
algorithms have nodes with different connectivities: the WS model perturbs a regular
lattice, giving rise to a distribution of connectivities which is approximately
Poissonian, while the SF model is built from the very beginning with a distribution of
connectivitities (which turns out to follow a power law). Besides providing some
long-range connections, the introduction into the graph of some nodes whose
connectivity degree is higher (or smaller) than the average may have two further
effects:
the previous condition of homogeneity among the nodes no longer holds;
the dynamical rule of the node whose connectivity has changed must be
changed, too.
It is impossible to tell in advance whether the consequences of these changes are
more or less important than those due to the introduction of some random long-range
connections in a regular topology like that of a CA. We present here an algorithm
which introduces at random some long range connections, but which doesn't change
the connectivity of any node of the system, and doesn't change the connectedness of
the system. In this way we are able to introduce a topological perturbation into the
system without any other change of the system parameters (number of connections,
transition function, etc.): in this sense, we refer to this algorithm as a "minimal
perturbation algorithm". We will show that it displays the small world phenomenon
for a range of parameter values.
The algorithm, for an arbitrary undirected graph, involves the following steps:
1.
select two nodes (A
1
and A
2
) that are not directly connected to each other;
2.
for each node, select one of the neighbouring ones (B
1
and B
2
nodes);
3.
check the existence of a path that connects B
1
with A
2
, and another path which
connects B
2
with A
1;
these paths don't pass through the other already selected
nodes; if these paths don't exist, return to point 1;
4.
add an edge between A
1
and A
2
and an edge between B
1
and B
2
;
5.
delete the edges between A
1
and B
1
, and between A
2
and B
2
.
Let us remark that each node maintains exactly the same number of links as before,
and that the algorithm can be used for any kind of connected graph, either regular or
not (if the graph were directed, a similar algorithm with three cutting points instead of
two could be applied, with the same results, but here we consider only undirected
graphs).
In order to verify the small world properties, we performed a series of simulations
based upon the perturbation of a 1-lattice with a fixed connectivity degree for each
node, measuring both L and C as a function of the fraction f of links which have been
subject to the redirection algorithm described above. The number of nodes was 1000
and the tests were run for connectivities ranging between 4 and 10. Typical results are
shown in fig. 1 (note that f may exceed 1 as the algorithm can be applied indefinitely).
It is interesting to observe that already for very small f values, where the clustering
remains high (and where most of the links are regular) the introduction of a few
random connections leads to a drastic decrease of the characteristic path length L. The
small world region corresponds to the interval of values of f where C is still high
