基于邻域的大规模图数据动态分割算法

Large Scale Dynamic Graph Partitioning Based on Neighborhood Algorithm

随着图数据的规模日益增大,出现大量以动态图数据为基础的分布式处理需求,划分问题在动态图数据分布式处理领域尤为重要.对大规模动态图数据上的划分问题进行研究,根据图结构性质及动态图特点,提出并实现基于邻域的动态图分割算法.算法分为静态切分和动态调整两个阶段,其中基于割边算法整合现有最优化策略提出了大规模图数据的静态切割算法.在优化后的静态切割算法的基础上,根据图数据的动态扩张的特性提出动态分割算法.根据迁移顶点所达到的最小负载值进行顶点迁移,并在此基础上进行性能及割边控制优化操作.最后,改进算法在各类图数据集上进行了验证,验证的结果显示在平衡度和割边等指标上优化后的算法效果显著,提高了划分的合理性,并且在保证割边不增加的情况下提高了图分割的平衡度.

To solve the problem of graph data distributed processing, graph partitioning is more and more important. This paper studies the method of partitioning a large-scale dynamic graph. According to the characteristics of graph structure and dynamic graph, a dynamic graph partitioning algorithm based on neighborhood is proposed and implemented. The algorithm consists of two stages, static partition and dynamic adjustment. A static graph partitioning combines the cut-edges and the existing partition tools to get an optimized method. The dynamic adjustment focuses on the transferring of vertexes to its neighborhood. It calculates the value of vertexes transferring load and optimize the operations. Experiments on a series of common graph datasets show significant effect on the indexes of balance and cut-edges, which means the partition is reasonable and balanced.