Triangle counting is a building block for many social analytics, especially for the widely used clustering coefficient analytic. Clustering coefficients is used for finding key players in a network based on their local connectivity which is expressed based on the number of triangles that they belong to. There are many ways for finding the triangles a vertex may belong to. One of the most popular approaches for finding the triangles, is to do an intersection of two adjacency lists. If a pair of vertices <em>(u,v) </em>have any common neighbors, these will be found in the intersection process.

While the above may sound simple, implementing an efficient intersection on the GPU is not trivial or straightforward and requires smart partitioning of the work to make full use of the thousands of available threads that modern GPUs have. We just finished such an implementation.

&nbsp;

&nbsp;

<a href="http://sandbox.arrayfire.com/wp-content/uploads/2014/09/gpu.jpg"><img class="alignnone size-medium wp-image-6541" src="http://sandbox.arrayfire.com/wp-content/uploads/2014/09/gpu-300x150.jpg" alt="gpu" width="300" height="150" /></a>

scalable GPU implementation for triangle counting. Our approach uses a new list intersection algorithm called Intersect
Path (named after the Merge Path algorithm). This algorithm has two levels of parallelism. The first divides the
vertices to the GPUs streaming multiprocessors. The second level is responsible for parallelizing the work across the
GPUs streaming processors. For testing purposes, we used graphs taken from the DIMACS 10 Graph Challenge. Our
experiments were conducted on NVIDIA's K40 GPU. Our GPU triangle counting implementation achieves speedups in the range
of $9X-32X$ over
a CPU sequential implementation.