10.10. REFERENCES FOR CHAPTER 10
425
✦Transitive Closure and MapReduce: We can view transitive closure com-
putation as the iterative join of a path relation (pairs of nodes v and u
such that u is known to be reachable from v) and the arc relation of the
graph. Such an approach requires a number of MapReduce rounds equal
to the diameter of the graph.
✦Seminaive Evaluation: When computing the transitive closure for a graph,
we can speed up the iterative evaluation of the Path relation by recogniz-
ing that a Path fact is only useful on the round after that round when it
was ﬁrst discovered. A similar idea speeds up the reachability calculation
and many similar iterative algorithms.
✦Transitive Closure by Recursive Doubling: An approach that uses fewer
MapReduce rounds is to join the path relation with itself at each round.
At each round, we double the length of paths that are able to contribute
to the transitive closure. Thus, the number of needed rounds is only the
base-2 logarithm of the diameter of the graph.
✦Smart Transitive Closure: While recursive doubling can cause the same
path to be considered many times, and thus increases the total compu-
tation time (compared with iteratively joining paths with single arcs), a
variant called smart transitive closure avoids discovering the same path
more than once. The trick is to require that when joining two paths, the
ﬁrst has a length that is a power of 2.
✦Approximating Neighborhood Sizes: By using the Flajolet-Martin tech-
nique for approximating the number of distinct elements in a stream,
we can ﬁnd the neighborhood sizes at diﬀerent radii approximately. We
maintain a set of tail lengths for each node. To increase the radius by
1, we examine each edge (u, v) and for each tail length for u we set it
equal to the corresponding tail length for v if the latter is larger than the
former.
10.10
References for Chapter 10
Simrank comes from [8]. An alternative approach in [11] views similarity of two
nodes as the propability that random walks from the two nodes will be at the
same node. [3] combines random walks with node classiﬁcation to predict links
in a social-network graph. [16] looks at the eﬃciency of computing simrank as
a personalized PageRank.
The Girvan-Newman Algorithm is from [6]. Finding communities by search-
ing for complete bipartite graphs appears in [9].
Normalized cuts for spectral analysis were introduced in [13]. [19] is a sur-
vey of spectral methods for ﬁnding clusters, and [5] is a more general survey
of community ﬁnding in graphs. [10] is an analysis of communities in many
networks encountered in practice.
