Scalable Triangle Counting and LCC with Caching

Graph analytical algorithms gained great importance in recent years as they proved to be useful in a variety of fields, such as data mining, social network analysis, or cybersecurity. To cope with the computational and memory demands that stem from the size of today's networks highly parallel solutions have to be developed. In this thesis, we present our algorithm for shared memory as well as for distributed triangle counting and local clustering coefficient. We analyze different techniques for the computation of triangles and achieve shared memory parallelism with OpenMP. Our distributed implementation is based on row-wise graph partitioning and uses caching to save communication time. We take advantage of MPI's Remote Memory Access interface to achieve a fully asynchronous distributed algorithm that utilizes RDMA for data transfer. We show how the CLaMPI library for caching remote memory accesses can be used in the context of triangle counting and analyze the relationship between the caching performance and the graph structure. Furthermore, we develop an application-specific score used for the eviction procedure in CLaMPI that leads to additional performance gains