罗晓霞，司丰玮，罗香玉

(西安科技大学 计算机科学与技术学院，西安 710054)(*通信作者电子邮箱676915315@qq.com)

0 引言

图是一种抽象数据结构类型，图的应用几乎涵盖了所有的领域，如大规模集成电路设计[1]、社交网络[2]、煤矿安全、并行计算过程中的任务分配[3-4]等。近年来，图数据的规模迅速增长，据中国互联网络信息中心(China Internet Network Information Center, CNNIC)统计，2016年Facebook在全球有15亿9千万活跃用户，并且其用户以每年几乎10%的速度增长。若将用户看作图的顶点，用户与用户之间的关系看作边，整个社交网络就变成一张巨大的图。如此庞大的社交网络图，传统的单机模式显然已经无法胜任对其的处理，因此，分布式大图处理成为了必然的趋势。如何对大规模图进行划分是影响分布式处理效率最基本也是最重要的问题之一。

大规模图的划分问题已经成为国内外的研究热点[5-7]，许多学者提出了相关的解决思路和方法，但是这些方法一般是通过优化规则迭代式的对大图划分进行调整。这种调整一方面是基于局部信息进行的，对全局的划分效果改善是有限的，另一方面需要多次迭代完成，这样导致时间开销较大，因此，这些方法并未被业界主流的分布式图数据处理系统采用。而现有算法难以对大规模图进行有效划分的一个重要原因是忽略了图结构对其划分效果的影响。例如图1(a)、(b)均包括8个顶点和12条边，但它们显然具有不同的结构特征。在均衡的二划分时，图1(a)的最优划分有0条交叉边，而图1(b)采用何种算法都会有4条交叉边。……