CMU-ML-08-103
Machine Learning Department
School of Computer Science, Carnegie Mellon University



CMU-ML-08-103

Fast Counting of Triangles in Real-World Networks
Proofs, Algorithms and Observations

Charalampos E. Tsourakakis

May 2008

CMU-ML-08-103.pdf


Keywords: Triangles, algorithms, graph mining, Kronecker graphs


How can we quickly find the number of triangles in a large graph, without actually counting them? Triangles are important for real world social networks, lying at the heart of the clustering coefficient and of the transitivity ratio. However, straight-forward and even approximate counting algorithms can be slow, trying to execute or approximate the equivalent of a 3-way database join. In this paper, we provide two algorithms, the EIGENTRIANGLE for counting the total number of triangles in a graph, and the EIGENTRIANGLELOCAL algorithm that gives the count of triangles that contain a desired node. Additional contributions include the following: (a) We show that both algorithms achieve excellent accuracy, with up to 1000x faster execution time, on several, real graphs and (b) we discover two new power laws (DEGREE-TRIANGLE and TRIANGLEPARTICIPATION laws) with surprising properties.

20 pages


SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu