About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
MLSP 2024
Conference paper
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.