Local Algorithms for Hierarchical Dense Subgraph Discovery

Summary: Local, parallel algorithms for core, truss, and nucleus decompositions enable hierarchical dense-subgraph discovery without synchronization. Extends h-index to higher-order decompositions with convergence bounds, enabling local, scalable approximations. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h9057a19c3e03a37b
Venue: VLDB
Year: 2019
Pagerank: 0.0001076734
Overall Rank: 1,398 | 90.64%
DOI: 10.14778/3275536.3275540
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Ahmet Erdem Sarıyüce (State University of New York at Buffalo)
2. C. Seshadhri (University of California)
3. Ali Pinar (Sandia National Laboratories)

BibTeX Citation

@article{saryuce_vldb19,
        title = {{Local Algorithms for Hierarchical Dense Subgraph Discovery}},
        author = {Sarıyüce, Ahmet Erdem and Seshadhri, C. and Pinar, Ali},
        journal = {PVLDB},
        series = {{VLDB} '19},
        volume = {12},
        number = {1},
        pages = {43--56},
        doi = {10.14778/3275536.3275540},
        url = {https://doi.org/10.14778/3275536.3275540},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 22 of 22 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,988	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB	9.2301018e-05
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
3,387	Mining Bursting Core in Large Temporal Graphs	2022	VLDB	7.3346183e-05
3,499	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB	7.2351042e-05
3,880	Distributed D-core Decomposition over Large Directed Graphs	2022	VLDB	6.9318416e-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
5,725	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB	5.9991587e-05
6,666	Efficient Parallel D-core Decomposition at Scale	2024	VLDB	5.698709e-05
7,303	Towards Distributed Bitruss Decomposition on Bipartite Graphs	2022	VLDB	5.5455743e-05
7,752	RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs	2021	VLDB	5.4440674e-05
7,832	A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery	2024	SIGMOD	5.4289543e-05
8,088	Efficient Star-based Truss Maintenance on Dynamic Graphs	2023	SIGMOD	5.3746503e-05
8,865	MCR-Tree: An Efficient Index for Multi-dimensional Core Search	2024	SIGMOD	5.2471429e-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,241	Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs	2020	VLDB	5.041918e-05
10,407	Scaling Up Density Decomposition on Massive Graphs	2027	SIGMOD	4.9605343e-05
10,457	On Sketching Trimmed Statistics	2026	PODS	4.9605343e-05
10,562	Nucleus Decomposition Revisited: An Efficient Counting-Based Approach	2026	SIGMOD	4.9605343e-05
12,176	Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice	2020	VLDB	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
269	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00022625826
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,900	Piggybacking on Social Networks	2013	VLDB	7.8819591e-05
4,731	Efficient Cohesive Subgraphs Detection in Parallel	2014	SIGMOD	6.4313179e-05
5,593	Ego-net Community Mining Applied to Friend Suggestion	2016	VLDB	6.054993e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,333	Neighborhood-based Hypergraph Core Decomposition	2023	VLDB
2	10,360	Parallel Colorful h-star Core Maintenance in Dynamic Graphs	2023	VLDB
3	96	Truss Decomposition in Massive Networks	2012	VLDB
4	10,879	Efficient Locally h-Clique Densest Subgraph Discovery via Divide-and-Conquer	2026	VLDB
5	10,562	Nucleus Decomposition Revisited: An Efficient Counting-Based Approach	2026	SIGMOD
6	9,957	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB
7	8,444	Truss Decomposition in Hypergraphs	2025	VLDB
8	2,005	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB
9	9,911	Parallel Algorithms for Hierarchical Nucleus Decomposition	2024	SIGMOD
10	5,725	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB