Parallel k-Core Decomposition: Theory and Practice
Summary: A simple, work-efficient parallel framework for k-core decomposition enabling high parallelism. It uses sampling to reduce contention on high-degree vertices, vertical granularity control to cut scheduling overhead for low-degree vertices, and a hierarchical bucket structure for high coreness, yielding strong gains over ParK/PKC/Julienne on 96-core graphs (up to 315x vs ParK). (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Youzhe Liu
- 2. Xiaojun Dong
- 3. Yan Gu
- 4. Yihan Sun
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 6 of 6 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 966 | Streaming Algorithms for k-core Decomposition | 2013 | VLDB | 0.00014960672 |
| 1,150 | K-Core Decomposition of Large Networks on a Single PC | 2016 | VLDB | 0.00013657353 |
| 5,298 | Distributed D-core Decomposition over Large Directed Graphs | 2022 | VLDB | 5.5799987e-05 |
| 6,513 | Efficient Parallel D-core Decomposition at Scale | 2024 | VLDB | 5.0321577e-05 |
| 6,880 | Theoretically and Practically Efficient Parallel Nucleus Decomposition | 2022 | VLDB | 4.8970985e-05 |
| 11,191 | Parallel Strong Connectivity Based on Faster Reachability | 2023 | SIGMOD | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 11,191 | Parallel Strong Connectivity Based on Faster Reachability | 2023 | SIGMOD | 4.1945683e-05 |
| 3,597 | Parallel Local Graph Clustering | 2016 | VLDB | 6.9345175e-05 |
| 966 | Streaming Algorithms for k-core Decomposition | 2013 | VLDB | 0.00014960672 |
| 5,298 | Distributed D-core Decomposition over Large Directed Graphs | 2022 | VLDB | 5.5799987e-05 |
| 1,150 | K-Core Decomposition of Large Networks on a Single PC | 2016 | VLDB | 0.00013657353 |
| 9,146 | Accelerating Core Decomposition in Billion-Scale Hypergraphs | 2025 | SIGMOD | 4.3849295e-05 |
| 10,947 | Parallel Algorithms for Hierarchical Nucleus Decomposition | 2024 | SIGMOD | 4.1945683e-05 |
| 6,141 | Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs | 2021 | VLDB | 5.1903263e-05 |
| 6,880 | Theoretically and Practically Efficient Parallel Nucleus Decomposition | 2022 | VLDB | 4.8970985e-05 |
| 6,513 | Efficient Parallel D-core Decomposition at Scale | 2024 | VLDB | 5.0321577e-05 |