随着互联网的日益兴盛,互联网上的数据规模越来越大,而且数据变得也越来越复杂,怎样在海量的数据中获取有用的信息已经成为一个十分紧迫的问题。为了应对海量的数据处理分析,分布式计算平台应运而生。将数据放到分布式平台上存储,这样可以解决单台机器存储能力有限的问题,同时,分布式平台另一点好处是移动计算,数据被划分后放到多台机器上存储,利用这台机器的计算能力去处理本机存储的数据,集群并行处理数据,从而加速海量数据的处理。图数据计算是大数据处理的核心问题之一,平衡图划分是图计算中的一个难点。平衡图划分在社交网络、生物网络、道路网络等方面都有着十分广泛的应用。在过去的研究中,存在大量的图划分的算法,其中大多数的算法需要对全图进行遍历,分布式系统会将数据划分后放到多台机器上存储,遍历全图一定会加大数据通讯的代价,而遍历全图数据对当前超大规模的数据来说更是不切实际。2013年Rahimian发表的图划分算法是一个以单个顶点为处理单元,在计算中只需要访问该顶点的直接邻居顶点和少数的随机顶点,不需要全图访问,集群中各个机器之间的通信代价无疑是大大的降低了,从而提高算法的处理能力。性能好的图划分算法结合使用性更高的分布式平台,这无疑是大大的提升了算法的实用性。新的编程框架实现算法流程,不能够使用原有算法的思路,要根据新的计算框架重新设计,这里面会涉及到内存问题,算法流程设计等等。根据图的属性加入了关系发现能力,使得算法得到的划分结果中关系发现能力上升。在保证图划分算法能够得到一个很好的割边的前提下,本文提出了基于MapReduce编程模型实现的并行图划分算法,并且在划分中加入了子图关系能力的计算。本文的最后,利用不同的数据集和并行算法性的性能评测手段,对该并行算法的加速比、可扩展性、规模增长性进行评估,验证了算法的有效性和准确性。