Pseudoarboricity-Based Skyline Important Community Search in Large Networks

TY - JOUR

T1 - Pseudoarboricity-Based Skyline Important Community Search in Large Networks

AU - Jiang, Jiaqi

AU - Li, Rong Hua

AU - Lin, Longlong

AU - Zhang, Yalong

AU - Zeng, Yue

AU - Ye, Xiaowei

AU - Wang, Guoren

N1 - Publisher Copyright: © 1989-2012 IEEE.

PY - 2026

Y1 - 2026

N2 - Important communities are densely connected subgraphs containing vertices with high importance values, which have received wide attention recently. However, existing methods, predominantly based on the k-core model, suffer from limitations such as rigid degree constraints and suboptimal density, often failing to capture highly important vertices. To address these limitations, we propose a new community model based on pseudoarboricity that guarantees near-optimal density while preserving important vertices. Further, we introduce a novel problem of Psudoarboricity-based Skyline Important Community (PSIC), which uniquely treats density and importance as independent attributes. To efficiently address PSIC, we first devise a basic algorithm ClimbStairs, which iteratively refines communities by peeling vertices with low importance. To boost efficiency, we develop an advanced algorithm DivAndCon, which employs a recursive divide-and-conquer strategy combined with weight-based and pseudoarboricity-based pruning techniques, significantly reducing the search space. For massive graphs with billions of edges, inspired by a recursive division tree, we develop several parallel algorithms utilizing thread-pool and free-synchronization mechanism. Finally, we conduct extensive experiments on 10 real-world networks, and the results demonstrate the superiority of our solutions in terms of effectiveness, efficiency, and scalability.

AB - Important communities are densely connected subgraphs containing vertices with high importance values, which have received wide attention recently. However, existing methods, predominantly based on the k-core model, suffer from limitations such as rigid degree constraints and suboptimal density, often failing to capture highly important vertices. To address these limitations, we propose a new community model based on pseudoarboricity that guarantees near-optimal density while preserving important vertices. Further, we introduce a novel problem of Psudoarboricity-based Skyline Important Community (PSIC), which uniquely treats density and importance as independent attributes. To efficiently address PSIC, we first devise a basic algorithm ClimbStairs, which iteratively refines communities by peeling vertices with low importance. To boost efficiency, we develop an advanced algorithm DivAndCon, which employs a recursive divide-and-conquer strategy combined with weight-based and pseudoarboricity-based pruning techniques, significantly reducing the search space. For massive graphs with billions of edges, inspired by a recursive division tree, we develop several parallel algorithms utilizing thread-pool and free-synchronization mechanism. Finally, we conduct extensive experiments on 10 real-world networks, and the results demonstrate the superiority of our solutions in terms of effectiveness, efficiency, and scalability.

KW - Important community

KW - divide-and-conquer

KW - parallel algorithm

KW - pseudoarboricity

KW - skyline computation

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

U2 - 10.1109/TKDE.2025.3631112

DO - 10.1109/TKDE.2025.3631112

M3 - Article

AN - SCOPUS:105021669461

SN - 1041-4347

VL - 38

SP - 1264

EP - 1279

JO - IEEE Transactions on Knowledge and Data Engineering

JF - IEEE Transactions on Knowledge and Data Engineering

IS - 2

ER -