Information Technology Reference
In-Depth Information
Giant clusters
We have seen that increasing
p
has the effect of establishing a larger number of links
and also that of creating clusters, the triangles found in Figure
6.7
being, in fact, a kind
of lowest-order cluster. Is it possible to find a critical value of
p
, much smaller than
1, that allows a walker to move freely from one border to the opposite border of the
network? In Figure
6.8
we sketch a giant cluster making it possible for the walker to
realize a complete North-South or East-West trip. What is the critical value of
p
that
we have to assign to the network for this giant cluster to appear?
Let us denote by
s
the fraction of the nodes of the graph that
do not belong
to the giant
cluster. When the number of nodes is very large, the quantity
s
can also be interpreted
as the probability that a node randomly chosen from the network does not belong to the
giant component. The fraction
S
of the graph occupied by the giant cluster is therefore
S
=
1
−
s
.
(6.68)
Now consider a node not belonging to the giant cluster and assume that the node
has degree
k
, namely it has
k
links. If the node we are considering does not belong to
the giant cluster, neither do its
k
nearest neighbors. In fact, if one of these neighbors
belonged to the giant cluster, then the node under consideration would belong to it as
well. Thus, we obtain
∞
p
k
s
k
s
=
.
(6.69)
k
=
0
In fact, since
s
is a probability it follows that the probability that the
k
neighbors do not
belong to the giant cluster is
s
k
. The probability that the node under consideration has
k
neighbors and the probability that the neighbors do not belong to the giant component
are independent of one another. This explains the product
p
k
s
k
. The sum from
k
=
0
Figure 6.8.
When the probability
p
reaches a critical value
p
c
=
1
/(
N
−
1
)
a walker can travel from the
Southern to the Northern border and from the Western to the Eastern border. The black links
indicate a giant cluster spanning the world from East to West and from North to South. The gray
links indicate local clusters.
