Database Reference
In-Depth Information
10.7.1
Why Count Triangles?
If we start with
n
nodes and add
m
edges to a graph at random, there will be an expected
number of triangles in the graph. We can calculate this number without too much difficulty.
There are sets of three nodes, or approximately
n
3
/6 sets of three nodes that might be a
triangle. The probability of an edge between any two given nodes being added is or ap-
proximately 2
m/n
2
. The probability that any set of three nodes has edges between each pair,
if those edges are independently chosen to be present or absent, is approximately (2
m/n
2
)
3
= 8
m
3
/n
6
. Thus, the expected number of triangles in a graph of
n
nodes and
m
randomly
selected edges is approximately (8
m
3
/n
6
)(
n
3
/6) =
If a graph is a social network with
n
participants and
m
pairs of “friends,” we would
expect the number of triangles to be much greater than the value for a random graph. The
reason is that if
A
and
B
are friends, and
A
is also a friend of
C
, there should be a much
greater chance than average that
B
and
C
are also friends. Thus, counting the number of
triangles helps us to measure the extent to which a graph looks like a social network.
We can also look at communities within a social network. It has been demonstrated that
the age of a community is related to the density of triangles. That is, when a group has just
formed, people pull in their like-minded friends, but the number of triangles is relatively
small. If
A
brings in friends
B
and
C
, it may well be that
B
and
C
do not know each oth-
er. As the community matures,
B
and
C
may interact because of their membership in the
community. Thus, there is a good chance that at sometime the triangle {
A, B, C
} will be
completed.
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 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 since otherwise the sum of the degrees of the heavy hitter nodes would
be more than 2
m
. 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:
