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
11861
Venue
VLDB
Year
2019
Pagerank
7.9229304e-05
Overall Rank
2,913 | 79.76%
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,291 Effective and Efficient Community Search over Large Heterogeneous Information Networks 2020 VLDB 9.0894835e-05
3,323 Hierarchical Core Maintenance on Large Dynamic Graphs 2021 VLDB 7.2170169e-05
3,496 Efficient Maximal Biclique Enumeration for Large Sparse Bipartite Graphs 2022 VLDB 7.0376611e-05
3,579 Finding Locally Densest Subgraphs: A Convex Programming Approach 2022 VLDB 6.9461197e-05
4,147 Scaling Up k-Clique Densest Subgraph Detection 2023 SIGMOD 6.4060893e-05
4,266 Efficient k-Clique Listing: An Edge-Oriented Branching Strategy 2024 SIGMOD 6.3006582e-05
4,341 Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs 2020 SIGMOD 6.268429e-05
4,460 Efficient Bi-triangle Counting for Large Bipartite Networks 2021 VLDB 6.1592411e-05
4,536 Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice 2020 VLDB 6.099154e-05
4,626 Efficient Biclique Counting in Large Bipartite Graphs 2023 SIGMOD 6.0340995e-05
4,737 Cohesive Subgraph Search over Big Heterogeneous Information Networks: Applications, Challenges, and Solutions 2021 SIGMOD 5.9529218e-05
5,274 A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery 2022 SIGMOD 5.5919087e-05
5,365 Anchored Densest Subgraph 2022 SIGMOD 5.5463723e-05
5,548 Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021 VLDB 5.4445937e-05
5,599 Neighborhood-based Hypergraph Core Decomposition 2023 VLDB 5.4164926e-05
6,185 Efficient Core Maintenance in Large Bipartite Graphs 2023 SIGMOD 5.1618114e-05
6,509 Efficient Parallel D-core Decomposition at Scale 2024 VLDB 5.0273291e-05
6,796 Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020 VLDB 4.9195203e-05
6,882 Theoretically and Practically Efficient Parallel Nucleus Decomposition 2022 VLDB 4.8923998e-05
7,450 Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks 2023 SIGMOD 4.7218383e-05
7,806 RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs 2021 VLDB 4.6421951e-05
9,231 Efficiently Counting Triangles in Large Temporal Graphs 2025 SIGMOD 4.3648789e-05
9,251 Densest Multipartite Subgraph Search in Heterogeneous Information Networks 2024 VLDB 4.3648789e-05
9,409 A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery 2024 SIGMOD 4.3399748e-05
9,557 An Efficient and Exact Algorithm for Locally h-Clique Densest Subgraph Discovery 2024 SIGMOD 4.3212967e-05
9,648 BYO: A Unified Framework for Benchmarking Large-Scale Graph Containers 2024 VLDB 4.3067693e-05
9,950 Parallel Colorful h-star Core Maintenance in Dynamic Graphs 2023 VLDB 4.236537e-05
10,072 Efficient and Scalable Directed Densest Subgraph Discovery 2026 SIGMOD 4.1905499e-05
10,500 Integral Densest Subgraph Search on Directed Graphs 2025 SIGMOD 4.1905499e-05
10,526 Faster and Efficient Density Decomposition via Proportional Response with Exponential Momentum 2025 SIGMOD 4.1905499e-05
10,544 In-depth Analysis of Densest Subgraph Discovery in a Unified Framework 2025 VLDB 4.1905499e-05
10,689 Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory 2025 VLDB 4.1905499e-05
10,869 Approximate Anchored Densest Subgraph Search on Large Static and Dynamic Graphs 2025 VLDB 4.1905499e-05
10,950 Parallel Algorithms for Hierarchical Nucleus Decomposition 2024 SIGMOD 4.1905499e-05
11,305 Density Personalized Group Query 2023 VLDB 4.1905499e-05
11,413 Densest Subgraph Discovery on Large Graphs: Applications, Challenges, and Techniques 2022 VLDB 4.1905499e-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
280 3-HOP: A High-Compression Indexing Scheme for Reachability Query 2009 SIGMOD 0.00029092277
284 Querying K-Truss Community in Large and Dynamic Graphs 2014 SIGMOD 0.00029014359
327 The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing 2018 VLDB 0.00027312381
370 Online Search of Overlapping Communities 2013 SIGMOD 0.00025391823
645 Densest Subgraph in Streaming and MapReduce 2012 VLDB 0.00018727714
734 Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis 2013 VLDB 0.00017419528
1,000 Effective Community Search for Large Attributed Graphs 2016 VLDB 0.00014714977
1,014 Robust Local Community Detection: On Free Rider Effect and Its Elimination 2015 VLDB 0.00014631717
1,484 Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks 2019 VLDB 0.00011705344
1,645 Attribute-Driven Community Search 2017 VLDB 0.00011027616
1,848 Effective Community Search over Large Spatial Graphs 2017 VLDB 0.00010331574
2,043 Local Algorithms for Hierarchical Dense Subgraph Discovery 2019 VLDB 9.6970812e-05
2,516 Fast Hierarchy Construction for Dense Subgraphs 2017 VLDB 8.6114467e-05
2,685 Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms 2016 SIGMOD 8.314724e-05
2,787 Scalable Distributed Subgraph Enumeration 2017 VLDB 8.1219297e-05
2,963 Subgraph Matching: on Compression and Computation 2018 VLDB 7.8061004e-05
3,406 Piggybacking on Social Networks 2013 VLDB 7.1298853e-05
4,341 Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs 2020 SIGMOD 6.268429e-05
Previous Page 1 / 1 Next

Semantically Similar Papers