Efficient Locally h-Clique Densest Subgraph Discovery via Divide-and-Conquer

Finding the densest subgraph (DS) from a graph is a fundamental problem in graph databases. It has been extensively studied in the literature and has found many real applications in a wide range of fields, such as biology, finance, and social networks. This paper studies how to efficiently discover the locally h -clique densest subgraph (L h CDS), which is a recently-proposed variant of DS. An L h CDS is a subgraph which is the densest among the "local neighbors". Given a graph G , a number of L h CDSes can be returned, which reflect different dense regions of G and thus give more information than DS. Existing L h CDS solutions suffer from low efficiency due to extensive redundant computation. To improve efficiency, in this paper, we propose a divide-and-conquer-based algorithm, which not only reduces the search space but also has an improved time complexity. Extensive experiments on 15 large real-world graph datasets show that our proposed algorithm is up to two orders of magnitude faster than the state-of-the-art.