414
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
1. Compute a new value for Q by joining it with itself and thus discovering
paths of twice the length as those in Q, using the SQL query
SELECT DISTINCT q1.X, q2.Y
FROM Q q1, Q q2
WHERE q1.Y = q2.X;
2. Subtract Path from the relation Q computed in Step (1) Note that Step (1)
discovers all paths of length 2i+1. But some pairs connected by these paths
may also have shorter paths. The result of Step (2) is to leave in Q all
and only those pairs (u, v) such that the shortest path from u to v has
length exactly 2i+1.
3. Join Path with the new value of Q computed in Step (2), using the SQL
query
SELECT DISTINCT Q.X, Path.Y
FROM Q, Path
WHERE Q.Y = Path.X;
At the beginning of the round, Path contains all (y, z) such that the
shortest path from y to z has a length up to 2i+1 −1, and the new value
of Q contains all pairs (x, y) for which the shortest path from x to y is of
length 2i+1. Thus, the result of this query is the set of pairs (x, y) such
that the shortest path from x to y has a length between 2i+1 + 1 and
2i+2 −1, inclusive.
4. Set the new value of Path to be the union of the relation computed in
Step (3), the new value of Q computed in step (1), and the old value of
Path. These three terms give us all pairs (x, y) whose shortest path is of
length 2i+1 + 1 through 2i+2 −1, exactly 2i+1, and 1 through 2i+1 −1,
respectively.
Thus, the union gives us all shortest paths up to length
2i+2 −1, as required by the inductive hypothesis about what is true after
each round.
Each round of the smart transitive-closure algorithm uses steps that are joins,
aggregations (duplicate eliminations), or unions. A round can thus be imple-
mented as a short sequence of MapReduce jobs. Further, a good deal of work
can be saved if these operations can be combined, say by using the more general
patterns of communication permitted by a workﬂow system (see Section 2.4.1).
Interestingly, smart TC already incorporates the seminaive trick. At each
round, the relation Q contains only facts Q(u, v) that have never been in Q
before, since the shortest path from U to v is longer than the shortest paths
that were represented in Q at any previous round. Further, when we join Q
with Path, we are using only facts in Q that were not in Q in previous rounds,
so Q is a subset of what would be NewPath in the algorithm of Section 10.8.7.
