Scaling properties of random walks on small-world networks

Using both numerical simulations and scaling arguments, we study the behavior of a random walker on a one-dimensional small-world network. For the properties we study, we find that the random walk obeys a characteristic scaling form. These properties include the average number of distinct sites visited by the random walker, the mean-square displacement of the walker, and the distribution of first-return times. The scaling form has three characteristic time regimes. At short times, the walker does not see the small-world shortcuts and effectively probes an ordinary Euclidean network in d dimensions. At intermediate times, the properties of the walker shows scaling behavior characteristic of an infinite small-world network. Finally, at long times, the finite size of the network becomes important, and many of the properties of the walker saturate. We propose general analytical forms for the scaling properties in all three regimes, and show that these analytical forms are consistent with our numerical simulations.