自20世纪80年代开始,复杂系统的研究逐渐兴起,它被认为是解决各个领域研究面临的困难的一个重要突破点。而复杂网络是研究复杂系统的一个重要工具,如物流运输、道路规划、社交网络、生物研究等问题在研究的过程中,都可以抽象成由边和顶点组成的复杂网络,借助于复杂网络的相关技术对其进行研究。但系统中基本单元常常达到成千上万甚至是数以亿计,这就使得复杂网络的研究不得不借助于高效的计算工具来解决实时的、规模足够大的计算问题。分布式计算技术是现在最成熟、应用最广、最可行的计算加速技术之一。因此研究复杂网络的分布式计算技术具有十分重要的意义。在做分布式计算之前,需要将原始复杂网络划分成若干个子网络,保证各个子网络规模相对均衡和网络间的通信开销最小化是分布式计算性能好坏的关键。图划分技术就是解决这一问题的有效手段。图划分算法按照划分方式的不同,可以分为点划分算法和边划分算法。数据量的快速增长对图划分算法的划分质量和划分效率提出了新的要求。本文主要工作体现在以下方面:(1)针对当前点划分算法划分质量较低的问题,本文提出了基于滑动窗口的流式图划分模型(Graph Win),该模型通过引入滑动窗口机制,根据当前划分质量和划分时间,动态调整每次划分时参考的信息量(顶点度信息和邻接信息),以达到允许损失一定划分效率的前提下尽可能提高划分质量的目的。此外,Graph Win模型的评分函数在传统流式图划分算法的基础上做了改进,它包括自适应均衡评分函数、度评分函数、聚类评分函数,综合考虑了分区均衡性、顶点度、分区聚类系数在图划分中起到的作用。实验结果表明,相较于其他算法,Graph Win模型在一定程度上能够有效降低平均复制度。(2)针对当前边划分算法划分效率较低的问题,本文提出了基于GPU加速的图划分模型(Graph GPU),Graph GPU模型分为初始划分阶段和优化划分阶段:在初始阶段,使用Boruvka算法对原始图数据做初始聚类,将亲和度较大的顶点尽可能被划分到同一分区;在优化划分阶段,使用桶交换算法对初始划分结果做进一步的优化。因为Boruvka算法和桶交换算法都具有并行性,所以Graph GPU模型建立在CPU+GPU异构并行计算框架基础之上。实验结果表明,Graph GPU模型相较于现有成熟的图划分算法在提高划分效率的同时,也能够降低割边率。