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: 13677
Venue: VLDB
Year: 2024
Pagerank: 5.8212982e-05
Overall Rank: 6,617 | 54.61%
DOI: 10.14778/3675034.3675054

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 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,534	Anchored Maximum Communities over Large Directed Graphs	2026	VLDB	5.093636e-05
10,772	Parallel k-Core Decomposition: Theory and Practice	2025	SIGMOD	5.093636e-05
10,807	In-depth Analysis of Densest Subgraph Discovery in a Unified Framework	2025	VLDB	5.093636e-05
10,930	Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory	2025	VLDB	5.093636e-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
102	Truss Decomposition in Massive Networks	2012	VLDB	0.00034255289
189	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00026114928
780	Maximum Biclique Search at Billion Scale	2020	VLDB	0.00014091815
793	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00013978774
825	K-Core Decomposition of Large Networks on a Single PC	2016	VLDB	0.00013779895
1,328	Truss-based Community Search over Large Directed Graphs	2020	SIGMOD	0.00011140898
1,416	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	0.00010839488
1,647	Effective and Efficient Community Search over Large Heterogeneous Information Networks	2020	VLDB	0.00010125633
2,024	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB	9.2907829e-05
2,294	(p,q)-biclique Counting and Enumeration for Large Sparse Bipartite Graphs	2022	VLDB	8.7939844e-05
2,323	Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms	2016	SIGMOD	8.750808e-05
3,312	On Querying Historical K-Cores	2021	VLDB	7.5309892e-05
3,737	Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs	2020	SIGMOD	7.1609645e-05
3,855	Distributed D-core Decomposition over Large Directed Graphs	2022	VLDB	7.0712144e-05
4,579	Cohesive Subgraph Search over Big Heterogeneous Information Networks: Applications, Challenges, and Solutions	2021	SIGMOD	6.6203846e-05
5,540	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	6.1809407e-05
5,556	Fast Maximal Clique Enumeration on Uncertain Graphs: A Pivot-based Approach	2022	SIGMOD	6.1751704e-05
5,674	Efficient Core Maintenance in Large Bipartite Graphs	2023	SIGMOD	6.1255689e-05
5,977	Maximal D-truss Search in Dynamic Directed Graphs	2023	VLDB	6.0219619e-05
6,368	Theoretically and Practically Efficient Parallel Nucleus Decomposition	2022	VLDB	5.8975125e-05
9,519	A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery	2024	SIGMOD	5.2562724e-05
11,608	Densest Subgraph Discovery on Large Graphs: Applications, Challenges, and Techniques	2022	VLDB	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,640	Distance-generalized Core Decomposition	2019	SIGMOD
2	9,301	Accelerating Core Decomposition in Billion-Scale Hypergraphs	2025	SIGMOD
3	825	K-Core Decomposition of Large Networks on a Single PC	2016	VLDB
4	10,246	Geld: Load-balanced D-Core Decomposition for Consumer GPUs	2026	SIGMOD
5	793	Streaming Algorithms for k-core Decomposition	2013	VLDB
6	6,368	Theoretically and Practically Efficient Parallel Nucleus Decomposition	2022	VLDB
7	9,695	Parallel Algorithms for Hierarchical Nucleus Decomposition	2024	SIGMOD
8	5,697	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB
9	10,772	Parallel k-Core Decomposition: Theory and Practice	2025	SIGMOD
10	3,855	Distributed D-core Decomposition over Large Directed Graphs	2022	VLDB