Common-Truss-Based Community Search on Multilayer Graphs

Xudong Liu; Zhaonian Zou

doi:10.1007/978-3-031-46671-7_19

Common-Truss-Based Community Search on Multilayer Graphs

Xudong Liu
, Zhaonian Zou^*

^*Corresponding author for this work

Faculty of Computing

Harbin Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Scopus citations

Abstract

Multilayer graphs have a multitude of applications in diverse fields, ranging from biology to social networks. In the context of the community search in multilayer graphs, the goal is to identify a target multilayer graph that contains query vertices. However, existing algorithms do not succeed in finding a common graph in subgraphs, while also ensuring that the multilayer graph is sufficiently dense. To address this limitation, we propose the CTruss model, a novel structure for multilayer graphs. This structure aims to find a common graph that exists on each layer in the subgraph. Next, we present a Baseline algorithm to find a multilayer graph containing the query vertices. We also propose Top-Down and Bottom-Up algorithms that can compute the CTruss quickly under different conditions. Finally, we conduct experiments to demonstrate that our proposed model can achieve a higher density in some cases compared to the state of art models such as FirmTruss and K-core.

Original language	English
Title of host publication	Advanced Data Mining and Applications - 19th International Conference, ADMA 2023, Proceedings
Editors	Xiaochun Yang, Bin Wang, Heru Suhartanto, Guoren Wang, Jing Jiang, Bing Li, Huaijie Zhu, Ningning Cui
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	277-291
Number of pages	15
ISBN (Print)	9783031466700
DOIs	https://doi.org/10.1007/978-3-031-46671-7_19
State	Published - 2023
Event	19th International Conference on Advanced Data Mining and Applications, ADMA 2023 - Shenyang, China Duration: 21 Aug 2023 → 23 Aug 2023

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14178 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	19th International Conference on Advanced Data Mining and Applications, ADMA 2023
Country/Territory	China
City	Shenyang
Period	21/08/23 → 23/08/23

Keywords

Community Search
Multilayer Graph
Truss

Access to Document

10.1007/978-3-031-46671-7_19

Cite this

Liu, X., & Zou, Z. (2023). Common-Truss-Based Community Search on Multilayer Graphs. In X. Yang, B. Wang, H. Suhartanto, G. Wang, J. Jiang, B. Li, H. Zhu, & N. Cui (Eds.), Advanced Data Mining and Applications - 19th International Conference, ADMA 2023, Proceedings (pp. 277-291). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14178 LNAI). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-46671-7_19

Liu, Xudong ; Zou, Zhaonian. / Common-Truss-Based Community Search on Multilayer Graphs. Advanced Data Mining and Applications - 19th International Conference, ADMA 2023, Proceedings. editor / Xiaochun Yang ; Bin Wang ; Heru Suhartanto ; Guoren Wang ; Jing Jiang ; Bing Li ; Huaijie Zhu ; Ningning Cui. Springer Science and Business Media Deutschland GmbH, 2023. pp. 277-291 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{07fc8c8204a840bd8fff57c99b2284fd,

title = "Common-Truss-Based Community Search on Multilayer Graphs",

abstract = "Multilayer graphs have a multitude of applications in diverse fields, ranging from biology to social networks. In the context of the community search in multilayer graphs, the goal is to identify a target multilayer graph that contains query vertices. However, existing algorithms do not succeed in finding a common graph in subgraphs, while also ensuring that the multilayer graph is sufficiently dense. To address this limitation, we propose the CTruss model, a novel structure for multilayer graphs. This structure aims to find a common graph that exists on each layer in the subgraph. Next, we present a Baseline algorithm to find a multilayer graph containing the query vertices. We also propose Top-Down and Bottom-Up algorithms that can compute the CTruss quickly under different conditions. Finally, we conduct experiments to demonstrate that our proposed model can achieve a higher density in some cases compared to the state of art models such as FirmTruss and K-core.",

keywords = "Community Search, Multilayer Graph, Truss",

author = "Xudong Liu and Zhaonian Zou",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.; 19th International Conference on Advanced Data Mining and Applications, ADMA 2023 ; Conference date: 21-08-2023 Through 23-08-2023",

year = "2023",

doi = "10.1007/978-3-031-46671-7\_19",

language = "英语",

isbn = "9783031466700",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "277--291",

editor = "Xiaochun Yang and Bin Wang and Heru Suhartanto and Guoren Wang and Jing Jiang and Bing Li and Huaijie Zhu and Ningning Cui",

booktitle = "Advanced Data Mining and Applications - 19th International Conference, ADMA 2023, Proceedings",

address = "德国",

}

Liu, X & Zou, Z 2023, Common-Truss-Based Community Search on Multilayer Graphs. in X Yang, B Wang, H Suhartanto, G Wang, J Jiang, B Li, H Zhu & N Cui (eds), Advanced Data Mining and Applications - 19th International Conference, ADMA 2023, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14178 LNAI, Springer Science and Business Media Deutschland GmbH, pp. 277-291, 19th International Conference on Advanced Data Mining and Applications, ADMA 2023, Shenyang, China, 21/08/23. https://doi.org/10.1007/978-3-031-46671-7_19

Common-Truss-Based Community Search on Multilayer Graphs. / Liu, Xudong; Zou, Zhaonian.
Advanced Data Mining and Applications - 19th International Conference, ADMA 2023, Proceedings. ed. / Xiaochun Yang; Bin Wang; Heru Suhartanto; Guoren Wang; Jing Jiang; Bing Li; Huaijie Zhu; Ningning Cui. Springer Science and Business Media Deutschland GmbH, 2023. p. 277-291 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14178 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Common-Truss-Based Community Search on Multilayer Graphs

AU - Liu, Xudong

AU - Zou, Zhaonian

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.

PY - 2023

Y1 - 2023

N2 - Multilayer graphs have a multitude of applications in diverse fields, ranging from biology to social networks. In the context of the community search in multilayer graphs, the goal is to identify a target multilayer graph that contains query vertices. However, existing algorithms do not succeed in finding a common graph in subgraphs, while also ensuring that the multilayer graph is sufficiently dense. To address this limitation, we propose the CTruss model, a novel structure for multilayer graphs. This structure aims to find a common graph that exists on each layer in the subgraph. Next, we present a Baseline algorithm to find a multilayer graph containing the query vertices. We also propose Top-Down and Bottom-Up algorithms that can compute the CTruss quickly under different conditions. Finally, we conduct experiments to demonstrate that our proposed model can achieve a higher density in some cases compared to the state of art models such as FirmTruss and K-core.

AB - Multilayer graphs have a multitude of applications in diverse fields, ranging from biology to social networks. In the context of the community search in multilayer graphs, the goal is to identify a target multilayer graph that contains query vertices. However, existing algorithms do not succeed in finding a common graph in subgraphs, while also ensuring that the multilayer graph is sufficiently dense. To address this limitation, we propose the CTruss model, a novel structure for multilayer graphs. This structure aims to find a common graph that exists on each layer in the subgraph. Next, we present a Baseline algorithm to find a multilayer graph containing the query vertices. We also propose Top-Down and Bottom-Up algorithms that can compute the CTruss quickly under different conditions. Finally, we conduct experiments to demonstrate that our proposed model can achieve a higher density in some cases compared to the state of art models such as FirmTruss and K-core.

KW - Community Search

KW - Multilayer Graph

KW - Truss

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

U2 - 10.1007/978-3-031-46671-7_19

DO - 10.1007/978-3-031-46671-7_19

M3 - 会议稿件

AN - SCOPUS:85177428516

SN - 9783031466700

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 277

EP - 291

BT - Advanced Data Mining and Applications - 19th International Conference, ADMA 2023, Proceedings

A2 - Yang, Xiaochun

A2 - Wang, Bin

A2 - Suhartanto, Heru

A2 - Wang, Guoren

A2 - Jiang, Jing

A2 - Li, Bing

A2 - Zhu, Huaijie

A2 - Cui, Ningning

PB - Springer Science and Business Media Deutschland GmbH

T2 - 19th International Conference on Advanced Data Mining and Applications, ADMA 2023

Y2 - 21 August 2023 through 23 August 2023

ER -

Liu X, Zou Z. Common-Truss-Based Community Search on Multilayer Graphs. In Yang X, Wang B, Suhartanto H, Wang G, Jiang J, Li B, Zhu H, Cui N, editors, Advanced Data Mining and Applications - 19th International Conference, ADMA 2023, Proceedings. Springer Science and Business Media Deutschland GmbH. 2023. p. 277-291. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-46671-7_19