# REFERENCES

Comment on “Small-world networks: Evidence for a crossover picture”

In a recent letter, Barthélémy and Nunes Amaral  examine the crossover behaviour of networks known as “small-world”. They claim that, for an initial network with $`n`$ vertices and $`z`$ links per vertex, each link being rewired according to the procedure of  with a probability $`p`$, the average distance $`\mathrm{}`$ between two vertices scales as

$$\mathrm{}(n,p)n^{}F\left(\frac{n}{n^{}}\right)$$
(1)   
where $`F(u1)u`$, and $`F(u1)\mathrm{ln}u`$, and $`n^{}`$ $`n^{}p^\tau `$ with $`\tau =2/3`$ as $`p`$ goes to zero.

Other quantities can be of interest in small-world networks, and will be discussed in . In this comment however, we concentrate like  on $`\mathrm{}`$ and we show, using analytical arguments and numerical simulations with larger values of $`n`$, that: (i) the proposed scaling form $`\mathrm{}(n,p)n^{}F(n/n^{})`$ seems to be valid, BUT (ii) the value of $`\tau `$ cannot be lower than $`1`$, and therefore the value found in  is clearly wrong.

The naive argument developed in  uses the mean number of rewired links, $`N_r=pnz/2`$. According to , one could expect that the crossover happens for $`N_r=O(1)`$, which gives $`\tau =1`$ . However they find $`\tau =2/3`$. Let us suppose that $`\tau <1`$. Then, if we take $`\alpha `$ such that $`\tau <\alpha <1`$, according to eq (1), we obtain that

$$\mathrm{}(n,n^{1/\alpha })n^{\tau /\alpha }F(n^{1\tau /\alpha })n^{\tau /\alpha }\mathrm{ln}(n^{1\tau /\alpha })$$
(2)   
since $`\tau /\alpha <1`$ and $`n^{1\tau /\alpha }1`$ for large $`n`$. However, the mean number of rewired links in this case is $`N_r=n^{11/\alpha }z/2`$, which goes to zero for large $`n`$. The immediate conclusion is that a change in the behaviour of $`\mathrm{}`$ (from $`\mathrm{}n`$ to $`\mathrm{}n^{\tau /\alpha }\mathrm{ln}(n)`$) could occur by the rewiring of a vanishing number of links! This is a physical nonsense, showing that, if $`n^{}p^\tau `$, $`\tau `$ cannot be lower than $`1`$.

We know present our numerical simulations. The value of $`n^{}(p)`$ is obtained by studying, at fixed $`p`$ (we take $`p=2^k/2^{20}`$, $`k=0,\mathrm{}20`$), the crossover between $`\mathrm{}n`$ at small $`n`$ to $`\mathrm{}\mathrm{ln}(n)`$ at large $`n`$ . For small values of $`p`$, it is difficult to reach large enough values of $`n`$ to accurately determine $`n^{}`$, and we think that the underestimation of $`n^{}`$ given by  comes from this problem. We here simulate networks with $`z=4,6,10`$ up to sizes $`n=11000`$, and find that $`n^{}`$ behaves like $`1/p`$ for small $`p`$ (Inset of fig. (1)). We moreover show the collapse of the curves $`\mathrm{}/n^{}`$ versus $`n/n^{}`$ in figure (1), for $`z=4`$ and $`z=10`$: note that we obtain the collapse over a much wider rabge than .

Besides, we present results for another quantity: at fixed $`n`$ we evaluate $`\mathrm{}(n,p)`$ and look for the value $`p_{1/2}(n)`$ of $`p`$ such that $`\mathrm{}(n,p_{1/2}(n))=\mathrm{}(n,0)/2`$. This value of $`p`$ corresponds to the rapid drop in the plot of $`\mathrm{}`$ versus $`p`$ at fixed $`N`$, and can therefore also be considered as a crossover value. If we note $`u^{}`$ the number such that $`F(u^{})=u^{}/2`$, then we obtain, since $`\mathrm{}(n,0)n`$, that $`n^{}(p_{1/2}(n))=n/u^{}`$. If $`n^{}(p)p^\tau `$, this implies $`p_{1/2}(n)n^{1/\tau }`$. We show in fig (2) that $`p_{1/2}(n)1/n`$ (and clearly not $`n^{3/2}`$ like the results of  would imply), meaning that $`\tau =1`$: a finite number of rewired links already has a strong influence on $`\mathrm{}`$. Again the $`\tau =2/3`$ result of  is clearly ruled out.

It is a pleasure to thank G. Biroli, R. Monasson and M. Weigt for discussions.

A. Barrat

Laboratoire de Physique Théorique , Université de Paris-Sud, 91405 Orsay cedex, France