期刊
PHYSICAL REVIEW LETTERS
卷 102, 期 23, 页码 -出版社
AMER PHYSICAL SOC
DOI: 10.1103/PhysRevLett.102.238702
关键词
-
资金
- Israel Science Foundation
- Israel Academy of Sciences and Humanities
- NSF [PHY-0555312]
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 similar to 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 similar to ln(2)L when alpha=d, and otherwise as T similar to L-x, with x=(d-alpha)/(d+1-alpha) for alpha < d, x=alpha-d for d < 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据