CPU-based parallelization of BDAC: Enhancing K-Clique approximation

Abstract

The number of k-cliques in a dataset is significant and employed in diverse fields, including community detection, anomaly detection, and spam detection. This facilitates the identification of densely connected clusters or groups of nodes, which can subsequently be used to reveal underlying structures or patterns in the data. However, the combinatorial complexity of counting k-cliques, especially when identifying them in large networks or for higher values of k, poses considerable computational difficulties. This study introduces an accelerated version of the Boundary-Driven Approximations of K-Cliques (BDAC) algorithm, emphasizing CPU-based parallelization to boost performance when working with large, dense graphs. The BDAC algorithm sets a boundary for k-clique counts instead of providing a specific estimation, which removes the need for recursive enumeration and sampling. We evaluate the performance of BDAC on various graph datasets, showing clear improvements in execution time with parallelization while still keeping the approximation bounds intact. The results show that accelerated BDAC is particularly effective for dense networks, achieving efficient k-clique approximations at large scales. This work highlights the potential of BDAC for high-speed network analysis, contributing an optimized, scalable solution for k-clique approximation in complex datasets.