Harmony in the small-world

The small-world phenomenon, popularly known as six degrees of separation, h as been mathematically formalized by Watts and Strogatz in a study of the t opological properties of a network. Small-world networks are defined in ter ms of two quantities: they have a high clustering coefficient C like regula r lattices and a short characteristic path length L typical of random netwo rks. Physical distances are of fundamental importance in applications to re al cases; nevertheless, this basic ingredient is missing in the original fo rmulation. Here, we introduce a new concept, the connectivity length D, tha t gives harmony to the whole theory. D can be evaluated on a global and on a local scale and plays in turn the role oft and I:C. Moreover, it can be c omputed for any metrical network and not only for the topological cases. D has a precise meaning in terms of information propagation and describes in a unified way, both the structural and the dynamical aspects of a network: small-worlds are defined by a small global and local D, i.e., by a high eff iciency in propagating information both on a local and global scale. The ne ural system of the nematode C, elegans, the collaboration graph of film act ors, and the oldest US subway system, can now be studied also as metrical n etworks and are shown to be small-worlds. (C) 2000 Elsevier Science B.V. Al l rights reserved.