what-when-how
In Depth Tutorials and Information
v
w
u
(a)
(b)
Figure5.6
(A)Atwo-dimensionalgridnetworkwithn=6,p=1,andq=0.(B)
Thecontactsofanodeuwithp=1andq=2.vandwarethetwolong-range
contacts. (From J. Kleinberg, The small-world phenomenon: An algorithm per-
spective,
Annual ACM Symposium on Theory of Computing
,2000,pp.163-170.)
local information. Mechanisms guiding this are what institute decentralized algo-
rithms. he local information available to each holder,
u
, is as follows [5]:
1. Neighboring contacts among all nodes (i.e., the grid structure)
2. he location of the target
t
3. he locations of long-distance contacts of all nodes
With this,
u
must pass the message on to one of its contacts,
v
, without knowing
which of its long-range contacts have not touched the message. It is of interest to
find the number of steps taken by the algorithm to deliver the message over a net-
work generated according to an inverse
r
-
th-power distribution, from a source to a
target chosen uniformly at random from the set of nodes. his number is called the
expected delivery time. If
u
had any global knowledge of the nodes in the network,
the shortest path could be found with a simple search.
Kleinberg then moves on to study how the ability of a decentralized algorithm
to construct a short path is affected by the structure of the network. Noting that
r
= 0 results in the uniform distribution over long-range contacts, Kleinberg states
his first theorem regarding the notion that there is no way for a decentralized algo-
rithm to find short chains in the network. His
heorem1
states [5]:
hereisaconstant
α
0
,dependingonpandqbutindependentofn,sothat
whenr=0,theexpecteddeliverytimeofanydecentralizedalgorithmisat
least
α
0
n
2/3
.(Henceexponentialintheexpectedminimumpathlength.)
As
r
increases, the long-range contacts will be closer to
u
.
and can be used more
frequently since they have a higher chance of being able to move the message in
a certain direction. On the other hand, they will not be as useful in moving the
