Parallel Algorithms for Hierarchical Nucleus Decomposition

Summary: Scalable parallel algorithms for nucleus decomposition; produce a dense subgraph hierarchy with interleaved coreness and a concurrent union-find. Parallel approximation with low span, bounded work, and speedups to 60x, with 1.3x coreness error. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6903
Venue: SIGMOD
Year: 2024
Pagerank: 5.2351259e-05
Overall Rank: 9,695 | 33.49%
DOI: 10.1145/3639287

Incoming Non-self Citations Over Time

Authors

1. Jessica Shi (Massachusetts Institute of Technology)
2. Laxman Dhulipala (University of Maryland)
3. Julian Shun (Massachusetts Institute of Technology)

BibTeX Citation

@inproceedings{shi_sigmod24,
        title = {{Parallel Algorithms for Hierarchical Nucleus Decomposition}},
        author = {Shi, Jessica and Dhulipala, Laxman and Shun, Julian},
        series = {{SIGMOD} '24},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3639287},
        url = {https://dl.acm.org/doi/10.1145/3639287},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,273	Nucleus Decomposition Revisited: An Efficient Counting-Based Approach	2026	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 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
138	Discovering Large Dense Subgraphs in Massive Graphs	2005	VLDB	0.00029823423
189	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00026114928
590	Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis	2013	VLDB	0.0001605572
825	K-Core Decomposition of Large Networks on a Single PC	2016	VLDB	0.00013779895
1,069	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB	0.00012323497
1,113	Approximate Closest Community Search in Networks	2016	VLDB	0.00012124571
1,416	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	0.00010839488
2,024	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB	9.2907829e-05
2,083	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB	9.1976617e-05
2,243	Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs	2019	SIGMOD	8.8813183e-05
2,826	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	8.0865974e-05
3,503	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB	7.3592701e-05
6,368	Theoretically and Practically Efficient Parallel Nucleus Decomposition	2022	VLDB	5.8975125e-05
7,624	RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs	2021	VLDB	5.5805027e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,640	Distance-generalized Core Decomposition	2019	SIGMOD
2	10,100	Parallel Colorful h-star Core Maintenance in Dynamic Graphs	2023	VLDB
3	9,301	Accelerating Core Decomposition in Billion-Scale Hypergraphs	2025	SIGMOD
4	5,697	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB
5	2,083	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB
6	1,416	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB
7	6,617	Efficient Parallel D-core Decomposition at Scale	2024	VLDB
8	10,772	Parallel k-Core Decomposition: Theory and Practice	2025	SIGMOD
9	10,273	Nucleus Decomposition Revisited: An Efficient Counting-Based Approach	2026	SIGMOD
10	6,368	Theoretically and Practically Efficient Parallel Nucleus Decomposition	2022	VLDB