Parallel Triangle Counting in Massive Streaming Graphs
The number of triangles in a graph is a fundamental metric widely used in social network analysis, link classification and recommendation, and more. In these applications, modern graphs of interest tend to both large and dynamic. This paper presents the design and implementation of a fast parallel algorithm for estimating the number of triangles in a massive undirected graph whose edges arrive as a stream. Our algorithm is designed for shared-memory multicore machines and can make efficient use of parallelism and the memory hierarchy. We provide theoretical guarantees on performance and accuracy, and our experiments on real-world datasets show accurate results and substantial speedups compared to an optimized sequential implementation.
This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Tangwongsan, Kanat, Aduri Pavan, and Srikanta Tirthapura. "Parallel triangle counting in massive streaming graphs." In Proceedings of the 22nd ACM International Conference on Information & Knowledge Management, (2013): 781-786. DOI:10.1145/2505515.2505741.