title: Asymptotic behavior of the Kleinberg model.
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 approximately r(-alpha) 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 T approximately ln(2)L when alpha=d, and otherwise as T approximately L(x), with x=(d-alpha)/(d+1-alpha) for alpha<d, x=alpha-d for d<alpha<d+1, and x=1 for alpha>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 alpha's.
authors: Department of Physics, Bar-Ilan University, Ramat Gan 52900, Israel.
authors: Shai
authors: S
authors: Carmi
authors: Stephen
authors: S
authors: Carter
authors: Jie
authors: J
authors: Sun
authors: Daniel
authors: D
authors: Ben-Avraham
mesh_terms: D000465:Algorithms; D008962:Models, Theoretical; D012944:Social Support