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 F that is different from the rate f 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.

9 pages, 5 figures

References in corpus (1)

• Static Pairwise Annihilation in Complex Networks

Cited by in corpus (12)

• Random walks and diffusion on networks
• Synchronization in Weighted Uncorrelated Complex Networks in a Noisy Environment: Optimization and Connections with Transport Efficiency
• Walks on Apollonian networks
• Walks on weighted networks
• Extensions of Effective Medium Theory of Transport in Disordered Systems
• Effects of disorder in location and size of fence barriers on molecular motion in cell membranes
• Effective medium approximation for lattice random walks with long-range jumps
• Transport Properties of Random Walks on Scale-Free/Regular-Lattice Hybrid Networks
• Diffusion Processes on Small-World Networks with Distance-Dependent Random-Links
• Random Walk Access Times on Partially-Disordered Complex Networks: an Effective Medium Theory
• Universal scaling hypothesis of quantum spatial search in complex networks
• Markov chain approach to anomalous diffusion on Newman-Watts networks