论文研究-GPLP：基于标签传播的大图多级划分算法.pdf

图数据划分问题是大图处理系统的关键问题，制约着图处理系统的计算效率。目前可用的划分算法可分为随机划分和多层次划分，已有的算法难以在划分速度和划分效果两个方面同时满足要求。提出了一种新的基于标签传播的多级划分算法GPLP，该方法将图划分过程分为数据标记、图粗糙化和数据迁移三部分，在多级划分框架下采用标签传播算法，并对其进行了改进。从数据划分时间和迭代计算时间两个方面对比GPLP算法、Hash算法和ParMETIS算法的性能，实验结果表明GPLP算法能够提高迭代计算速度，减少了划分时间，并且数据规模越大，其优势越明显。