Incremental Graph Partitioning Based on MapReduce

Abstract

Graph partitioning is widely used in many diverse domains. Incremental graph is a member of Graph which evolves with time. Traditional static graph partitioning methods can not meet the requirement with the incremental graph partitioning due to expensive computational cost and long off-line processing time. In this paper, we propose a distributed incremental graph partitioning algorithm to partition the incremental Graphs into smaller components with Hadoop. Our method considers four different modification events of incremental graph partitioning. Moreover, we evaluate our method in Metis and the experimental results show our method is more effective in terms of different measurements than baselines.