what-when-how
In Depth Tutorials and Information
Some of the compelling experiments done on the small-world phenomenon
were those conducted by Stanley Milgram and his coworkers in the 1960s. he
objective was to find links between any two people in the United States that did
not know each other. In the experiment, a source person would be given a letter
to send to a target person, with only their name and address being given. he
source would then be instructed to give the letter to someone they knew on a first-
name basis in order to transmit the letter. his next person would be given the
same instructions. his would continue until the letter was received by the target.
he results of the experiment showed that the average number of people between
each source and target was between five and six, and hence the “six degrees of
separation.”
Models of this phenomenon have focused on the question of why there exists
this chain of acquaintances between two random strangers. An early theory was
that uniformly random social networks have a low diameter. his means that two
people grouped together in a random network with symmetric acquaintanceship
would be linked by a short chain with high probability. However, the low diameter
in Milgram's experiments would not be achieved if the network was too clustered.
he results of Milgram's experiments really had two amazing features. he irst
was that these links between two people actually exist, and the second was that
people could actually find these connections while knowing so little about their
target person. While other models focused on the first of these, Kleinberg's paper
chooses to study the question of how people are able to find these links.
While it is easy to picture networks in which short chains exist, no mechanism
based solely on local information can ind them. he fact that it is possible for people
to find them suggests that there are latent navigational hints embedded in the net-
work by which messages can be guided quickly from source to target. Kleinberg's
work studies decentralized algorithms in which individuals attempt to transmit a
message along a short path knowing only the locations of their acquaintances.
To design this model, Kleinberg chooses a two-dimensional grid with directed
edges (Figure 5.6). he nodes of the grid represent individuals. he local contacts
of each node are the nodes that are within a lattice distance
p
. Long-range contacts
are represented by directed edges from
u
to
q
, and other nodes are constructed using
the universal constants
q
.
≥
0 and
r
.
≥
0. he i-th directed edge from
u
has endpoint
v
with probability to [d(
u,v
)]
-r
.
his model is easy to visualize: the nodes represent people on a grid who know
their neighbors for a number of steps in all directions and have a few long-distance
acquaintances. If
.
p
and
.
q
are constants, then different families of network models
can be obtained by varying
r
. Increasing
r
increases the clustering of a node's long-
range contacts near its vicinity. In this way,
r
is a basic parameter representing how
widely networked the underlying society of nodes is.
Selecting two arbitrary nodes in the network,
s
and
t
, we try to transmit a mes-
sage from
s
to
t
in as few steps as possible. As in the Milgram study, the message is
passed from the current holder to one of its local or long-range contacts using only
