随着信息时代的到来,人们在现实生活中积累了大量的图结构数据,分布式图计算框架通过将大规模图数据划分至多台机器上进行并行处理以获得高效的计算效率。图数据的划分作为分布式计算的基础,划分结果的优劣严重影响着分布式图计算的性能,因此,面向分布式图计算的图划分算法成为学者们研究的热点问题。已有的图划分算法根据划分方式的不同可被分为离线图划分算法和流式图划分算法,其中离线图划分算法划分精度较高,但需要依赖完整的图数据信息进行划分操作,而流式图划分算法仅依赖部分图数据信息进行划分,但划分精度较低。本文针对以上问题对图划分算法进行了深入研究并设计新的图划分算法,使得在基于局部图数据信息的情况下可以得到较高的图划分精度。本文研究主要包括以下两个方面:(1)提出两阶段局部图划分算法。针对已有图划分算法的缺点,本文设计了一种新的图划分思想:局部图划分。该划分思想可基于局部图数据信息进行划分操作,同时在划分过程中至多只需保存单个分区的数据信息,有效的降低了对机器性能的要求,更适合大规模图数据的划分问题。基于该划分思想,本文提出了一种两阶段局部图划分算法。该算法引入模块度的概念以量化每个分区的结构紧密程度,并根据结构的变化将每个分区的划分过程分为两个阶段,在两个阶段中分别采用不同的划分策略进行图划分操作。通过大量的实验结果可以验证该算法在仅基于局部图数据信息的情况下可以取得较好的图划分精度。(2)提出自适应局部图划分算法。针对局部图划分速度较慢的缺陷,本文对局部图划分思想进行改进,由每次划分单个节点改进为每次划分多个节点,有效的提高了划分速度。同时对目前的图划分策略进行总结,并将两种主流的图划分策略基于改进后的局部图划分思想进行形式化表示,通过自适应的方法进行结合。通过实验对比分析,相较于两阶段局部图划分算法,自适应局部图划分算法可以大幅的提高图划分效率;同时在所有对比实验中,自适应局部图划分算法的划分精度要高于目前主流的图划分算法,具有较好的划分效果。