Asymptotic behavior of the Kleinberg model
arXiv:0901.4535 · doi:10.1103/PhysRevLett.102.238702
Abstract
We study Kleinberg navigation (the search of a target in a d-dimensional lattice, where each site is connected to one other random site at distance r, with probability proportional to r^{-a}) by means of an exact master equation for the process. We show that the asymptotic scaling behavior for the delivery time T to a target at distance L scales as (ln L)^2 when a=d, and otherwise as L^x, with x=(d-a)/(d+1-a) for a<d, x=a-d for d<a<d+1, and x=1 for a>d+1. These values of x exceed the rigorous lower-bounds established by Kleinberg. We also address the situation where there is a finite probability for the message to get lost along its way and find short delivery times (conditioned upon arrival) for a wide range of a's.
References in corpus (7)
- Navigability of Complex Networks
- Bidimensional intermittent search processes: an alternative to Levy flights strategies
- Extended navigability of small world networks: exact results and new insights
- Intermittent random walks for an optimal search strategy: One-dimensional case
- Kleinberg Navigation in Fractal Small World Networks
- Navigating ultrasmall worlds in ultrashort time
- Two-dimensional small-world networks: navigation with local information
Cited by in corpus (18)
- Designing optimal transport networks
- Long-Range Navigation on Complex Networks using Lévy Random Walks
- Quantum Google in a Complex Network
- Extended navigability of small world networks: exact results and new insights
- Annealed and Mean-Field formulations of Disease Dynamics on Static and Adaptive Networks
- Complex networks with tuneable dimensions as a universality playground
- Exact Solution for Optimal Navigation with Total Cost Restriction
- Robustness of Spatial Micronetworks
- Dynamics on Spatial Networks and the Effect of Distance Coarse Graining
- Greedy Connectivity of Geographically Embedded Graphs
- On the decentralized navigation of multiple packages on transportation networks
- Degree heterogeneity in spatial networks with total cost constraint
- Maximizing Entropy Yields Spatial Scaling in Social Networks
- Competition and evolution in restricted space
- Cost of material or information flow in complex transportation networks
- Universality of critical dynamics on a complex network
- Navigation in non-uniform density social networks
- Quantum Google Algorithm: Construction and Application to Complex Networks