  The problem of finding locally dense components of a graph is an important
primitive in data analysis, with wide-ranging applications from community
mining to spam detection and the discovery of biological network modules. In
this paper we present new algorithms for finding the densest subgraph in the
streaming model. For any epsilon>0, our algorithms make O((log n)/log
(1+epsilon)) passes over the input and find a subgraph whose density is
guaranteed to be within a factor 2(1+epsilon) of the optimum. Our algorithms
are also easily parallelizable and we illustrate this by realizing them in the
MapReduce model. In addition we perform extensive experimental evaluation on
massive real-world graphs showing the performance and scalability of our
algorithms in practice.
