Re: Six-degrees of separation in Nature last year

Dave Long (
Tue, 04 May 1999 23:43:29 -0700


> 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=

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=

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?


(not Long-Bacon-Driver-Kleitman-Erd=F6s)