412
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
Reachability From Recursive Doubling
We have claimed that computing reachability inherently requires a number
of rounds equal to the diameter of the graph. That is not strictly true, but
there is a downside to deviating from the method given in Section 10.8.4 for
reachability. If we want the set Reach(v), we can compute the transitive
closure of the entire graph by recursive doubling, and then throw away all
pairs that do not have v as their ﬁrst component. But we cannot throw
away all those pairs until we are done. During the computation of the
transitive closure, we could wind up computing many facts Path(x, y),
where neither x nor y is reachable from v, and even if they are reachable
from v, we may not need to know x can reach y. If the graph is large, it
may be infeasible to store all the Path facts, even though we could store
the Reach facts.
union as the Path relation in the next round of recursive doubling. The query
itself can be implemented by two MapReduce jobs, one to do the join and the
other to do the union and eliminate duplicates. As we observed for the parallel
reachability computation, the methods of Sections 2.3.7 and 2.3.8 suﬃce. The
union, discussed in Section 2.3.6 doesn’t really require a MapReduce job of its
own; it can be combined with the duplicate-elimination.
If a graph has diameter d, then after log2 d rounds of the above algorithm
Path contains all pairs (x, y) connected by a path of length at most d; that is,
it contains all pairs in the transitive closure. Unless we already know d, one
more round will be necessary to verify that no more pairs can be found, but
for large d, this process takes many fewer rounds than the breadth-ﬁrst search
that we used for reachability.
However, the above recursive-doubling method does a lot of redundant work.
An example should make the point clear.
Example 10.31 : Suppose the shortest path from x0 to x17 is of length 17; in
particular, let there be a path x0 →x1 →· · · →x17. We shall discover the
fact Path(x0, x17) on the ﬁfth round, when Path contains all pairs connected by
paths of length up to 16. The same path from x0 to x17 will be discovered 16
times when we join Path with itself. That is, we can take the fact Path(x0, x16)
and combine it with Path(x16, x17) to obtain Path(x0, x17). Or we can combine
Path(x0, x15) with Path(x15, x17) to discover the same fact, and so on. On the
other hand, linear TC would discover this path only once: when Path(x0, x16)
was in NewPath.
✷
As for the previous algorithms, the recursive-doubling algorithm has a more
eﬃcient version that uses seminaive evaluation. Again, we use two relations,
Path(X, Y ) and NewPath(X, Y ).
Instead of joining two copies of Path, we
