Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams

While in many graph mining applications it is crucial to handle a stream of updates efficiently in terms of em both time and space, not much was known about achieving such type of algorithm. In this paper we study this issue for a problem which lies at the core of many graph mining applications called em densest subgraph problem. We develop an algorithm that achieves time- and space-efficiency for this problem simultaneously. It is one of the first of its kind for graph problems to the best of our knowledge. In a graph G = (V, E), the "density" of a subgraph induced by a subset of nodes S subseteq V is defined as |E(S)|/|S|, where E(S) is the set of edges in E with both endpoints in S. In the densest subgraph problem, the goal is to find a subset of nodes that maximizes the density of the corresponding induced subgraph. For any ε>0, we present a dynamic algorithm that, with high probability, maintains a (4+ε)-approximation to the densest subgraph problem under a sequence of edge insertions and deletions in a graph with n nodes. It uses tilde O(n) space, and has an amortized update time of tilde O(1) and a query time of tilde O(1). Here, tilde O hides a O(polylog1+ε n) term. The approximation ratio can be improved to (2+ε) at the cost of increasing the query time to tilde O(n). It can be extended to a (2+ε)-approximation sublinear-time algorithm and a distributed-streaming algorithm. Our algorithm is the first streaming algorithm that can maintain the densest subgraph in em one pass. The previously best algorithm in this setting required O(log n) passes [Bahmani, Kumar and Vassilvitskii, VLDB'12]. The space required by our algorithm is tight up to a polylogarithmic factor.