EUVIMEDEUVIMED entdecken
Crossref

Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance

Yingli Zhou, Youran Sun, Yixiang Fang

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →