Triangle Counting Through Cover-Edges

David A. Bader, Fuhuan Li, Anya Ganeshan, Ahmet Gundogdu, Jason Lew, Oliver Alvarado Rodriguez, Zhihui Du

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publication2023 IEEE High Performance Extreme Computing Conference, HPEC 2023
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9798350308600
StatePublished - 2023
Event2023 IEEE High Performance Extreme Computing Conference, HPEC 2023 - Virtual, Online, United States
Duration: Sep 25 2023Sep 29 2023

Publication series

Name2023 IEEE High Performance Extreme Computing Conference, HPEC 2023


Conference2023 IEEE High Performance Extreme Computing Conference, HPEC 2023
Country/TerritoryUnited States
CityVirtual, Online

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Modeling and Simulation
  • Artificial Intelligence
  • Computer Science Applications
  • Software
  • Media Technology
  • Computational Mathematics


  • Graph Algorithms
  • High Performance Data Analytics
  • Parallel Algorithms
  • Triangle Counting


Dive into the research topics of 'Triangle Counting Through Cover-Edges'. Together they form a unique fingerprint.

Cite this