Large-scale Distributed Graph Partitioning Algorithms

With the emergence of big graphs in a variety of real applications like social networks,machine learning based on distributed graph-computing(DGC)frameworks has attracted much attention from large-scale machine learning community.In the DGC framework,the graph partitioning(GP)strategy plays a key role to affect the performance,including the communication cost and workload balance.Typically,the degree distributions of natural graphs from real applications follow power laws,which makes GP a challenging task.Recently,many methods have been proposed to solve the GP problem.However,the existing GP methods cannot achieve satisfactory performance for applications with power-law graphs.In this paper,we propose a novel vertex-cut GP framework,called PowerLore,by making effective use of the power-law degree distribution in graphs.PowerLore includes a degree-based hashing algorithm(called Libra)and two degreebased greedy algorithms(called Constell and Zodiac).Theoretical analysis shows that Libra can achieve lower communication cost than existing hashing-based methods and can simultaneously guarantee good workload balance.Empirical results show that the two degree-based greedy algorithms can further improve the performance of Libra which is non-greedy.Moreover,empirical results on several large power-law graphs also show that PowerLore can outperform existing state-of-the-art GP methods.