随着计算机及网络技术的飞速发展,越来越多的应用领域需要对大规模图数据进行处理。传统的单机处理模式不能有效地适应大规模图数据计算,因此出现了许多分布式环境下的图处理框架,如Pregel、Giraph、Graphlab等。图划分是分布式图处理过程中的关键步骤,现有的分布式图处理系统大多采用一次性静态图划分技术来平衡各个计算节点的工作负载。由于在分布式图处理的迭代过程中,不同特性的图算法每次迭代计算所访问的图顶点数可能不同,其执行过程中的运行时负载是随图算法执行行为而变化的。一次静态图划分未考虑这种图算法行为所产生的运行时负载不均衡对计算性能的影响,无法保证图算法整个计算过程中的负载均衡,从而降低了图处理的效率。基于动态再划分的负载优化方法采用动态负载平衡技术,依据图计算的行为特性监测负载的运行时状态,动态地将超载计算节点的负载转移到未超载计算节点,从而减少图算法行为对负载的不均衡影响,提高分布式图处理的效率。主要研究内容包括:提出基于图算法行为特征的节点负载计算方法,建立以活跃顶点、传入消息数及远程传出消息为量化参数的节点负载计算模型;提出以局部节点负载为基础,根据图计算的行为变化平衡全局负载的两阶段负载动态再划分方法;设计实现节点监控程序以及以顶点为中心的负载迁移机制,在每次迭代最后阶段将监控到的节点负载发送到其它计算节点,由各节点协同地进行超载判定,确定负载并进行迁移。针对多种图算法,在大量数据集上对所提出的动态再划分机制进行测试。测试结果表明,相比未采用动态再划分机制的图计算系统,动态再划分方法能够有效地改善系统运行时的负载不均衡状况,图计算任务的执行效率在最好情况下提升50%,整个系统具有良好的扩展性。对于非稳定型图算法,动态再划分方法具有更好的性能提升效果。