Densest Subgraph in Streaming and MapReduce
Large-scale graph processing remains a challenging problem in data analysis. In this paper, the authors focus on the densest subgraph problem that forms a basic primitive for a diverse number of applications ranging from those in computational biology to community mining and spam detection. 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, they present new algorithms for finding the densest subgraph in the streaming model.