随着互联网信息规模的急速膨胀,对大规模数据进行快速处理、学习和挖掘的需求也变得越来越多。在许多真实应用比如社交网络中,具有图结构的数据的规模也在不断变大。因此,基于图计算的大规模分布式(并行)机器学习框架受到了越来越多的关注。一方面,许多数据间的依赖关系可以自然地用图来进行建模,而且许多数据本身就具有图或网络的结构,例如社交网络数据;另一方面,许多机器学习和数据挖掘的算法也可以用图或网络来建模。在基于图计算的大规模机器学习框架中,数据以图的结构表示。为了在这种图结构的数据上运行分布式(并行)机器学习或数据挖掘算法,首先必须将这些结构化的数据分配到分布式环境中的每一台计算机上。数据的分配会影响到算法运行期间,集群中的计算机直接的通信量和每台计算机的负载均衡,因此会在很大程度上影响分布式算法的运行效率。图结构的数据分配因而在基于图计算的大规模机器学习框架中扮演了重要的角色。理想的数据分配方式,将会在大致平衡每台计算机之间的负载的同时,最小化集群中计算机之间的通信量。这一类具有图结构的数据的分配问题统称为图的分割问题。为了快速求解图分割问题,往往使用随机化的图分割算法。许多真实数据的图的节点度数分布往往服从幂律分布,这样的分布增加了数据分配的难度。近年来,研究者们提出了一些随机化算法来求解图分割问题。然而,现存的随机化图分割算法对于服从幂律分布的图难以得到令人满意的效果。此外,极少有随机化的图分割算法利用了图中每个节点的度数信息。在本课题的研究将会提出新的图分割算法,包括随机化图分割算法和贪心算法。本课题还将对随机化图分割算法的通信量和负载均衡进行理论分析。最后,将通过实验展示算法的优越性。