Efficient size-prescribed k-core search

Yiping Liu; Bo Yan; Bo Zhao; Hongyi Su; Yang Chen; Michael Witbrock

doi:10.1145/3625007.3627316

Efficient size-prescribed k-core search

Yiping Liu, Bo Yan, Bo Zhao, Hongyi Su, Yang Chen, Michael Witbrock

School of Computer Science and Technology

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

Abstract

k-core is a subgraph where every node has at least k neighbors within the subgraph. The k-core subgraphs has been employed in large platforms like Network Repository to comprehend the underlying structures and dynamics of the network. Existing studies have primarily focused on finding k-core groups without considering their size, despite the relevance of solution sizes in many real-world scenarios. This paper addresses this gap by introducing the size-prescribed k-core search (SPCS) problem, where the goal is to find a subgraph of a specified size that has the highest possible core number. We propose two algorithms, namely the TSizeKcore-BU and the TSizeKcore-TD, to identify cohesive subgraphs that satisfy both the k-core requirement and the size constraint. Our experimental results demonstrate the superiority of our approach in terms of solution quality and efficiency. The TSizeKcore-BU algorithm proves to be highly efficient in finding size-prescribed k-core subgraphs on large datasets, making it a favorable choice for such scenarios. On the other hand, the TSizeKcore-TD algorithm is better suited for small datasets where running time is less critical.

Original language	English
Title of host publication	Proceedings of the 2023 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2023
Editors	B. Aditya Prakash, Dong Wang, Tim Weninger
Publisher	Association for Computing Machinery, Inc
Pages	271-275
Number of pages	5
ISBN (Electronic)	9798400704093
DOIs	https://doi.org/10.1145/3625007.3627316
Publication status	Published - 6 Nov 2023
Event	15th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2023 - Kusadasi, Turkey Duration: 6 Nov 2023 → 9 Nov 2023

Publication series

Name	Proceedings of the 2023 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2023

Conference

Conference	15th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2023
Country/Territory	Turkey
City	Kusadasi
Period	6/11/23 → 9/11/23

Keywords

community detection
k-core
prescribed size
social network
subgraph search

Access to Document

10.1145/3625007.3627316

Cite this

Liu, Y., Yan, B., Zhao, B., Su, H., Chen, Y., & Witbrock, M. (2023). Efficient size-prescribed k-core search. In B. Aditya Prakash, D. Wang, & T. Weninger (Eds.), Proceedings of the 2023 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2023 (pp. 271-275). (Proceedings of the 2023 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2023). Association for Computing Machinery, Inc. https://doi.org/10.1145/3625007.3627316

Liu, Yiping ; Yan, Bo ; Zhao, Bo et al. / Efficient size-prescribed k-core search. Proceedings of the 2023 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2023. editor / B. Aditya Prakash ; Dong Wang ; Tim Weninger. Association for Computing Machinery, Inc, 2023. pp. 271-275 (Proceedings of the 2023 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2023).

@inproceedings{26be394911334310927c24933b46e135,

title = "Efficient size-prescribed k-core search",

abstract = "k-core is a subgraph where every node has at least k neighbors within the subgraph. The k-core subgraphs has been employed in large platforms like Network Repository to comprehend the underlying structures and dynamics of the network. Existing studies have primarily focused on finding k-core groups without considering their size, despite the relevance of solution sizes in many real-world scenarios. This paper addresses this gap by introducing the size-prescribed k-core search (SPCS) problem, where the goal is to find a subgraph of a specified size that has the highest possible core number. We propose two algorithms, namely the TSizeKcore-BU and the TSizeKcore-TD, to identify cohesive subgraphs that satisfy both the k-core requirement and the size constraint. Our experimental results demonstrate the superiority of our approach in terms of solution quality and efficiency. The TSizeKcore-BU algorithm proves to be highly efficient in finding size-prescribed k-core subgraphs on large datasets, making it a favorable choice for such scenarios. On the other hand, the TSizeKcore-TD algorithm is better suited for small datasets where running time is less critical.",

keywords = "community detection, k-core, prescribed size, social network, subgraph search",

author = "Yiping Liu and Bo Yan and Bo Zhao and Hongyi Su and Yang Chen and Michael Witbrock",

note = "Publisher Copyright: {\textcopyright} 2023 ACM.; 15th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2023 ; Conference date: 06-11-2023 Through 09-11-2023",

year = "2023",

month = nov,

day = "6",

doi = "10.1145/3625007.3627316",

language = "English",

series = "Proceedings of the 2023 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2023",

publisher = "Association for Computing Machinery, Inc",

pages = "271--275",

editor = "{Aditya Prakash}, B. and Dong Wang and Tim Weninger",

booktitle = "Proceedings of the 2023 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2023",

}

Liu, Y, Yan, B, Zhao, B, Su, H, Chen, Y & Witbrock, M 2023, Efficient size-prescribed k-core search. in B Aditya Prakash, D Wang & T Weninger (eds), Proceedings of the 2023 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2023. Proceedings of the 2023 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2023, Association for Computing Machinery, Inc, pp. 271-275, 15th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2023, Kusadasi, Turkey, 6/11/23. https://doi.org/10.1145/3625007.3627316

Efficient size-prescribed k-core search. / Liu, Yiping; Yan, Bo; Zhao, Bo et al.
Proceedings of the 2023 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2023. ed. / B. Aditya Prakash; Dong Wang; Tim Weninger. Association for Computing Machinery, Inc, 2023. p. 271-275 (Proceedings of the 2023 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2023).

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

TY - GEN

T1 - Efficient size-prescribed k-core search

AU - Liu, Yiping

AU - Yan, Bo

AU - Zhao, Bo

AU - Su, Hongyi

AU - Chen, Yang

AU - Witbrock, Michael

PY - 2023/11/6

Y1 - 2023/11/6

N2 - k-core is a subgraph where every node has at least k neighbors within the subgraph. The k-core subgraphs has been employed in large platforms like Network Repository to comprehend the underlying structures and dynamics of the network. Existing studies have primarily focused on finding k-core groups without considering their size, despite the relevance of solution sizes in many real-world scenarios. This paper addresses this gap by introducing the size-prescribed k-core search (SPCS) problem, where the goal is to find a subgraph of a specified size that has the highest possible core number. We propose two algorithms, namely the TSizeKcore-BU and the TSizeKcore-TD, to identify cohesive subgraphs that satisfy both the k-core requirement and the size constraint. Our experimental results demonstrate the superiority of our approach in terms of solution quality and efficiency. The TSizeKcore-BU algorithm proves to be highly efficient in finding size-prescribed k-core subgraphs on large datasets, making it a favorable choice for such scenarios. On the other hand, the TSizeKcore-TD algorithm is better suited for small datasets where running time is less critical.

AB - k-core is a subgraph where every node has at least k neighbors within the subgraph. The k-core subgraphs has been employed in large platforms like Network Repository to comprehend the underlying structures and dynamics of the network. Existing studies have primarily focused on finding k-core groups without considering their size, despite the relevance of solution sizes in many real-world scenarios. This paper addresses this gap by introducing the size-prescribed k-core search (SPCS) problem, where the goal is to find a subgraph of a specified size that has the highest possible core number. We propose two algorithms, namely the TSizeKcore-BU and the TSizeKcore-TD, to identify cohesive subgraphs that satisfy both the k-core requirement and the size constraint. Our experimental results demonstrate the superiority of our approach in terms of solution quality and efficiency. The TSizeKcore-BU algorithm proves to be highly efficient in finding size-prescribed k-core subgraphs on large datasets, making it a favorable choice for such scenarios. On the other hand, the TSizeKcore-TD algorithm is better suited for small datasets where running time is less critical.

KW - community detection

KW - k-core

KW - prescribed size

KW - social network

KW - subgraph search

UR - http://www.scopus.com/inward/record.url?scp=85190625948&partnerID=8YFLogxK

U2 - 10.1145/3625007.3627316

DO - 10.1145/3625007.3627316

M3 - Conference contribution

AN - SCOPUS:85190625948

T3 - Proceedings of the 2023 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2023

SP - 271

EP - 275

BT - Proceedings of the 2023 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2023

A2 - Aditya Prakash, B.

A2 - Wang, Dong

A2 - Weninger, Tim

PB - Association for Computing Machinery, Inc

T2 - 15th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2023

Y2 - 6 November 2023 through 9 November 2023

ER -

Liu Y, Yan B, Zhao B, Su H, Chen Y, Witbrock M. Efficient size-prescribed k-core search. In Aditya Prakash B, Wang D, Weninger T, editors, Proceedings of the 2023 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2023. Association for Computing Machinery, Inc. 2023. p. 271-275. (Proceedings of the 2023 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2023). doi: 10.1145/3625007.3627316

Efficient size-prescribed k-core search

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this