Real-time Edge Repartitioning for Dynamic Graph

To improve the performance of large graph computing, graph partitioning has become a mandatory step in distributed graph computing frameworks. Some existing frameworks partition edges of an input graph in a streaming way. As the scale of real-world graphs grows dynamically, they need to limit the increasing communication cost and time cost in graph computing by reducing vertex replicas(each vertex can be replicated to multiple partitions). In this paper, we propose a real-time edge repartitioning algorithm for dynamic graph, which reduces the vertex replicas by reassigning edges near the new edge. We find that some edges are migrated just after being assigned, which leads to unnecessary migrations. To reduce migration cost, according to the replicas distribution of neighbors of two vertices connected by the new edge, we assign the new edge to the partition where it is most likely to be located after repartitioning. Our evaluation shows that it improves the performance of graph computing by only a small amount of migration.