410
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
to consider node u again in the current round. By considering each member of
Reach only at the round after its reachability was discovered, we save a lot of
work.
The improved algorithm, which is an instance of what is called seminaive
evaluation,6 uses not only a set Reach(X) but also a set NewReach(X), con-
sisting of all and only those nodes that were ﬁrst discovered reachable at the
previous round. Initially, we set NewReach to be {v}, the source node, while
Reach is empty. We repeat the following steps until at some round, NewReach
is a subset of Reach; i.e., no new Reach facts can be discovered.
1. Insert each node in NewReach into Reach. If no change to Reach occurs,
then we have discovered all reachable nodes, and the iteration ends.
2. Otherwise, compute a new value for relation NewReach(X) by setting it
to be the result of the following query:
SELECT DISTINCT Arc.Y
FROM NewReach, Arc
WHERE Arc.X = NewReach.X;
10.8.6
Linear Transitive Closure
The method of Section 10.8.4 can be applied to compute the entire transitive
closure in parallel, if we compute the reachable set from each node. However,
there are more straightforward ways to compute the relation Path(X, Y ) from
the relation Arc(X, Y ), and also ways that are more eﬃcient. The simplest way
to compute transitive closure is to start with Path(x, Y ) equal to Arc(x, Y ),
and in each parallel round extend the lengths of paths that we know about
by extending paths by a single arc. This approach is called linear transitive
closure. In SQL terms, each round computes the new paths by
SELECT DISTINCT Path.X, Arc.Y
FROM Path, Arc
WHERE Arc.X = Path.Y;
As for reachability, we use the MapReduce algorithms for join and grouping-
and-aggregation to execute this query, and then take the union of the query
result with the old value of Path.
The result will be the value of Path for
the next round. The number of rounds we must execute is the same as for
reachability. After d rounds, where d is the diameter of the graph, we will have
6This rather strange term has a history behind it. In the 1980’s when it was ﬁrst observed
that “naive” algorithms for computing relations recursively by using the entire recursive
relation at each round could be improved by only considering the new tuples at each round, it
was assumed that shortly an even better approach, which could justify the name “not naive,”
would be discovered. Alas, no such improvement has ever been found, so we are left with the
term “seminaive.”
