# Small-world networks: Evidence for a crossover picture

## Abstract

Watts and Strogatz \[Nature 393, 440 (1998)\] have recently introduced a model for disordered networks and reported that, even for very small values of the disorder $`p`$ in the links, the network behaves as a small-world. Here, we test the hypothesis that the appearance of small-world behavior is not a phase-transition but a crossover phenomenon which depends both on the network size $`n`$ and on the degree of disorder $`p`$. We propose that the average distance $`\mathrm{}`$ between any two vertices of the network is a scaling function of $`n/n^{}`$. The crossover size $`n^{}`$ above which the network behaves as a small-world is shown to scale as $`n^{}(p1)p^\tau `$ with $`\tau 2/3`$.

PACS numbers: 05.10.-a, 05.40.-a, 05.50.+q, 87.18.Sn

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 —see for a review. 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.

To bridge the two limiting cases, and to provide a model for real-world systems, Watts and Strogatz have recently introduced a new type of network which is obtained by randomizing a fraction $`p`$ of the links of the regular network. As Ref. , 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`$. Reference  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.1\]. The effect of a change in $`p`$ is extremely nonlinear as is visually demonstrated by the difference between Figs. 1a,d and Figs. 1b,e where a very small change in the adjacency matrix leads to a dramatic change in the distance between different pairs of vertices.

Here, we study the origins of the small-world behavior. In particular, we investigate if the onset of small-world networks is a phase transition or a crossover phenomena. To answer this question we consider not only changes in the value of $`p`$ but also in the system size $`n`$.

The motivation for this study is the following. In a regular one-dimensional network with $`n`$ vertices and $`z`$ links per vertex, the average distance $`\mathrm{}`$ between two vertices increases as $`n/(2z)`$ —the distance is defined as the minimum number of steps between the two vertices. The regular network is similar to Manhattan: Walking along $`5^{th}`$ Avenue from Washington Square Park in $`4^{th}`$ Street to Central Park in $`59^{th}`$ Street, we have to go past 55 blocks. On the other hand, for a random network, each “block” brings us to a point with $`z`$ new neighbors. Hence, the number of vertices increases with the number of steps $`k`$ as $`nz^k`$, which implies that $`\mathrm{}`$ increase as $`\mathrm{ln}n/\mathrm{ln}z`$. The random network is then like a strange subway system that would directly connect different parts of Manhattan and enable us to go from Washington Square Park to Central Park in just one stop. In view of these facts, it is natural to enquire if the change from large-world ($`\mathrm{}n`$) to small-world ($`\mathrm{}\mathrm{ln}n`$) in disordered networks occurs through a phase transition for some given value of $`p`$ or if, for any value of $`p`$, there is a crossover size $`n^{}(p)`$ below which our network is a large-world and above which it is a small-world.

In the present Letter we report that the appearance of the small-world behavior is not a phase-transition but a crossover phenomena. We propose the scaling ansatz

$$\mathrm{}(n,p)n^{}F\left(\frac{n}{n^{}}\right),$$
(1)   
where $`F(u1)u`$, and $`F(u1)\mathrm{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/21`$, the network should be a small-world. Hence, the crossover size should occur for $`n^{}p=O(1)`$, which implies $`n^{}p^\tau `$ with $`\tau =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 scaling ansatz (1) is indeed verified by the average distance $`\mathrm{}`$ between any two vertices of the network. We also identify the crossover size $`n^{}`$ above which the network behaves as a small-world, and find that it scales as $`n^{}p^\tau `$ with $`\tau 2/3`$, distinct from the trivial expectation $`\tau =1`$.

Next, we define the model and present our results. We start from a regular one-dimensional network with $`n`$ vertices, each connected to $`z`$ neighbors. We then apply the “rewiring” algorithm of  to this network. The algorithm prescribes that every link has a probability $`p`$ of being broken and replaced by a new random link. We replace the broken link by a new one connecting one of the original vertices to a new randomly selected vertex. Each of the other $`n2`$ vertices —we exclude the other vertex of the broken link— has an a priori equal probability of being selected but we then make sure that there are no duplicate links. Hence, the algorithm preserves the total number of links which is equal to $`nz/2`$. A quantity that is affected by the rewiring algorithm is the probability distribution of local connectivities. For $`p0`$, this probability is narrowly peaked around $`z`$, but it gets broader with increasing $`p`$. For $`p=1`$, the average and the standard deviation of the local connectivity are of the same order of magnitude and equal to $`z`$.

Once the disordered network is created, we calculate the distance between any two vertices of the network and its average value $`\mathrm{}`$. To calculate all the distances between vertices, we use the Moore-Dijkstra algorithm whose execution time scales with network size as $`n^3\mathrm{ln}n`$. We perform between 100 and 300 averages over realizations of the disorder for each pair of values of $`n`$ and $`p`$.

Here, we present results for three values of connectivity $`z=10,20`$ and $`30`$ and system sizes up to $`1000`$. The scaling ansatz (1) enables us to determine $`n^{}(p)`$ from $`\mathrm{}(n)`$ at fixed $`p`$. Indeed, $`\mathrm{}(nn^{})n^{}\mathrm{ln}n`$ which implies that $`n^{}`$ is the asymptotic value of $`d\mathrm{}/d(\mathrm{ln}n)`$ \[Fig. 2(a)\]. Figure 2(b) shows the dependence of $`n^{}`$ on $`p`$ for different values $`z`$. We hypothesize that

$$n^{}\frac{1}{\mathrm{ln}z}p^\tau g(p),$$
(2)   
where the term in $`z`$ arises from the fact that $`\mathrm{}=\mathrm{ln}n/\mathrm{ln}z`$ for a random network ($`p=1`$), and $`g(p1)0`$. Moreover, $`g(p)`$ approaches a constant as $`p0`$, leading to

$$n^{}p^\tau ,$$
(3)   
for small $`p`$. Due to the effect of $`g`$ and the fact that $`n<1000`$ in our numerical simulations, we are constrained to estimate $`\tau `$ from the region $`2.5\times 10^4<p<2\times 10^2`$. For all values of $`z`$ we obtain $`\tau =0.67\pm 0.10`$ \[Fig. 2\].

Using this value of $`\tau `$ and the scaling form (1) we are able to collapse all the values of $`\mathrm{}(n,p)`$ onto a single curve \[Fig. 3\]. This data collapse confirms our scaling ansatz and estimate of $`\tau `$.

In summary, we have shown that the onset of small-world behavior is a crossover phenomena and not a phase transition from a large-world to a small one. The crossover size scales as $`p^\tau `$ with $`\tau 2/3`$. The surprising fact that $`\tau <1`$, shows that the rewiring process is highly nonlinear and can have dramatic consequences on the global behavior of the network. This implies that in order to decrease the radius of a network it is necessary to rewire only a few links. We also note that the value of the exponent $`\tau `$ will likely depend on the dimensionality of the initial regular network. This point will be adressed in future work.

We believe that the disordered networks introduced in  may constitute a promising topology for more realistic studies of many important problems such as flow in electric-power or information networks, spread of epidemics, or financial systems. The results reported here support this hypothesis because they suggest that, for any given degree of disorder of the network, if the system is larger than the crossover size, the network will be in the small-world regime.

We thank S.V. Buldyrev, L. Cruz, P. Gopikrishnan, P. Ivanoc, H. Kallabis, E. La Nave, T.J.P. Penna, A. Scala, and H.E. Stanley for stimulating discussions. L.A.N.A. thanks the FCT/Portugal and M.B. thanks the DGA for financial support.