Information Technology Reference
In-Depth Information
Figure 6.18.
The characteristic path length
L
(
p
)
and clustering coefficient
C
(
p
)
for the family of randomly
rewired graphs described in Figure
6.17
. Here
L
is defined as the number of edges in the shortest
path between two vertices, averaged over all pairs of vertices. The clustering coefficient
C
is
defined according to the proposal of (
6.105
). The data shown in this figure are averages over
twenty random realizations of the rewiring process described in Figure
6.17
, and have been
normalized by the values
L
(
0
)
and
C
(
0
)
for a regular lattice. All the graphs have
N
=
1
,
000
vertices and an average degree of
k
10 edges per vertex. We note that the logarithmic
horizontal scale has been used to resolve the rapid drop in
L
=
(
p
)
corresponding to the onset of
the small-world phenomenon. During this drop,
C
remains almost constant at its value for
the regular lattice, indicating that the transition to a small world is almost undetectable at the
local level [
35
]. Reproduced with permission.
(
p
)
(a) Poisson Distribution
(b) Scale-free Distribution
0.0
0.12
0.10
0.08
0.06
0.04
0.02
0.00
-0.5
-1.0
-1.5
0
5
10
15
20
0.0
0.2
0.4
0.6
0.8
1.0
k
log k
Figure 6.19.
(a) A random graph is characterized by a Poisson distribution. The typical scale of this web is
given by the average node degree
k
. The probability of finding nodes with high or low node
degree is statistically very small because the degree distribution
P
(
k
)
decays exponentially. (b)
By contrast, scale-free webs are characterized by a power-law degree distribution
P
(
k
)
∝
k
−
α
.
In this web, there is no typical scale; that is, it is scale-free and it is possible to find highly
connected nodes (hubs). In the log-log plot, the power law is characterized by a straight line of
negative slope.
these empirical inverse power laws, one expects that real webs do not have the Pois-
son structure of the left panel of Figure
6.19
but rather correspond to the structure
sketched in the right panel of that figure. However, it seems that
3 generated by the
model of preferential attachment is the upper limit of the power-law indices observed
α
=
