10.8. NEIGHBORHOOD PROPERTIES OF GRAPHS
405
!! (c) Assume we plan to use k Reduce tasks. For each of your joins from (a),
into how many buckets should you hash each of W, X, Y , and Z in order
to minimize the communication cost?
(d) Unlike the case of triangles, it is not guaranteed that each square is pro-
duced only once, although we can be sure that each square is produced by
only one of the three joins. For example, a square in which the two nodes
at opposite corners are each lower numerically than each of the other two
nodes will only be produced by the join (i). For each of the three joins,
how many times does it produce any square that it produces at all?
! Exercise 10.7.4: Show that the number of sequences of integers 1 ≤i ≤j ≤
k ≤b is
b+2
3

.
Hint: show that these sequences can be placed in a 1-to-1
correspondence with the binary strings of length b + 2 having exactly three 1’s.
10.8
Neighborhood Properties of Graphs
There are several important properties of graphs that relate to the number of
nodes one can reach from a given node along a short path.
In this section
we look at algorithms for solving problems about paths and neighborhoods for
very large graphs. In some cases, exact solutions are not feasible for graphs
with millions of nodes. We therefore look at approximation algorithms as well
as exact algorithms.
10.8.1
Directed Graphs and Neighborhoods
In this section we shall use a directed graph as a model of a network. A directed
graph has a set of nodes and a set of arcs; the latter is a pair of nodes written
u →v. We call u the source and v the target of the arc. The arc is said to be
from u to v.
Many kinds of graphs can be modeled by directed graphs. The Web is a
major example, where the arc u →v is a link from page u to page v. Or, the
arc u →v could mean that telephone subscriber u has called subscriber v in
the past month. For another example, the arc could mean that individual u is
following individual v on Twitter. In yet another graph, the arc could mean
that research paper u references paper v.
Moreover, all undirected graphs can be represented by directed graphs. In-
stead of the undirected edge (u, v), use two arcs u →v and v →u. Thus, the
material of this section also applies to graphs that are inherently undirected,
such as a friends graph in a social network.
A path in a directed graph is a sequence of nodes v0, v1, . . . , vk such that
there are arcs vi →vi+1 for all i = 0, 1, . . . , k −1. The length of this path is k,
the number of arcs along the path. Note that there are k + 1 nodes in a path
of length k, and a node by itself is considered a path of length 0.
