关键词: 动态图划分, GN算法, 交叉边, 负载均衡度

Abstract: With the rapid growth of graph scale, the demand for real-time processing of dynamic graphs is increasing. Most of the existing algorithms are effective for static graph partitioning, but directly using them to process dynamic graphs will bring greater communication overheads. To solve this problem, a dynamic graph partitioning method based on GN algorithm is proposed. Firstly, the vertices to be inserted in the dynamic graph over a period of time are collected. Then, the GN algorithm is used to pre-partition these newly inserted vertices to generate several internally connected communities. Finally, the community results generated by the pre-partitioning are inserted into the current graph that has been partitioned. Through experiments, the proposed method is compared with the traditional streaming partitioning method in terms of crossed edges and load balance. The results show that, on the public datasets, The proposed method can reduce the number of crossed edges by 13%, and the load balance by 42.3%. It can be seen that, compared with the streaming partitioning method, the proposed method can significantly improve the quality of dynamic graph partitioning.

Key words: dynamic graph partitioning, GN algorithm, crossed edge, load balance