Communication-Efficient Triangle Counting

Counting and finding triangles in graphs is often used in real-world analytics to characterize cohesiveness and identify communities in graphs. In this paper, we present novel sequential and parallel triangle counting algorithms based on identifying horizontal-edges in a breadth-first search (BFS) traversal of the graph. Identifying horizontal-edges allows our algorithm to drastically reduce the number of edges examined for set intersections. Our new approach is a communication-efficient parallel algorithm that asymptotically reduces communication on massive graphs such as from real social networks and synthetic graphs from the Graph500 Benchmark. In our estimate from massive-scale Graph500 graphs, our new algorithm reduces the communication by 22.1x on a scale 36 and by 181x on a scale 42. Because communication is known to be the dominant cost of distributed parallel triangle counting, our new parallel algorithm can significantly reduce the practical execution time for counting triangles in large graphs.