Random Walk Access Times on Partially-Disordered Complex Networks: an Effective Medium Theory

Abstract

An analytic effective medium theory is constructed to study the mean access times for random walks on hybrid disordered structures formed by embedding complex networks into regular lattices, considering transition rates $F$ that are different for steps across lattice bonds from the rates $f$ across network shortcuts. The theory is developed for structures with arbitrary shortcut distributions and applied to a class of partially-disordered traversal enhanced networks in which shortcuts of fixed length are distributed randomly with finite probability. Numerical simulations are found to be in excellent agreement with predictions of the effective medium theory on all aspects addressed by the latter. Access times for random walks on these partially disordered structures are compared to those on small-world networks, which on average appear to provide the most effective means of decreasing access times uniformly across the network.

12 pages, 8 figures; added new results and discussion; added appendix on numerical procedures. To appear in PRE

References in corpus (21)

• Statistical mechanics of complex networks
• Evolution of networks
• Renormalization group analysis of the small-world network model
• Scaling and percolation in the small-world network model
• Efficient routing on complex networks
• Small world effect in an epidemiological model
• Diffusion, localization and dispersion relations on ``small-world'' lattices
• Exploring complex networks by walking on them
• Exploring Complex Networks through Random Walks
• Small-World Networks: Links with long-tailed distributions
• Small-world networks and the conformation space of a lattice polymer chain
• Random spread on the family of small-world networks
• Scaling Properties of Random Walks on Small-World Networks
• Synchronization in Weighted Uncorrelated Complex Networks in a Noisy Environment: Optimization and Connections with Transport Efficiency
• Small-World Rouse Networks as models of cross-linked polymers
• Scaling of random spreading in small world networks
• Vector opinion dynamics in a model for social influence
• Traversal Times for Random Walks on Small-World Networks
• Irreversible Opinion Spreading on Scale-Free Networks
• Irreversible growth of binary mixtures on small-world networks
• Transport Properties of Random Walks on Scale-Free/Regular-Lattice Hybrid Networks

Cited by in corpus (2)

• Extensions of Effective Medium Theory of Transport in Disordered Systems
• Effective medium approximation for lattice random walks with long-range jumps