10.7. COUNTING TRIANGLES
401
Other Triangles: We ﬁnd the other triangles a diﬀerent way. Consider each
edge (v1, v2). If both v1 and v2 are heavy hitters, ignore this edge. Suppose,
however, that v1 is not a heavy hitter and moreover v1 ≺v2. Let u1, u2, . . . , uk
be the nodes adjacent to v1. Note that k < √m. We can ﬁnd these nodes,
using the index on nodes, in O(k) time, which is surely O(√m) time. For each
ui we can use the ﬁrst index to check whether edge (ui, v2) exists in O(1) time.
We can also determine the degree of ui in O(1) time, because we have counted
all the nodes’ degrees. We count the triangle {v1, v2, ui} if and only if the edge
(ui, v2) exists, and v1 ≺ui. In that way, a triangle is counted only once – when
v1 is the node of the triangle that precedes both other nodes of the triangle
according to the ≺ordering. Thus, the time to process all the nodes adjacent
to v1 is O(√m). Since there are m edges, the total time spent counting other
triangles is O(m3/2).
We now see that preprocessing takes O(m) time. The time to ﬁnd heavy-
hitter triangles is O(m3/2), and so is the time to ﬁnd the other triangles. Thus,
the total time of the algorithm is O(m3/2).
10.7.3
Optimality of the Triangle-Finding Algorithm
It turns out that the algorithm described in Section 10.7.2 is, to within an
order of magnitude the best possible. To see why, consider a complete graph
on n nodes. This graph has m =
n
2

edges and the number of triangles is
n
3

. Since we cannot enumerate triangles in less time than the number of those
triangles, we know any algorithm will take Ω(n3) time on this graph. However,
m = O(n2), so any algorithm takes Ω(m3/2) time on this graph.
One might wonder if there were a better algorithm that worked on sparser
graphs than the complete graph. However, we can add to the complete graph
a chain of nodes with any length up to n2. This chain adds no more triangles.
It no more than doubles the number of edges, but makes the number of nodes
as large as we like, in eﬀect lowering the ratio of edges to nodes to be as close
to 1 as we like. Since there are still Ω(m3/2) triangles, we see that this lower
bound holds for the full range of possible ratios of m/n.
10.7.4
Finding Triangles Using MapReduce
For a very large graph, we want to use parallelism to speed the computation.
We can express triangle-ﬁnding as a multiway join and use the technique of
Section 2.5.3 to optimize the use of a single MapReduce job to count triangles.
It turns out that this use is one where the multiway join technique of that section
is generally much more eﬃcient than taking two two-way joins. Moreover, the
total execution time of the parallel algorithm is essentially the same as the
execution time on a single processor using the algorithm of Section 10.7.2.
To begin, assume that the nodes of a graph are numbered 1, 2, . . ., n. We
use a relation E to represent edges. To avoid representing each edge twice,
we assume that if E(A, B) is a tuple of this relation, then not only is there
