402
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
an edge between nodes A and B, but also, as integers, we have A < B.3
This requirement also eliminates loops (edges from a node to itself), which we
generally assume do not exist in social-network graphs anyway, but which could
lead to “triangles” that really do not involve three diﬀerent nodes.
Using this relation, we can express the set of triangles of the graph whose
edges are E by the natural join
E(X, Y ) ⊲⊳E(X, Z) ⊲⊳E(Y, Z)
(10.5)
To understand this join, we have to recognize that the attributes of the relation
E are given diﬀerent names in each of the three uses of E. That is, we imagine
there are three copies of E, each with the same tuples, but with a diﬀerent
schemas. In SQL, this join would be written using a single relation E(A, B) as
follows:
SELECT e1.A, e1.B, e2.B
FROM E e1, E e2, E e3
WHERE e1.A = e2.A AND e1.B = e3.A AND e2.B = e3.B
In this query, the equated attributes e1.A and e2.A are represented in our join
by the attribute X. Also, e1.B and e3.A are each represented by Y ; e2.B and
e3.B are represented by Z.
Notice that each triangle appears once in this join. The triangle consisting
of nodes v1, v2, and v3 is generated when X, Y , and Z are these three nodes in
numerical order, i.e., X < Y < Z. For instance, if the numerical order of the
nodes is v1 < v2 < v3, then X can only be v1, Y is v2, and Z is v3.
The technique of Section 2.5.3 can be used to optimize the join of Equa-
tion 10.5. Recall the ideas in Example 2.9, where we considered the number
of ways in which the values of each attribute should be hashed. In the present
example, the matter is quite simple. The three occurrences of relation E surely
have the same size, so by symmetry, attributes X, Y , and Z will each be hashed
to the same number of buckets. In particular, if we hash nodes to b buckets,
then there will be b3 reducers. Each Reduce task is associated with a sequence
of three bucket numbers (x, y, z), where each of x, y, and z is in the range 1 to
b.
The Map tasks divide the relation E into as many parts as there are Map
tasks.
Suppose one Map task is given the tuple E(u, v) to send to certain
Reduce tasks. First, think of (u, v) as a tuple of the join term E(X, Y ). We
can hash u and v to get the bucket numbers for X and Y , but we don’t know
the bucket to which Z hashes. Thus, we must send E(u, v) to all Reducer tasks
that correspond to a sequence of three bucket numbers
h(u), h(v), z

for any
of the b possible buckets z.
3Do not confuse this simple numerical ordering of the nodes with the order ≺that we
discussed in Section 10.7.2 and which involved the degrees of the nodes. Here, node degrees
are not computed and are not relevant.
