A feasible graph partition framework for parallel computing of big graph

作者：Liu, X.; Zhou, Y.^*; Guan, X.; Shen, C.

来源：Knowledge-Based Systems, 2017, 134: 228-239.

DOI：10.1016/j.knosys.2017.08.001

• Graph partition
• Parallelism
• Big graph
• Objective optimization
• Greedy algorithm

With the emerging of large scale complex networks, graph computation, such as community detection, meets new technology challenges of extremely large computational cost. In order to deal with these challenges, the parallelism is becoming necessary. Graph partition is a fundamental problem of parallel computing for big graph data. The challenges of graph partition include large numbers of communications between partitions, extreme replication of vertices, and unbalanced partition. In this paper, we propose a feasible graph partition framework for parallel computing of big graph. The framework is based on an objective optimization problem to reduce the bandwidth, memory and storage cost on condition that the load balance could be guaranteed. In this framework, three greedy graph partition algorithms are proposed. By running the algorithms on the different kinds of graphs, including real-world graphs and synthetic graphs, the experimental results show that our algorithms surpass the state of the art heuristic algorithms. For example, running time is reduced more than 21.56% and the communication cost is decreased by more than 17.90% for weighted graph. The adequate experiments verify that our algorithms are capable of solving the problem of graph partition with different needs.

• 出版日期2017-10-15
• 单位西安交通大学; 清华大学