Pseudoarboricity-Based Skyline Important Community Search in Large Networks

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.