Asymptotic behavior of the Kleinberg model

Details Asymptotic behavior of the Kleinberg model Asymptotic behavior of the Kleinberg model

2009-01-28

arxiv.org/abs/0901.4535v1

Physics

Condensed Matter

Statistical Mechanics

Scientific paper

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 ad+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.

Affiliated with

Also associated with

No associations

Rating

Asymptotic behavior of the Kleinberg model does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Asymptotic behavior of the Kleinberg model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asymptotic behavior of the Kleinberg model will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-345522