Detecting maximum k-durable structures on temporal graphs

doi:10.1016/j.knosys.2023.110561

Detecting maximum k-durable structures on temporal graphs

2023-07-01

1

PRE

AI

DOI：10.1016/j.knosys.2023.110561

Original

Original request for help

Save

Abstract

En 中文

In this paper, we study the problem of detecting maximum k-durable structures on temporal graphs, which can be used to mine and analyze more knowledge behind the temporal graphs. We first prove that this problem is NP-complete and hard to approximate. Next, we propose an efficient algorithm to detect maximum k-durable structures. The algorithm accelerates the detection process by using an auxiliary graph and several well-designed pruning strategies. Massive experiments on five large temporal social networks demonstrate that our algorithm can save 2-4 orders of magnitude number of recursive invocation and is at least 30x faster than the baseline algorithm.(c) 2023 Elsevier B.V. All rights reserved.

Keywords:

Temporal graph

Durable structure

Parameterized complexity

Biclique

Detecting maximum k-durable structures on temporal graphs

Abstract

Journal

Organization