基于并行約束規劃的最大團識別研究

肖成龍,聶紫陽,王 寧,張重鵬,王珊珊

(遼寧工程技術大學 軟件學院,遼寧 葫蘆島 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的情況下,不同基準圖得到的加速比不同。對于小規?；鶞蕡D,如C250.9、brock400_2,并行算法的加速比受集群規模變化的影響不大。相比于較大規模基準圖,加速比受集群規模變化的影響較大。由此可知,無論對于何等規模的數據,處理過程中不可避免需要進行數據傳輸,都會產生通信時間。對于小規模基準圖,通信時間對算法的加速比影響更大。所以,對于大規模的數據,采用并行處理能夠明顯縮短運行時間,提高求解效率,但是對于較小規模的數據,并不適合進行并行處理。實驗結果表明,本文提出的基于約束規劃的最大團并行求解算法能夠有效提高復雜圖例中的最大團識別效率,具有較好的靈活性。

4 結束語

本文提出一種基于約束規劃的最大團并行求解算法,使用Spark集群有效提高最大團識別效率,尤其是對于大規模的圖計算來說,加速效果更明顯。同時,設計基于時間預測模型的負載均衡控制策略,進一步縮短整體運行時間。針對分割產生的子問題的求解,引入約束規劃方法對子問題進行建模,采用約束規劃求解工具靈活高效地找出最大團。實驗結果表明,本文算法具有較高的求解效率,且相對于傳統最大團求解算法,由于在最大團求解部分使用可對組合優化問題進行靈活求解的約束規劃技術,因此具有更好的通用性,對于其他類型的NP問題,只需根據問題要求建模并調整負載均衡策略,即可應用本文算法對問題進行并行求解。后續將通過改進約束規劃中變量排序啟發式算法、搜索算法和相容性技術等,進一步提高算法求解效率。