Information Technology Reference
In-Depth Information
condition with a high prevalence of either 1 or 0, the system is likely to reach a
uniform state of "all 1" or "all 0". We will give a special name to these uniform
attractors, U1 and U0 respectively.
Let us consider first the case where the topology is regular and no link has been
redirected (i.e. f=0), and let r be the fraction of "1" in the initial conditions (for
obvious symmetry reasons, we can limit our discussion to the interval r
[0,1/2]). By
performing experiments with 1000 different initial conditions, one observes that, if r
is very small, all the initial states tend to the U0 attractor. By increasing r, one
observes that also other attractors are reached and, in experiments with r=0.2, it may
happen that some hundreds of attractors are actually reached (table 1). An interesting
feature is that all these attractors share a large common part with U0, i.e. most of their
nodes (>90%) take the value 0, and the Hamming distances among these attractors are
very small. They can then be considered as "perturbations" of the uniform U0
attractor, with some "regions of disorder". Let
0
(v) be defined, for each node v, as
the fraction of initial conditions that leads to a final state in which node v takes the
value 0. For each network,
min
and
max
are defined respectively as the minimum
0
0
and maximum value of
0
(v). We can see that in the f=0 case, while
0
(v) is close to 1
min
can take also small values.
When r=0.5, the initial state has no prevalence of either 0 or 1: here every initial
condition out of 1000 almost always leads to a different fixed point, but now these are
more different from each other, as it can be seen by examining their Hamming
distances, which take large values (table 1) and show a distribution around the value
500 (which is the average distance between two random boolean vectors of 1000
elements each). Note also that
for most nodes,
0
max
are close to 0.5.
We then modified the fraction of redirected links. It is interesting to notice that the
introduction of long-range connections may modify the dynamical behaviour. As it
can be seen from table 1 when r=0.2 but f=0.8 one finds that only the U0 attractor is
reached: the presence of long range connections seems to eliminate the cloud of
attractors similar to U0 which were reached in the case of a regular topology.
This guess is confirmed by considering the r=0.5 case. When r=0.5 the average
number of attractors which are reached from 1000 random initial conditions shows a
large decrease between f=0.4 and f=0.8 (fig. 2). By considering the distribution of
Hamming distances, one observes that in the f=0.8 case there are the uniform
attractors U0 and U1 (with fairly large basins of attraction, see table 1), and a number
of other attractors whose Hamming distances are distributed around 500. The uniform
attractors are not surrounded by a cloud of slightly different fixed points, but there are
still a large number of attractors which are markedly different from both.
It is interesting to consider also the case of a graph which is closer to the regular
one, e.g. the f=0.08 case (table 1), where one can see that the dynamical behaviour is
already affected by the introduction of a few random long range connections. At r=0.2
the number of reached fixed points is reduced, with respect to the regular case, and
the basin of attraction of U0 is larger. The cloud of similar attractors is shrunk, but
has not yet disappeared as in the f=0.8 case. In the r=0.5 case one observes that 1000
random initial conditions are mapped into 1000 different fixed points, as in the
regular graph. An indication that shows that the dynamical properties are modified
comes from the values of
min
and
0
0
min
and
max
, which are intermediate between the regular
0
0
