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.698709e-05
Overall Rank: 6,666 | 55.32%
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,095	Parallel k-Core Decomposition: Theory and Practice	2025	SIGMOD	5.3739121e-05
10,789	Anchored Maximum Communities over Large Directed Graphs	2026	VLDB	4.9605343e-05
10,879	Efficient Locally h-Clique Densest Subgraph Discovery via Divide-and-Conquer	2026	VLDB	4.9605343e-05
11,284	In-depth Analysis of Densest Subgraph Discovery in a Unified Framework	2025	VLDB	4.9605343e-05
11,383	Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory	2025	VLDB	4.9605343e-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
96	Truss Decomposition in Massive Networks	2012	VLDB	0.00034261728
182	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00026383593
732	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00014341313
771	Maximum Biclique Search at Billion Scale	2020	VLDB	0.00014081924
829	K-Core Decomposition of Large Networks on a Single PC	2016	VLDB	0.00013587885
1,357	Truss-based Community Search over Large Directed Graphs	2020	SIGMOD	0.00010903497
1,398	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	0.0001076734
1,590	Effective and Efficient Community Search over Large Heterogeneous Information Networks	2020	VLDB	0.00010110798
1,995	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB	9.2189157e-05
2,072	Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms	2016	SIGMOD	9.0668141e-05
2,339	(p,q)-biclique Counting and Enumeration for Large Sparse Bipartite Graphs	2022	VLDB	8.599495e-05
3,170	On Querying Historical K-Cores	2021	VLDB	7.5572564e-05
3,778	Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs	2020	SIGMOD	7.0037629e-05
3,880	Distributed D-core Decomposition over Large Directed Graphs	2022	VLDB	6.9318416e-05
3,881	Cohesive Subgraph Search over Big Heterogeneous Information Networks: Applications, Challenges, and Solutions	2021	SIGMOD	6.9309694e-05
4,567	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	6.5173666e-05
4,753	Fast Maximal Clique Enumeration on Uncertain Graphs: A Pivot-based Approach	2022	SIGMOD	6.4218566e-05
5,575	Theoretically and Practically Efficient Parallel Nucleus Decomposition	2022	VLDB	6.0626208e-05
5,643	Efficient Core Maintenance in Large Bipartite Graphs	2023	SIGMOD	6.0363665e-05
6,078	Maximal D-truss Search in Dynamic Directed Graphs	2023	VLDB	5.8765432e-05
7,832	A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery	2024	SIGMOD	5.4289543e-05
11,966	Densest Subgraph Discovery on Large Graphs: Applications, Challenges, and Techniques	2022	VLDB	4.9605343e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,945	Resource-Efficient FirmCore Decomposition on Billion-scale Multilayer Graphs	2026	VLDB
2	829	K-Core Decomposition of Large Networks on a Single PC	2016	VLDB
3	10,537	Geld: Load-balanced D-Core Decomposition for Consumer GPUs	2026	SIGMOD
4	10,407	Scaling Up Density Decomposition on Massive Graphs	2027	SIGMOD
5	732	Streaming Algorithms for k-core Decomposition	2013	VLDB
6	5,575	Theoretically and Practically Efficient Parallel Nucleus Decomposition	2022	VLDB
7	9,911	Parallel Algorithms for Hierarchical Nucleus Decomposition	2024	SIGMOD
8	5,725	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB
9	8,095	Parallel k-Core Decomposition: Theory and Practice	2025	SIGMOD
10	3,880	Distributed D-core Decomposition over Large Directed Graphs	2022	VLDB