10.7. COUNTING TRIANGLES
399
(b) As a function of k, compute the conductance of the community consisting
of the ﬁrst k nodes.
(c) Using density as the measure of goodness for a community, what is the
best value of k?
(d) Using conductance as the measure of goodness for a community, what is
the best value of k?
10.7
Counting Triangles
One of the most useful properties of social-network graphs is the count of tri-
angles and other simple subgraphs. In this section we shall give methods for
estimating or getting an exact count of triangles in a very large graph. We be-
gin with a motivation for such counts and then give some methods for counting
eﬃciently.
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 diﬃculty. There are
n
3

sets of three nodes, or approximately
n3/6 sets of three nodes that might be a triangle. The probability of an edge
between any two given nodes being added is m/
n
2

, or approximately 2m/n2.
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
(2m/n2)3 = 8m3/n6. Thus, the expected number of triangles in a graph of
n nodes and m randomly selected edges is approximately (8m3/n6)(n3/6) =
4
3(m/n)3.
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 other. 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.
