Scalable Triangle Counting with GPUs
Graph Mining
Triangle counting is a graph algorithm that calculates the number of triangles involving each vertex in a graph. Triangle counting gains popularity from social network analysis, where it is exploited to detect communities and measure the corresponding cohesiveness. In this project, we proposes and implements the H-INDEX based approach for triangle counting that avoids the preprocessing step of sorting the neighbor list. For better memory access pattern, we further introduce interleaved format for the hash bucket storage. Taken together, H-INDEX achieves beyond 100 billion TEPS computing rate for some graphs. This work was awarded the graphchallenge champion in IEEE HPEC 2019.