Parallel Triangle Counting in Massive Streaming Graphs

Date
2013-01-01
Authors
Pavan, A.
Tirthapura, Srikanta
Tirthapura, Srikanta
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Computer Science
Organizational Unit
Journal Issue
Series
Department
Computer ScienceElectrical and Computer Engineering
Abstract

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.

Comments

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.

Description
Keywords
Citation
DOI