Towards a distributed local-search approach for partitioning large-scale social networks

Large-scale social graph data poses significant challenges for social analytic tools to monitor and analyze social networks. A feasible solution is to parallelize the computation and leverage distributed graph computing frameworks to process such big data. However, it is nontrivial to partition social graphs into multiple parts so that they can be computed on distributed platforms. In this paper, we propose a distributed local search algorithm, named dLS, which enables quality and efficient partition of large-scale social graphs. With the vertex-centric computing model, dLS can achieve massive parallelism. We employ a distributed graph coloring strategy to differentiate neighbor nodes and avoid interference during the parallel execution of each vertex. We convert the original graph into a small graph, Quotient Network, and obtain local search solution from processing the Quotient Network, thus further improving the partition quality and efficiency of dLS. We have evaluated the performance of dLS experimentally using real-life and synthetic social graphs, and the results show that dLS outperforms two state-of-the-art algorithms in terms of partition quality and efficiency.