what-when-how
In Depth Tutorials and Information
0.8
Lower bound T
on delivery time
(given as log n T)
0.6
0.4
0.2
Clustering exponent
r
0
0
1
2
3
4
5
Figure5.10
ThelowerboundimpliedbyTheorem3.TheX-axisisthevalueof
r;theY-axisistheresultingexponentonn.(FromJ.Kleinberg,Thesmall-world
phenomenon:Analgorithmperspective,
Annual ACM Symposium on Theory of
Computing
,2000,pp.163-170.)
chains whose length is a polynomial in log n. his leads to Kleinberg's
heorem3
[5] (see Figure 10):
a.Let0≤r<2.hereisaconstant
α
r,dependingonp,q,rbutinde-
pendentofn,sothattheexpecteddeliverytimeofanydecentralized
algorithmisatleast
α
rn
(2-r)/3
.
b.Letr>2.hereisaconstant
α
r,dependingonp,q,rbutindepen-
dent of n, so that the expected delivery time of any decentralized
algorithmisatleast
α
rn
(r-2)/(r-1)
.
hese results can be extended beyond two dimensions to an arbitrary k dimen-
sions with constant k as well as other graphs with similar scaling properties. In
the k-dimensional case, a decentralized algorithm can construct paths of length
polynomial in log n if and only if
r
=
k
. he proof of these theorems uncovers a
general structural property that brings to light the optimality of the
r
= 2 case for
two-dimensional grids: it is the single exponent at which a node's long-range con-
tacts are close to being uniformly distributed over all “distance scales.” he rest of
the paper [5] goes into detail explaining the proofs of these theorems. he proofs
are not covered in [5] since we are focusing on the overall explanation of the algo-
rithm along with the results and how they contribute to social networking models
as a whole.
In conclusion, Kleinberg reiterates how these results are quite different from
the results of previous studies, while sharing the general goal of identifying the
