Efficient $k$-Clique Listing: An Edge-Oriented Branching Strategy
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913188158636032 |
|---|---|
| author | Wang, Kaixin Yu, Kaiqiang Long, Cheng |
| author_facet | Wang, Kaixin Yu, Kaiqiang Long, Cheng |
| contents | $k$-clique listing is a vital graph mining operator with diverse applications in various networks. The state-of-the-art algorithms all adopt a branch-and-bound (BB) framework with a vertex-oriented branching strategy (called VBBkC), which forms a sub-branch by expanding a partial $k$-clique with a vertex. These algorithms have the time complexity of $O(k m (δ/2)^{k-2})$, where $m$ is the number of edges in the graph and $δ$ is the degeneracy of the graph. In this paper, we propose a BB framework with a new edge-oriented branching (called EBBkC), which forms a sub-branch by expanding a partial $k$-clique with two vertices that connect each other (which correspond to an edge). We explore various edge orderings for EBBkC such that it achieves a time complexity of $O(δm + k m (τ/2)^{k-2})$, where $τ$ is an integer related to the maximum truss number of the graph and we have $τ< δ$. The time complexity of EBBkC is better than that of VBBkC algorithms for $k>3$ since both $O(δm)$ and $O(k m (τ/2)^{k-2})$ are bounded by $O(k m (δ/2)^{k-2})$. Furthermore, we develop specialized algorithms for sub-branches on dense graphs so that we can early-terminate them and apply the specialized algorithms. We conduct extensive experiments on 19 real graphs, and the results show that our newly developed EBBkC-based algorithms with the early termination technique consistently and largely outperform the state-of-the-art (VBBkC-based) algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_13798 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Efficient $k$-Clique Listing: An Edge-Oriented Branching Strategy Wang, Kaixin Yu, Kaiqiang Long, Cheng Databases Data Structures and Algorithms $k$-clique listing is a vital graph mining operator with diverse applications in various networks. The state-of-the-art algorithms all adopt a branch-and-bound (BB) framework with a vertex-oriented branching strategy (called VBBkC), which forms a sub-branch by expanding a partial $k$-clique with a vertex. These algorithms have the time complexity of $O(k m (δ/2)^{k-2})$, where $m$ is the number of edges in the graph and $δ$ is the degeneracy of the graph. In this paper, we propose a BB framework with a new edge-oriented branching (called EBBkC), which forms a sub-branch by expanding a partial $k$-clique with two vertices that connect each other (which correspond to an edge). We explore various edge orderings for EBBkC such that it achieves a time complexity of $O(δm + k m (τ/2)^{k-2})$, where $τ$ is an integer related to the maximum truss number of the graph and we have $τ< δ$. The time complexity of EBBkC is better than that of VBBkC algorithms for $k>3$ since both $O(δm)$ and $O(k m (τ/2)^{k-2})$ are bounded by $O(k m (δ/2)^{k-2})$. Furthermore, we develop specialized algorithms for sub-branches on dense graphs so that we can early-terminate them and apply the specialized algorithms. We conduct extensive experiments on 19 real graphs, and the results show that our newly developed EBBkC-based algorithms with the early termination technique consistently and largely outperform the state-of-the-art (VBBkC-based) algorithms. |
| title | Efficient $k$-Clique Listing: An Edge-Oriented Branching Strategy |
| topic | Databases Data Structures and Algorithms |
| url | https://arxiv.org/abs/2311.13798 |