10.8. NEIGHBORHOOD PROPERTIES OF GRAPHS
409
which is essentially a breadth-ﬁrst search of the graph from v. In relational
terms, suppose we have a relation Arc(X, Y ) containing those pairs (x, y) such
that there is an arc x →y. We want to compute iteratively a relation Reach(X)
that is the set of nodes reachable from node v. After i rounds, Reach(X) will
contain all those nodes in N(v, i).
Initially, Reach(X) contains only the node v. Suppose it contains all the
nodes in N(v, i) after some round of MapReduce.
To construct N(v, i + 1)
we need to join Reach with the Arc relation, then project onto the second
component and perform a union of the result with the old value of Reach. In
SQL terms, we perform
SELECT DISTINCT Arc.Y
FROM Reach, Arc
WHERE Arc.X = Reach.X;
This query asks us to compute the natural join of Reach(X) and Arc(X, Y ),
which we can do by MapReduce as explained in Section 2.3.7. Then, we have
to group the result by Y and eliminate duplicates, a process that can be done
by another MapReduce job as in Section 2.3.8.
We then take the union of the result of this query with the current value of
Reach. At some round, we will ﬁnd that there are no new Reach facts added,
and at that point we can stop. The current value of Reach will be N(v, ∞).
How many rounds this process requires depends on how far from v is the
furthest node that v can reach. In many social-network graphs, the diameter is
small, as discussed in the box on “Six Degrees of Separation.” If so, computing
reachability in parallel, using MapReduce or another approach, is feasible. Few
rounds of computation will be needed, and the space requirements are not
greater than the space it takes to represent the graph.
However, there are some graphs where the number of rounds is a serious
impediment. For instance, in a typical portion of the Web, it has been found
that most pages reachable from a given page are reachable by paths of length
10–15. Yet there are some pairs of pages such that the ﬁrst reaches the second,
but only through paths whose length is measured in the hundreds. For instance,
blogs are sometimes structured so each response is reachable only through the
comment to which it responds. Running arguments lead to long paths with
no way to ‘shortcut” around that path. Or a tutorial on the Web, with 50
chapters, may be structured so you can only get to Chapter i through the page
for Chapter i −1.
10.8.5
Seminaive Evaluation
There is a common trick that can make iterative evaluations such as that of
Section 10.8.4 more eﬃcient. There, at each round we joined the entire set of
known reachable nodes with the arcs. However, if we knew at a previous round
that node u was reachable, and there is an arc from u to some node w, then
we have already discovered that w is reachable. Therefore, it is not necessary
