New Parallel and Streaming Algorithms for Directed Densest Subgraph

Finding dense subgraphs is a fundamental problem with applications to community detection, clustering, and data mining. Our work focuses on finding approximate densest subgraphs in directed graphs in computational models for processing massive data. We consider two such models: Massively Parallel Computation (MPC) and semi-streaming. We show how to find a (2+ε)-approximation in O( logn) MPC rounds with sublinear memory per machine.