Skip to Main content Skip to Navigation
Journal articles

KClist++: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs

Abstract : The problem of finding densest subgraphs has received increasing attention in recent years finding applications in biology , finance, as well as social network analysis. The k-clique densest subgraph problem is a generalization of the densest subgraph problem, where the objective is to find a subgraph maximizing the ratio between the number of k-cliques in the subgraph and its number of nodes. It includes as a special case the problem of finding subgraphs with largest average number of triangles (k = 3), which plays an important role in social network analysis. Moreover, algorithms that deal with larger values of k can effectively find quasi-cliques. The densest subgraph problem can be solved in polynomial time with algorithms based on maximum flow, linear programming or a recent approach based on convex optimization. In particular, the latter approach can scale to graphs containing tens of billions of edges. While finding a densest subgraph in large graphs is no longer a bottleneck , the k-clique densest subgraph remains challenging even when k = 3. Our work aims at developing near-optimal and exact algorithms for the k-clique densest subgraph problem on large real-world graphs. We give a surprisingly simple procedure that can be employed to find the maximal k-clique densest subgraph in large-real world graphs. By leveraging appealing properties of existing results, we combine it with a recent approach for listing all k-cliques in a graph and a sampling scheme, obtaining the state-of-the-art approaches for the aforementioned problem. Our theoretical results are complemented with an extensive experimental evaluation showing the effectiveness of our approach in large real-world graphs.
Complete list of metadata

Cited literature [33 references]  Display  Hide  Download
Contributor : Lionel Tabourier Connect in order to contact the contributor
Submitted on : Wednesday, November 11, 2020 - 11:07:19 AM
Last modification on : Tuesday, September 21, 2021 - 2:16:03 PM
Long-term archiving on: : Friday, February 12, 2021 - 6:19:49 PM


Files produced by the author(s)


  • HAL Id : hal-02999881, version 1


Bintao Sun, Maximilien Danisch, T-H Chan, Mauro Sozio. KClist++: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs. Proceedings of the VLDB Endowment (PVLDB), VLDB Endowment, 2020. ⟨hal-02999881⟩



Record views


Files downloads