自20世纪90年代开始,以因特网为代表的信息技术的迅猛发展使人类社会大步迈入了网络时代,使得人类在任何地点任何时间都能够互联互通。从城市网络到全球航空网络,从大脑神经网络到各种新陈代谢网络,各种复杂网络已经充斥着人们生活的方方面面,包括经济,政治,科学等。复杂网络的研究能够广泛地应用到生物、计算机等各个学科领域,使人们更好的了解现实世界中的复杂系统。而如今,网络规模十分巨大,如果把大脑中的神经元看作顶点,神经元之间互连的树突看作边,那么整个网络将包含890亿个顶点及100万亿条边。如何对这些大规模图数据进行有效率的挖掘计算,是研究复杂网络的首要任务。并行计算技术是现在最成熟、应用最广、最可行的计算加速技术之一。因此研究复杂网络计算的并行加速技术具有十分重要的意义。而如何在各计算单元间分配任务是并行计算性能好坏的关键。图划分技术就是解决这一问题的有效手段。图划分问题的研究是随着实际应用的需求不断驱动。随着云计算技术的快速发展,不管是公有云还是私有云,不可避免会出现集群的异构性;数据量的快速增长对图划分算法的划分质量,划分效率及可扩展性提出新的要求;以寻找最短路径等为代表的局部挖掘的图计算应用的广泛性,对之前图划分算法都将成为新的挑战,使得之前划分技术难以适用当今复杂多变的集群环境和应用需求。针对以上三个挑战,分别提出了不同的解决方法。本文的主要贡献如下:1、针对异构计算环境下的分布式集群,本文提出了一种异构感知的流式图划分算法(HaSGP)。该方法根据并行异构环境中硬件性能的不同特点,合理的分配任务,使之提升分布式图计算的效率。同时针对流式图划分,设计了一种基于邻边结构的动态缓存数据管理机制,该机制有效的管理划分过程中的缓存数据。相对于现有的基于邻点结构的流算法,划分效率明显提升。2、针对大规模图划分的问题,本文设计了一种基于层次亲和聚类的分布式大图划分算法(DisHAP)。具体创新点为:设计了基于Boruvka算法的层次亲和聚类,将其作为初始划分。以顶点相似度为距离度量,迭代合并距离较近的两顶点,并移去子图中邻点相似度和值最小的顶点以约束规模过大的子图。在没有后续优化的情况下,划分质量也接近于现有的某些大图划分方法;针对大规模子图之间的割边率优化问题,DisHAP使用降维的操作,将初始划分结果线性嵌入为一维顶点序列。通过分片优化割边的方式对顶点序列重排列,将原问题转化为多个复杂度较小的子问题以利于并行计算。3、设计了一种面向多子图查询感知的图划分算法(Muti-QS)。该算法根据查询的历史记录对图数据进行动态的划分,实验表明,Muti-QS能够达到最高76%的查询在本地化执行。而且查询感知划分速度很快,因为它只对少量查询区域进行操作而不是优化大量的顶点。同时也提出了一种具有局部和全局屏障的混合模型—子查询屏障。由于子查询屏障中的局部屏障产生的最小化开销,使局部屏障能够最大化的减少本地化查询的延迟。而子查询屏障中的全局屏障能够很好的执行动态的优化分割。为了进一步降低分区之间的通信量,Muti-QS使用一种分离器和组合器,通过非集合通信进行同步,降低并发网络通信开销的影响。