The small-world phenomenon: Two limiting-case topologies have been extensively considered in the literature. The first is the regular lattice, or regular network, which has been the chosen topology of innumerable physical models such as the Ising model or percolation. The second is the random graph, or random network, which has been studied in mathematics and used in both natural and social sciences. Erdös and co-workers studied extensively the properties of random networks. Most of this work concentrated on the case in which the number of vertices is kept constant but the total number of links between vertices increases: The Erdös-Rényi result states that for many important quantities there is a percolation-like transition at a specific value of the average number of links per vertex. In physics, random networks are used, for example, in studies of dynamical problems, spin models and thermodynamics, random walks, and quantum chaos. Random networks are also widely used in economics and other social sciences to model, for example, interacting agents.

In contrast to these two limiting topologies, empirical evidence suggests that many biological, technological or social networks appear to be somewhere in between these extremes. Specifically, many real networks seem to share with regular networks the concept of neighborhood, which means that if vertices i and j are neighbors then they will have many common neighbors --- which is obviously not true for a random network. On the other hand, studies on epidemics show that it can take only a few ``steps'' on the network to reach a given vertex from any other vertex. This is the foremost property of random networks, which is not fulfilled by regular networks.

  The Watts-Strogatz' model: To bridge the two limiting cases, and to provide a model for real-world systems, Watts and Strogatz [Nature 393, 440 (1998)] have recently introduced a new type of network which is obtained by randomizing a fraction p of the links of the regular network. As Watts and Strogatz, we consider as an initial structure (p=0) the one-dimensional regular network where each vertex is connected to its z nearest neighbors. For 0 < p < 1, we denote these networks disordered, and keep the name random network for the case p=1. Watts and Strogatz reports that for a small value of the parameter p --- which interpolates between the regular (p=0) and random (p=1) networks --- there is an onset of small-world behavior. The small-world behavior is characterized by the fact that the distance between any two vertices is of the order of that for a random network and, at the same time, the concept of neighborhood is preserved, as for regular lattices [Fig. 2]. The effect of a change in p is extremely nonlinear as is visually demonstrated by the difference between Figs. 2(a,d) and Figs. 2(b,e) where a very small change in the connectivity of the network leads to a dramatic change in the distance between different pairs of vertices.

  Scaling laws for the network's diameter: The scientific question we are trying to answer is illustrated in Fig. 3. Does the onset of the small-world behavior occurs at a given value of p or does it occur for a value of the system size n which depends on p? To investigate this question, we need to look at the behavior of the system as a function of p for different values of n.

We find that the appearance of the small-world behavior is not a phase-transition but a crossover phenomena. We propose the scaling ansatz for the average distance l

                          l (n,p) ~ n^* F ( n / n^* )

where F(u << 1) ~ u, and F(u >> 1) ~ln u, and n^* is a function of p. Naively, we would expect that when the average number of rewired links, pnz/2, is much less than one, the network should be in the large-world regime. On the other hand, when pnz/2 >> 1, the network should be a small-world. Hence, the crossover size should occur for

                          n^* p = O(1)      which implies      n^* ~ p-1.

This result relies on the fact that the crossover from large to small worlds is obtained with only a small but finite fraction of rewired links. We find that the above scaling ansatz is indeed verified by the average distance l between any two vertices of the network. We also identify the crossover size above which the network behaves as a small-world, and find that it scales as

                          n^* ~ p^-tau,       $tau$ = 0.93 +- 0.10

which is consistent with the expectation tau = 1.

  Scale-free networks: It was proposed by Barabási and Albert that real-world networks in general --- and more specifically, the networks such as (a) the electric-power grid for Southern California, (b) the network of movie-actor collaborations, (c) the neuronal network of the worm C. elegans, (d) world-wide web, and (e) the network of citations of scientific papers--- 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. Scale free networks are also small-world networks because (i) they have clustering coefficients much larger than random networks, and (ii) their diameter increases logarithmically with the number of vertices n.

We have addressed the question of the conditions under which disordered networks are scale-free through the analysis of several networks in social, economic, technologic, biologic, and physical systems. We have identified 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.

  Empirical analysis of real-world networks: First, we consider two examples of technologic and economic networks: (i) the electric-power grid of Southern California, the vertices being generators, transformers and substations and the links high-voltage transmission lines, and (ii) the network of world airports, the vertices being the airports and the links non-stop connections. For the case of the airport network we have access to data on number of passengers in transit and of cargo leaving or arriving at the airport, instead of data on the number of distinct connections. one can expect that the number of distinct connections from a major airports is proportional to the number of passengers in transit through that airport, making the two examples, (i) and (ii), comparable. Figure x1 shows the connectivity distribution for these two examples. It is visually apparent that neither case has a power-law regime, and that both have exponentially decaying tails, implying that there is a single scale for the connectivity k.

Second, we consider three examples of ``social'' networks: (iii) the movie-actors network, the links in this network indicating that the two actors were cast at least once in the same movie, (iv) the acquaintance network of Mormons, the vertices being 43 Utah Mormons and the number of links the number of other Mormons they know, and (v) the friendship-network of 417 Madison Junior High School students. These three examples describe apparently distinct types of social networks with very different sample sizes. In fact it can be argued that the network of movie-actors collaborations is not really a social network but is instead an economic network. However, since it was considered in other publications as a social network we classify it similarly here. We feel that the acquaintance and friendship networks may be better proxys of real social networks and as such expect similar results from the analysis of both networks. Figure x2 shows the connectivity distribution for these social networks. The scale-free (power-law) behavior of the actor's network is truncated by an exponential tail. In contrast, the network of acquaintances of the Utah Mormons and the friendship network of the high-school students display no power-law regime, but instead we find results consistent with a Gaussian distribution of connectivities, indicating the existence of a single scale for k.

Third, we consider two examples of networks from the natural sciences: (vi) the neuronal network of the worm C. elegans, the vertices being the individual neurons and the links being connections between neurons, and (vii) the conformation space of a lattice polymer chain, the vertices being the possible conformations of the polymer chain and the links the possibility of connecting two conformations through local movements of the chain. The conformation space of a linear polymer chain shares appears to be well described by the small-world networks of Watts and Strogatz. Figures x3a,b show for C. elegans the cumulative distribution of k for both incoming and outgoing neuronal links. The tails of both distributions are well approximated by exponential decays, consistent with a single scale for the connectivities. For the network of conformations of a polymer chain the connectivity follows a binomial distribution, which converges to the Gaussian, so we also find a single scale for the connectivity of the vertices.  

  Constraints on the connectivity: We find empirical evidence for the occurrence of three structural classes of small-world networks: (a) scale-free networks, characterized by a connectivity distribution with a tail that decays as a power law; (b) broad-scale or truncated scale-free networks, characterized by a connectivity distribution that has a power-law regime followed by a sharp cut-off, like an exponential or Gaussian decay of the tail [see example (iii)]; (c) single-scale networks, characterized by a connectivity distribution with a fast decaying tail, such as exponential or Gaussian [see examples (i),(ii),(iv-vii)].

A natural question is ``what are the reasons for such a rich range of possible structures for small-world networks?'' To answer this question let us recall that preferential attachment in growing networks gives rise to a power-law distribution of connectivities. However, preferential attachment can be hindered by two classes of factors:

   Aging of the vertices. This effect can be pictured for the network of actors: in time, every actress or actor will stop acting. For the network, this fact implies that even a very highly connected vertex will, eventually, stop receiving new links. The vertex is still part of the network and contributing to network statistics, but it no longer receives links. The aging of the vertices thus limits the preferential attachment preventing a scale-free distribution of connectivities.

   Cost of adding links to the vertices or the limited capacity of a vertex. This effect is exemplified by the network of world airports: for reasons of efficiency, commercial airlines prefer to have a small number of hubs where all routes would connect. To first approximation, this is indeed what happens for individual airlines, but when we consider all airlines together, it becomes physically impossible for an airport to become a hub to all airlines. Due to space and time constraints, each airport will limit the number of landings/departures per hour, and the number of passengers in transit. Hence, physical costs of adding links and limited capacity of a vertex will limit the number of possible links attaching to a given vertex.

  Analogy to critical phenomena: These results on the distributions of connectivity of the small-world networks have an analogy in the theory of critical phenomena. At the gas-liquid critical point, the distribution of sizes of the droplets of the gas (or of the liquid) is scale-free, as there is no free-energy cost in their formation. As for the case of a scale-free network, the size s of a droplet is power-law distributed: p(s) ~ s ^-alpha . As we move away from the critical point, the appearance of a non-negligible surface tension introduces a free-energy cost for droplets which limits their sizes, so that their distribution becomes broad-scale: p(s) ~ s ^-alpha f (s / xi ), where xi is the typical size for which surface tension starts to be significant and the function f(s / xi) introduces a sharp cut-off for droplet sizes s > xi. Far from the critical point, the scale xi becomes so small that no power-law regime is observed and the droplets become single-scale distributed: p(s) ~ f (s / xi). Often, the distribution of sizes in this regime is exponential or Gaussian.