Counting Triangles of Graphs via Matrix Partitioning

Abstract

Counting the number of triangles is an important task in the computation of several network-related metrics such as transitivity ratio, link recommendation, near-clique subgraph detection, and clustering coefficient. This contribution presents a new algorithm based on non-overlapping subgraph decomposition and matrix partitioning. The part of the adjacency matrix associated with each submatrix is replaced by a low-rank approximation resulting to complexity savings. The proposed algorithm is also suitable for high-latency architectures as well as graphs whose entries are updated over time. Several practical and theoretical aspects are discussed while numerical experiments on real-world graphs demonstrate the potential of the proposed algorithm.