408
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
Six Degrees of Separation
There is a famous game called “six degrees of Kevin Bacon,” the object
of which is to ﬁnd paths of length at most six in the graph whose nodes
are movie stars and whose edges connect stars that played in the same
movie. The conjecture is that in this graph, no movie star is of distance
more than six from Kevin Bacon. More generally, any two movie stars
can be connected by a path of length at most six; i.e., the diameter of
the graph is six. A small diameter makes computation of neighborhoods
more eﬃcient, so it would be nice if all social-network graphs exhibited
a similar small diameter. In fact, the phrase “six degrees of separation,”
refers to the conjecture that in the network of all people in the world,
where an edge means that the two people know each other, the diameter is
six. Unfortunately, as we shall discuss in Section 10.8.3, not all important
graphs exhibit such tight connections.
These two concepts relate to the notions of neighborhoods that we have seen
earlier. Deﬁne N(u, ∞) to be S
i≥0 N(u, i). Then v is in N(u, ∞) if and only
if v = u or Path(u, v) is true. Thus, the reachability problem is to compute
the union of all the neighborhoods of any radius for a given node u.
The
discussion in Section 10.8.2 reminds us that we can compute the reachable set
for u by computing its neighborhoods up to that smallest radius d for which
N(u, d) = N(u, d + 1).
The two problems – transitive closure and reachability – are related, but
there are many examples of graphs where reachability is feasible and transitive
closure is not. For instance, suppose we have a Web graph of a billion nodes.
If we want to ﬁnd the pages (nodes) reachable from a given page, we can do so,
even on a single machine with a large main memory. However, just to produce
the transitive closure of the graph could involve 1018 pairs of nodes, which is
not practical, even using a large computer cluster.5
10.8.4
Reachability Via MapReduce
When it comes to parallel implementation, transitive closure is actually more
readily parallelizable than is reachability. If we want to compute N(v, ∞), the
set of nodes reachable from node v, without computing the entire transitive
closure, we have no option but to compute the sequence of neighborhoods,
5While we cannot compute the transitive closure completely, we can still learn a great
deal about the structure of a graph, provided there are large strongly connected components.
For example, the Web graph experiments discussed in Section 5.1.3 were done on a graph of
about 200 million nodes. Although they never listed all the pairs of nodes in the transitive
closure, they were able to describe the structure of the Web. We discuss the needed algorithm
in Section 10.8.10.
