2023/11/18 by Slobodan Mitrović, Mitrović, Slobodan, Theodore Pan +1 · 1 citation
Computer Science · #Caching and Content Delivery #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.2311.10924
openalex publication_date 2023/11/18 · openalex created_date 2023/11/22 · openalex updated_date 2026/07/28
Finding dense subgraphs is a fundamental algorithmic tool in data mining, community detection, and clustering. In this problem, one aims to find an induced subgraph whose edge-to-vertex ratio is maximized. We study the directed case of this question in the context of semi-streaming and massively parallel algorithms. In particular, we show that it is possible to find a (2+ε) approximation on randomized streams even in a single pass by using O(n ⋅ \rm poly log n) memory on n-vertex graphs. Our result improves over prior works, which were designed for arbitrary-ordered streams: the algorithm by Bahmani et al. (VLDB 2012) which uses O(log n) passes, and the work by Esfandiari et al. (2015) which makes one pass but uses O(n3/2) memory. Moreover, our techniques extend to the Massively Parallel Computation model yielding O(1) rounds in the super-linear and O(√(log n)) rounds in the nearly-linear memory regime. This constitutes a quadratic improvement over state-of-the-art bounds by Bahmani et al. (VLDB 2012 and WAW 2014), which require O(log n) rounds even in the super-linear memory regime. Finally, we empirically evaluate our single-pass semi-streaming algorithm on 6 benchmarks and show that, even on non-randomly ordered streams, the quality of its output is essentially the same as that of Bahmani et al. (VLDB 2012) while it is 2 times faster on large graphs.