Information Technology Reference
In-Depth Information
Figure 6.17.
The random rewiring procedure for interpolating between a regular ring lattice and a random
web, without altering the number of vertices or edges in the graph. WS start with a ring of N
vertices, each connected to its k nearest neighbors by undirected edges. (For clarity, N = 20 and
k =
4 in the schematic examples shown here.) WS choose a vertex and the edge that connects it
to its nearest neighbor in a clockwise sense. With probability p , they reconnect this edge to a
vertex chosen uniformly at random over the entire ring, with duplicate edges forbidden;
otherwise they leave the edge in place. They repeat this process by moving clockwise around the
ring, considering each vertex in turn until one lap has been completed. Next, WS consider the
edges that connect the vertices to their second-nearest neighbors clockwise. As before, they
randomly rewire each of these edges with probability p , and continue this process, circulating
around the ring and proceeding outward to more distant neighbors after each lap, until each edge
in the original lattice has been considered once. (Since there are Nk / 2 edges in the entire graph,
the rewiring process stops after k = 2 laps.) Three realizations of this process are shown, for
different values of p .For p = 0, the original ring is unchanged; as p increases, the graph
becomes increasingly disordered until, for p = 1, all edges are rewired randomly. One of the
main results of the WS paper [ 35 ] is that, for intermediate values of p , the graph is a small-world
network: highly clustered like a regular graph, yet with small characteristic path length, like a
random graph [ 35 ]. Reproduced with permission.
The probability p of Section 6.2.1 is given by the ratio of the number of links established
according to the deterministic rule, which is 2 N , to the maximum number of links,
which is N
(
N
1
)/
2. The ratio of these two quantities is
4
=
1 .
R
(6.106)
N
This formula applies for N
>
5, and,
in the case of N
=
1
,
000 considered in
Figure 6.18 , yields R
=
0
.
004. Note that this value is small, but larger than the
critical probability p c =
001, which corresponds, according to ( 6.73 ),
to the emergence of a giant cluster. According to ( 6.105 ), with p replaced by R ,
we expect
1
/(
N
1
) =
0
.
that C
(
1
) =
0
.
004, which corresponds in fact
to the value plotted in
Figure 6.18 .
Beyond the model of preferential attachment
Earlier we found that real webs are characterized by the scale-free property. We have
justified the observation that the distribution of links is an inverse power law by pointing
out that this corresponds to the prescriptions of the laws of Pareto and Zipf. Because of
 
Search WWH ::




Custom Search