Directed densest subgraph approximations made efficient with sparsification
Sparsification Framework for Directed Densest Subgraph
Data Structures and Algorithms
Summary
Finding the densest subgraph in a directed graph is a way to identify tightly connected groups, but it is computationally challenging for big graphs. The authors present a new method to shrink the graph while keeping enough information to find nearly optimal densest subgraphs. This faster approach works well even when memory or time is limited, improving on older methods in single-pass streaming, parallel computing, and sublinear time algorithms. Their work helps close gaps between directed and undirected graphs in these settings.
What this means in practice
- •For big data engineers: Compute dense clusters in large directed graphs using limited memory and single-pass algorithms.
- •For distributed system architects: Implement fast parallel graph analytics to find dense subgraphs efficiently in near-linear memory MPC frameworks.
Authors
Slobodan Mitrović, Theodore Pan
Abstract
We develop a new approach for computing approximate directed densest subgraphs (DDS). Our main result is a sparsification procedure that reduces a directed graph $G$ on $n$ vertices to a graph with $n \cdot \text{poly} \log n$ edges while preserving enough structure to recover an approximate DDS of $G$. Instantiating this framework in several memory-constrained settings, we obtain the following improvements over the state of the art: In semi-streaming, we obtain a single-pass algorithm that computes a $(1-\varepsilon)$-approximate DDS. Previously, the only semi-streaming algorithm that computed a constant approximation of DDS was by Bahmani, Kumar, and Vassilvitskii (2012), providing a $0.5-\varepsilon$ approximation in $O(\log n)$ passes. Hence, our work completely closes the approximation gap between undirected and directed DS in the semi-streaming setting, matching the $(1-\varepsilon)$-approximate undirected DS algorithm by Esfandiari, Hajiaghayi, and Woodruff (2016). In the near-linear-memory MPC regime, we obtain an $O(1)$-round algorithm for $(1-\varepsilon)$-approximate DDS, improving over the $O(\sqrt{\log n})$-round $(0.5-\varepsilon)$-approximation algorithm of Mitrović and Pan (2024). In the sublinear-time setting, we obtain an algorithm using $\tilde{O}(n)$ time, space, and oracle queries to compute a $(1-\varepsilon)$-approximate DDS, improving over the $\tilde{O}(n^{1.5})$ time, space, and query algorithm of Esfandiari, Hajiaghayi, and Woodruff (2016).