Estimating Edge-Local Triangle Count Heavy Hitters in Edge-Linear Time and Almost-Vertex-Linear Space
Benjamin W. Priest, Roger Pearce, Geoffrey Sanders · 2018
We describe a methodology for estimating edge-local triangle counts using cardinality approximation sketches. While the approach does not guarantee relative error bounds, we will show that it preserves triangle count heavy hitters - the edges incident upon the largest number of triangles - well in practice. Furthermore, we provide empirical evidence that the sum of edge-local estimations yield reasonable estimates of the global triangle count for free. In this paper we describe a two-pass algorithm for estimating edge-local triangle count heavy hitters. The algorithm requires time linear in the number of edges, memory almost linear in the number of vertices, and is easy to parallelize. We provide results on dozens of real-world and synthetic graphs.