AdaptiveCore: Adaptive Parallel Core Decomposition Framework
- 19 December 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 75 (3) , 1111-1124
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.
Keywords
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:
- A survey on dynamic graph processing on GPUs: concepts, terminologies and systemsFrontiers of Computer Science, 2023
- Identifying important nodes in complex networks based on extended degree and E-shell hierarchy decompositionScientific Reports, 2023
- A robust core architecture of functional brain networks supports topological resilience and cognitive performance in middle- and old-aged adultsProceedings of the National Academy of Sciences, 2022
- K-core robustness in ecological and financial networksScientific Reports, 2020
- The core decomposition of networks: theory, algorithms and applicationsThe VLDB Journal, 2019
- -core: Theories and applicationsPhysics Reports, 2019
- Accelerating Core Decomposition in Large Temporal Networks Using GPUs2017
- K-shell decomposition reveals hierarchical cortical organization of the human brainNew Journal of Physics, 2016
- The H-index of a network node and its relation to degree and corenessNature Communications, 2016
- Accelerating Large Graph Algorithms on the GPU Using CUDA2008