在数学上,图分割(Graph Partition)是指将一个图分割为若干互不相交的子图,而在实际应用上,图分割是分布式图计算系统中的一个重要组成部分,其旨在平衡每个子系统的工作量和缩短总的工作完成时间。在许多图分割策略中,边分割(Edge Partition)策略因其在幂律图(Power-law graph)中表现出比传统顶点分割(Vertex Partition)更好的性能,而被众多的分布式图计算系统以设置为默认分割策略采用。平衡边分割将图的边集分割为若干互不相交的边子集,使得各个边子集的大小尽量相等的同时,让重复的顶点尽量少。在分布式图计算系统中,一个更平衡,且重复顶点个数更少的边分割,意味着更平衡的工作分配和更少的通信需求,因此对于一个大型网络而言,寻找平衡且重复顶点少的边分割是非常有现实意义,也成为了并行计算,分布式系统等领域的一个热门问题。与以往研究如何设计一个新的边分割策略不同,本文从一个全新的角度来研究边分割问题,即采用局部搜索(Local Search)的策略来改进已有的边分割策略并提升边分割的质量。为此,本文设计了两个新颖且具有针对性的数据结构,即可调整边(adjustable edges)和块(blocks)。基于这两种数据结构,本文首先从理论上分析了边分割的近似率(approximation ratio)并很大程度上改进了现有的近似率。接着,本文为边分割的局部搜索开发了两个启发式算法,一个采用贪心策略,而另一个利用最大流模型实现。本文针对提出的两个局部搜索算法与已知的前沿边分割算法进行了实验对比,实验采用从线上数据库中得到的大量图数据,其中同时包括真实网络,也包括人造网络。本文同时将两个局部搜索算法应用在了分布式图计算系统GraphX中,通过测量不同图分析任务所需要的运行时间,包括PageRank与三角形计数两个分析任务,来对我们的算法性能做出比较。结果显示,我们的局部搜索算法能够很显著地提升边分割的质量。