Parallel k k -Core Decomposition: Theory and Practice DOI: XXXXXXX.XXXXXXX CCS: Computer systems organization Embedded systems CCS: Computer systems organization Redundancy CCS: Computer systems organization Robotics CCS: Networks Network reliability
Youzhe Liu, Xiaojun Dong, Yan Gu, Yihan Sun · 2025
Read Parallel k k -Core Decomposition: Theory and Practice DOI: XXXXXXX.XXXXXXX CCS: Computer systems organization Embedded systems CCS: Computer systems organization Redundancy CCS: Computer systems organization Robotics CCS: Networks Network reliability by Youzhe Liu, Xiaojun Dong, Yan Gu, Yihan Sun (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-08042.txt.
Description
Youzhe Liu and co-authors speed up in 2025 a classic graph peeling task, k-core decomposition, on many core machines. The k-core of a graph is what survives after repeatedly stripping away thinly connected vertices. The decomposition labels every vertex with its depth in that peeling, a basic map used across network science.
Existing parallel methods hit walls: wasted work, fights over popular vertices, or scheduling overhead on quiet ones. The authors' framework stays work efficient in theory while inviting practical tricks. Sampling calms contention on high degree vertices. A vertical granularity control batches small jobs to cut overhead. A layered bucket structure handles graphs whose cores run deep. On a ninety-six core machine across twenty-five real and synthetic graphs, their code beat three leading rivals on nearly every graph, sometimes by very wide margins. Fast cores make huge network maps practical to draw.
Catalog record
| CREATOR | Youzhe Liu, Xiaojun Dong, Yan Gu, Yihan Sun |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 88 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-08042