近年来,由于社交网络等发展,图数据规模变的越来越大。在如此大图上进行的计算超出了传统集中式计算系统的能力,因此应用程序部署已经从少量的HPC服务器或超级计算机转移到了云环境下的商业集群。为了支持复杂的图处理计算(如,Pagerank,最短路径等),需要将图数据进行分布式并行处理,以BSP模型为基础的图计算系统变应运而生。而图数据划分是基于BSP编程模型的大规模图处理系统需要解决的重要问题之一。特别在云环境下,由于数据规模过大,更需要将图数据划分为多个分区,交由集群中的计算节点并行处理。对于某个特定的社交网络数据,用户数据往往呈阶段性递增的方式产生,而图计算系统在每次计算都进行一次在线的图划分并不是一种高效的方式,因为在每次计算的过程中,计算系统都要重新的加载图数据并进行数据划分和分发,消耗了不必要的时间,并且在线的图划分难以达到很好的划分效果,即保证分区的负载均衡和分区间的交互边数尽可能少。为此,在项目组基于BSP模型开发了可进行大图计算的图处理系统BC-BSP的基础上,本文主要基于LDG启发式规则设计和实现了适用于基于BSP模型系统的离线图划分算法。本文的主要贡献如下:(1)本文引入了顶点收益模型,将LDG启发式规则应用在数据划分上,保证了各个分区的负载均衡性,减少了分区间的交互边,保留了图的局部拓扑性。(2)分析并发现了 LDG启发式规则在顶点随机输入时性能波动较大的缺陷,提出了基于影响力的两阶段划分流程,即先划分影响力较大的顶点,然后再划分影响力较小的顶点,这样可以在划分过程中维护图的拓扑结构。(3)应用LDG启发式规则进行图划分需要维护一个全局的顶点映射信息,因此难以在大图上进行扩展,本文为了提高LDG处理顶点的量级,设计了两种方案,一种是基于分布式内存的分布式LDG划分算法,将全局的顶点信息分布映射到不同的计算节点上,来解决集中式映射表内存占用的瓶颈。另一种是先将原图进行浓缩,然后对浓缩图进行处理。因此,本文提出了以基于高介数边删除的子图浓缩算法,该算法能够使得浓缩图极大地维护图的拓扑结构。基于浓缩图,本文提供了两种划分策略,一种是基于顶点迁移的划分算法,另一种是利用基于分布式内存的策略划分浓缩图。对于基于分布式内存策略划分浓缩图的方案,能够极大的扩展图顶点划分的量级。本文将提出的数据划分算法和一次划分多次使用的思想应用于BC-BSP系统,通过实验证明,其完成了 BC-BSP系统中图划分模块的功能,具有良好的可扩展性和稳定性。