A Bottom-up Algorithm to Find the Densest Subgraphs Based on MapReduce

Woonghee Lee, Younghoon Kim

http://doi.org/

Finding the densest subgraphs from social networks, such that people in the subgraph are in a particular community or have common interests, has been a recurring problem in numerous studies undertaken. However, these algorithms focused only on finding the single densest subgraph. We suggest a heuristic algorithm of the bottom-up type, which finds the densest subgraph by increasing its size from a given starting node, with the repeated addition of adjacent nodes with the maximum degree. Furthermore, since this approach matches well with parallel processing, we further implement a parallel algorithm on the MapReduce framework. In experiments using various graph data, we confirmed that the proposed algorithm finds the densest subgraphs in fewer steps, as compared to other related studies. It also scales efficiently for many given starting nodes.