A while back I wrote a blog on triangle counting in networks using CUDA (see <a href="http://sandbox.arrayfire.com/triangle-counting-in-graphs-on-the-gpu-part-1/" title="Part 1" target="_blank"> Part 1</a> for the post). In this post, I will cover in more detail the internals of the algorithm and the CUDA implementation. Before I take a deep dive into the details of the algorithm, I want to remind the reader that there are multiple ways for finding triangles in a graph. Our approach is based off the intersection of two adjacency lists and finding the common elements in both those lists. Two additional approaches would simply be to compare all the possible node-triplets in the graph or using via matrix multiplication of the incidence array. The last of these two approaches can be computationally  demanding, especially for sparse networks. This makes the adjacency list intersection approach preferable in most cases. For the intersection to be efficient, typically the lists are presorted. This by no means is an exaggerated requirement. 
An extended discussion on the pros and cons of the different approaches can be found in both the papers by <a href="http://www.emis.ams.org/journals/JGAA/accepted/2005/SchankWagner2005.9.2.pdf" title="Finding, counting and listing all triangles in large graphs, an experimental study" target="_blank">Shanck & Wagner</a> and in <a href="http://www.cc.gatech.edu/grads/o/ogreen3/_docs/2014LoadBalancecClusteringCoefficients.pdf" title="Load Balanced Clustering Coefficients" target="_blank">Green et al.</a> 