Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance
Proceedings of the ACM on Management of Data · 18.05.2026 · 4 (3) · 1-27
DOI: 10.1145/3802044 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.05.2026. Verfasst von Yingli Zhou und 2 weiteren Autor:innen. Die Arbeit nennt 85 Literaturangaben.
Abstract (Originalsprache)
Densest subgraph discovery (DSD) is a fundamental research topic in network science and graph databases. As a typical variant of DSD, the anchored densest subgraph (ADS) problem aims to detect a densest subgraph that is anchored around user-defined seed vertices. The ADS problem has been shown to be very useful in some personalized applications, such as community search and recommendation. While the ADS problem is very useful, existing algorithms suffer from weak theoretical guarantees and perform poorly in practice. To address these issues, we first propose a novel approximation algorithm with improved time complexity, achieving the same accuracy as existing methods while requiring significantly fewer iterations. To further enhance practical performance, we introduce a graph reduction technique that localizes the ADS search to a much smaller subgraph, while still providing non-trivial theoretical guarantees. Building on this approximation, we also develop an efficient exact algorithm. We have performed an extensive empirical evaluation of our approaches on 12 real large datasets. The results show that our proposed algorithms are up to four orders of magnitude faster than the state-of-the-art.
Zitieren
APA
Zhou, Y., Sun, Y., & Fang, Y. (2026). Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance. Proceedings of the ACM on Management of Data, 4(3), 1-27. https://doi.org/10.1145/3802044
Vancouver
Zhou Y, Sun Y, Fang Y. Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance. Proceedings of the ACM on Management of Data. 2026;4(3):1-27. doi:10.1145/3802044
BibTeX
@article{Zhou2026,
author = {Zhou, Yingli and Sun, Youran and Fang, Yixiang},
title = {Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {3},
pages = {1--27},
doi = {10.1145/3802044}
}
EUVIMED