Approximate Triangle Counting

Date Added: Jun 2009
Format: PDF

Triangle counting is an important problem in graph mining. Clustering coefficients of vertices and the transitivity ratio of the graph are two metrics often used in complex network analysis. Furthermore, triangles have been used successfully in several real-world applications. However, exact triangle counting is an expensive computation. In this paper the authors present the analysis of a practical sampling algorithm for counting triangles in graphs. The analysis yields optimal values for the sampling rate, thus resulting in tremendous speedups ranging from 2800x to 70000x when applied to real-world networks. At the same time the accuracy of the estimation is excellent.