社交网络、网页链接、城市道路交通网和大规模集成电路等均可抽象为顶点和边的数量在千万级以上的大规模图(数据),对这类大规模图的高效分析与计算需要在分布式平台上进行。然而,大规模图均衡划分是分布式处理图数据的核心问题,优良的大规模图划分结果可以充分利用集群资源、提升数据处理效率。已有许多研究者以线性规划、多级划分、启发式等方法对大规模图划分问题进行了研究,并提出了许多求解算法。但已有算法存在划分效率低、未充分考虑图结构、划分结果质量差等问题。因此,对大规模图划分算法进行研究与创新,使其能够提升大规模图数据处理任务的计算效率,在大数据分析领域具有极大的理论意义和应用价值。论文选题来源于国家自然科学基金项目,作者针对已有算法缺陷,结合标签传播机制、多目标优化和对大规模图内部结构的研究创新提出了两种新的大规模图划分算法,同时,用所提出的算法优化了Giraph图处理框架中的图划分处理组件,使其图处理框架的性能得到了较大的提升。本文主要工作内容及创新如下:(1)针对传统大规模图划分算法划分效率低、划分质量差且未充分利用分布式平台的问题,本文基于轻量级的标签传播机制,创新提出了一种新的高效平衡大规模图划分算法BGPLP。首先,BGPLP算法将多目标优化问题转化成单目标优化问题,以简化求解过程。然后,在迭代过程中同时考虑优化分区负载平衡和最小化通信开销,从而提高图划分结果的质量。针对已有的标签传播算法中标签更新规则不能适应划分情况变化的问题,本文提出了动态标签更新策略。针对不能准确判断算法迭代收敛的问题,本文提出了双条件收敛判断准则。最后,在不同规模数据集上与当前最好的大规模图划分算法进行了性能对比实验,实验结果表明:BGPLP算法的划分质量与效率都优于目前最好的大规模图划分算法。(2)针对传统大规模图划分算法在迭代优化过程中会陷入局部最优的问题,本文在BGPLP算法的基础上,提出多阶段大规模图划分算法GPMP。首先,在图的初始划分过程中,GPMP算法充分利用大规模图结构信息,从而提高初始划分质量。然后,在后续的迭代步骤中,GPMP算法分为寻优和跳出局部最优两个阶段进行大规模图的精细划分。寻优阶段快速优化划分结果质量,跳出局部最优阶段对算法迭代进行扰动从而极大增加算法跳出局部最优的机会,两阶段协作交替运行从而提升算法全局寻优能力。同时,根据所提出的大规模图最优划分状态保留策略,从而解决迭代过程中划分质量波动问题。最后,本文在不同规模数据集上将GPMP算法与BGPLP算法进行了对比实验,实验结果表明GPMP算法的图划分结果具有更优的负载平衡和更少的通信开销。(3)为了优化Giraph图处理框架的性能,本文按照Giraph图处理框架的接口要求将GPMP算法实现为图划分组件,替换了Giraph默认图划分组件。然后在优化前和优化后的Giraph上实现了网页排名PageRank计算和连通分量Connected Components计算。通过在各种数据集上对上述两个大规模图运算实例的实验结果分析表明:优化后的Giraph大大减少了图计算任务的运行时间,表明GPMP算法对Giraph图处理框架具有显著优化作用。作者今后将进一步研究特殊的大规模幂律图,并且将进一步优化与扩展所提出的算法,使其具有处理大规模动态图的能力。