Efficient Parallel D-core Decomposition at Scale

Summary: Proposes multicore parallel algorithms for full D-core ((k,l)-core) decomposition using implicit level-by-level vertex removal per k to reduce dependencies while keeping sequential-like time complexity. Introduces D-shell to prune redundant k-values and derive larger-k D-cores, achieving up to 100× speedup over prior parallel methods on 32 threads for large graphs. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h3751e218831daa1f
Venue: VLDB
Year: 2024
Pagerank: 5.717615e-05
Overall Rank: 6,655 | 55.28%
DOI: 10.14778/3675034.3675054
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Wensheng Luo (Chinese University of Hong Kong)
2. Yixiang Fang (Chinese University of Hong Kong)
3. Chunxu Lin (Chinese University of Hong Kong)
4. Yingli Zhou (Chinese University of Hong Kong)

BibTeX Citation

@article{luo_vldb24,
        title = {{Efficient Parallel D-core Decomposition at Scale}},
        author = {Luo, Wensheng and Fang, Yixiang and Lin, Chunxu and Zhou, Yingli},
        journal = {PVLDB},
        series = {{VLDB} '24},
        volume = {17},
        number = {10},
        pages = {2654--2667},
        doi = {10.14778/3675034.3675054},
        url = {https://doi.org/10.14778/3675034.3675054},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,077	Parallel k-Core Decomposition: Theory and Practice	2025	SIGMOD	5.3917406e-05
10,728	Anchored Maximum Communities over Large Directed Graphs	2026	VLDB	4.9769913e-05
10,818	Efficient Locally h-Clique Densest Subgraph Discovery via Divide-and-Conquer	2026	VLDB	4.9769913e-05
11,228	In-depth Analysis of Densest Subgraph Discovery in a Unified Framework	2025	VLDB	4.9769913e-05
11,329	Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory	2025	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
100	Truss Decomposition in Massive Networks	2012	VLDB	0.0003396253
184	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00026097449
758	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00014182137
766	Maximum Biclique Search at Billion Scale	2020	VLDB	0.00014111575
834	K-Core Decomposition of Large Networks on a Single PC	2016	VLDB	0.00013576778
1,354	Truss-based Community Search over Large Directed Graphs	2020	SIGMOD	0.00010922947
1,444	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	0.00010630508
1,664	Effective and Efficient Community Search over Large Heterogeneous Information Networks	2020	VLDB	9.9394611e-05
2,044	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB	9.1373547e-05
2,088	Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms	2016	SIGMOD	9.064678e-05
2,328	(p,q)-biclique Counting and Enumeration for Large Sparse Bipartite Graphs	2022	VLDB	8.6269174e-05
3,251	On Querying Historical K-Cores	2021	VLDB	7.4903737e-05
3,791	Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs	2020	SIGMOD	7.0158046e-05
3,868	Distributed D-core Decomposition over Large Directed Graphs	2022	VLDB	6.9548387e-05
3,875	Cohesive Subgraph Search over Big Heterogeneous Information Networks: Applications, Challenges, and Solutions	2021	SIGMOD	6.9503439e-05
4,733	Fast Maximal Clique Enumeration on Uncertain Graphs: A Pivot-based Approach	2022	SIGMOD	6.4430756e-05
5,631	Efficient Core Maintenance in Large Bipartite Graphs	2023	SIGMOD	6.0563927e-05
5,664	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	6.0444315e-05
5,976	Theoretically and Practically Efficient Parallel Nucleus Decomposition	2022	VLDB	5.9272031e-05
6,062	Maximal D-truss Search in Dynamic Directed Graphs	2023	VLDB	5.8960391e-05
7,814	A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery	2024	SIGMOD	5.4469653e-05
11,922	Densest Subgraph Discovery on Large Graphs: Applications, Challenges, and Techniques	2022	VLDB	4.9769913e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,648	Distance-generalized Core Decomposition	2019	SIGMOD
2	10,884	Resource-Efficient FirmCore Decomposition on Billion-scale Multilayer Graphs	2026	VLDB
3	834	K-Core Decomposition of Large Networks on a Single PC	2016	VLDB
4	10,471	Geld: Load-balanced D-Core Decomposition for Consumer GPUs	2026	SIGMOD
5	758	Streaming Algorithms for k-core Decomposition	2013	VLDB
6	5,976	Theoretically and Practically Efficient Parallel Nucleus Decomposition	2022	VLDB
7	9,878	Parallel Algorithms for Hierarchical Nucleus Decomposition	2024	SIGMOD
8	5,721	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB
9	8,077	Parallel k-Core Decomposition: Theory and Practice	2025	SIGMOD
10	3,868	Distributed D-core Decomposition over Large Directed Graphs	2022	VLDB