关键词: 大图分布式处理, 大图划分, 图结构特征, 负载均衡, 交叉边

Abstract: This research focuses on the problem of how the large-scale graphs' structural features affect the partitioning quality. Firstly, through the structural features of vertex degree, a method of describing the large-scale graphs' structural features was proposed. Then, based on the real graph data, a number of simulation data sets with the same vertices and edges but different structural features are calculated. Through the similarity between the real graph and the simulation graph calculated by the algorithm, the validity of the method for describing the structure of the real large-scale graphs was verified. Finally, the relationship between the structural features of the graph and the effect of the partition is verified by the Hash algorithm and point-to-point exchange algorithm. When the point-to-point algorithm is performed to 50,000 times, the number of intersecting edges of the real graph G (6301, 20777) is reduced by 54.32% compared with the Hash partitioning algorithm. When the two graphs with entirely different structural features are partitioned in the simulation data, the number of cross edges are 6233 and 316, respectively. The experimental results show that the point-to-point algorithm can reduce the number of intersecting edges. The larger difference of the vertex degree distribution and the smaller the number of intersecting edges are, the better partitioning quality is. Therefore, the structural features of large graphs affect the division effect, which lays the foundation for the scale-model investigation of the relationship between structural features and partitioning quality.

Key words: large-scale graphs' distributed processing, large-scale graphs' partition, graph structural features, load balance, crossed edge