404
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
with b = 6. That is, there are b3 = 216 Reduce tasks and the communication
cost is 3mb = 18m. We cannot use exactly 216 Reduce tasks with the method of
this section, but we can come very close if we choose b = 10. Then, the number
of Reduce tasks is
12
3

= 220, and the communication cost is mb = 10m. That
is, the communication cost is 5/9th of the cost of the straightforward method.
✷
10.7.6
Exercises for Section 10.7
Exercise 10.7.1: How many triangles are there in the graphs:
(a) Figure 10.1.
(b) Figure 10.9.
! (c) Figure 10.2.
Exercise 10.7.2: For each of the graphs of Exercise 10.7.1 determine:
(i) What is the minimum degree for a node to be considered a “heavy hitter”?
(ii) Which nodes are heavy hitters?
(iii) Which triangles are heavy-hitter triangles?
! Exercise 10.7.3: In this exercise we consider the problem of ﬁnding squares
in a graph. That is, we want to ﬁnd quadruples of nodes a, b, c, d such that the
four edges (a, b), (b, c), (c, d), and (a, d) exist in the graph. Assume the graph
is represented by a relation E as in Section 10.7.4. It is not possible to write a
single join of four copies of E that expresses all possible squares in the graph,
but we can write three such joins. Moreover, in some cases, we need to follow
the join by a selection that eliminates “squares” where one pair of opposite
corners are really the same node. We can assume that node a is numerically
lower than its neighbors b and d, but there are three cases,depending on whether
c is
(i) Also lower than b and d,
(ii) Between b and d, or
(iii) Higher than both b and d.
(a) Write the natural joins that produce squares satisfying each of the three
conditions above. You can use four diﬀerent attributes W, X, Y , and Z,
and assume that there are four copies of relation E with diﬀerent schemas,
so the joins can each be expressed as natural joins.
(b) For which of these joins do we need a selection to assure that opposite
corners are really diﬀerent nodes?
