Classes of small-world networks

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.

Figure 1

Technological and economic networks. (a) Linear-log plot of the cumulative distribution of connectivities for the electric power grid of Southern California (2). For this type of plot, the distribution falls on a straight line, indicating an exponential decay of the distribution of connectivities. The full line, which is an exponential fit to the data, displays good agreement with the data. (b) Log-log plot of the cumulative distribution of connectivities for the electric power grid of Southern California. If the distribution would have a power law tail then it would fall on a straight line in a log-log plot. Clearly, the data reject the hypothesis of power law distribution for the connectivity. (c) Linear-log plot of the cumulative distribution of traffic at the world's largest airports for two measures of traffic, cargo, and number of passengers. The network of world airports is a small-world network; one can connect any two airports in the network by only one to five links. To study the distribution of connectivities of this network, we assume that, for a given airport, cargo and number of passengers are proportional to the number of connections of that airport with other airports. The data are consistent with a decay of the distribution of connectivities for the network of world airports that decays exponentially or faster. The full line is an exponential fit to the cargo data for values of traffic between 500 and 1,500. For values of traffic larger than 1,500, the distribution seems to decay even faster than an exponential. The long-dashed line is an exponential to the passenger data for values of traffic between 500 and 1,500. a.u., arbitrary units. (d) Log-log plot of the cumulative distribution of traffic at the world's largest airports. This plot confirms that the tails of the distributions decay faster than a power law would.

Figure 2

Social networks. (a) Linear-log plot of the cumulative distribution of connectivities for the network of movie actors (2). The full line is a guide for the eye of what an exponential decay would be. The data seem to fall faster in the tail than they would for an exponential decay, suggesting a Gaussian decay. Both exponential and Gaussian decays indicate that the connectivity distribution is not scale-free. (b) Log-log plot of the cumulative distribution of connectivities for the network of movie actors. This plot suggests that, for values of number of collaborations between 30 and 300, the data are consistent with a power law decay. The apparent exponent of this cumulative distribution, α − 1 ≈ 1.3, is consistent with the value α = 2.3 ± 0.1 reported for the probability density function (5). For larger numbers of collaborations, the power law decay is truncated. (c) Linear-log plot of the cumulative distribution of connectivities for the network of acquaintances of 43 Utah Mormons (25). The full line is the fit to the cumulative distribution of a Gaussian. The tail of the distribution seems to fall off as a Gaussian, suggesting that there is a single scale for the number of acquaintances in social networks. (d) Linear-log plot of the cumulative distribution of connectivities for the friendship network of 417 high school students (26). The number of links is the number of times a student is chosen by another student as one of his/her two (or three) best friends. The lines are Gaussian fits to the empirical distributions.

Figure 3

Biological and physical networks. (a) Linear-log plot of the cumulative distribution of outgoing (i.e., connections by axons to other cells) and incoming (i.e., connections by axons from other cells) connections for the neuronal network of the worm C. elegans (27, 28). The full and long-dashed lines are exponential fits to the distributions of outgoing and incoming connections, respectively. The tails of the distributions seem consistent with an exponential decay. (b) Log-log plot of the cumulative distribution of outgoing and incoming connections for the neuronal network of the worm C. elegans. If the distribution would have a power law tail, then it would fall on a straight line in a log-log plot. The data seem to reject the hypothesis of a power law distribution for the connectivity. (c) Linear-log plot of the probability density function of connectivities for the network of conformations of a lattice polymer chain (29). A simple argument suggests that the connectivities follow a binomial distribution. The full and dashed lines are fits of a binomial probability density function to the data for polymer chains of different lengths. For the values of the parameters obtained in the fit, the binomial closely resembles the Gaussian, indicating that there is a single scale for the connectivities of the conformation space of polymers.

Figure 4

Truncation of scale-free connectivity by adding constraints to the model of ref. . (a) Effect of aging of vertices on the connectivity distribution. We see that aging leads to a cutoff of the power law regime in the connectivity distribution. For sufficient aging of the vertices, the power law regime disappears altogether. (b) Effect of cost of adding links on the connectivity distribution. Our results indicate that the cost of adding links also leads to a cutoff of the power law regime in the connectivity distribution and that, for a sufficiently large cost, the power law regime disappears altogether.