title: Traversal times for random walks on small-world networks.
abstract: We study the mean traversal time for a class of random walks on Newman-Watts small-world networks, in which steps around the edge of the network occur with a transition rate that is different from the rate for steps across small-world connections. When f>>F, the mean time to traverse the network exhibits a transition associated with percolation of the random graph (i.e., small-world) part of the network, and a collapse of the data onto a universal curve. This transition was not observed in earlier studies in which equal transition rates were assumed for all allowed steps. We develop a simple self-consistent effective-medium theory and show that it gives a quantitatively correct description of the traversal time in all parameter regimes except the immediate neighborhood of the transition, as is characteristic of most effective-medium theories.
authors.affiliation: Consortium of the Americas for Interdisciplinary Science and Department of Physics and Astronomy, University of New Mexico, Albuquerque, New Mexico 87131, USA.
authors.forename: Paul E
authors.initials: PE
authors.lastname: Parris
authors.forename: V M
authors.initials: VM
authors.lastname: Kenkre