关键词: 图划分, 标签传播, 多级划分算法, 大图

Abstract: Graph data partition is a critical part of the large scale graph and it restricts the efficiency of the system. Now the system usually uses random partition or multi-level partition, but the requirements of the two aforementioned aspects are hard to be satisfied in aspects of partition speed and partition effects. Therefore, this paper presents a new multi-level partition algorithm called GPLP （Graph Partitioning based on Label Propagation） based on the label propagation. GPLP consists of data marking, coarsening and data moving. Label propagation algorithm has been improved and used in multi-level structure. At last, some experiments have been done to compare the performance among GPLP, Hash and ParMETIS from multiple aspects. The results show that GPLP can improve the job executing efficiency and effectively solve the problems of large scale graph among partitions.

Key words: graph partition, label propagation, multi-level partition, large scale graph