Hidden Small World Networks

Y. Grondin and D. J. Raine, Department of Physics and Astronomy, University of Leicester, Leicester LE1 7RH, UK

Small world networks are characterised by high degrees of clustering of their nodes and by small diameters. Such structure leads to the phenomenon of six-degrees of separation and plays a important role in areas as various as the spread of viruses or the routing capability over the Internet, for example.

Some methods have been introduced to generate such classes of networks for non-growing (Watts & Strogatz, 1998) or growing networks (Klemm & Eguíluz, 2002). However, those methods lacks power in differentiating the local order/disorder as given by the clustering coefficient from the global order/randomness as expressed by the degree distribution of the networks.

We introduce here a simple method to generate small-world networks from non-growing networks for virtually any fixed degree distribution. This demonstrates that the small world property does not only arise at the interface of order and random networks, but is, on the contrary, independent of any manipulation the degree distribution or of its ‘order’.