[StreamGraph] Fast Counting of Triangles in Large Real Networks: Algorithms and Laws

http://www.cs.cmu.edu/~ctsourak/tsourICDM08.pdf

Fast Counting of Triangles in Large Real Networks: Algorithms and Laws

How can we quickly nd 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 coe cient 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 Eigen-Triangle 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 TriangleParticipa-
tion laws) with surprising properties.