An Efficient Method for Graph Repartitioning in Distributed Environments

He LI  YanNa LIU  XuHua WANG  LiangCai SU  Hang YUAN  JaeSoo YOO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E103-D   No.7   pp.1773-1776
Publication Date: 2020/07/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2020EDL8018
Type of Manuscript: LETTER
Category: Data Engineering, Web Information Systems
Keyword: 
large graph,  dynamic graph,  graph partitioning,  graph repartitioning,  graph algorithms,  

Full Text: PDF(463.4KB)>>
Buy this Article




Summary: 
Due to most of the existing graph repartitioning methods are known for poor efficiency in distributed environments. In this paper, we introduce a new graph repartitioning method with two phases in distributed environments. In the first phase, a local method is designed to identify all the potential candidate vertices that should be moved to the other partitions at once in each partition locally. In the second phase, a streaming graph processing model is adopted to reassign the candidate vertices to achieve lightweight graph repartitioning. During the reassignment of the vertex, we propose an objective function to balance both the load balance and the number of crossing edges among the distributed partitions. The experimental results with a large set of real word and synthetic graph datasets show that the communication cost can be reduced by nearly 1 to 2 orders of magnitude compared with the existing methods.