Counting triangles is important for real-world network analysis (motif detection,transitivity ratio, clustering coefficient) Current approaches try to balance between accuracy, time and space complexity. In this work, we prove a theorem that serves as a basis for two algorithms:

• The EIGENTRIANGLE algorithm, an approximating algorithm with time and space complexity linear with respect to the number of edges. The algorithm is parallelizable and finds the total number of triangles with remarkable accuracy. The validity of this algorithm is verified in real-world data where we can get more than 24000 times faster performance than a straight-forward competitor as well as in stochastic Kronecker graphs.
• The KRONECKERTRC algorithm which counts the exact number of triangles in deterministic Kronecker graphs. Our algorithm outperforms all other triangle counting algorithms.

30 pages

This page maintained by reports@cs.cmu.edu