近年来,随着互联网蓬勃的发展,网络的规模不断扩大,因而形成许多规模庞大的网络图。对这些图的研究已经形成一种趋势。但是由于图的规模非常庞大,单机已经无法满足计算需求,从而我们转向分布式方式来处理大规模图计算问题。在进行分布式图计算之前,我们首先需要将图划分为多个子图。为了保证系统的均衡,我们需要保证各个分区的规模相对均衡,同时为了降低各个节点之间的通信开销,我们需要保证各个分区之间的割边尽量少。此外,我们面临的不仅仅是大规模图的问题,在许多情况下图的结构随着时间的推移而不断发生变化。我们需要实时的对图进行划分,这也就意味着我们不能够在图的结构一发生变化就对整个图重新进行划分。因为这是非常耗时的,当图的规模变的非常巨大的时候,图划分任务将无法继续执行。因此研究分布式增量图划分算法对于当今大规模增量图网络划分有非常重要的意义。本文对分布式增量图划分算法进行了详细的分析和研究,主要包括以下几个方面:针对增量图的特点,当图的结构发生变化时,本文并没有对整张图进行重新划分。而只是对受影响的节点进行移动和调整。这样将大大减少图划分的时间消耗。本文针对图结构的不同变化进行了不同的调整,确保了图划分结果的负载均衡,尽可能的减少割边。在上述策略的基础上,本文采用了禁忌搜索算法来尽量避免局部最优解。上述策略是一种基于贪婪算法的启发式方法,极有可能陷入局部最优解的陷阱。我们采用了禁忌搜索算法,通过多次迭代和禁忌规则限制使节点移动过程尽可能的跳出局部最优解陷阱。最后,本文在上述模型的基础上设计了一个分布式增量图划分系统,并通过实验验证了系统的有效性和可行性。