Fast Triangle Counting

2023/09/16 by Bader, David A. · 3 citations
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.2309.09064

Abstract

Listing and counting triangles in graphs is a key algorithmic kernel for network analyses including community detection, clustering coefficients, k-trusses, and triangle centrality. We design and implement a new serial algorithm for triangle counting that performs competitively with the fastest previous approaches on both real and synthetic graphs, such as those from the Graph500 Benchmark and the MIT/Amazon/IEEE Graph Challenge. The experimental results use the recently-launched Intel Xeon Platinum 8480+ and CPU Max 9480 processors.

Cited by

• Efficient and Adaptive Estimation of Local Triadic Coefficients
• Evaluating Efficiency and Novelty of LLM-Generated Code for Graph Analysis
• Accelerating Triangle Counting with Real Processing-in-Memory Systems

Related

• Cover Edge-Based Novel Triangle Counting
• Accelerating Triangle Counting with Real Processing-in-Memory Systems
• Triangle Counting Through Cover-Edges
• A Block-Based Triangle Counting Algorithm on Heterogeneous Environments
• Distributed-Memory Parallel Algorithms for Counting and Listing Triangles in Big Graphs