PEGASUS - Large Scale and Big Data: Processing and Management - page 257

8.2.1.2 Six Degrees of Separation
Six degrees of separation is the theory that anyone in the world is no more than six rela-
tionships away from any other person. In the early twentieth century, Nobel Peace Prize
winner Guglielmo Marconi, the father of modern radio, suggested that it would take
only six relay stations to cover and connect the earth by radio [37]. It is likely that this
idea was the seed for the six degrees of separation theory, which was further supported
by Frigyes Karinthy in a short story called Chains . Since then, many scientists, includ-
ing Michael Gurevich, Ithiel De Sola Pool have worked on this theory. In a famous
experiment, Stanley Milgram asked people to route a postcard to a fixed recipient by
passing them to direct acquaintances [39]. Milgram observed that depending on the
sample of people chosen the average number of intermediaries was between 4.4 and 5.7.
Nowadays, the World Wide Web and online social networks provide us with data
that reach the planetary scale. Recently, Backstrom, Boldi, Rosa, Ugander, and Vigna
show that the world is even smaller than what the six degrees of separation theory
predicts [7]. Specifically, they perform the first world-scale social-network graph-
distance computation, using the entire Facebook network of active users (at that time
721 million users, 69 billion friendship links) and observe an average distance of 4.74.
8.2.2 g raPh t heoretiC D eFinitions
First, we review basic graph theoretic definitions [14] and then introduce the notions
of effective radius and diameter. Let G ( V , E ) be a directed graph. The radius/eccen-
tricity of a vertex v is the greatest shortest-path distance between v and any other
vertex. The radius r ( G ) is the minimum radius of any vertex. The diameter d ( G ) is
the maximum radius of any vertex. Since the radius and the diameter are susceptible
to outliers (e.g., long chains), we follow the literature [31] and define the effective
radius and diameter as follows.
Definition 8.1 (Effective Radius)
For a node v in a graph G, the effective radius r eff (v) of v is the 90th percentile of all
the shortest distances from v .
Definition 8.2 (Effective Diameter)
The effective diameter d eff (G) of a graph G is the minimum number of hops in which
90% of all connected pairs of nodes can reach each other .
In Section 8.6, we use the following three radius-based plots:
1. Static Radius Plot (or just “radius plot”) of graph G shows the distribution
(count) of the effective radius of nodes at a specific time.
2. Temporal Radius Plot shows the distributions of effective radius of nodes
at several times.
3. Radius-Degree Plot shows the scatter-plot of the effective radius r eff ( v ) vs.
the degree d v for each node v .