Detecting maximum k-durable structures on temporal graphs

Faming Li; Zhaonian Zou; Xianmin Liu; Jianzhong Li; Xiaochun Yang; Bin Wang

doi:10.1016/j.knosys.2023.110561

Detecting maximum k-durable structures on temporal graphs

Faming Li^*
, Zhaonian Zou
, Xianmin Liu
, Jianzhong Li
, Xiaochun Yang
, Bin Wang

^*Corresponding author for this work

Northeastern University China
School of Computer Science and Technology, Harbin Institute of Technology
Shenzhen Institute of Advanced Technology
National Frontiers Science Center for Industrial Intelligence and Systems Optimization

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

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 30× faster than the baseline algorithm.

Original language	English
Article number	110561
Journal	Knowledge-Based Systems
Volume	271
DOIs	https://doi.org/10.1016/j.knosys.2023.110561
State	Published - 8 Jul 2023
Externally published	Yes

Keywords

Biclique
Durable structure
Parameterized complexity
Temporal graph

Access to Document

10.1016/j.knosys.2023.110561

Cite this

@article{9c99743229be466c9e008fe54b26119e,

title = "Detecting maximum k-durable structures on temporal graphs",

abstract = "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{\textendash}4 orders of magnitude number of recursive invocation and is at least 30{\texttimes} faster than the baseline algorithm.",

keywords = "Biclique, Durable structure, Parameterized complexity, Temporal graph",

author = "Faming Li and Zhaonian Zou and Xianmin Liu and Jianzhong Li and Xiaochun Yang and Bin Wang",

note = "Publisher Copyright: {\textcopyright} 2023 Elsevier B.V.",

year = "2023",

month = jul,

day = "8",

doi = "10.1016/j.knosys.2023.110561",

language = "英语",

volume = "271",

journal = "Knowledge-Based Systems",

issn = "0950-7051",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Detecting maximum k-durable structures on temporal graphs

AU - Li, Faming

AU - Zou, Zhaonian

AU - Liu, Xianmin

AU - Li, Jianzhong

AU - Yang, Xiaochun

AU - Wang, Bin

PY - 2023/7/8

Y1 - 2023/7/8

N2 - 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 30× faster than the baseline algorithm.

AB - 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 30× faster than the baseline algorithm.

KW - Biclique

KW - Durable structure

KW - Parameterized complexity

KW - Temporal graph

UR - https://www.scopus.com/pages/publications/85153185399

U2 - 10.1016/j.knosys.2023.110561

DO - 10.1016/j.knosys.2023.110561

M3 - 文章

AN - SCOPUS:85153185399

SN - 0950-7051

VL - 271

JO - Knowledge-Based Systems

JF - Knowledge-Based Systems

M1 - 110561

ER -

Detecting maximum k-durable structures on temporal graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this