Abstract
Core decomposition is a widely used hierarchical analysis algorithm for large-scale graphs. It achieves this decomposition by iteratively peeling the vertices along with their adjacency edges off into different hierarchies. With the timeliness requirements of modern applications, many researchers have introduced accelerators, particularly GPUs, to improve the computational efficiency of graph algorithms. However, the empty, sparse, and numerous hierarchies in large graphs lead to inefficient computation and parallelism, not only including unnecessary searching for the hierarchy’s vertices, but also significant thread wastage when peeling off the adjacency edges of these vertices. In this paper, we propose an adaptive parallel framework for core decomposition, named AdaptiveCore. First, it improves vertex searching efficiency by adaptively skipping the empty hierarchies and reducing the search space. Moreover, it greatly improves thread utilization by adaptively allocating the available threads to peel off the adjacency edges. Comprehensive experiments show that, compared with the state-of-the-art works, the proposed framework achieves an average speedup of $7.1\times$ on the GPU platform and up to $2.0\times$ on the multi-core CPU platform.
Funding Information
  • National Natural Science Foundation of China (62372333)
  • Key Research and Development Program of Hubei Province (2024BAB044)
  • Key Research and Development Program of Hubei Province (2023BAB078)
  • Project Funded by China Postdoctoral Science Foundation (2022M722459)
  • Science and Technology Program of XPCC (2025AA017)

This publication has 52 references indexed in Scilit: