顧軍華，霍士杰，武君艷，尹 君，張素琪

(1.河北工業(yè)大學 人工智能與數據科學學院，天津 300401； 2.天津商業(yè)大學 信息工程學院，天津 300134)(*通信作者電子郵箱zhangsuqie@163.com)

0 引言

最大團問題(Maximum Clique Problem, MCP)是經典的組合優(yōu)化問題，屬于NP(Non-deterministic Polynomial)完全問題[1]。很多重要的NP問題如無序樹同構問題、子圖同構問題等都可以轉化為最大團問題，在實踐中也有廣泛的應用，如圖像處理[2]、生物計算[3]、信號傳輸[4]、社會網絡分析[5]、故障診斷[6]等，對最大團問題的研究具有較高的理論價值和現實意義。

在大數據時代下，實際圖中節(jié)點的海量性和分析的復雜性，對最大團問題的研究在速度和精度上都提出了更高的要求，而目前有關求解最大團的相關算法比如回溯法[7]、分支限界法[8]、蟻群算法[9]、順序貪婪算法[10]和遺傳算法[11]等，都無法直接用于大型實例的求解。因此，將搜索空間進行劃分，并行獨立運算求解子空間的最大團結構成為一個可行的方案。

圖劃分也是個NP問題，在很多研究領域都有廣泛的應用。基于啟發(fā)式規(guī)則的KL(Kernighan-Lin) 算法[12]將圖隨機化成兩等份，并逐步改善以減少割邊。FM(Fiduccia-Mattheyses) 算法[13]對KL 算法進行了改進，采用單點移動，并引入了桶列表數據結構，減少了時間復雜度。后來Karypis等[14]提出基于heavy-edge heuristic的多層圖劃分，通過粗糙化將大圖歸約進行隨機劃分，通過反粗糙化以及優(yōu)化技術還原劃分。上述圖劃分算法嘗試將圖中的節(jié)點集劃分成一定數量的規(guī)模相近的子集，以最大限度地減少割邊。這些方法提高了分圖的收斂速度，但是會破壞圖信息的完整性。隨著圖規(guī)模的大幅增加，求解最大團問題時不僅需要較快的收斂速度，在圖劃分階段還不應該破壞團結構，因此上述劃分圖的策略并不適合于大規(guī)模圖的最大團問題求解。

針對上述問題，Wu等[15]提出一種單層圖劃分方法(Single Graph Partitioning method, SGP)求出圖中所有點的導出子圖，并且利用MapReduce架構實現了SGP，針對每一個點的導出子圖，采用分支定界算法枚舉各個子圖中的最大團，但是該算法沒有考慮負載均衡，同時會產生重復的、不準確的中間輸出數據，需要額外的處理過程刪除重復數據、甄別正確結果。Xiang 等[16]提出基于MapReduce并行求解最大團的算法，該算法采用著色分圖，使用分支定界算法并行獨立求解各個子圖的最大團；但是應用該算法求得的子圖數量過多、規(guī)模較大，求解各個子圖最大團的時間復雜度和空間復雜度高，并且該文并未給出大規(guī)模圖的劃分結果。Svendsen等[17]提出了基于密鑰的并行求解最大團的算法，該算法是對Wu 等[15]提出方法的改進，主要對分支定界算法進行改善，采用并行枚舉各個子圖的最大團，有效地解決了負載均衡問題；但是該算法求解的子圖規(guī)模較大，并且分支定界算法枚舉最大團的效率較低。Mukherjee等[18]提出了基于MapReduce并行求解二分最大團的算法，該算法將大規(guī)模圖例轉化為小規(guī)模圖例，通過對搜索空間的剪枝操作，降低了子圖搜索的冗余。該算法通過對所有節(jié)點度排序，進行合理的任務分配，從而平衡了集群的負載，最后該算法使用枚舉的方法求得所有的二分最大團。

盡管上述算法使得在大規(guī)模圖例上求解最大團成為了可能，但是，MapReduce編程模型需要頻繁地進行I/O操作，無法充分地利用內存，而且任務的調度和啟動的開銷較大，因此MapReduce編程模型并不適合做迭代式的算法。而Spark平臺是一種基于內存的編程框架，具有容錯性高、執(zhí)行速度快的優(yōu)點，Spark的GraphX圖計算框架有著豐富的API，在對大規(guī)模圖例的計算時，具有速度快、操作簡單的優(yōu)點，因此本文提出求解最大團問題的并行多層圖劃分方法(Parallel Multi-layer Graph Partitioning method for Solving Maximum Clique, PMGP_SMC)。首先，本文提出了多層圖劃分(Multi-layer Graph Partitioning, MGP)方法，在文獻[15]、文獻[17]所采用的SGP的基礎上，對圖中的節(jié)點按度排序，在保持圖中原有團結構不變的情況下大幅度減少子圖規(guī)模，并對規(guī)模較大的子圖進行多層圖劃分，進一步縮小子圖規(guī)模，為了對大規(guī)模圖例進行圖劃分，本文應用Spark的GraphX圖計算框架實現MGP形成并行的多層圖劃分(Parallel MGP, PMGP)方法。然后，考慮到對圖進行最大團問題的求解在速度和精度方面的要求，本文選取了基于懲罰值的局部搜索算法(Local Search algorithm Based on Penalty value, PBLS)求解最大團問題，由于PMGP可以將大規(guī)模圖例分圖產生很多小規(guī)模子圖，因此本文根據子圖的規(guī)模優(yōu)化了PBLS的迭代次數，提出基于速度優(yōu)化的PBLS(PBLS based on Speed optimization, SPBLS)，對劃分后的各個子圖，使用SPBLS獨立求解各個子圖的最大團。最后，將PMGP和SPBLS相結合，形成求解最大團問題的并行多層圖劃分方法(PMGP_SMC)。為了驗證算法的有效性，本文應用Spark的GraphX圖計算框架實現SGP形成并行的SGP(Parallel SGP, PSGP)，并且將PSGP和PBLS相結合形成求解最大團問題的PSGP(PSGP for Solving Maximum Clique, PSGP_SMC)。極大團枚舉(Maximal Clique Enumeration, MCE)是一種暴力求解最大團問題的方法，該方法雖然可以精準求出子圖的最大團，但效率低下。為了比較求解最大團問題的準確性，本文將PMGP與極大團枚舉方法相結合形成基于MCE求解最大團問題的并行多層圖劃分方法(Parallel Multi-layer Graph Partitioning for solving maximum clique based on MCE, PMGP_MCE)。實驗結果表明，與PSGP_SMC相比，PMGP_SMC可以更快地求解各個子圖的最大團，與PMGP_MCE相比，PMGP_SMC可以高效精確地求解各個子圖的最大團。

1 多層圖劃分方法

1.1 最大團基本定義

定義1 完全子圖。稱U=(V′,E′)是無向圖G=(V,E)的完全子圖，當且僅當對于任意給定的無向圖G=(V,E)，若V′ ?V，E′ ?E，且對于?u,v∈V′，有(u,v) ∈E′。

定義2 團。稱無向圖G的完全子圖U是G的一個團，當且僅當完全子圖U不包含在圖G的更大完全子圖中。

定義3 最大團。稱無向圖G的最大團C為圖中包含頂點數最多的團，最大團問題即求解圖G=(U,V)的最大團C。

1.2 MGP流程

Wu等[15]提出了單層圖劃分方法(SGP)，該方法根據圖中各個節(jié)點及其鄰接點之間的相連關系產生導出子圖，然后針對每個子圖進行最大團的求解。該算法在不破壞最大團結構的前提下，可以將大規(guī)模圖例分解為小規(guī)模圖例，然后對小規(guī)模圖例并行求解最大團。假設存在圖G=(V,E)，依次選取V中的頂點vi，構造子圖Gi=(V′,E′)。SGP的具體流程如下:

步驟1 初始化頂點V′和邊集合E′為空，將vi和節(jié)點vi的鄰接節(jié)點集合加入V′。

步驟2 依次選擇頂點集合V′中的節(jié)點i和節(jié)點j，如果邊(i,j)∈E，則將邊(i,j)添加到E′當中，直到遍歷完頂點集合V′，完成子圖Gi的構建。

SGP生成的子圖規(guī)模主要取決于起始節(jié)點的度，但在大規(guī)模圖中節(jié)點的度往往差異較大，生成子圖的規(guī)模也相差較大，導致求解最大團時因負載不均衡將耗費大量時間。為了克服這些不足，本文提出MGP，在單層圖劃分的基礎上基于節(jié)點的度對節(jié)點進行排序，在構建子圖時刪除度數值較起始節(jié)點vi低的節(jié)點(在度數相等時，刪除節(jié)點編號小于vi的節(jié)點)，在保持原有的團結構不變的情況下，利用排序大幅度減小子圖規(guī)模，并且針對規(guī)模較大的圖進行多層圖劃分，以平衡求解最大團時的任務負載。假設存在圖G=(V,E)，依次選取V中的頂點v，構造子圖Gv=(Vv,Ev)。MGP的具體流程如下：

步驟1 首先隨機給節(jié)點編號1,2，…，m(m為節(jié)點的個數)，初始化頂點Vv和邊集合Ev為空。

步驟2 首先求得v的鄰接點集合vList，vList中的任意節(jié)點vertex滿足如下兩個條件：①vertex節(jié)點度數大于v的度數；②vertex節(jié)點度數等于v的度數，但vertex節(jié)點的編號大于v節(jié)點的編號。將節(jié)點v和vList集合中的節(jié)點加入Gv的頂點集合Vv。

步驟3 依次選擇頂點集合Vv中的節(jié)點i和節(jié)點j，如果邊(i,j)∈E，則將邊(i,j)添加到Ev當中，直到遍歷完頂點集合Vv，完成子圖Gv的構建。

步驟4 若子圖Gv中節(jié)點個數大于一定的閾值(設為300)，則繼續(xù)對子圖使用步驟5進行多重圖劃分，否則，算法結束。

步驟5 依次選擇子圖Gv中的節(jié)點u構建子圖Gu=(Vu,Eu),首先得到u的鄰接點集合uList，uList中的任意節(jié)點vertex滿足如下兩個條件：①vertex節(jié)點度數大于u的度數；②vertex節(jié)點度數等于u的度數，但vertex節(jié)點的編號大于u節(jié)點的編號,將節(jié)點u和uList集合中的節(jié)點加入Vu。依次選擇頂點集合Vu中的節(jié)點i和節(jié)點j，如果邊(i,j)∈Ev，則將邊(i,j)添加到Eu當中，直到遍歷完頂點集合Vu，完成子圖Gu的構建。

MGP的關鍵在于步驟2并沒有將v和v的全部鄰接節(jié)點加入Gv，只選擇了滿足①和②條件的鄰居節(jié)點，為了證明這樣不會破壞原圖G的團結構，只需證明圖G的任意一個團結構都包含在MGP構造的某個Gv中。本文給出了定理1進行說明，具體如下。

定理1 利用MGP進行圖劃分，圖G中所有團結構將被保留到各個子圖當中。

證明 對于圖G=(V,E),C= (Vc,Ec)是圖中任意的一個團，假設團C中存在點v，v滿足在原圖G當中度數最小(當團C中存在有多個節(jié)點滿足這個條件時，選擇節(jié)點編號最小的節(jié)點)。根據MGP，構造以點v為誘導節(jié)點的子圖Gv(圖Gv中的節(jié)點在原圖G中的度數大于v，或者節(jié)點編號大于v),對于?u∈Vc，u節(jié)點在原圖G中的度數大于v或者在度數相等時，u節(jié)點編號大于節(jié)點v，故u∈Gv，以此類推，團C中的所有節(jié)點均包含于Gv，即圖中所有的團結構都被保留在各個子圖中。

得證

為了進一步說明MGP不會破壞原圖的團結構，本文以圖1為例說明，其中圖1(a)示例圖G包括3個團，分別如圖1(b)、圖1(c)和圖1(d)所示。以圖1(b)為例，在{2,3,5}節(jié)點集合中，節(jié)點5在圖1(a)中的節(jié)點度數最小。依據MGP得到的圖劃分如圖2所示，其中加黑的點表示針對該節(jié)點的分圖產生的子圖。針對5節(jié)點的子圖為圖2(e),很明顯可以看出，圖1(b)中的節(jié)點均位于圖2(e)中，同理，圖1(c)中1節(jié)點的序號最小，圖1(c)中的節(jié)點均位于針對1節(jié)點的子圖(圖2(a))中，圖1(d)中6節(jié)點的度數最小，圖1(d)中的節(jié)點均位于針對6節(jié)點的子圖(圖2(f))中，因此MGP不會破壞原圖的團結構。

圖1 示例圖G及其團結構Fig. 1 Example graph G and its clique structures

以圖1(a)為例對比SGP和MGP兩種分圖方法的性能。根據MGP的流程對圖G的劃分結果如圖2所示，根據SGP的流程對圖G的劃分結果如圖3所示。針對圖G，SGP求得的子圖的平均節(jié)點個數為4.33，節(jié)點個數最多為5；而MGP求得子圖的平均節(jié)點個數為2.67，節(jié)點個數最多為4，因此在不影響求解最大團的基礎上，MGP對子圖的劃分規(guī)模明顯低于SGP。

圖2 MGP圖劃分結果Fig. 2 Graph partitioning results of MGP

圖3 SGP圖劃分結果Fig. 3 Graph partitioning results of SGP

2 并行多重圖劃分方法

為了在大規(guī)模圖例上進行圖劃分，本文應用GraphX圖計算框架實現MGP形成并行的多層圖劃分方法(PMGP)，并將PMGP框架部署到Spark分布式云計算平臺上。下面首先介紹Spark和GraphX的特點，并給出GraphX框架的常用方法，然后詳細說明PMGP的實現過程和偽代碼。

2.1 Spark和GraphX

Spark是基于內存計算的大數據分布式計算框架，是一種快速、通用、可擴展的大數據分析引擎，它擁有Hadoop平臺和MapReduce框架的全部優(yōu)點，但不同的是Spark運算的中間結果能存儲在內存中，而不再需要讀寫Hadoop分布式文件系統(tǒng)(Hadoop Distributed File System, HDFS)，提高了并行計算的速度，因此Spark更適合進行數據挖掘與機器學習等需要迭代處理的算法[19]。目前，Spark生態(tài)系統(tǒng)已經發(fā)展成為一個包含多個子項目的集合，包含SparkSQL、Spark Streaming、MLlib、GraphX等子項目,其中GraphX是圖結構數據的并行處理系統(tǒng)?；跀祿⑿幸?Spark，GraphX采用了頂點分割策略，一個圖的頂點和邊都帶有屬性并且可以使用兩個彈性分布式數據集頂點RDD和邊RDD來表示。因此，GraphX對圖并行計算和數據并行計算進行了結合，使得其在計算速度上能夠和專業(yè)的圖計算系統(tǒng)相媲美，同時還保留了數據并行系統(tǒng)的表達力,可以方便且高效地完成圖計算的一整套流水作業(yè)。圖的應用程序編程接口(Application Programming Interface, API)方法有很多種，包括圖的構建、更改圖的頂點和邊的屬性值、統(tǒng)計圖的結構信息等，其中并行多層圖劃分方法(PMGP)用到的API方法如表1所示。

表1 GraphX圖計算方法Tab. 1 GraphX graph calculation method

2.2 PMGP流程

PMGP的步驟如下：

1)數據預處理。對與尋找最大團來說，圖中的重復邊以及自循環(huán)的邊都會影響最終的求解過程，因此首先要進行數據預處理過程。數據預處理主要是對文本數據的操作，首先應用Spark的textFile算子從HDFS中讀取數據，其次使用filter算子去掉自循環(huán)的邊和重復的邊，最后針對過濾后的數據先進行map操作將RDD中的數據轉換為Edge類型，再使用GraphX圖計算框架的fromEdges方法生成圖Graph1，其中圖Graph1包括頂點RDD和邊RDD，具體的流程如圖4所示。

圖4 數據預處理RDD轉化圖Fig. 4 RDD transformation graph of data preprocessing

2)獲取圖的必要參數。在步驟1)得到圖Graph1的基礎上，使用GraphX的degrees方法獲取DegreeRDD，使用collectNeighborIds方法獲取NeighborRDD。

3)針對每一個節(jié)點尋找滿足條件的鄰居節(jié)點。在步驟2)獲取DegreeRDD以后，使用DegreeRDD和GraphX的outerJoinVertices方法將圖Graph1的頂點屬性更新為每一個節(jié)點的度數，然后使用aggregateMessages方法尋找每一個節(jié)點滿足條件的鄰居節(jié)點。aggregateMessages可以并行化地對圖中的每一個triplet進行操作,triplet的定義如圖5所示。在GraphX中，triplet表示一個五元組，包括源點編號srcId、源點屬性srcAttr、目的點編號dstId、目的點屬性dstAttr和邊的屬性attr。在sendMsg階段，根據MGP圖劃分方法，當圖Graph1的頂點屬性變?yōu)轫旤c的度數時，當scrAttr>dstAttr或者當srcAttr=dstAttr但srcId>dstId時，就向目的頂點發(fā)送源頂點的srcId，否則就向源頂點發(fā)送dstId。在mergeMsg階段，針對每一個節(jié)點，將收到的消息進行合并形成滿足條件的鄰居節(jié)點集合，該方法最終返回VertexRDD類型的EligibleRDD，其頂點的屬性為每一個節(jié)點滿足條件的鄰居節(jié)點集合。

圖5 triplet類型的定義Fig. 5 Definition of triplet type

4)針對每一個節(jié)點構造子圖。調用aggregateMessages方法生成子圖，在發(fā)送消息階段，分為如下兩步：①當源節(jié)點的度數大于目的節(jié)點的度數或兩者度數相等但源節(jié)點的編號大于目的節(jié)點的編號時，按照MGP的步驟3，依次遍歷源節(jié)點的每一個鄰居節(jié)點temp，如果目的節(jié)點滿足條件的鄰居節(jié)點集中出現過的節(jié)點temp，則節(jié)點temp和源節(jié)點之間形成一條邊，當遍歷完源節(jié)點所有的鄰居節(jié)點以后，將生成的子圖發(fā)給目的節(jié)點。②當源節(jié)點的度數小于目的節(jié)點的度數或兩者度數相等但源節(jié)點的編號小于目的節(jié)點的編號時，則依次遍歷目的節(jié)點的每一個鄰居節(jié)點temp，如果源節(jié)點滿足條件的鄰居節(jié)點中包含temp，則在temp節(jié)點和目的節(jié)點之間添加一條邊，當遍歷完目的節(jié)點的所有鄰居節(jié)點以后，將生成的子圖發(fā)給源節(jié)點。在合并消息階段，每一個節(jié)點將收到的消息進行合并即可。該方法最終返回VertexRDD類型的EligibleSubGraphRDD，其頂點的屬性為每一個節(jié)點產生的子圖。

5)進行多重圖劃分。使用filter算子從EligibleSubGraphRDD中過濾出節(jié)點規(guī)模大于300的子圖，按照MGP的步驟5，使用map算子對大于300個節(jié)點規(guī)模的子圖進行多重圖劃分，得到VertexRDD類型的Last_Eligible_SubGraphRDD，即為最終劃分的結果。

PMGP的偽代碼如算法1所示。

算法1 PMGP。

輸入 文本文件的輸入路徑input；

輸出 滿足條件的子圖。

1)

數據預處理得到EdgesRDD

2)

Graph1 ← Graph. fromEdges(EdgesRDD)

3)

使用degrees和collectNeighborIds得到DegreeRDD和

NeighborRDD

4)

Graph2←Graph1.outerJoinVertices(DegreeRDD).

outerJoinVertices(NeighborRDD)

5)

依據第3)步得到EligibleRDD

6)

Graph3← Graph2.outerJoinVertices(EligibleRDD).

outerJoinVertices(NeighborRDD)

7)

依據第4)步構造每一個節(jié)點的子圖，得到

EligibleSubGraphRDD

8)

依據第5)步對大于300個節(jié)點規(guī)模的子圖進行多重圖劃

分，得到Last_Eligible_SubGraphRDD

9)

Last_Eligible_SubGraphRDD即為求得的子圖，算法結束

按照PMGP的流程，GraphX環(huán)境下的RDD轉化圖如圖6所示。

圖6 PMGP的RDD轉化圖Fig. 6 RDD transformation graph of PMGP

2.3 PMGP的實驗結果

為了說明圖劃分的有效性，本文選取了表2所示的Stanford Large Network Dataset Collection作為測試圖例，該數據集是研究和分析大規(guī)模圖數據的常用圖例。作為對比，本文應用Spark的GraphX圖計算框架實現并行單層圖劃分方法(PSGP)。對多個圖例進行并行多層圖劃分的實驗結果如表3所示，其中：Max表示劃分后子圖的最大規(guī)模(子圖中的最大節(jié)點數)，Avg表示子圖的平均規(guī)模，ρ表示子圖的平均密度。對于每一個子圖Gi的密度ρi計算如式(1)所示：

ρi=|E|/(|V|*(|V|-1))

(1)

其中:|V|表示子圖Gi的節(jié)點個數;|E|表示子圖Gi的邊數。

表2 測試圖例的基本屬性Tab. 2 Basic attributes of test graph examples

子圖的平均密度計算如式(2)所示:

(2)

其中N表示原圖G的節(jié)點個數。

從表3可以看出，PMGP在所有的數據集上求得的最大子圖規(guī)模相較于PSGP要小得多。在as-skitter網絡上，PSGP求得的最大子圖規(guī)模為35 456，而PMGP求得的最大子圖規(guī)模為232，是PSGP的1/150左右；在com_youtube網絡上，PMGP求得的最大子圖規(guī)模是PSGP的1/170左右。此外，在所有的數據集上，PMGP求得的子圖的平均密度相比PSGP也較小，即劃分的子圖更加緊湊。綜上所述，PMGP在不影響求解最大團的基礎上，減少求解最大團時的搜索空間規(guī)模。

表3 PSGP和PMGP圖劃分的實驗結果Tab. 3 Experimental results of PSGP and PMGP graph partitioning

3 基于速度優(yōu)化的懲罰值局部搜索算法

在完成圖劃分后，需要分別求得的每個子圖的最大團，再得到整個圖的最大團，最大團問題的早期研究主要采用確定性算法，如枚舉法、分支定界法等，但最大團問題求解的復雜度會隨著圖規(guī)模增大呈指數級增長，確定性算法不適合求解大規(guī)模圖例的最大團問題，因此，本文選取了復雜度較低，執(zhí)行速度快的局部搜索算法來求解最大團問題。PBLS[20]是本團隊之前提出的較好的局部搜索算法，由于PMGP產生的子圖規(guī)模較小，為了增加PBLS的靈活性，本文提出基于速度優(yōu)化的懲罰值局部搜索算法(SPBLS)。

3.1 SPBLS

張素琪[20]在Random_BLS(Random Breakout Local Search for maximum clique problems)算法[21]的基礎上提出了基于懲罰值的PBLS，該算法在局部搜索過程中根據各節(jié)點的禁忌值和懲罰值對節(jié)點進行選擇，禁忌值和懲罰值在每次迭代后更新。首先，圖中各節(jié)點的禁忌值和懲罰值初始化為0。局部搜索時從候選集中選擇不被禁忌且懲罰值最小的點加入CurrentClique(如果這樣的點有多個，從其中隨機選擇)，局部搜索結束后更新禁忌值和懲罰值。對節(jié)點進行禁忌和懲罰可增強搜索過程的多樣性，使得未被搜索到即未加入過團的點有更多的添加可能。

盡管PBLS在求解最大團問題時復雜度低、執(zhí)行速度快，但是PBLS的迭代次數需要人為設定，算法運行的迭代次數越多，求解的準確率越高。圖7是使用PMGP對as-skitter圖例劃分產生的子圖分布，其中，橫坐標代表as-skitter產生的各個子圖的節(jié)點個數(即子圖的規(guī)模)，縱坐標表示as-skitter產生的各種子圖規(guī)模下的子圖個數占子圖總個數的百分比。從圖7可以看出， PMGP可以對大規(guī)模圖例分圖產生較小的子圖，對as-skitter圖例來說，約97%的子圖規(guī)模都在70個節(jié)點以下。在使用PBLS對PMGP產生的子圖并行求解最大團時，為了保證規(guī)模較大的子圖可以準確地求解出最大團，PBLS需要設定較高的迭代次數，但是，對于小規(guī)模的子圖，通常只需要很少的迭代次數就可以求解出比較好的結果，這樣就導致PBLS在求解小規(guī)模圖例的最大團時，時間效率較低。因此為了增加PBLS的靈活性，提高算法的執(zhí)行速度，本文根據子圖的規(guī)模優(yōu)化PBLS的迭代次數提出了SPBLS。

SPBLS的迭代次數的定義如式(3)所示:

(3)

其中:T表示最大迭代次數;N表示圖中節(jié)點的個數;m是取值在10到100之間的常量;c是取值在0到1之間的常量。式(3)表明當圖中的節(jié)點個數越多時，SPBLS求解最大團所需要的迭代次數越多，當求得的迭代次數為小數時，迭代次數向上取整。為了進一步驗證式(3)的有效性,本文求出了300個節(jié)點以內的子圖所需的迭代次數分布,如圖8所示,這里m取值為50，c取值為0.5，T取值為15。從圖8可以看出，隨著子圖規(guī)模的不斷增大，SPBLS運行的迭代次數也不斷增加，該算法保證了較小規(guī)模子圖使用較少的迭代次數，較大規(guī)模子圖使用較多的迭代次數。

圖7 PMGP在as-skitter上產生的子圖規(guī)模分布Fig. 7 Subgraph scale distribution generated by PMGP on as-skitter

圖8 SPBLS的迭代次數分布Fig. 8 Iteration number distribution of SPBLS

為了進一步驗證SPBLS的有效性，本文從as-skitter圖例產生的子圖中分別取出50個節(jié)點規(guī)模的子圖、100個節(jié)點規(guī)模的子圖、150個節(jié)點規(guī)模的子圖和200個節(jié)點規(guī)模的子圖，分別使用PBLS求解最大團，對比PBLS在求解到最大團時所需的迭代次數和SPBLS依據節(jié)點規(guī)模所求的迭代次數，其結果分別如圖9所示。

從圖9可以看出，隨著子圖規(guī)模不斷增加，算法求解到最大團所需的迭代次數也在不斷增加。從圖9(a)可以看出，對于50個節(jié)點規(guī)模的圖例，應用PBLS求解最大團時，迭代到2次時，最大團的規(guī)模已經不再發(fā)生變化，對于SPBLS來說，應用式(3)可以求得50節(jié)點規(guī)模的子圖大約需要3次迭代，因此PBLS在求解到最大團時所需的迭代次數和SPBLS依據節(jié)點規(guī)模所求的迭代次數是幾乎相同的，使用SPBLS不會影響求解最大團的精度。從圖9(b)可以看出，對于100個節(jié)點規(guī)模的子圖，PBLS運行6次迭代，最大團規(guī)模就已經不再變化，而對于SPBLS，依據式(3)，100個節(jié)點規(guī)模的子圖大約需要6次迭代，因此SPBLS也不影響求解最大團的精度。同理，從圖9(c)和圖9(d)也可以看出，在150個節(jié)點規(guī)模和200個節(jié)點規(guī)模的子圖上，SPBLS也不影響求解最大團的精度。綜上所述，SPBLS保證了在不影響求解最大團精度的前提下，對小規(guī)模子圖使用較少的迭代次數，較大規(guī)模子圖使用較多的迭代次數，從而依據子圖規(guī)模動態(tài)調整迭代次數，提高算法的整體效率。

圖9 不同節(jié)點規(guī)模PBLS求解最大團的迭代次數變化Fig. 9 Iterative number change in solving maximum clique of PBLS at different node scales

3.2 SPBLS的偽代碼

SPBLS的偽代碼算法2所示。

算法2 SPBLS。

輸入 圖G(V,E)，最優(yōu)團更新次數t，禁忌參數基本值φ,定向擾動概率的閾值P0，隨機擾動幅度α；

輸出 圖G的最大團BestClique。

從圖G中隨機選取點v，加入當前團CurrentClique中，初始化最大擾動強度Imax為|V|的0.1倍，最小擾動強度Imin為頂點數的0.01倍，當前迭代次數numsteps為0，初始化所有點的禁忌值和懲罰值為0，最優(yōu)團未更新次數w為0，初始化算法求得最大團RbestClique為空,初始化最大團BestClique為空；

按照式(3)計算圖G所需的迭代次數maxsteps

while(numsteps

向RbestClique加入節(jié)點；

if(RbestClique.length>BestClique.length) then

BestClique←RbestClique；

w←0；

else

w←w+1

end if

初始化Clique_local為空；

if(w>T) then

w←0；

以Imax的強度在CurrentClique上執(zhí)行隨機擾動，更新節(jié)點的

禁忌值和懲罰值；

CurrentClique中的節(jié)點加入Clique_local;

else

perturbSte←0;

ifClique_local==CurrentCliquethen

perturbSte←perturbSte+1;

else

perturbSte←Imin；

end if

依據定向擾動概率P0計算概率P；

產生從0到1的隨機數k；

if(p≤k)

以perturbSte的強度在Clique上執(zhí)行定向擾動，更新所有

節(jié)點的禁忌值和懲罰值；

CurrentClique中的節(jié)點加入Clique_local;

else

以perturbSte的強度在Clique上執(zhí)行定向擾動，更新所有

節(jié)點的禁忌值和懲罰值；

CurrentClique中的節(jié)點加入Clique_local;

end if

end if

end while

得到最大團BestClique，算法結束。

4 實驗結果與分析

本次實驗將PMGP和SPBLS相結合，形成求解最大團問題的并行多重圖劃分方法(PMGP_SMC)。為了驗證PMGP_SMC在求解最大團問題的高效性和準確性，本文應用Spark的GraphX圖計算框架實現SGP形成并行的單層圖劃分方法(PSGP)，并且將PSGP和PBLS相結合形成求解最大團問題的并行單層圖劃分方法(PSGP_SMC)，將PMGP與極大團枚舉(MCE)方法相結合形成基于極大團枚舉求解最大團問題的并行多重圖劃分方法(PMGP_MCE)，并對3種算法在速度和精度方面作對比。實驗采用表2所示的Stanford的9個大規(guī)模數據集[22]進行測試。PSGP_SMC在使用PBLS求解最大團時，由于SGP產生的子圖規(guī)模較大，因此為了保證求解最大團的精度，本文將PBLS的迭代次數統(tǒng)一設置為20。SPBLS所需的迭代次數maxsteps依據式(3)確定，最大團未更新的最大次數t為maxsteps的一半，禁忌參數基本值φ為7,定向擾動概率的閾值P0為0.8，隨機擾動幅度α為0.6。

本文使用了Spark 集群進行實驗，其中包括1個master節(jié)點和5個worker節(jié)點。worker節(jié)點硬件配置如下：Intel Xeon Core E5-1620,CPU@3.70 GHz processor; 256 GB內存。軟件配置如下：Linux CentOS 6.5，JDK1.7.0_67，Spark-1.6.2版本。

PMGP_SMC與PSGP_SMC兩種算法的運行時間比較如表4所示，其中，T_time表示每一個大規(guī)模圖例運行的總時間，P_time包括兩部分，P_time1表示在圖劃分階段的運行時間，P_time2表示在分階段突破局部搜索求解最大團階段的運行時間。由實驗結果可知，由于PMGP_SMC方法進行了多重圖劃分，因此在圖劃分方面PMGP_SMC算法比PSGP_SMC慢，但由于PMGP_SMC算法求得的子圖規(guī)模比較小，在使用SPBLS求解最大團時，能夠依據節(jié)點個數動態(tài)調整算法的迭代次數，因此與PSGP_SMC算法相比，所需的迭代次數較少，速度較快，從總的時間來看，PMGP_SMC較PSGP_SMC有很大程度的改善。其中：在ego-facebook數據集上，PMGP_SMC算法的速度相比PSGP_SMC提高了33倍；在email-Enron，PMGP_SMC的速度提高了172倍；在其他數據集上，算法提高了幾十倍不等。驗證了PMGP_SMC有更快的速度和更高的效率。

表4 PMGP_SMC和PSGP_SMC運行時間比較 msTab. 4 Running time comparison of PMGP_SMC and PSGP_SMC ms

為了進一步驗證求解最大團問題的有效性，本文將PMGP_SMC、PMGP_MCE和PSGP_SMC在求出的最大團規(guī)模方面作了對比，3種算法求得的最大團規(guī)模如表5所示。從表5可以看出，由于PMGP產生的子圖規(guī)模較小，因此使用PMGP_SMC和PMGP_MCE求得最大團規(guī)模一致，但PMGP_SMC相比PMGP_MCE具有較高的求解效率；由于在求解最大團時，PSGP_SMC將迭代次數設置為20次，因此也可以求得比較好的結果，但與PMGP_SMC相比，該算法的執(zhí)行速度較慢。因此與其他兩種算法相比，PMGP_SMC算法在求解最大團問題時，具有高效性和準確性。

表5 不同算法求得的最大團規(guī)模對比Tab. 5 Maximum clique scale comparison of different algorithms

5 結語

并行圖劃分是大規(guī)模圖例進行最大團問題求解的一個重要研究方向。針對求解大規(guī)模圖的最大團問題中復雜度高、通用性差等問題，本文提出求解最大團問題的并行多重圖劃分方法(PMGP_SMC)。首先本文提出了MGP圖劃分方法，在SGP的基礎上，對圖中的節(jié)點按度排序，在保持圖中原有團結構不變的情況下大幅度減少子圖規(guī)模，并對規(guī)模較大的子圖進行多重圖劃分，進一步縮小子圖規(guī)模；然后，本文應用Spark的GraphX并行圖計算框架實現MGP形成PMGP。此外，本文依據子圖的規(guī)模優(yōu)化了PBLS的迭代次數，提出了SPBLS，對劃分后的各個子圖，分別使用SPBLS并行求解各個子圖的最大團。最后，將PMGP和SPBLS相結合，形成求解最大團問題的并行多重圖劃分方法PMGP_SMC。實驗證明，與PSGP_SMC和PMGP_MCE相比，PMGP_SMC可以有效地處理數以百萬節(jié)點的圖例，高效精準求解大規(guī)模圖例的最大團，為其他組合優(yōu)化問題的高效求解帶來啟示。