Unusual percolation in simple small-world networks

We present an exact solution of percolation in a generalized class of Watts-Strogatz graphs defined on a one-dimensional underlying lattice. We find a nonclassical critical point in the limit of the number of long-range bonds in the system going to zero, with a discontinuity in the percolation probability and a divergence in the mean finite-cluster size. We show that the critical behavior falls into one of three regimes depending on the proportion of occupied long-range to unoccupied nearest-neighbor bonds, with each regime being characterized by different critical exponents. The three regimes can be united by a single scaling function around the critical point. These results can be used to identify the number of long-range links necessary to secure connectivity in a communication or transportation chain. As an example, we can resolve the communication problem in a game of “telephone.”

Figure 1

Examples of small-world graphs: (a) a fully connected ordered ring with $N=20$ vertices. (b) A graph generated by the original Watts-Strogatz algorithm with $k=1$ and $p_l=\varphi =1/5$, giving $p_s=4/5$. Note that every long-range link is created by reattaching the far end of the broken short-range link. (c) The Watts-Strogatz variant used for analytical calculations. Again $k=1$ and $\varphi =1/5$ but this time the addition of long-range bonds and deletion of short-range bonds is carried out independently; this makes the appearance of disconnected (finite) clusters more likely but does not prevent the appearance of small-world behavior. (d) A generalized Watts-Strogatz graph with $k=1$, $p=p_l=1/4$, and $n=1/2$, giving $p_s=1/2$.

Figure 2

Example of six sites forming part of a connected cluster with nearest-neighbor bonds (solid lines), long-range bonds (dot-dash), and ghost bonds (dashes). The ghost bonds connect sites (1), (3), and (5) to the ghost supersite, indicated by a black circle. For any finite value of $h$, a finite proportion of sites in the graph will be connected together via ghost bonds to the supersite, and so all clusters involving ghost bonds must belong to the infinite cluster.

Figure 3

Small-world trajectories: the lines (a)–(c) show examples of small-world trajectories superimposed on the phase diagram of the more general percolation system. The arrows show the direction of decreasing $p$. Trajectory (d) shows a nonsmall-world trajectory for which mean-field behavior holds at the transition. Trajectory (a), with $n=1$, corresponds to the standard Watts-Strogatz graph and is clearly always percolating. Trajectories (b) and (c), with $n=1/4$ and $n=1/8$, respectively, are always in the nonpercolating regime.

Figure 4

Numerical results for the standard $\left(n=1\right)$ Watts-Strogatz network: (a) cluster size generating function $G\left(p\right)$, (b) percolation probability $P\left(p\right)$, and (c) the mean finite-cluster size $S\left(p\right)$.