Database Paper Browser

Back to papers

Efficient Algorithms for Densest Subgraph Discovery

Summary: Introduces a k-core–driven paradigm for densest subgraph discovery (DSD) with theoretical guarantees, delivering exact and approximation algorithms. Supports diverse density notions (clique-based and general pattern-based) and achieves up to 10^4× speedups on real and synthetic graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
11860
Venue
VLDB
Year
2019
Pagerank
7.9305767e-05
Overall Rank
2,909 | 79.77%
DOI
10.14778/3342263.3342645

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 36 of 36 citing papers.

Rank Citing Paper Year Venue Pagerank
2,286 Effective and Efficient Community Search over Large Heterogeneous Information Networks 2020 VLDB 9.0982591e-05
3,321 Hierarchical Core Maintenance on Large Dynamic Graphs 2021 VLDB 7.223972e-05
3,492 Efficient Maximal Biclique Enumeration for Large Sparse Bipartite Graphs 2022 VLDB 7.044442e-05
3,575 Finding Locally Densest Subgraphs: A Convex Programming Approach 2022 VLDB 6.9528126e-05
4,145 Scaling Up k-Clique Densest Subgraph Detection 2023 SIGMOD 6.4122551e-05
4,270 Efficient k-Clique Listing: An Edge-Oriented Branching Strategy 2024 SIGMOD 6.3067205e-05
4,344 Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs 2020 SIGMOD 6.2744553e-05
4,459 Efficient Bi-triangle Counting for Large Bipartite Networks 2021 VLDB 6.1651553e-05
4,534 Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice 2020 VLDB 6.1049756e-05
4,626 Efficient Biclique Counting in Large Bipartite Graphs 2023 SIGMOD 6.0399035e-05
4,743 Cohesive Subgraph Search over Big Heterogeneous Information Networks: Applications, Challenges, and Solutions 2021 SIGMOD 5.9586508e-05
5,265 A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery 2022 SIGMOD 5.5972878e-05
5,355 Anchored Densest Subgraph 2022 SIGMOD 5.5517073e-05
5,540 Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021 VLDB 5.4498271e-05
5,589 Neighborhood-based Hypergraph Core Decomposition 2023 VLDB 5.4216989e-05
6,183 Efficient Core Maintenance in Large Bipartite Graphs 2023 SIGMOD 5.1667703e-05
6,513 Efficient Parallel D-core Decomposition at Scale 2024 VLDB 5.0321577e-05
6,795 Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020 VLDB 4.9242446e-05
6,880 Theoretically and Practically Efficient Parallel Nucleus Decomposition 2022 VLDB 4.8970985e-05
7,451 Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks 2023 SIGMOD 4.7263711e-05
7,804 RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs 2021 VLDB 4.6466513e-05
9,228 Efficiently Counting Triangles in Large Temporal Graphs 2025 SIGMOD 4.3690661e-05
9,244 Densest Multipartite Subgraph Search in Heterogeneous Information Networks 2024 VLDB 4.3690661e-05
9,403 A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery 2024 SIGMOD 4.3441378e-05
9,557 An Efficient and Exact Algorithm for Locally h-Clique Densest Subgraph Discovery 2024 SIGMOD 4.3254416e-05
9,647 BYO: A Unified Framework for Benchmarking Large-Scale Graph Containers 2024 VLDB 4.3109001e-05
9,951 Parallel Colorful h-star Core Maintenance in Dynamic Graphs 2023 VLDB 4.2405999e-05
10,072 Efficient and Scalable Directed Densest Subgraph Discovery 2026 SIGMOD 4.1945683e-05
10,490 Integral Densest Subgraph Search on Directed Graphs 2025 SIGMOD 4.1945683e-05
10,517 Faster and Efficient Density Decomposition via Proportional Response with Exponential Momentum 2025 SIGMOD 4.1945683e-05
10,535 In-depth Analysis of Densest Subgraph Discovery in a Unified Framework 2025 VLDB 4.1945683e-05
10,681 Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory 2025 VLDB 4.1945683e-05
10,865 Approximate Anchored Densest Subgraph Search on Large Static and Dynamic Graphs 2025 VLDB 4.1945683e-05
10,947 Parallel Algorithms for Hierarchical Nucleus Decomposition 2024 SIGMOD 4.1945683e-05
11,303 Density Personalized Group Query 2023 VLDB 4.1945683e-05
11,410 Densest Subgraph Discovery on Large Graphs: Applications, Challenges, and Techniques 2022 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
279 3-HOP: A High-Compression Indexing Scheme for Reachability Query 2009 SIGMOD 0.00029113513
283 Querying K-Truss Community in Large and Dynamic Graphs 2014 SIGMOD 0.00029041257
331 The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing 2018 VLDB 0.00027214222
370 Online Search of Overlapping Communities 2013 SIGMOD 0.00025415479
644 Densest Subgraph in Streaming and MapReduce 2012 VLDB 0.00018748988
738 Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis 2013 VLDB 0.00017435236
999 Effective Community Search for Large Attributed Graphs 2016 VLDB 0.00014726563
1,013 Robust Local Community Detection: On Free Rider Effect and Its Elimination 2015 VLDB 0.00014645542
1,484 Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks 2019 VLDB 0.00011714263
1,645 Attribute-Driven Community Search 2017 VLDB 0.00011037459
1,844 Effective Community Search over Large Spatial Graphs 2017 VLDB 0.00010341077
2,039 Local Algorithms for Hierarchical Dense Subgraph Discovery 2019 VLDB 9.7061003e-05
2,512 Fast Hierarchy Construction for Dense Subgraphs 2017 VLDB 8.6196023e-05
2,684 Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms 2016 SIGMOD 8.3136866e-05
2,801 Scalable Distributed Subgraph Enumeration 2017 VLDB 8.0992955e-05
2,997 Subgraph Matching: on Compression and Computation 2018 VLDB 7.7559339e-05
3,403 Piggybacking on Social Networks 2013 VLDB 7.136763e-05
4,344 Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs 2020 SIGMOD 6.2744553e-05
Previous Page 1 / 1 Next

Semantically Similar Papers