  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 $\epsilon>0$, we present a dynamic
algorithm that, with high probability, maintains a $(4+\epsilon)$-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(\poly\log_{1+\epsilon} n)$ term. The approximation ratio
can be improved to $(2+\epsilon)$ at the cost of increasing the query time to
$\tilde O(n)$. It can be extended to a $(2+\epsilon)$-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.
