Fast Hierarchy Construction for Dense Subgraphs

Summary: Fast hierarchy construction for dense subgraphs during peeling; uses disjoint-set forests to build the hierarchy on the fly. Neighborhood-visit construction avoids extra traversals, yielding speedups for k-core, k-truss, and nucleus hierarchies. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hd3299611585e40da
Venue: VLDB
Year: 2017
Pagerank: 9.1851569e-05
Overall Rank: 2,005 | 86.57%
DOI: 10.14778/3021924.3021925
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Ahmet Erdem Sarıyüce (Sandia National Laboratories)
2. Ali Pinar (Sandia National Laboratories)

BibTeX Citation

@article{saryuce_vldb17,
        title = {{Fast Hierarchy Construction for Dense Subgraphs}},
        author = {Sarıyüce, Ahmet Erdem and Pinar, Ali},
        journal = {PVLDB},
        series = {{VLDB} '17},
        volume = {10},
        number = {3},
        pages = {97--108},
        doi = {10.14778/3021924.3021925},
        url = {https://doi.org/10.14778/3021924.3021925},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,045	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB	0.00012318828
1,613	Distance-generalized Core Decomposition	2019	SIGMOD	0.00010057822
1,995	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB	9.2189157e-05
2,246	Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs	2019	SIGMOD	8.7594692e-05
2,873	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	7.9005874e-05
3,499	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB	7.2351042e-05
4,861	An Optimal and Progressive Approach to Online Search of Top-K Influential Communities	2018	VLDB	6.3646812e-05
5,575	Theoretically and Practically Efficient Parallel Nucleus Decomposition	2022	VLDB	6.0626208e-05
7,752	RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs	2021	VLDB	5.4440674e-05
7,891	A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition	2022	VLDB	5.4156949e-05
9,911	Parallel Algorithms for Hierarchical Nucleus Decomposition	2024	SIGMOD	5.0983269e-05
9,957	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB	5.0910746e-05
10,360	Parallel Colorful h-star Core Maintenance in Dynamic Graphs	2023	VLDB	5.014328e-05
10,407	Scaling Up Density Decomposition on Massive Graphs	2027	SIGMOD	4.9605343e-05
10,562	Nucleus Decomposition Revisited: An Efficient Counting-Based Approach	2026	SIGMOD	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 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
130	Discovering Large Dense Subgraphs in Massive Graphs	2005	VLDB	0.0003029792
182	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00026383593
580	Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis	2013	VLDB	0.00016057466
732	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00014341313
829	K-Core Decomposition of Large Networks on a Single PC	2016	VLDB	0.00013587885
978	Dense Subgraph Maintenance under Streaming Edge Weight Updates for Real-time Story Identification	2012	VLDB	0.00012699423
2,072	Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms	2016	SIGMOD	9.0668141e-05
2,900	Piggybacking on Social Networks	2013	VLDB	7.8819591e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,879	Efficient Locally h-Clique Densest Subgraph Discovery via Divide-and-Conquer	2026	VLDB
2	7,891	A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition	2022	VLDB
3	10,407	Scaling Up Density Decomposition on Massive Graphs	2027	SIGMOD
4	2,873	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB
5	9,957	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB
6	1,398	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB
7	9,911	Parallel Algorithms for Hierarchical Nucleus Decomposition	2024	SIGMOD
8	3,778	Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs	2020	SIGMOD
9	1,995	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB
10	10,562	Nucleus Decomposition Revisited: An Efficient Counting-Based Approach	2026	SIGMOD