Information Technology Reference
In-Depth Information
We see that a random graph for
N
very large is characterized by a small clustering
coefficient.
Web efficiency
Following [
22
], let us define the concept of
web efficiency
. Consider the shortest distance
between two arbitrary nodes
i
and
j
and denote it by the symbol
L
ij
. In the case of
Figure
6.13
the shortest distance is
L
ij
=
3. The communication efficiency between
i
and
j
is defined by
1
L
ij
.
ij
=
(6.88)
When there is no path in the graph between
i
and
j
,
L
ij
=∞
ij
=
0, namely we have the condition of minimum efficiency and no communication. The
global efficiency of the web is defined by
and consequently
1
1
L
ij
.
E
=
(6.89)
N
(
N
−
1
)
i
,
j
In the case of all-to-all coupling,
L
ij
=
1 and
1
L
ij
=
(
−
).
N
N
1
(6.90)
i
,
j
Thus, the all-to-all coupling case corresponds to that of maximum efficiency.
The question is how do real webs depart from the condition of weak clustering that
is typical of random webs?
6.2.2
Real webs
Watts and Strogatz (WS) [
35
] have shown that the statistical properties of real webs
significantly depart from those of random webs. This observation captured the atten-
tion of the scientific community, resulting in their paper becoming very popular; as of
March 3, 2009 it had over 4
000 citations. This number of citations is particularly signif-
icant because the distribution of citations is another inverse power law and the average
number of citations to a scientific paper in a year is a little over 3.
WS studied the following real webs.
,
(a)
Film actors
. The first web they considered was one motivated, at least in part, by the
party game determining the distance between two actors in terms of the movies in
which they have acted. For example, if they acted in a movie together the separation
distance is zero. If, however, they have each acted in a movie with a third party
then the distance between them is one and so on. Two actors are considered to be
joined by an edge or link if they have acted in a film together; see, for example,
Figure
6.14
. So, in terms of the web, the above party game can be cast in terms of
the links between actors. In an earlier section we saw that random webs may have
giant clusters, where the linked elements form closed groups. Although the web
