Scaling Properties of Random Walks on Small-World Networks

Abstract

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.

arXiv comment7 pages, 8 figures, two-column format. Submitted to PRE

References in corpus (20)

• Statistical mechanics of complex networks
• Epidemic spreading in scale-free networks
• Random graphs with arbitrary degree distributions and their applications
• The spread of epidemic disease on networks
• Evolution of networks
• Synchronization in small-world systems
• Renormalization group analysis of the small-world network model
• The Web of Human Sexual Contacts
• Scaling and percolation in the small-world network model
• Halting viruses in scale-free networks
• Fast Response and Temporal Coding on Coherent Oscillations in Small-World Networks
• Small world effect in an epidemiological model
• Diffusion, localization and dispersion relations on ``small-world'' lattices
• Small-world networks and the conformation space of a lattice polymer chain
• Relaxation Properties of Small-World Networks
• Random spread on the family of small-world networks
• Exact results and scaling properties of small-world networks
• Characterizing the structure of small-world networks
• Scaling of random spreading in small world networks
• Random spreading phenomena in annealed small world networks

Cited by in corpus (39)

• Analysis of weighted networks
• Spatial Networks
• Voter Model on Heterogeneous Graphs
• Random walks and diffusion on networks
• Network dynamics of innovation processes
• Exploring complex networks by walking on them
• First Passage Properties of the Erdos-Renyi Random Graph
• Random walks on complex trees
• Self-avoiding walks on scale-free networks
• Random walk and trapping processes on scale-free networks
• Ring structures and mean first passage time in networks
• Networking - A Statistical Physics Perspective
• Investigation of a Protein Complex Network
• Walks on Apollonian networks
• Walks on weighted networks
• Constrained spin dynamics description of random walks on hierarchical scale-free networks
• Hopping in the crowd to unveil network topology
• Traversal Times for Random Walks on Small-World Networks
• Network Discovery by Generalized Random Walks
• Dynamic topologies of activity-driven temporal networks with memory
• Random walks and diameter of finite scale-free networks
• Critical scaling in standard biased random walks
• Kinetic growth walks on complex networks
• A scale-free network hidden in the collapsing polymer
• Random walks on networks: cumulative distribution of cover time
• Critical properties of a dissipative sandpile model on small world networks
• Transport Properties of Random Walks on Scale-Free/Regular-Lattice Hybrid Networks
• Self-avoiding walks and connective constants in clustered scale-free networks
• Fractional dynamics on circulant multiplex networks: optimal coupling and long-range navigation for continuous-time random walks
• Random Walk Access Times on Partially-Disordered Complex Networks: an Effective Medium Theory
• Reactive explorers to unravel network topology
• Novel ballistic to diffusive crossover in the dynamics of a one dimensional Ising model with variable range of interaction
• Structurally dynamic spin market networks
• Full counting statistics of random transition-rate matrices
• In an Attempt to Introduce Long-range Interactions into Small-world Networks
• On The Critical Packet Injection Rate Of A Preferential Next-Nearest Neighbor Routing Traffic Model On Barabasi-Albert Networks
• Superdiffusion on complex networks: the role of shortcuts and long-range interactions
• Markov chain approach to anomalous diffusion on Newman-Watts networks
• Elastic properties of small-world spring networks