Classes of small-world networks
Files
First author draft
Date
2000-10-10
Authors
Nunes Amaral, Luís A.
Scala, Antonio
Barthélémy, Marc
Stanley, H. Eugene
Version
First author draft
OA Version
Citation
Luís A. Nunes Amaral, Antonio Scala, Marc Barthélémy, H. Eugene Stanley. 2000. "Classes of small-world networks." PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, Volume 97, Issue 21, pp. 11149 - 11152. https://doi.org/10.1073/pnas.200327197
Abstract
We study the statistical properties of a variety of diverse real-world networks. We present evidence of the occurrence of three classes of small-world networks: (a) scale-free networks, characterized by a vertex connectivity distribution that decays as a power law; (b) broad-scale networks, characterized by a connectivity distribution that has a power law regime followed by a sharp cutoff; and (c) single-scale networks, characterized by a connectivity distribution with a fast decaying tail. Moreover, we note for the classes of broad-scale and single-scale networks that there are constraints limiting the addition of new links. Our results suggest that the nature of such constraints may be the controlling factor for the emergence of different classes of networks.
Disordered networks, such as small-world networks are the focus of recent interest because of their potential as models for the interaction networks of complex systems (1–7). Specifically, neither random networks nor regular lattices seem to be an adequate framework within which to study “real-world” complex systems (8) such as chemical-reaction networks (9), neuronal networks (2), food webs (10–12), social networks (13, 14), scientific-collaboration networks (15), and computer networks (4, 16–19).
Small-world networks (2), which emerge as the result of randomly replacing a fraction P of the links of a d dimensional lattice with new random links, interpolate between the two limiting cases of a regular lattice (P = 0) and a random graph (P = 1). A small-world network is characterized by the following properties: (i) the local neighborhood is preserved (as for regular lattices; ref. 2); and (ii) the diameter of the network, quantified by average shortest distance between two vertices (20), increases logarithmically with the number of vertices n (as for random graphs; ref. 21). The latter property gives the name small-world to these networks, because it is possible to connect any two vertices in the network through just a few links, and the local connectivity would suggest the network to be of finite dimensionality.
The structure of small-world networks and of real networks has been probed through the calculation of their diameter as a function of network size (2). In particular, networks such as (a) the electric power grid for Southern California, (b) the network of movie-actor collaborations, and (c) the neuronal network of the worm Caenorhabditis elegans seem to be small-world networks (2). Further, it was proposed (5) that these three networks (a–c) as well as the world-wide web (4) and the network of citations of scientific papers (22, 23) are scale-free—that is, they have a distribution of connectivities that decays with a power law tail.
Scale-free networks emerge in the context of a growing network in which new vertices connect preferentially to the more highly connected vertices in the network (5). Scale-free networks are also small-world networks, because (i) they have clustering coefficients much larger than random networks (2) and (ii) their diameter increases logarithmically with the number of vertices n (5).
Herein, we address the question of the conditions under which disordered networks are scale-free through the analysis of several networks in social, economic, technological, biological, and physical systems. We identify a number of systems for which there is a single scale for the connectivity of the vertices. For all these networks, there are constraints limiting the addition of new links. Our results suggest that such constraints may be the controlling factor for the emergence of scale-free networks.