图结构因其能较为准确地表示现实世界中实体间的关系,而被广泛应用于社交网络、生物信息网络、智能交通网等众多领域。随着信息技术的飞速发展,图数据规模日益增大,分布式并行计算成为解决大规模图数据处理的有效方法,而应用分布式并行计算的前提是快速有效地将图分割并分配到若干台计算机中,并尽可能保证负载平衡,避免因较大偏差造成存储空间的浪费。同时,现实应用中,图常随时间而动态变化,如何对大规模动态图进行有效地分割成为处理图数据的关键,因而成为当前图数据处理技术的研究热点之一。本文针对当前图分割问题进行了深入研究,发现在当前数据增长的规模与速度背景下,现实应用对图分割效率、分割结果优劣以及分割中的冗余存储等方面提出了更高的要求,现有的图分割方法已无法有效地解决大规模动态图的分割问题。针对上述问题,本文根据相邻两时刻,图的分区结构具有一定相似性的短暂平滑效应,将动态图分割问题分为两个阶段进行解决。首先针对初始图的静态结构,基于分层划分思想框架,针对初始分割阶段提出了一种利用部分节点交换的算法来进行划分,以尽可能保证负载均衡,即MPA-S方法。其次针对动态图结构,为避免重新分割造成的巨大开销,本文提出一种有向性动态维护策略,即MPA-D方法,该方法以时间片T为单位,收集T时间片内图的动态变化,并通过判断这些变化是否涉及边界节点而给出不同的逻辑移动策略;同时提出一种有向动态优化算法将逻辑移动策略结果进行调整以适应收集到的图节点或边的变化。最后,真实数据集上的大量实验验证,本文提出的MPA方法通过压缩和还原,在一定程度上有效解决大规模图的分割问题,尽可能保证各计算节点的负载平衡,并减少因计算过程的冗余存储造成的存储空间浪费问题,且最终的分割结果质量也有所提高。