Parallel k -Core Decomposition: Theory and Practice
Open Access
- 17 June 2025
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (3) , 1-27
Abstract
This paper proposes efficient solutions for k -core decomposition with high parallelism. The problem of k -core decomposition is fundamental in graph analysis and has applications across various domains. However, existing algorithms face significant challenges in achieving work-efficiency in theory and/or high parallelism in practice, and suffer from various performance bottlenecks. We present a simple, work-efficient parallel framework for k -core decomposition that is easy to implement and adaptable to various strategies for improving work-efficiency. We introduce two techniques to enhance parallelism: a sampling scheme to reduce contention on high-degree vertices, and vertical granularity control (VGC) to mitigate scheduling overhead for low-degree vertices. Furthermore, we design a hierarchical bucket structure to optimize performance for graphs with high coreness values. We evaluate our algorithm on a diverse set of real-world and synthetic graphs. Compared to state-of-the-art parallel algorithms, including ParK, PKC, and Julienne, our approach demonstrates superior performance on 23 out of 25 graphs when tested on a 96-core machine. Our algorithm shows speedups of up to 315× over ParK, 33.4× over PKC, and 52.5× over Julienne.Keywords
Funding Information
- UCR Regents Faculty Development Award
- Google Research Scholar Program
- Universitas Brawijaya (CCF-2103483,TI-2346223, IS-2227669, CCF-2238358, CCF-2339310)
This publication has 54 references indexed in Scilit:
- The core decomposition of networks: theory, algorithms and applicationsThe VLDB Journal, 2019
- -core: Theories and applicationsPhysics Reports, 2019
- Incremental k-core decomposition: algorithms and evaluationThe VLDB Journal, 2016
- Reservoir computing compensates slow response of chemosensor arrays exposed to fast varying gas concentrations in continuous monitoringSensors and Actuators B: Chemical, 2015
- Defining and evaluating network communities based on ground-truthKnowledge and Information Systems, 2013
- Scalable Clustering Algorithm for N-Body Simulations in a Shared-Nothing Cluster2010
- Using the k-core decomposition to analyze the static structure of large-scale software systemsThe Journal of Supercomputing, 2009
- Peeling the yeast protein networkProteomics, 2005
- Models of social networks based on social distance attachmentPhysical Review E, 2004
- Thread Scheduling for Multiprogrammed MultiprocessorsTheory of Computing Systems, 2001