Skip to main content

Triangle Counting

Problem Specification#

Input#

G=(V,E)G=(V, E), an undirected graph.

Output#

TGT_{G}, the total number of triangles in GG. Each unordered (u,v,w)(u,v,w) triangle is counted once.

Algorithm Implementations#

In GBBS we implement the triangle counting algorithm described by Shun and Tangwongsan [1]. This algorithm parallelizes Latapy's \emph{compact-forward} algorithm [2], which creates a directed graph DGDG where an edge (u,v)E(u,v) \in E is kept in DGDG iff °u<°v\degree{u} < \degree{v}. Although triangle counting can be done directly on the undirected graph in the same work and depth asymptotically, directing the edges helps reduce work, and ensures that every triangle is counted exactly once. More details can be found in Section 6.4 of [3].

The code for our implemenation is available here.

Cost Bounds#

Our implementation runs in O(m3/2)O(m^{3/2}) work and O(logn)O(\log n) depth. More details can be found in Section 6.4 of [3].

Compiling and Running#

The benchmark can be compiled by running:

bazel build -c opt //benchmarks/BFS/NonDeterministicBFS:BFS

It can then be run on a test input graph in the uncompressed format as follows:

numactl -i all ./bazel-bin/benchmarks/BFS/NonDeterministicBFS/BFS_main -s -m -src 1 inputs/rMatGraph_J_5_100

It can then be run on a test input graph in the compressed format as follows:

numactl -i all ./bazel-bin/benchmarks/BFS/NonDeterministicBFS/BFS_main -s -c -m -src 1 inputs/rMatGraph_J_5_100.bytepda

References#

[1] Julian Shun and Kanat Tangwongsan
Multicore Triangle Computations Without Tuning
Proceedings of the IEEE International Conference on Data Engineering (ICDE), pp. 149-160, 2015.

[2] Matthieu Latapy
Main-memory Triangle Computations for Very Large (Sparse (Power-law)) Graphs
Theor. Comput. Sci., 407(1-3), pp. 458-473, 2008

[3] Laxman Dhulipala, Guy Blelloch, and Julian Shun
Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable
Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 393-404, 2018.