基于并行约束规划的最大团识别研究

肖成龙,聂紫阳,王 宁,张重鹏,王珊珊

(辽宁工程技术大学 软件学院,辽宁 葫芦岛 125105)

0 概述

最大团问题(Maximum Clique Problem,MCP)是图论中经典的组合优化问题,也是一类NP完全问题,在数据挖掘、图像处理、计算机视觉、生物学、模式识别、人工智能等领域均具有非常广泛的应用。例如,最大团算法在数据挖掘网格系统上的应用[1],融合社交网络特征的最大团并行算法用于图压缩处理[2],通过最大团算法解决低失真图像视觉特征匹配问题[3],使用最大团算法进行网络重叠社区检测[4],运用最大团算法解决组合竞拍中竞胜标确定问题[5],最大团算法在生物计算上的应用[6]等。因此,最大团问题的研究具有较高的理论价值和现实意义。但是,随着图规模呈指数级增长,传统精确算法和启发式算法存在通用性差、求解效率低等问题。

针对大数据背景下图节点的海量性和分析的复杂性,研究者提出并行化处理的求解思路。例如,使用MapReduce[7-8]和Pregel[9]等面向海量数据和密集型计算的并行处理框架,这些框架具有较好的容错性和可扩展性,同时提供了简单的处理方法和功能强大的编程模型。并行处理计算框架的应用和不断发展促进了各种并行算法的实现。文献[10]提出基于MapReduce的分布式算法实现图分割,并采用分支定界方法枚举分割后产生子图中的团结构,但该研究没有考虑计算节点间的负载均衡,并且会有大量错误、重复的中间值输出。文献[11]提出基于MapReduce框架的最大团并行求解方法,该方法通过采用图着色方法进行图分割,然后使用分支定界方法求解子图中的最大团,但是产生子图数目过多,可能增加分支定界法求解子图的时间复杂度和空间复杂度,同时该文献中没有对大规模图进行测试,无法证实算法对于大规模图例的有效性[12]。考虑到大规模图例计算的复杂性和密集性,本文设计基于Spark框架的最大团并行化求解方法。

1 问题介绍

1.1 最大团问题描述

本文使用的符号及其释义说明如表1所示。给定无向图G=(V,E),其中,V是非空集合,称为顶点集,E是V中元素构成的无序二元组集合,称为边集,无向图中的边均是顶点的无序对,无序对用“( )”表示。如果U⊆V且对任意两个顶点u,v∈U存在(u,v)∈E,则称U是G的完全子图。团(又称集团)是图的顶点集的一个子集,使得其导出子图为完全子图,如果一个团不是任何其他团的子集,则称该团为极大团。一个图中含有顶点数最多的团,称为该图的最大团[13]。

表1 符号说明

1.2 相关定理

根据最大团问题的描述和定义,下文给出问题的相关性质以及证明过程,其中部分定理可参考文献[14]。

定理1设vi∈S并且(vi,vj)∉E,则vj∉S,其中S为最大团。

证明根据团的性质,由反证法可知,若vi属于最大团S,则显然vi与最大团S中所有元素都相连,而vi与vj之间不存在边相连,则vj与vi不会出现在同一个最大团S中。

定理2若V中某顶点vi的度数为n-1,则点vi必然属于最大团S。

证明假设顶点个数为n,度数为n-1的顶点与图中其他顶点均相连,同理,该顶点与该图最大团中所有顶点均相连。根据最大团定义,由反证法可知,若vi不在最大团中,则该最大团不是图中真正的最大团,即只要图G中存在度数为n-1的节点,那么最大团必定包含该节点vi。同理可推,当节点度数越高,它出现在最大团S中的概率越大。

2 基于并行约束规划的最大团识别算法

本文提出的融合并行约束规划的最大团识别算法主要包括三部分:并行图划分处理,约束规划求解策略和基于任务的运行时间预测模型,流程如图1所示。

图1 基于并行约束规划的最大团求解流程

并行图划分处理采用BMT多层图分割算法,并在多层图划分过程中调用运行时间预测模型,实现实时控制产生的子图大小以确保集群负载均衡。Spark集群中每一个计算节点均采用Choco约束规划求解器[15],通过约束规划方法计算得出子图中的最大团,最终得到对应图例的最大团。

2.1 图划分问题

图划分问题是经典的组合优化问题,即将图中的节点集合划分为一系列数量规模相近的子集合,在满足约束条件的同时使目标得到优化。图划分在很多领域都具有广泛的应用,如大规模数字集成电路设计、数据挖掘、并行计算等。

2.1.1 BMC图划分策略

文献[11]提出的BMC算法采用基于颜色的多层分割策略,根据图中顶点度数由大到小的顺序进行图着色处理,每次选择度数大的顶点分割,直至满足限定条件。

第一次分割如下:

G1=v1∪N(G,v1)

G2=v2∪N(G-{v1},v2)

⋮

GK=vK∪N(G-{v1,v2,…,vK-1},vK)

(1)

其中,子图G1由图G中度数最大的顶点v1及其邻居顶点组成,子图G2是由图G中除去顶点v1及其邻边后,图中度数最大的顶点v2及其邻居顶点组成,以此类推,得出若干个子图,完成第一次分割。

第二次分割如下:

G1,1={v1,w1}∪N(G1-{v1},w1)

G2,1={v2,w2}∪N(G2-{v2},w2)

⋮

GK,1={vK,wK}∪N(GK-{vK},wK)

(2)

通过第一次分割策略实现了将复杂图G分割为顶点数目不同、图密度不等的K个子图。在K个子图中,有的子图顶点较多或者图密度较大,则求解时间较长需要继续分割,有的子图顶点较少或者图密度较小,则求解时间较短可以不再分割。因此,将需要继续分割的子图进行第二次分割,直至满足限定条件,完成图分割过程。

2.1.2 BMT图划分策略

本文结合BMC图划分策略中多层划分方法,提出基于任务运行时间预测模型的BMT并行图划分策略。算法主要考虑到两个方面:一是实现有效的图分割,将复杂图分割为若干个更小且最大团关系相互独立的子图,使得Spark集群中的计算节点可以独立计算,降低通信开销;二是保证集群中各个计算节点的负载均衡,通过预测时间模型估算求解时间,决定图分割的深度。

依据最大团特性,定理1在最大团中任意两点之间均有边,若某两个顶点之间没有边相连,则这两个顶点不会出现在同一个最大团中。定理2在最大团中若某一顶点的度数较高,则它出现在最大团中的几率就更大。因此,本文设计了基于任务运行时间负载均衡的BMT图划分策略。相比于其他图划分方法,本文提出的BMT图划分方法产生的子图数目更少,子图之间最大团关系保持独立,同时运行时间预测模型严格控制子图范围的大小,实现集群负载均衡。

第一次分割如下:

G1=v1∪N(G,v1)

G2=v2∪N(G,v2)

⋮

GK=vK∪N(G,vK)

(3)

其中,v1,v2,…,vK是图中相互之间没有边连接的若干顶点。根据定理1可知,v1,v2,…,vK顶点不会出现在同一个最大团中。

首先根据顶点度数从大到小排列,选择度数最大的顶点v1,然后在剩余顶点中,选择与v1顶点没有边相连且度数最大的顶点v2,依次类推选出互相之间没有边连接的顶点v3,v4,…,vK,直至完成第一次分割,实现将图划分为最大团关系独立的若干子图。

第二次分割过程是在子图G1,G2,…,GK的基础上进行迭代分割。同时,调用任务运行时间预测模型,估算出从每个子图中求解最大团所需的运行时间,对于运行时间大于平均预测时间的子图继续进行分割,直至满足计算节点之间的负载均衡。

本文BMT图划分方法的理论准确性证明过程如下:

假设∀v1,v2,…,vK∈G,且(vi,vj)∉E,i,j∈(1,K)。若第一次分割后得到K个子图,则K个子图之间最大团关系相互独立。

证明在已知第一次分割后,得到分别包含v1,v2,…,vK的K个子图G1,G2,…,GK,且v1,v2,…,vK之间没有边相连。以子图G1为例,G1中最大团S必包含v1顶点。因为子图G1由顶点v1及其邻居顶点组成,若邻居顶点之间能够形成团S′,由于顶点v1与团S′中每一个顶点均有边相连,则根据最大团定义可知,v1可加入团S′中,得到子图G1中的最大团S。同理可推,对于子图G1,G2,…,GK分别会得到包含v1,v2,…,vK顶点的各自子图中的最大团。若最大团S中包含顶点v1,则由于v1,v2,…,vK之间没有边相连,不会再包含v2,v3,…,vK中任意一个顶点,因此K个子图之间最大团关系相互独立,即假设成立。

BMT图划分过程如图2所示。由图2(a)经过一次分割得到最大团关系相互独立的子图,如图2(b)所示。划分过程如下:首先,在图2(a)中按照顶点度数由大到小排列得到顶点集合{5,1,9,4,6,7,8,2,3},由此可知,图2(a)中度数最大的顶点为顶点5,选择顶点5及其邻居顶点集合为{1,3,4,6,7,8,9};然后,根据最大图独立关系,选择与顶点5没有边相连且度数最大的顶点,在本图中满足条件的为顶点2,选择顶点2及其邻居顶点集合{6,8,9},此时实现将一个图2(a)分为最大团关系独立的两个子图,同时无孤立顶点,根据最大团定理1可知,图2(a)中顶点5与顶点2不会存在于同一个最大团中,基于此实现第一次分割;最后,调用预测时间模型计算子图并使用约束规划求解需要的时间,从而决定是否继续进行图分割。假定图2(b)中包含顶点2的子图,顶点数目少且所需计算时间短,不需要继续分割,而包含顶点5的子图需要进行二次分割。第二次分割是在第一次分割得到的子图基础上进行,重复式(3)划分过程。对包含顶点5的子图进行再分割,可得到图2(c)中两个子图。通过以上图划分方法实现将多顶点数、高密度的复杂图例分割为顶点数少、密度低的子图,降低约束规划计算的复杂度。

图2 BMT图划分过程

2.2 约束规划

约束规划是人工智能领域的一个重要分支,可解决现实生活中的很多问题,包括计算机视觉、通信、调度中的资源分配、电子商务、机器学习等。约束规划是由一组变量集合和一组约束集合组成,公式描述简单、易于理解,同时可根据实际问题,求解得出该问题的一个解、所有解或最优解[16]。

约束规划求解方法是由使用者声明一组约束条件对问题进行建模,Choco约束规划求解器主要通过调整约束过滤算法解决问题,其包括丰富的原语、逻辑和条件约束及全局约束,同时将问题描述和问题求解分离,具有更好的灵活性和通用性[17]。

约束条件:xi+xj≤1,∀(i,j)∉E

xi∈(0,1),i={1,2,…,n}

(4)

在目标函数中,n值代表图中顶点数目,xi代表图中的每一个顶点;xi+xj≤1,∀e(xi,xj)∉E为约束条件,即图中任意两点之间若无边,则任意两点之和不大于1;xi∈(0,1),i={1,2,…,n}表示图中共n个顶点,每一个顶点的取值为0或1。

2.3 负载均衡控制策略

负载均衡是协调集群中各个计算节点运行时间,通过控制每个计算节点得到的子图大小,使得各个计算节点运行时间接近,将运行时间之差控制在可接受范围内。本文中设置的运行时间差为10%,即从集群第一个计算节点运行结束到整个程序运行结束的时间差,不超过程序运行总时间的10%(算法中的运行时间差可以根据实际问题的具体情况更改设置),即(时间最大值-时间最小值)/时间最大值≤10%。严格控制运行时间差,就能最大化提高程序整体运行效率,实现集群负载均衡。

在BMT图划分过程中,使用负载均衡控制策略。在程序运行过程中,通过调用预测运行时间模型计算每个子图求解最大团所需运行的时间。假设集群中有10台机器,计算出第一次分割后的子图个数,如果子图个数小于10,则进行第二次分割,直到子图个数大于或等于集群机器数目。在每一次分割后,预估子图运行时间,同时计算子图合理分配给集群平台后每个节点所需的运行时间,并计算求解时间差,若大于阈值,则将预测时间大于均值的子图继续进行分割,其他子图则等待分配给计算节点。在每一次分割后,均调用预测运行时间模型进行实时调整,以确保分割操作后集群系统负载均衡。

估算运行时间模型是在同一实验环境中测试不同顶点数、图密度的图例使用约束规划求解得到最大团所需要的运行时间,记录相关实验数据并进行非线性回归,计算得出预测时间模型,同时确定模型中各变量系数。

由实验数据计算在同一顶点数下运行时间与图密度变量之间的关系。以顶点数100为例,依次测试图密度从0.1到0.9的图例数据,记录求解时间,实验结果如图3所示。

需求情况：农业方面，当前为农业用肥淡季，尿素需求冷清。工业方面，上周复合肥企业和胶合板企业开工率保持低位，经销商对当前尿素高价较为抵触，需求较前期有所缩减。出口方面，由于国际尿素供给偏紧，价格持续上涨，但国内经销商出口报价目前已经低于中东地区，但仍高于其他主流货源地，出口量少。

图3 约束规划求解最大团问题的运行时间

由图3可知,对于给定顶点数目的图,其密度与运行时间之间成指数关系。因此,预测时间模型假定为指数函数,形如T(G)=f(|G|,ρ(G))|G| g(ρ(G)),其中,f(|G|,ρ(G))和g(ρ(G))是关于顶点数目和图密度的多项式函数,g(ρ(G))是关于图密度的二次函数,定义为ρ(G)2+bρ(G)+c,同时对函数f(|G|,ρ(G))进行泰勒展开[18],得到预测时间模型如下:

(5)

其中,k用来控制模型的自由度,即泰勒展开级数,ai,j、b和c为未知变量系数,由实验数据验证得出。训练运行时间模型的图例数据由程序随机生成,并测试不同顶点数目及不同密度的图使用约束规划算法求解最大团所需运行时间。同时,将得到的训练数据信息通过数学优化分析综合工具软件1stOpt[19]进行非线性回归计算,得出模型中参数的值。

2.4 算法描述与分析

上文已分别介绍BMT图划分策略、约束规划求解最大团方法、任务运行时间预测模型等。估算运行时间模型决定分割的次数和深度,各计算节点通过约束规划求解提高最大团识别准确度,任务运行时间预测模型严格控制集群负载均衡。融合并行约束规划的最大团识别算法流程如图4所示。

图4 最大团识别算法流程

本文算法主要包括BMT图划分算法、约束规划最大团求解算法和时间预测算法。BMT图划分算法将复杂图分割为简单图,方便约束规划求解。首先,读取数据集,得到图信息并以邻接表Vertex[]的形式存放。然后,对图数据进行分割,划分后的子图数据存放到一个全局变量list中。在分割过程中,调用时间模型控制负载均衡,根据式(3)的分割方法进行多深度图分割。Choco约束规划求解最大团主要包括问题定义、变量取值范围描述和约束条件限定。算法伪代码具体如下:

/*图划分函数*/

1.funcition BMCpartiton(G)

2.GrpahList= {}

3.n=6;/*机器数目*/

4.LOAD_BALANCE(GraphList,n)

5.while (Tmax-Tmin)/Tmax>=BOUND do

6.maxList={s.t.RunningTime(G)>AvgTime}

7.minList={s.t.RunningTimt(G)

8.GraphList=GraphList-{GraphList}

9.BMCpartiton(maxList[i]);

10.GraphList=GraphList∪partitionList;

11.GraphList=GraphList∪minList

12.LOAD_BALANCE(GraphList,n)

13.end while

/*约束规划函数*/

14.function ChocoBMC(G)

15.Model model;

16.IntVar[n] v,s.t.vi∈(0,1)

17.IntVar z=1

18.for i in range(0,n) do

19.model.arithm(vi+vj<=z)

20.IntVar cost=model.intVar("cost",0,n,true);

21.model.sum(v,"=",cost).post();

22.model.setObjective(Model.MAXIMIZE,cost);

/*负载均衡函数*/

23.function LOAD_BALANCE(list,n)

24.timeList={};

25.sum=0;

26.for i in range(0,n) do

27.timeList=timeLis∪{RUNNING_TIME[list[i]]}

28.sum=sum+RUNNING_TIME[list[i]]

29.t[]=timeList

30.for in range(0,n) do

31.temp=0

32.k=t[0]

33.for j in range(0,n) do

34.if t[j]<=k then temp=j

35.t[temp]=t[temp]∪timeList[i]

36.max=min=t[0]

37.for i in range(0,n) do

38.if max

39.if min>t[i] then min=t[i]

40.result=max∪min∪sum/n

41.return

3 实验结果与对比分析

本文实验的环境为青云公有云计算平台[20]。单机环境是选择一台处理器为4核、运行内存16 GB的主机。集群环境是选择SparkMR集群,Spark版本为1.6.0,配置为4核16 GB内存,包含1个主节点、6个从节点。

本文实验数据来源于国际通用的DIMACS基准图例库[21]。DIMACS基准图为最大团算法的测试提供了统一标准,该组图例是进行最大团研究的标准图例,包括顶点数从125到1 500的不同密度图数据。

3.1 任务运行时间预测模型的准确性评价

在拟合实验中,采用1stOpt数学优化分析综合工具软件,设置拟合公式和参数。输入数据包括不同的图顶点数、图密度以及由实际应用得出的图例约束规划求解运行时间,通过非线性回归计算,输出拟合公式中的参数值和拟合效果图,如图5所示,其中相关系数R= 0.988 3。

图5 任务运行时间预测值与实测值的拟合效果

3.2 BMT与BMC算法的图划分结果对比与分析

在图划分对比实验中,比较本文BMT图划分算法与文献[11]的BMC图划分算法,在多层图分割中产生的子图数目和最大子图顶点数目变化情况。实验数据为DIMACS基准图中的C125.9、C250.9和C500.9,其中,depth代表图分割次数,n代表子图数目,v代表最大子图顶点数目,实验结果如表2所示。

表2 图划分算法实验结果比较

从实验结果可知,相比于BMC图划分算法,由于图分割策略不同,在第一次分割后,本文BMT图划分算法产生的子图数目远小于BMC算法产生的子图数目,最大子图顶点数目大于BMC算法产生的最大子图顶点数目。其原因在于图数据中所选图例密度均为0.9,属于高密度图,而随着图密度的增大,图中没有边相连的顶点数目减少,因此,在第一次分割后,两种算法子图数目相差较悬殊。但随着图分割深度的增加,子图数目差距逐步减少。而且在大多数情况下,经过3次分割后,本文算法得到的子图数目和最大子图顶点数目均小于BMC图划分方法。由此可知,本文算法能够在确保结果准确的前提下有效减少子图数目,更快地得出最大团关系相互独立的子图,降低搜索空间,提高求解效率。

3.3 BMT与BMC算法的并行求解效率对比与分析

在并行算法效率对比实验中,图例数据包括c1000.9、c2000.9、phat1500-2、C250.9和brock400_2。在不同集群规模下,比较两种算法在加速比和求解效率方面的差异。

将本文中的加速比定义为同一个任务在单处理器系统和并行处理器系统中运行消耗的时间比率,用来衡量并行系统或程序并行化的性能和效果。计算公式如下:

(6)

其中,SP是加速比,T1是单处理器下的运行时间,TP是在有P个处理器下的运行时间。

不同集群规模下运行时间比较如表3所示。其中,“—”表示单个处理器,因此无加速比。从表3中数据可以看出,本文BMT算法在求解效率和并行加速比方面均明显优于BMC图划分算法。由于多层分割后,本文算法得到的子图数目、最大子图顶点数目均少于BMC算法,因此在求解效率上优于BMC算法。

表3 不同集群规模下运行时间比较

同时,从表3数据可知,在处理器数量为1、3、6的情况下,不同基准图得到的加速比不同。对于小规模基准图,如C250.9、brock400_2,并行算法的加速比受集群规模变化的影响不大。相比于较大规模基准图,加速比受集群规模变化的影响较大。由此可知,无论对于何等规模的数据,处理过程中不可避免需要进行数据传输,都会产生通信时间。对于小规模基准图,通信时间对算法的加速比影响更大。所以,对于大规模的数据,采用并行处理能够明显缩短运行时间,提高求解效率,但是对于较小规模的数据,并不适合进行并行处理。实验结果表明,本文提出的基于约束规划的最大团并行求解算法能够有效提高复杂图例中的最大团识别效率,具有较好的灵活性。

4 结束语

本文提出一种基于约束规划的最大团并行求解算法,使用Spark集群有效提高最大团识别效率,尤其是对于大规模的图计算来说,加速效果更明显。同时,设计基于时间预测模型的负载均衡控制策略,进一步缩短整体运行时间。针对分割产生的子问题的求解,引入约束规划方法对子问题进行建模,采用约束规划求解工具灵活高效地找出最大团。实验结果表明,本文算法具有较高的求解效率,且相对于传统最大团求解算法,由于在最大团求解部分使用可对组合优化问题进行灵活求解的约束规划技术,因此具有更好的通用性,对于其他类型的NP问题,只需根据问题要求建模并调整负载均衡策略,即可应用本文算法对问题进行并行求解。后续将通过改进约束规划中变量排序启发式算法、搜索算法和相容性技术等,进一步提高算法求解效率。