Efficiently estimating the local number of triangles

With Luca Becchetti, Paolo Boldi and Aris Gionis we wrote this paper on triangle counting. It proposes an approximation of the number of triangles in which a node u participates based on the number of neighbors of it |S(u)| and a per-node counter Z_uv that can be computed easily by doing m sequential scans of the graph.

This algorithm uses an amount of memory in the order of the number of nodes, so it can scale well to collections of any size, and it is the first such algorithm as far as we know. It will be presented in Las Vegas, Nevada, in August 2008 at the ACM KDD conference.