Random spread on the family of small-world networks

Abstract

We present the analytical and numerical results of a random walk on the family of small-world graphs. The average access time shows a crossover from the regular to random behavior with increasing distance from the starting point of the random walk. We introduce an {\em independent step approximation}, which enables us to obtain analytic results for the average access time. We observe a scaling relation for the average access time in the degree of the nodes. The behavior of average access time as a function of $p$, shows striking similarity with that of the {\em characteristic length} of the graph. This observation may have important applications in routing and switching in networks with large number of nodes.

RevTeX4 file with 6 figures

References in corpus (4)

• Scaling and percolation in the small-world network model
• Epidemics and percolation in small-world networks
• Spreading and shortest paths in systems with sparse long-range connections
• Exact results and scaling properties of small-world networks

Cited by in corpus (36)

• The structure and function of complex networks
• Evolution of networks
• Random walks and diffusion on networks
• Exploring complex networks by walking on them
• Exact solution for mean first-passage time on a pseudofractal scale-free web
• Exploring Complex Networks through Random Walks
• A dynamic model of time-dependent complex networks
• Self-avoiding walks on scale-free networks
• Scaling Properties of Random Walks on Small-World Networks
• Explicit determination of mean first-passage time for random walks on deterministic uniform recursive trees
• Return times of random walk on generalized random graphs
• Characterizing the structure of small-world networks
• Networking - A Statistical Physics Perspective
• Trapping in scale-free networks with hierarchical organization of modularity
• Evolving small-world networks with geographical attachment preference
• Random walks in modular scale-free networks with multiple traps
• Dynamic Transitions in Small World Networks: Approach to Equilibrium
• Walks on Apollonian networks
• Walks on weighted networks
• Self-avoiding walks and connective constants in small-world networks
• Enhancement of spatiotemporal regularity in an optimal window of random coupling
• Constrained spin dynamics description of random walks on hierarchical scale-free networks
• Ising model in clustered scale-free networks
• Antiferromagnetic Ising model in small-world networks
• Random spreading phenomena in annealed small world networks
• Intentional Walks on Scale Free Small Worlds
• Kinetic growth walks on complex networks
• Kinetic-growth self-avoiding walks on small-world networks
• Self-avoiding walks and connective constants in clustered scale-free networks
• Transport Properties of Random Walks on Scale-Free/Regular-Lattice Hybrid Networks
• Zero-temperature Glauber dynamics on small-world networks
• Random Walk Access Times on Partially-Disordered Complex Networks: an Effective Medium Theory
• Intermittent exploration on a scale-free network
• Small-Worlds, Mazes and Random Walks
• Unusual percolation in simple small-world networks
• Markov chain approach to anomalous diffusion on Newman-Watts networks