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
- 14224
- Venue
- VLDB
- Year
- 2025
- Pagerank
- 4.1905499e-05
- Overall Rank
- 10,869 | 24.46%
- 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 |
| 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 |
| 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,392 |
Real-time Constrained Cycle Detection in Large Dynamic Graphs |
2018 |
VLDB |
0.00012224015 |
| 2,852 |
Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs |
2019 |
SIGMOD |
8.0158741e-05 |
| 2,913 |
Efficient Algorithms for Densest Subgraph Discovery |
2019 |
VLDB |
7.9229304e-05 |
| 3,155 |
Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs |
2022 |
VLDB |
7.4700348e-05 |
| 4,341 |
Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs |
2020 |
SIGMOD |
6.268429e-05 |
| 4,877 |
Discovering Polarization Niches via Dense Subgraphs with Attractors and Repulsers |
2022 |
VLDB |
5.8537804e-05 |
| 5,255 |
Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks |
2020 |
SIGMOD |
5.5991117e-05 |
| 5,266 |
Incrementalizing Graph Algorithms |
2021 |
SIGMOD |
5.5949839e-05 |
| 5,365 |
Anchored Densest Subgraph |
2022 |
SIGMOD |
5.5463723e-05 |
| 5,666 |
Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme |
2023 |
SIGMOD |
5.3824583e-05 |
| 5,701 |
Localizing Anomalous Changes in Time-evolving Graphs |
2014 |
SIGMOD |
5.36437e-05 |
| 6,195 |
Incrementalization of Graph Partitioning Algorithms |
2020 |
VLDB |
5.1583102e-05 |
| 7,439 |
BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale |
2022 |
SIGMOD |
4.7256836e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 5,274 |
A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery |
2022 |
SIGMOD |
5.5919087e-05 |
| 9,246 |
Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs |
2024 |
VLDB |
4.3648789e-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,072 |
Efficient and Scalable Directed Densest Subgraph Discovery |
2026 |
SIGMOD |
4.1905499e-05 |
| 2,913 |
Efficient Algorithms for Densest Subgraph Discovery |
2019 |
VLDB |
7.9229304e-05 |
| 11,051 |
Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs |
2024 |
VLDB |
4.1905499e-05 |
| 4,341 |
Efficient Algorithms for Densest Subgraph Discovery on Large Directed Graphs |
2020 |
SIGMOD |
6.268429e-05 |
| 10,500 |
Integral Densest Subgraph Search on Directed Graphs |
2025 |
SIGMOD |
4.1905499e-05 |
| 5,365 |
Anchored Densest Subgraph |
2022 |
SIGMOD |
5.5463723e-05 |