Becchetti et al. present efficient approximation algorithms that count the number of local triangles in large graphs (both undirected and directed). They suggest possible applications of the counting algorithms for Web spam detection and local clustering of social networks.

Counting local triangles in a small graph can be done with a brute-force approach. However, when counting local triangles in a large graph with millions of vertices and edges that model the Web, one must consider the spatial and time complexities of the counting algorithms. In this paper, the authors report that their algorithms use O(|V|) space in main memory and perform O(log|V|) sequential scans over the edges of the graph.

The basic building block of their algorithmic approach is “to estimate the size of the intersection of two sets” by using fast pseudorandom numbers to label the vertices of a graph. After presenting the theoretical foundations, the authors propose their counting algorithms for both undirected graphs and digraphs. Then, they report their experimental results on large graphs, mostly with millions of nodes and billions of edges. The experiments not only demonstrate the efficiency of their algorithms, but also show improved accuracy in some cases.

This paper is theoretical. That being said, practitioners could reasonably implement the algorithms in pseudocode, particularly since readers can follow the links provided at the end of the paper to download the Java code and test applications.