Electrical and Computer Engineering, Computer Science
22nd ACM International Conference on Information & Knowledge Management (CIKM '13)
Link to Published Version
Journal or Book Title
Proceedings of the 22nd ACM International Conference on Information & Knowledge Management (CIKM '13)
October 27-November 1, 2013
San Francisco, CA
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.
IBM T. J. Watson Research Center; Pavan, A.; and Tirthapura, Srikanta, "Parallel Triangle Counting in Massive Streaming Graphs" (2013). Electrical and Computer Engineering Conference Papers, Posters and Presentations. 57.