Back to papers
Approximate Anchored Densest Subgraph Search on Large Static and Dynamic Graphs
Summary: Introduce integer R-subgraph density giving an additive <1 approximation to the Anchored Densest Subgraph (AADS), enabling efficient approximate ADS search on large graphs and large R. Present a polynomial-time global algorithm (re-orientation network flow + binary search), a local shortest-path-based max-flow method for large R, and dynamic edge-update maintenance with strong empirical scalability.
(summarized by gpt-5-mini on Feb 09 2026)
- Paper ID
- 14223
- Venue
- VLDB
- Year
- 2025
- Pagerank
- 4.1945683e-05
- Overall Rank
- 10,865 | 24.42%
- DOI
-
10.14778/3712221.3712230
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
Outgoing Citations (Sorted by Pagerank)
Showing 17 of 17 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 |
| 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 |
| 1,394 |
Real-time Constrained Cycle Detection in Large Dynamic Graphs |
2018 |
VLDB |
0.0001221552 |
| 2,846 |
Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs |
2019 |
SIGMOD |
8.0234377e-05 |
| 2,909 |
Efficient Algorithms for Densest Subgraph Discovery |
2019 |
VLDB |
7.9305767e-05 |
| 3,146 |
Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs |
2022 |
VLDB |
7.477231e-05 |
| 4,344 |
Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs |
2020 |
SIGMOD |
6.2744553e-05 |
| 4,875 |
Discovering Polarization Niches via Dense Subgraphs with Attractors and Repulsers |
2022 |
VLDB |
5.8594122e-05 |
| 5,250 |
Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks |
2020 |
SIGMOD |
5.6044961e-05 |
| 5,292 |
Incrementalizing Graph Algorithms |
2021 |
SIGMOD |
5.5816687e-05 |
| 5,355 |
Anchored Densest Subgraph |
2022 |
SIGMOD |
5.5517073e-05 |
| 5,655 |
Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme |
2023 |
SIGMOD |
5.387631e-05 |
| 5,763 |
Localizing Anomalous Changes in Time-evolving Graphs |
2014 |
SIGMOD |
5.3369426e-05 |
| 6,193 |
Incrementalization of Graph Partitioning Algorithms |
2020 |
VLDB |
5.1632545e-05 |
| 7,441 |
BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale |
2022 |
SIGMOD |
4.7302202e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 5,265 |
A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery |
2022 |
SIGMOD |
5.5972878e-05 |
| 9,239 |
Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs |
2024 |
VLDB |
4.3690661e-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,072 |
Efficient and Scalable Directed Densest Subgraph Discovery |
2026 |
SIGMOD |
4.1945683e-05 |
| 2,909 |
Efficient Algorithms for Densest Subgraph Discovery |
2019 |
VLDB |
7.9305767e-05 |
| 11,048 |
Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs |
2024 |
VLDB |
4.1945683e-05 |
| 4,344 |
Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs |
2020 |
SIGMOD |
6.2744553e-05 |
| 10,490 |
Integral Densest Subgraph Search on Directed Graphs |
2025 |
SIGMOD |
4.1945683e-05 |
| 5,355 |
Anchored Densest Subgraph |
2022 |
SIGMOD |
5.5517073e-05 |