English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

$k$-clique listing is a vital graph mining operator with diverse applicationsin various networks. The state-of-the-art algorithms all adopt abranch-and-bound (BB) framework with a vertex-oriented branching strategy(called VBBkC), which forms a sub-branch by expanding a partial $k$-clique witha vertex. These algorithms have the time complexity of $O(k m(\delta/2)^{k-2})$, where $m$ is the number of edges in the graph and $\delta$is the degeneracy of the graph. In this paper, we propose a BB framework with anew edge-oriented branching (called EBBkC), which forms a sub-branch byexpanding a partial $k$-clique with two vertices that connect each other (whichcorrespond to an edge). We explore various edge orderings for EBBkC such thatit achieves a time complexity of $O(\delta m + k m (\tau/2)^{k-2})$, where$\tau$ is an integer related to the maximum truss number of the graph and wehave $\tau < \delta$. The time complexity of EBBkC is better than that of VBBkCalgorithms for $k>3$ since both $O(\delta m)$ and $O(k m (\tau/2)^{k-2})$ arebounded by $O(k m (\delta/2)^{k-2})$. Furthermore, we develop specializedalgorithms for sub-branches on dense graphs so that we can early-terminate themand apply the specialized algorithms. We conduct extensive experiments on 19real graphs, and the results show that our newly developed EBBkC-basedalgorithms with the early termination technique consistently and largelyoutperform the state-of-the-art (VBBkC-based) algorithms.

Efficient $k$-Clique Listing: An Edge-Oriented Branching Strategy