求解最大團(tuán)問(wèn)題的并行多層圖劃分方法

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

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

0 引言

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

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

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

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

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

1 多層圖劃分方法

1.1 最大團(tuán)基本定義

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

定義2 團(tuán)。稱無(wú)向圖G的完全子圖U是G的一個(gè)團(tuán)，當(dāng)且僅當(dāng)完全子圖U不包含在圖G的更大完全子圖中。

定義3 最大團(tuán)。稱無(wú)向圖G的最大團(tuán)C為圖中包含頂點(diǎn)數(shù)最多的團(tuán)，最大團(tuán)問(wèn)題即求解圖G=(U,V)的最大團(tuán)C。

1.2 MGP流程

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

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

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

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

步驟1 首先隨機(jī)給節(jié)點(diǎn)編號(hào)1,2，…，m(m為節(jié)點(diǎn)的個(gè)數(shù))，初始化頂點(diǎn)Vv和邊集合Ev為空。

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

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

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

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

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

定理1 利用MGP進(jìn)行圖劃分，圖G中所有團(tuán)結(jié)構(gòu)將被保留到各個(gè)子圖當(dāng)中。

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

得證

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

圖1 示例圖G及其團(tuán)結(jié)構(gòu)Fig. 1 Example graph G and its clique structures

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

圖2 MGP圖劃分結(jié)果Fig. 2 Graph partitioning results of MGP

圖3 SGP圖劃分結(jié)果Fig. 3 Graph partitioning results of SGP

2 并行多重圖劃分方法

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

2.1 Spark和GraphX

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

表1 GraphX圖計(jì)算方法Tab. 1 GraphX graph calculation method

2.2 PMGP流程

PMGP的步驟如下：

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

圖4 數(shù)據(jù)預(yù)處理RDD轉(zhuǎn)化圖Fig. 4 RDD transformation graph of data preprocessing

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

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

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

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

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

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

算法1 PMGP。

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

輸出 滿足條件的子圖。

1)

數(shù)據(jù)預(yù)處理得到EdgesRDD

2)

Graph1 ← Graph. fromEdges(EdgesRDD)

3)

使用degrees和collectNeighborIds得到DegreeRDD和

NeighborRDD

4)

Graph2←Graph1.outerJoinVertices(DegreeRDD).

outerJoinVertices(NeighborRDD)

5)

依據(jù)第3)步得到EligibleRDD

6)

Graph3← Graph2.outerJoinVertices(EligibleRDD).

outerJoinVertices(NeighborRDD)

7)

依據(jù)第4)步構(gòu)造每一個(gè)節(jié)點(diǎn)的子圖，得到

EligibleSubGraphRDD

8)

依據(jù)第5)步對(duì)大于300個(gè)節(jié)點(diǎn)規(guī)模的子圖進(jìn)行多重圖劃

分，得到Last_Eligible_SubGraphRDD

9)

Last_Eligible_SubGraphRDD即為求得的子圖，算法結(jié)束

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

圖6 PMGP的RDD轉(zhuǎn)化圖Fig. 6 RDD transformation graph of PMGP

2.3 PMGP的實(shí)驗(yàn)結(jié)果

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

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

(1)

其中:|V|表示子圖Gi的節(jié)點(diǎn)個(gè)數(shù);|E|表示子圖Gi的邊數(shù)。

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

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

(2)

其中N表示原圖G的節(jié)點(diǎn)個(gè)數(shù)。

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

表3 PSGP和PMGP圖劃分的實(shí)驗(yàn)結(jié)果Tab. 3 Experimental results of PSGP and PMGP graph partitioning

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

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

3.1 SPBLS

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

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

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

(3)

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

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

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

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

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

圖9 不同節(jié)點(diǎn)規(guī)模PBLS求解最大團(tuán)的迭代次數(shù)變化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)團(tuán)更新次數(shù)t，禁忌參數(shù)基本值φ,定向擾動(dòng)概率的閾值P0，隨機(jī)擾動(dòng)幅度α；

輸出 圖G的最大團(tuán)BestClique。

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

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

while(numsteps

向RbestClique加入節(jié)點(diǎn)；

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的強(qiáng)度在CurrentClique上執(zhí)行隨機(jī)擾動(dòng)，更新節(jié)點(diǎn)的

禁忌值和懲罰值；

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

else

perturbSte←0;

ifClique_local==CurrentCliquethen

perturbSte←perturbSte+1;

else

perturbSte←Imin；

end if

依據(jù)定向擾動(dòng)概率P0計(jì)算概率P；

產(chǎn)生從0到1的隨機(jī)數(shù)k；

if(p≤k)

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

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

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

else

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

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

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

end if

end if

end while

得到最大團(tuán)BestClique，算法結(jié)束。

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

表4 PMGP_SMC和PSGP_SMC運(yùn)行時(shí)間比較 msTab. 4 Running time comparison of PMGP_SMC and PSGP_SMC ms

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

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

5 結(jié)語(yǔ)

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