# Triangle Counting

## Application Description

This benchmark counts the number of triangles in a given undirected graph. It implements the node-iterator and edge-iterator algorithms in [1], and it implements an ordered count algorithm (also used in the GAP benchmark suite). All nodes/edges can be processed independently.

[1] Thomas Schank. Algorithmic Aspects of Triangle-Based Network Analysis. PhD Thesis. Universitat Karlsruhe. 2007.

## Algorithms

In the *Node-iterator* algorithm,
for a pair of nodes *a* and *b* where both are node
*n*'s neighbors, if *a* is *b*'s neighbor,
and vice versa, then there is a triangle composed of nodes
*n*, *a*, and *b*. Therefore, we can
count triangles by scanning through all pairs of neighbors
for all nodes and see if the pair of nodes are each other's
neighbor. To avoid double counting, we count a triangle only
if *a* < *n* < *b* by some criteria.
This requires pre-sorting of edge lists for all nodes. Figure 1
shows the pseudocode for node-iterator algorithm.

1 2 3 4 5 6 7 8 9 10 11 12 | /* sort edge lists for all nodes */ num_triangles = 0; foreach (Node n: graph) { foreach (Node a: n's neighbor) { if (a >= n) continue; foreach (Node b: n's neighbor) { if (b > n and b is a's neighbor) { num_triangles++; } } } } |

Figure 1: Pseudocode for node iterator algorithm of triangle counting

In the *Edge-iterator* algorithm,
given an edge *e* whose end points are *n*
and *m*, if *n* and *m* have a common
neighbor *a*, then there is a triangle formed by
nodes *n*, *m*, and *a*. Hence, we can
count triangles by intersecting each edge's end points' edge
lists and summing all intersections' sizes. To avoid double
counting, we only consider *n* < *a* < *m*
by some criteria when intersecting edge lists. This requires
pre-sorting of edge lists for all nodes. Figure 2 shows the pseudocode
for edge-iterator algorithm.

1 2 3 4 5 6 7 8 9 | /* sort edge lists for all nodes */ num_triangles = 0; foreach (Edge e: graph) { Node n = e.src; Node m = e.dst; NodeSet n_ngh = {s| s is n's neighbor and n < s < m}; NodeSet m_ngh = {t| t is m's neighbor and n < t < m}; num_triangles += |n_ngh intersect m_mgh|; } |

Figure 2: Pseudocode for edge-iterator algorithm of triangle counting

The *ordered count* algorithm relies on a sorted vertex order of the
graph in which high-degree nodes appear first. It then functions similarly to
the node-iterator algorithm: threads handle nodes separately, and a triangle a,
b, c is only counted if a > b > c. Since high-degree nodes appear at the
beginning, they will count no triangles, reducing the number of iterations of
the outer-most loop and overall computation time. For example, the thread with
a = 0 (the highest-degree node in the graph) will do no work as all vertices
have an ID greater than 0: a will never be greater than any other b. This
algorithm works well if the degree distribution is uneven (e.g., power-law
graphs where only a few nodes have very high degree).

## Parallelism

All of our algorithm implementations are topology-driven algorithms, since all nodes/edges are active. The graph is only read, so all activities at nodes/edges can proceed independently.

## Performance

Figures 2, 4, and 6 show the execution time of the edge-iterator algorithm, the
node-iterator algorithm, and the ordered count algorithm, respectively. Figures
3, 5, and 7 show the self-relative speedup, i.e, speedup with respect to the
single thread performance for edge-iterator, node-iterator, and ordered
count algorithm, respectively. The input is LiveJournal graph, and
the ** number of triangles** present in the graph is **285730264**.

## Machine Description

Performance numbers are collected on a 4 package (14 cores per package) Intel(R) Xeon(R) Gold 5120 CPU machine at 2.20GHz from 1 thread to 56 threads in increments of 7 threads. The machine has 192GB of RAM. The operating system is CentOS Linux release 7.5.1804. All runs of the Galois benchmarks used gcc/g++ 7.2 to compile.