@inproceedings{69f9d562c60d4bfa9513b5dfd9a868a4,
title = "Triangle Counting Through Cover-Edges",
abstract = "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 propose the novel concept of a cover-edge set that can be used to find triangles more efficiently. We use a breadth-first search (BFS) to quickly generate a compact cover-edge set. Novel sequential and parallel triangle counting algorithms are presented that employ cover-edge sets. The sequential algorithm avoids unnecessary triangle-checking operations, and the parallel algorithm is communication-efficient. The parallel algorithm can asymptotically reduce 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 parallel algorithm can reduce the communication on a scale 36 graph by 1156x and on a scale 42 graph by 2368x.",
keywords = "Graph Algorithms, High Performance Data Analytics, Parallel Algorithms, Triangle Counting",
author = "Bader, {David A.} and Fuhuan Li and Anya Ganeshan and Ahmet Gundogdu and Jason Lew and Rodriguez, {Oliver Alvarado} and Zhihui Du",
note = "Publisher Copyright: {\textcopyright} 2023 IEEE.; 2023 IEEE High Performance Extreme Computing Conference, HPEC 2023 ; Conference date: 25-09-2023 Through 29-09-2023",
year = "2023",
doi = "10.1109/HPEC58863.2023.10363465",
language = "English (US)",
series = "2023 IEEE High Performance Extreme Computing Conference, HPEC 2023",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
booktitle = "2023 IEEE High Performance Extreme Computing Conference, HPEC 2023",
address = "United States",
}