BDAC: Boundary-Driven Approximations of K-Cliques

Abstract

Clique counts are crucial in applications like detecting communities in social networks and recurring patterns in bioinformatics. Counting k-cliques—a fully connected subgraph with k nodes, where each node has a direct, mutual, and symmetric relationship with every other node—becomes computationally challenging for larger k due to combinatorial explosion, especially in large, dense graphs. Existing exact methods have difficulties beyond k = 10, especially on large datasets, while sampling-based approaches often involve trade-offs in terms of accuracy, resource utilization, and efficiency. This difficulty becomes more pronounced in dense graphs as the number of potential k-cliques grows exponentially. We present Boundary-driven approximations of k-cliques (BDAC), a novel algorithm that approximates k-clique counts without using recursive procedures or sampling methods. BDAC offers both lower and upper bounds for k-cliques at local (per-vertex) and global levels, making it ideal for large, dense graphs. Unlike other approaches, BDAC’s complexity remains unaffected by the value of k. We demonstrate its effectiveness by comparing it with leading algorithms across various datasets, focusing on k values ranging from 8 to 50.

Keywords

• approximate
• graphs
• clique counts
• k-cliques
• Turán’s theorem