400
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
10.7.2
An Algorithm for Finding Triangles
We shall begin our study with an algorithm that has the fastest possible running
time on a single processor. Suppose we have a graph of n nodes and m ≥n
edges. For convenience, assume the nodes are integers 1, 2, . . ., n.
Call a node a heavy hitter if its degree is at least √m.
A heavy-hitter
triangle is a triangle all three of whose nodes are heavy hitters. We use separate
algorithms to count the heavy-hitter triangles and all other triangles. Note that
the number of heavy-hitter nodes is no more than 2√m, since otherwise the sum
of the degrees of the heavy hitter nodes would be more than 2m. Since each
edge contributes to the degree of only two nodes, there would then have to be
more than m edges.
Assuming the graph is represented by its edges, we preprocess the graph as
follows:
1. Compute the degree of each node. This part requires only that we examine
each edge and add 1 to the count of each of its two nodes. The total time
required is O(m).
2. Create an index on edges, with the pair of nodes at its ends as the key.
That is, the index allows us to determine, given two nodes, whether the
edge between them exists. A hash table suﬃces. It can be constructed in
O(m) time, and the expected time to answer a query about the existence
of an edge is a constant, at least in the expected sense.2
3. Create another index of edges, this one with key equal to a single node.
Given a node v, we can retrieve the nodes adjacent to v in time propor-
tional to the number of those nodes. Again, a hash table, this time with
single nodes as the key, suﬃces in the expected sense.
We shall order the nodes as follows. First, order nodes by degree. Then, if
v and u have the same degree, recall that both v and u are integers, so order
them numerically. That is, we say v ≺u if and only if either
(i) The degree of v is less than the degree of u, or
(ii) The degrees of u and v are the same, and v < u.
Heavy-Hitter Triangles: There are only O(√m) heavy-hitter nodes, so we
can consider all sets of three of these nodes. There are O(m3/2) possible heavy-
hitter triangles, and using the index on edges we can check if all three edges exist
in O(1) time. Therefore, O(m3/2) time is needed to ﬁnd all the heavy-hitter
triangles.
2Thus, technically, our algorithm is only optimal in the sense of expected running time,
not worst-case running time. However, hashing of large numbers of items has an extremely
high probability of behaving according to expectation, and if we happened to choose a hash
function that made some buckets too big, we could rehash until we found a good hash function.
