> between these two extremes. Here we explore simple models of networks =
> that can be tuned through this middle ground: regular networks =
> 'rewired' to introduce increasing amounts of disorder.
The observation I found most interesting in this paper was the contrast =
between local and global network properties:
1) One can look at local properties, such as degree of clustering. In a =
regular network, most neighbors of a node are also neighbors of each othe=
r. =
In a random network, most neighbors of a node are not neighbors of each o=
ther.
2) One can also look at global properties, such as average number of hops=
=
between two nodes in the network. Compared to regular networks, random =
networks have much shorter characteristic path lengths (log N:N?).
3) These relationships seem simple enough: consider the set of nodes whic=
h are =
reachable in a given number of hops. Because of the high clustering, one=
more =
hop on a regular network doesn't yield many new nodes. On the other hand=
, the =
low clustering on a random network means that an additional hop yields mo=
stly =
new nodes. So degree of clustering and path length seem to vary together=
=2E
4) However, it turns out that a few random connections will suffice to pr=
ovide =
the difference in path length: the network still appears locally regular =
(local measures give high clustering values), yet has a (global) short =
characteristic path length. (Removing a regular connection and replacing=
it =
with a random one doesn't reduce the local degree of clustering significa=
ntly, =
but does introduce a "long range" connection which has a significant effe=
ct on =
global connectivity)
Now, how do we route to take advantage of a small-world network?
-Dave
(not Long-Bacon-Driver-Kleitman-Erd=F6s)