# Spreading and shortest paths in systems with sparse long-range connections.

## Abstract

Spreading according to simple rules (e.g. of fire or diseases) and shortest-path distances are studied on $`d`$-dimensional systems with a small density $`p`$ per site of *long-range connections* (“Small-World” lattices). The volume $`V(t)`$ covered by the spreading quantity on an infinite system is exactly calculated in all dimensions. We find that $`V(t)`$ grows initially as $`\mathrm{\Gamma }_dt^d/d`$ for $`t<<t^{}=(2p\mathrm{\Gamma }_d(d1)!)^{1/d}`$ and later exponentially for $`t>>t^{}`$, generalizing a previous result in one dimension. Using the properties of $`V(t)`$, the average shortest-path distance $`\mathrm{}(r)`$ can be calculated as a function of Euclidean distance $`r`$. It is found that $`\mathrm{}(r)r`$ for $`r<r_c=(2p\mathrm{\Gamma }_d(d1)!)^{1/d}\mathrm{log}(2p\mathrm{\Gamma }_dL^d)`$ and $`\mathrm{}(r)r_c`$ for $`r>r_c`$. The characteristic length $`r_c`$, which governs the behavior of shortest-path lengths, *diverges* with system size for all $`p>0`$. Therefore the mean separation $`sp^{1/d}`$ between shortcut-ends is not a relevant internal length-scale for shortest-path lengths. We notice however that the globally averaged shortest-path length $`\overline{\mathrm{}}`$ divided by $`L`$ is a function of $`L/s`$ only.

Regular $`d`$-dimensional lattices with a small density $`p`$ per site of long-ranged bonds (or “small-world” networks)  model the effect of weak unstructured (mean-field) interactions in a system where the dominant interactions have a regular $`d`$-dimensional structure, and thus may have many applications in physics as well as in other sciences .

In this work we study the spreading (See e.g.  and references therein) of some influence (e.g. a forest fire, or an infectious disease) according to the following simple law: we assume that, at each time-step, the fire or disease propagates from an burnt (or infected) site to all unburnt (uninfected) sites connected to it by a link. Long-range connections, or *shortcuts* represent sparks that start new fires far away from the original front, or, in the disease-spreading case, people who when first infected move to a random location amongst the non-infected population. For the dynamics of this simple problem, an important network property is the set of shortest-path distances $`\{\mathrm{}_{ij}\}`$, where $`\mathrm{}_{ij}`$ is defined as the minimum number of links one has to traverse between $`i`$ and $`j`$. On isotropic $`d`$-dimensional lattices $`\mathrm{}_{ij}`$ is proportional to $`d_{ij}^E`$, the Euclidean distance between $`i`$ and $`j`$. On regular lattices, both the number of sites within an Euclidean distance $`r`$ from $`i`$, and the number of sites within $`r`$ nearest-neighbor steps from $`i`$ behave as $`r^d`$.

Disorder can modify this in several ways. On a random fractal, the number of sites contained in a volume of Euclidean radius $`r`$ is $`r^{d_f}`$ , where $`d_f<d`$ is the fractal dimension. On the other hand, the number of sites visited in at most $`\mathrm{}`$ steps is $`\mathrm{}^{d_f/d_{min}}`$ , where $`d_{min}1`$ is the *shortest-path dimension*, defined such that $`\mathrm{}r^{d_{min}}`$. On fractals, shortest-path lengths $`\mathrm{}(r)`$ are thus much *larger* than Euclidean distances $`r`$.

Consider now a randomly connected network. If we have $`L^d`$ sites sitting on a regular $`d`$-dimensional lattice, but connect them at random with an average coordination number $`C`$ (i.e. a total of $`L^dC/2`$ bonds), the number of sites in a volume of radius $`r`$ is still $`r^d`$, but we can visit $`C^k`$ sites in $`k`$ steps. Thus all $`L^d`$ sites can be visited in $`𝒪(\mathrm{log}L^d)`$ steps, and therefore the typical shortest-path distance $`\overline{\mathrm{}}`$ is of order $`\mathrm{log}L`$, much *shorter* than the typical Euclidean distance $`\overline{r}L`$.

“Small-World” networks  are intermediate between the regular lattice, where $`\overline{\mathrm{}}L`$, and the random graph, where $`\overline{\mathrm{}}\mathrm{log}L`$. They consist of a regular $`d`$-dimensional lattice with $`N=L^d`$ sites, on which $`pL^d`$ *additional* long-range bonds have been connected between randomly chosen pairs of sites. The key finding of Watts and Strogatz  is that a vanishingly small density $`p`$ of long-range bonds is enough to make shortest-path distances proportional to $`\mathrm{log}L`$ instead of $`L`$. If $`L^dp<<1`$, the system typically contains no shortcuts, and the average shortest-path distance $`\overline{\mathrm{}}=1/N^2_{<ij>}\left[\mathrm{}_{ij}\right]_p`$ scales as $`L`$. If on the other hand $`L^dp>>1`$, one finds $`\overline{\mathrm{}}\mathrm{log}L`$ . For any fixed density $`p`$ of long-ranged bonds, a *crossover-size* $`L^{}(p)`$ exists , above which shortest-path distances are only logarithmically increasing with $`L`$. This crossover size diverges as $`p^{1/d}`$  when $`p0`$. The nature of the small-world transition at $`p=0`$ was recently discussed controversially. It is still a matter of debate  whether $`p=0`$ can be regarded as being equivalent to a critical point.

In this work we calculate the volume $`V(t)`$ that is covered, on a small-world network, by a spreading quantity as a function of time  when the spreading law is the simple rule above, and derive an exact expression for the average shortest-path $`\mathrm{}(r)`$ on these systems.

Assume a disease spreads with constant radial velocity $`v=1`$ from an original infection site $`A`$, as shown in Fig. 1. Let $`\rho =2p`$ be the density of *shortcut-ends* on the system. We work on the continuum for simplicity, so that the infected volume will initially grow as a sphere of radius $`t`$ and surface $`\mathrm{\Gamma }_dt^{d1}`$. We call the sphere stemming from $`A`$ “primary sphere”.

Each time the primary sphere hits a shortcut end, which happens with probability $`\rho \mathrm{\Gamma }_dt^{d1}`$ per unit time, a new sphere (“secondary”) starts to grow from a random point in non-infected space (the other end of the shortcut). These in turn later give rise to further secondary spheres in the same fashion.

Following Newman and Watts , we notice that the total infected volume is the sum of the primary volume $`\mathrm{\Gamma }_d_0^t\tau ^{d1}𝑑\tau `$ plus a contribution $`V(t\tau )`$ for each new sphere born at time $`\tau `$. Thus in the continuum the average total infected volume satisfies

$$V(t)=\mathrm{\Gamma }_d_0^t\tau ^{d1}\left\{1+\rho V(t\tau )\right\}𝑑\tau ,$$
(1)   
which can be rewritten in terms of rescaled variables $`\stackrel{~}{V}=\rho V`$ and $`\stackrel{~}{t}=(\rho \mathrm{\Gamma }_d(d1)!)^{1/d}t`$ as

$$\stackrel{~}{V}(\stackrel{~}{t})=\frac{1}{(d1)!}_0^{\stackrel{~}{t}}(\stackrel{~}{t}\stackrel{~}{\tau })^{d1}\left\{1+\stackrel{~}{V}(\stackrel{~}{\tau })\right\}𝑑\stackrel{~}{\tau }$$
(2)   
It is interesting to notice that $`\stackrel{~}{V}`$ is the total number of infected shortcut-ends, while $`\stackrel{~}{t}^d/d!`$ is the total number of shortcut-ends infected by the primary sphere. On an infinite system, the functional relation (2) that links these two variables has no parameters except for the space dimensionality $`d`$. On a system of finite volume $`\mathrm{\Gamma }_dL^d/d`$, an important parameter is the rescaled linear size $`\stackrel{~}{L}=(\rho \mathrm{\Gamma }_d(d1)!)^{1/d}L`$, whose $`d`$-th power gives the total number $`N_s`$ of shortcut-ends as $`N_s=\stackrel{~}{L}^d/d!`$.

Deriving (2) $`d`$ times with respect to $`\stackrel{~}{t}`$ we obtain

$$\frac{^d}{\stackrel{~}{t}^d}V(\stackrel{~}{t})=1+V(\stackrel{~}{t}),$$
(3)   
whose solution is

$$\stackrel{~}{V}(\stackrel{~}{t})=\underset{k=1}{\overset{\mathrm{}}{}}\frac{\stackrel{~}{t}^{dk}}{(dk)!}$$
(4)   
Notice that (4) is a series expansion of $`(e^{\stackrel{~}{t}}1)`$ with all powers not multiples of $`d`$ removed. Thus (4) can be written as a sum of $`d`$ exponentials, each with a different $`d`$-root of $`1`$ in its argument. In this way, powers which are not multiples of $`d`$ cancel out.

$$\stackrel{~}{V}(\stackrel{~}{t})=\frac{1}{d}\underset{n=0}{\overset{d1}{}}\mathrm{exp}\{\mu _d^n\stackrel{~}{t}\}1$$
(5)   
where $`\mu _d=e^{i2\pi /d}`$. Some specific examples are

$`\begin{array}{cccc}\stackrel{~}{V}(\stackrel{~}{t})\hfill & =& e^{\stackrel{~}{t}}1\hfill & \text{in 1d,}\hfill \\ & & & \\ \stackrel{~}{V}(\stackrel{~}{t})\hfill & =& \mathrm{cosh}\stackrel{~}{t}1\hfill & \text{in 2d,}\hfill \\ & & & \\ \stackrel{~}{V}(\stackrel{~}{t})\hfill & =& \frac{e^{\stackrel{~}{t}}+e^{\mu _3\stackrel{~}{t}}+e^{\mu _{3}^{}{}_{}{}^{2}\stackrel{~}{t}}}{3}1\hfill & \text{in 3d,}\hfill \end{array}`$

where the one-dimensional solution coincides with that previously derived by other methods .

A general property of (4) is that $`\stackrel{~}{V}`$ grows as $`\stackrel{~}{t}^d/d!`$ for $`\stackrel{~}{t}<1`$, and later exponentially as $`e^{\stackrel{~}{t}}/d`$. Thus the characteristic timescale  for the spreading process is $`t^{}=(\rho \mathrm{\Gamma }_d(d1)!)^{1/d}`$.

Notice that (1), and thus also (4), only hold on an infinite system. On a finite system with $`\stackrel{~}{L}^d>>1`$, $`\stackrel{~}{V}`$ will saturate after a time $`\stackrel{~}{t}_{sat}`$ that can be estimated by equating $`\stackrel{~}{V}e^{\stackrel{~}{t}_{sat}}/d\stackrel{~}{L}^d/d!`$ and therefore

$$\stackrel{~}{t}_{sat}\mathrm{log}(\stackrel{~}{L}^d/(d1)!),$$
(6)   
which can be rewritten as

$$t_{sat}(\rho \mathrm{\Gamma }_d(d1)!)^{1/d}\mathrm{log}(\rho \mathrm{\Gamma }_dL)$$
(7)   
If on the other hand $`\stackrel{~}{L}^d<<1`$, the spreading stops at $`\stackrel{~}{t}_{sat}=\stackrel{~}{L}`$, before reaching the exponential growth regime.

Thus for a finite system with $`\stackrel{~}{L}^d>>1`$ one has

$$\stackrel{~}{V}(\stackrel{~}{t})d\{\begin{array}{ccc}\stackrel{~}{t}^d/d!\hfill & \text{ for }& \stackrel{~}{t}<<1\hfill \\ e^{\stackrel{~}{t}}/d\hfill & \text{ for }& 1<<\stackrel{~}{t}<\stackrel{~}{t}_{sat}\mathrm{log}(\frac{\stackrel{~}{L}^d}{(d1)!})\hfill \\ \stackrel{~}{L}^d/d!\hfill & \text{ for }& \stackrel{~}{t}>\stackrel{~}{t}_{sat}\hfill \end{array}$$
(8)   
Assume now that $`\stackrel{~}{L}^d>>1`$. Because of the exponentially fast spreading process, the fraction of the total volume covered by the disease is negligible for $`\stackrel{~}{t}<\stackrel{~}{t}_{sat}`$ and saturates to one abruptly at $`t=t_{sat}`$. Therefore on a large system most of the points become infected essentially at the same time $`\stackrel{~}{t}_{sat}`$.

Now let us see how to calculate the average shortest-path distance $`\mathrm{}(r)`$ as a function of the Euclidean separation $`r`$ between two points. Since we assumed that the disease spreads with unit velocity, it is clear that the time $`t`$ at which a point $`x`$ becomes first infected is exactly the shortest-path distance $`\mathrm{}(A,x)`$ from $`A`$ to $`x`$. By definition, no part of the finite system remains uninfected after $`t=t_{sat}`$, so we conclude that no shortest-path distance can be larger than $`t_{sat}`$ on a finite system. Combining this with the fact that $`\mathrm{}(r)`$ cannot decrease with increasing $`r`$, we conclude that

$$\mathrm{}(r)=t_{sat}\text{for}rt_{sat}$$
(9)   
In order to calculate $`\mathrm{}(r)`$ for $`r<t_{sat}`$, let us write $`V(t)=V_1(t)+V_2(t)`$, where $`V_1`$ is the primary volume and $`V_2`$ the volume infected by secondary spheres.

Let $`p_2(t)`$ be the probability to become infected by the secondary infection exactly at time $`tt_{sat}`$. Consequently $`I_2(t)=_0^tp_2(\tau )𝑑\tau `$ is the probability for a point to become infected at time $`t`$ or earlier. Assuming that $`p_2(t)`$ is known, it is easy to calculate the average shortest-path distance $`\mathrm{}(r)`$ as a function of Euclidean distance $`r`$, according to the following. If an individual at $`x`$ becomes infected by a secondary sphere at time $`\tau <d^E(A,x)`$, its shortest-path distance $`\mathrm{}(A,x)`$ to $`A`$ is $`\tau `$. Otherwise if $`x`$ is still uninfected at time $`t=d^E(A,x)`$ (which happens with probability $`1I_2(d^E(A,x))`$), then $`\mathrm{}(A,x)=d^E(A,x)`$, since at that time the primary sphere hits $`x`$ with probability one. Therefore the average shortest-path satisfies

$`\mathrm{}(r)`$ $`=`$ $`{\displaystyle _0^r}tp_2(t)𝑑t+r\left\{1I_2(r)\right\}`$ (10)   
$`=`$ $`r{\displaystyle _0^r}I_2(t)𝑑t`$ (11)   
The fact that the secondary volume $`V_2`$ is randomly distributed in space makes this problem relatively simple. The probability $`I_2(t)`$ for a point to be infected by the secondary version of the disease at time $`t`$ or earlier is simply $`I_2=V_2(t)/(1/d\mathrm{\Gamma }_dL^d)`$, i.e. the fraction of the total volume which is covered by the secondary infection. Thus

$$\mathrm{}(r)=r\frac{d}{\mathrm{\Gamma }_dL^d}_0^rV_2(t)𝑑t$$
(12)   
If there are no shortcuts on the system, $`V_2`$ is zero at all times and thus $`\mathrm{}(r)=r`$ as expected. But it is also clear from this expression that $`\mathrm{}(r)=r`$ when $`L\mathrm{}`$, for all *finite* $`r`$, i.e. in the thermodynamic limit the shortest-pat distance $`\mathrm{}(r)`$ coincides with the Euclidean distance $`r`$ for all *finite* $`r`$, no matter what $`\rho `$ is.

On a finite system with $`\stackrel{~}{L}^d>>1`$, $`V_2(t)/L^d`$ is negligible for all $`t<t_{sat}`$ as we have already noticed. Therefore $`\mathrm{}(r)=r`$ if $`r<t_{sat}`$. Combining this with (9) we have

$$\mathrm{}(r)\{\begin{array}{ccc}r\hfill & \text{for}\hfill & r<r_c=(\rho \mathrm{\Gamma }_d(d1)!)^{1/d}\mathrm{log}(\rho \mathrm{\Gamma }_dL^d)\hfill \\ r_c\hfill & \text{for}\hfill & rr_c\hfill \end{array}$$
(13)   
Detailed knowledge of $`\mathrm{}(r)`$ for $`r=r_c`$ would only be possible if the finite-size effects that we ignored in (2) were exactly known, but the interesting remark is that the lack of this knowledge has little or no importance for $`rr_c`$.

We thus see that on a *finite* system, a characteristic length $`r_c=(\rho \mathrm{\Gamma }_d(d1)!)^{1/d}\mathrm{log}(\rho \mathrm{\Gamma }_dL^d)`$ exists, that governs the behavior of average shortest-path distances as a function of Euclidean separation. This characteristic length diverges when $`L\mathrm{}`$, for any $`\rho >0`$. The typical separation $`s=\rho ^{1/d}`$ between shortcut ends , which is size-independent, is *not relevant* for $`\mathrm{}(r)`$. The validity of (13) has been verified numerically in one dimension recently .

It is interesting to notice that the rescaled shortest-path distance $`\stackrel{~}{\mathrm{}}=(\rho \mathrm{\Gamma }_d)^{1/d}\mathrm{}`$ is a simple function of the rescaled Euclidean distance $`\stackrel{~}{r}=(\rho \mathrm{\Gamma }_d)^{1/d}r`$.

$$\stackrel{~}{\mathrm{}}(\stackrel{~}{r})=\{\begin{array}{ccc}\stackrel{~}{r}\hfill & \text{for}\hfill & \stackrel{~}{r}<1\hfill \\ 1\hfill & \text{for}\hfill & \stackrel{~}{r}1\hfill \end{array}$$
(14)   
Using (13) we can now calculate $`\overline{\mathrm{}}(\rho ,L)`$, the (global) average shortest-path length , when $`\stackrel{~}{L}^d>>1`$. One has

$`\overline{\mathrm{}}(\rho ,L)`$ $`=`$ $`{\displaystyle \frac{d}{L^d}}{\displaystyle _0^L}\mathrm{}(r)r^{d1}𝑑r`$ (15)   
$`=`$ $`{\displaystyle \frac{d}{L^d}}{\displaystyle _0^{r_c}}r^d𝑑r+{\displaystyle \frac{r_cd}{L^d}}{\displaystyle _{r_c}^L}r^{d1}𝑑r`$ (16)   
$`=`$ $`r_c\left[1{\displaystyle \frac{1}{d+1}}\left({\displaystyle \frac{r_c}{L}}\right)^d\right]`$ (17)   
So that the “order parameter” $`=\overline{\mathrm{}}/L`$  reads

$$=z(1\frac{z^d}{d+1})$$
(18)   
where $`z=r_c/L`$.

When $`\rho 0`$ faster than $`L^{1/d}`$ (so that $`\stackrel{~}{L}^d<<1`$), formula (16) holds with $`r_cL`$, and thus $`d/(d+1)`$ as expected. On the other hand if $`\rho >0`$ one has that $`r_c<<L`$ when $`L\mathrm{}`$, and thus $`0`$ in this limit. Therefore $``$ undergoes a discontinuity at $`\rho =0`$ in the $`L\mathrm{}`$ limit .

Notice that $`r_c/L=\mathrm{log}(\rho \mathrm{\Gamma }_dL^d)/L(\rho \mathrm{\Gamma }_d(d1)!)^{1/d}\mathrm{log}(L/s)/(L/s)`$, , where $`s\rho ^{1/d}`$  is the mean separation between shortcut-ends. Thus $``$ can be written as a function of $`L/s`$ only. Therefore if we measure $``$ on systems with several values of $`L`$ and $`\rho `$ and plot the data versus $`L/s`$, we would find that they *collapse* . Because of this behavior some authors  have suggested that the transition at $`\rho =0`$ is a *critical point* with a size-independent characteristic length $`\xi s\rho ^{1/d}`$. Our results here and in previous work  suggest that this is not the case. According to our calculation, the only characteristic length in regard to shortest-paths is $`r_c`$, and it diverges with system size $`L`$.

We have thus shown that, on a finite system with $`L^dp>>1`$, two widely separated timescales for spreading can be identified. The first one $`t^{}=(2p\mathrm{\Gamma }_d(d1)!)^{1/d}`$ determines the crossover from normal (i.e. proportional to $`t^d`$) to exponential spreading. A much larger timescale $`t_{sat}`$ given by (7) determines the saturation of the spreading process. This second timescale coincides with the lengthscale $`r_c`$ at which the behavior of shortest path lengths $`\mathrm{}(r)`$ saturates, as given by Eq. (13).

It is clear from our calculation that $`r_c`$ diverges with $`L`$ because the locations of the secondary spheres are uncorrelated with the location of the primary infection. In other words, because on a system of size $`L`$, the typical separation between both ends of a shortcut scales as $`L`$. A different situation would certainly arise if shortcuts had a length-dependent distribution. For example one can connect each site $`i`$, with probability $`p`$, to a single other site $`j`$, chosen with probability $`r_{ij}^\alpha `$, where $`\alpha `$ is a free parameter. For $`\alpha 0`$, this model is the same as discussed here, while for $`\alpha `$ large one would only have short-range connections and thus there would be no short-distance regime, even for $`p=1`$. We are presently studying this general model .

###### Acknowledgements.

I acknowledge useful discussions with M. Argollo de Menezes. This work is supported by FAPERJ.