标题： 新的并行和流式算法用于有向密集子图 显示英文标题

标题： New Parallel and Streaming Algorithms for Directed Densest Subgraph

摘要： 寻找密集子图是一个基本问题，广泛应用于社区检测、聚类和数据挖掘。 我们的工作集中在计算模型中查找有向图中的近似最稠密子图，这些计算模型用于处理大规模数据。 我们考虑了两种这样的模型：大规模并行计算（MPC）和半流式计算。 我们展示了如何在 $\tilde{O}(\sqrt{\log n})$ MPC 轮次中找到一个 $(2+\varepsilon)$-近似解，且每台机器的内存使用量为次线性。 这比 Bahmani 等人（WAW 2014）和 Mitrović & Pan（ICML 2024）的最新结果有所改进。 此外，我们展示了如何在半流式计算中通过一次遍历找到一个 $O(\log n)$-近似解。 这与之前的工作形成鲜明对比，之前的工作表明一次遍历只能得到 $\tilde{\Omega}(n^{1/6})$-近似解；只有在随机流的情况下才能获得更好的近似（Mitrović & Pan）。 这是第一个确定性的单遍历半流式算法，用于最稠密子图问题，适用于无向图和有向图。 我们的半流式方法也是一种仅插入的动态算法，在使用次线性内存的同时，实现了首个具有 $O(\log^2 n)$ 最坏情况更新时间的有向最稠密子图算法。 我们以两种方式对我们的方法进行了实证评估。 首先，我们展示了我们的单遍历半流式算法的表现远优于理论保证。 具体来说，它在时间序列数据集上的近似效果与 Bahmani 等人（VLDB 2012）提出的 $O(\log n)$-遍历算法的 $(2+\varepsilon)$-近似效果相匹配。 其次，我们证明了我们的 MPC 算法所需的轮次数少于之前的工作。 显示英文摘要

摘要： Finding dense subgraphs is a fundamental problem with applications to community detection, clustering, and data mining. Our work focuses on finding approximate densest subgraphs in directed graphs in computational models for processing massive data. We consider two such models: Massively Parallel Computation (MPC) and semi-streaming. We show how to find a $(2+\varepsilon)$-approximation in $\tilde{O}(\sqrt{\log n})$ MPC rounds with sublinear memory per machine. This improves the state-of-the-art results by Bahmani et al. (WAW 2014) and Mitrovi\'c & Pan (ICML 2024). Moreover, we show how to find an $O(\log n)$-approximation in a single pass in semi-streaming. This is in stark contrast to prior work, which implies $\tilde{\Omega}(n^{1/6})$-approximation for a single pass; a better approximation is known only for randomized streams (Mitrovi\'c & Pan). This is the first deterministic single-pass semi-streaming algorithm for the densest subgraph problem, both for undirected and directed graphs. Our semi-streaming approach is also an insertion-only dynamic algorithm, attaining the first directed densest subgraph algorithm with $O(\log^2 n)$ worst-case update time while using sub-linear memory. We empirically evaluate our approaches in two ways. First, we illustrate that our single-pass semi-streaming algorithm performs much better than the theoretical guarantee. Specifically, its approximation on temporal datasets matches the $(2+\varepsilon)$-approximation of an $O(\log n)$-pass algorithm by Bahmani et al. (VLDB 2012). Second, we demonstrate that our MPC algorithm requires fewer rounds than prior work.