416
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
Reachability and linear transitive closure will ﬁnd new Reach or Path facts until
the search implied by their iterations allow any node to be reached from any
other. That number of rounds is bounded by the diameter of the graph. When
computing the full transitive closure, there will always be some nodes u and v
such that the shortest path from u to v has distance d. Thus, linear transitive
closure always requires d rounds. However, when we search from one particular
node u, it is possible that it can reach all of the nodes it ever reaches using
paths much shorter than the diameter of the graph. That is, the value of d
could be determined by a pair of nodes that does not include u. For the two
recursive-doubling methods, the last two lines of Fig. 10.25, we noted that in
log2 d rounds, we discover all paths of length up to d, and therefore discover all
Path facts.
Now, consider the cost of the join in the seminaive version of the reachability
algorithm of Section 10.8.4. Each node u can be in NewReach at only one round.
In that round, it will meet all the arcs with head u at a reducer. Thus, over
all the rounds and all the reducers at each round, the cost of joining node u
with arcs is equal to the out-degree of u. Notice that each arc contributes to
the out-degree of exactly one node – the node at its tail. Thus, the sum of the
out-degrees of the nodes of a directed graph equals the number of arcs in the
graph. That observation justiﬁes the O(e) bound for the cost of a round for
reachability.
For seminaive linear transitive closure, consider a node u and the reducers
corresponding to u over all the rounds. For each node v, only one of these
reducers can receive the fact NewPath(v, u). At that round, this reducer will
join this fact with all the Arc(u, w) facts and thereby incur cost equal to the
out-degree of u. If we ﬁx v and let u vary, then the total work of all reducers
handling facts of the form NewPath(v, u) for any u is the sum of the out-degrees
of all nodes u, which is the total number of edges, e. Then, when we sum this
cost over all n of the nodes v, we ﬁnd that the total number of facts joined
among all the reducers at all the rounds is O(ne).
Next, look at the join associated with the seminaive recursive-doubling al-
gorithm of Section 10.8.7. Each fact NewPath(u, w) appears in NewPath at
only one round. At that round, it may meet any Path(v, u) fact. Thus, the
total work of all the reducers at all the rounds is n2 (for the number of diﬀerent
facts that may ever appear in NewPath) times n (for the number of Path facts
with which it may be joined when it appears. This argument justiﬁes the O(n3)
bound for seminaive recursive doubling.
Finally, look at smart transitive closure. Now, we are doing two joins at
each round: Q with itself, and Q with Path. A fact Q(u, w) can only appear
at one round, and at worst it will be joined with n other facts Q(v, u) at that
round. Thus, the total work is at most O(n3), which is the product of n2 facts
times a join with n facts. The argument for the second join, Q with Path, is
similar. Note that the upper bound on computation for smart TC is the same
as for recursive doubling. However, as we discussed in Section 10.8.8, there is
a strong likelihood that fewer pairs of Path facts will be connected using the
