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

CREATORYouzhe Liu, Xiaojun Dong, Yan Gu, Yihan Sun
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE88 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-08042

Browse the full library · About the Tower of Babel