# Mean-field solution of the small-world network model

## The continuum model as the <br>small-$`\varphi `$ limit of the discrete model

In this appendix, we rederive Equations (3) and (6) from the behavior of the discrete version of the small-world model to leading order in the shortcut density $`\varphi `$.

Consider a neighborhood of sites which are within distance $`r`$ of a given starting site in the discrete model. By analogy with the continuous case, let $`m`$ be the number of sites on the lattice which are not in this neighborhood and $`n`$ be the number of “gaps” between clusters of occupied sites around the ring. In fact, in the spirit of our mean-field approximation, $`m`$ and $`n`$ should be thought of as the average of these quantities over all possible realizations of lattice. This means that they may have non-integer values. Here we treat them as integers for combinatorial purposes, but our formulas are easily extended to non-integer values by replacing the factorials by $`\mathrm{\Gamma }`$-functions.

When we increase $`r`$ by one, the value of $`m`$ decreases for two reasons: first because the gaps between clusters shrink and second because of new sites which are reached by traveling down shortcuts encountered on the previous step. We write

$$m^{}=m\mathrm{\Delta }m$$
(25)   
where

$$\mathrm{\Delta }m=\mathrm{\Delta }m_g+\mathrm{\Delta }m_s,$$
(26)   
with the two terms representing the shrinking of gaps and the shortcut contribution respectively.

To calculate $`\mathrm{\Delta }m_g`$, we note that the probability of any particular gap having size $`j`$ is

$$p_j=\frac{\left(\genfrac{}{}{0pt}{}{mj1}{n2}\right)}{\left(\genfrac{}{}{0pt}{}{m1}{n1}\right)},$$
(27)   
and the average number of such gaps is $`n`$ times this. When we increase $`r`$ by one, gaps of size $`2k`$ or larger shrink by $`2k`$, while gaps smaller than $`2k`$ vanish altogether. Thus

$$\mathrm{\Delta }m_g=n\left[\underset{j=1}{\overset{2k}{}}jp_j+2k(1\underset{j=1}{\overset{2k}{}}p_j)\right]=m\frac{(m2k)!(mn)!}{(m1)!(mn2k)!}.$$
(28)   
To calculate the contribution $`\mathrm{\Delta }m_s`$ from the number of shortcuts, we note that the probability of encountering the end of a shortcut at any given site is $`2/\xi =2k\varphi `$, just as in the continuum case, so the number of new shortcuts encountered when we increase $`r`$ by one is $`2k\varphi \mathrm{\Delta }m`$. $`\mathrm{\Delta }m_s`$ in fact depends on the number of shortcuts encountered on the previous increase in $`r`$, so we need to write $`2k\varphi \mathrm{\Delta }m^{(r1)}`$. Only those shortcuts which land us at one of the $`m\mathrm{\Delta }m_g`$ unoccupied sites contributes to $`\mathrm{\Delta }m_s`$, so

$$\mathrm{\Delta }m_s=2k\varphi \mathrm{\Delta }m^{(r1)}[m\mathrm{\Delta }m_g^{(r)}].$$
(29)   
Substituting Eqs. (28) and (29) into Eq. (26) we get our complete expression for $`\mathrm{\Delta }m`$. Now we note that, except when the lattice is very nearly full, the number of unfilled sites $`m`$ is of order $`L`$. The number of clusters of filled sites can be no greater than the number of shortcuts on the lattice plus one for the initial cluster around the starting point. Thus $`n\varphi L+1`$, and the ratio $`(n1)/m`$ is a quantity of order $`\varphi `$. Expanding in powers of this quantity and assuming the number of sites $`m`$ to be much greater than $`2k`$ then gives

$$\mathrm{\Delta }m=2kn,$$
(30)   
plus terms of order $`\varphi `$. Physically, the reason for the simplicity of this expression is that, to first order in $`(n1)/m`$, most gaps have size $`2k`$ or larger, and the contribution from new shortcuts to can be neglected, since most sites are connected only to their local neighbors.

The change in the value of $`n`$ has also two contributions. First, the number of gaps increases when a shortcut creates a new cluster, and divides a gap into two new ones. As we have already shown this happens $`\mathrm{\Delta }m_s`$ times on average when we increase $`r`$ by one, where $`\mathrm{\Delta }m_s`$ is given by Eq. (29). Second, gaps disappear when their edges meet. When we increase $`r`$ by one, a gap will close if its size is $`2k`$ or less. Thus the change in $`n`$ is

$$n^{}=n+\mathrm{\Delta }n,$$
(31)   
where

$$\mathrm{\Delta }n=\mathrm{\Delta }m_sn\underset{j=1}{\overset{2k}{}}p_j=\mathrm{\Delta }m_sn\frac{(mn)!(m2k1)!}{(m1)!(mn2k)!}.$$
(32)   
where $`\mathrm{\Delta }m_s`$ is given by Eq. (29). Expanding to lowest order in $`(n1)/m`$, taking $`m2k`$ again, and combining the result with Eq. (29) gives

$$\mathrm{\Delta }n=\frac{4k^2\varphi mn}{L}\frac{2kn(n1)}{m}.$$
(33)   
Changing Eqs. (30) and (33) from difference equations to differential ones and dividing by $`L`$ to transform from $`m`$ and $`n`$ to $`\mu `$ and $`\nu `$ gives

$`{\displaystyle \frac{d\mu }{dr}}`$ $`=`$ $`2k\nu ,`$ (34)   
$`{\displaystyle \frac{d\nu }{dr}}`$ $`=`$ $`4k^2\varphi \mu \nu +{\displaystyle \frac{2k\nu (\nu 1/L)}{\mu }}.`$ (35)   
Recalling that $`\xi =1/(k\varphi )`$, we can see that these equations are identical to Equations (3) and (6).