基于并行約束規(guī)劃的最大團(tuán)識別研究

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

(遼寧工程技術(shù)大學(xué) 軟件學(xué)院,遼寧 葫蘆島 125105)

0 概述

最大團(tuán)問題(Maximum Clique Problem,MCP)是圖論中經(jīng)典的組合優(yōu)化問題,也是一類NP完全問題,在數(shù)據(jù)挖掘、圖像處理、計算機(jī)視覺、生物學(xué)、模式識別、人工智能等領(lǐng)域均具有非常廣泛的應(yīng)用。例如,最大團(tuán)算法在數(shù)據(jù)挖掘網(wǎng)格系統(tǒng)上的應(yīng)用[1],融合社交網(wǎng)絡(luò)特征的最大團(tuán)并行算法用于圖壓縮處理[2],通過最大團(tuán)算法解決低失真圖像視覺特征匹配問題[3],使用最大團(tuán)算法進(jìn)行網(wǎng)絡(luò)重疊社區(qū)檢測[4],運(yùn)用最大團(tuán)算法解決組合競拍中競勝標(biāo)確定問題[5],最大團(tuán)算法在生物計算上的應(yīng)用[6]等。因此,最大團(tuán)問題的研究具有較高的理論價值和現(xiàn)實意義。但是,隨著圖規(guī)模呈指數(shù)級增長,傳統(tǒng)精確算法和啟發(fā)式算法存在通用性差、求解效率低等問題。

針對大數(shù)據(jù)背景下圖節(jié)點的海量性和分析的復(fù)雜性,研究者提出并行化處理的求解思路。例如,使用MapReduce[7-8]和Pregel[9]等面向海量數(shù)據(jù)和密集型計算的并行處理框架,這些框架具有較好的容錯性和可擴(kuò)展性,同時提供了簡單的處理方法和功能強(qiáng)大的編程模型。并行處理計算框架的應(yīng)用和不斷發(fā)展促進(jìn)了各種并行算法的實現(xiàn)。文獻(xiàn)[10]提出基于MapReduce的分布式算法實現(xiàn)圖分割,并采用分支定界方法枚舉分割后產(chǎn)生子圖中的團(tuán)結(jié)構(gòu),但該研究沒有考慮計算節(jié)點間的負(fù)載均衡,并且會有大量錯誤、重復(fù)的中間值輸出。文獻(xiàn)[11]提出基于MapReduce框架的最大團(tuán)并行求解方法,該方法通過采用圖著色方法進(jìn)行圖分割,然后使用分支定界方法求解子圖中的最大團(tuán),但是產(chǎn)生子圖數(shù)目過多,可能增加分支定界法求解子圖的時間復(fù)雜度和空間復(fù)雜度,同時該文獻(xiàn)中沒有對大規(guī)模圖進(jìn)行測試,無法證實算法對于大規(guī)模圖例的有效性[12]?？紤]到大規(guī)模圖例計算的復(fù)雜性和密集性,本文設(shè)計基于Spark框架的最大團(tuán)并行化求解方法。

1 問題介紹

1.1 最大團(tuán)問題描述

本文使用的符號及其釋義說明如表1所示。給定無向圖G=(V,E),其中,V是非空集合,稱為頂點集,E是V中元素構(gòu)成的無序二元組集合,稱為邊集,無向圖中的邊均是頂點的無序?qū)?無序?qū)τ谩? )”表示。如果U?V且對任意兩個頂點u,v∈U存在(u,v)∈E,則稱U是G的完全子圖。團(tuán)(又稱集團(tuán))是圖的頂點集的一個子集,使得其導(dǎo)出子圖為完全子圖,如果一個團(tuán)不是任何其他團(tuán)的子集,則稱該團(tuán)為極大團(tuán)。一個圖中含有頂點數(shù)最多的團(tuán),稱為該圖的最大團(tuán)[13]。

表1 符號說明

1.2 相關(guān)定理

根據(jù)最大團(tuán)問題的描述和定義,下文給出問題的相關(guān)性質(zhì)以及證明過程,其中部分定理可參考文獻(xiàn)[14]。

定理1設(shè)vi∈S并且(vi,vj)?E,則vj?S,其中S為最大團(tuán)。

證明根據(jù)團(tuán)的性質(zhì),由反證法可知,若vi屬于最大團(tuán)S,則顯然vi與最大團(tuán)S中所有元素都相連,而vi與vj之間不存在邊相連,則vj與vi不會出現(xiàn)在同一個最大團(tuán)S中。

定理2若V中某頂點vi的度數(shù)為n-1,則點vi必然屬于最大團(tuán)S。

證明假設(shè)頂點個數(shù)為n,度數(shù)為n-1的頂點與圖中其他頂點均相連,同理,該頂點與該圖最大團(tuán)中所有頂點均相連。根據(jù)最大團(tuán)定義,由反證法可知,若vi不在最大團(tuán)中,則該最大團(tuán)不是圖中真正的最大團(tuán),即只要圖G中存在度數(shù)為n-1的節(jié)點,那么最大團(tuán)必定包含該節(jié)點vi。同理可推,當(dāng)節(jié)點度數(shù)越高,它出現(xiàn)在最大團(tuán)S中的概率越大。

2 基于并行約束規(guī)劃的最大團(tuán)識別算法

本文提出的融合并行約束規(guī)劃的最大團(tuán)識別算法主要包括三部分:并行圖劃分處理,約束規(guī)劃求解策略和基于任務(wù)的運(yùn)行時間預(yù)測模型,流程如圖1所示。

圖1 基于并行約束規(guī)劃的最大團(tuán)求解流程

并行圖劃分處理采用BMT多層圖分割算法,并在多層圖劃分過程中調(diào)用運(yùn)行時間預(yù)測模型,實現(xiàn)實時控制產(chǎn)生的子圖大小以確保集群負(fù)載均衡。Spark集群中每一個計算節(jié)點均采用Choco約束規(guī)劃求解器[15],通過約束規(guī)劃方法計算得出子圖中的最大團(tuán),最終得到對應(yīng)圖例的最大團(tuán)。

2.1 圖劃分問題

圖劃分問題是經(jīng)典的組合優(yōu)化問題,即將圖中的節(jié)點集合劃分為一系列數(shù)量規(guī)模相近的子集合,在滿足約束條件的同時使目標(biāo)得到優(yōu)化。圖劃分在很多領(lǐng)域都具有廣泛的應(yīng)用,如大規(guī)模數(shù)字集成電路設(shè)計、數(shù)據(jù)挖掘、并行計算等。

2.1.1 BMC圖劃分策略

文獻(xiàn)[11]提出的BMC算法采用基于顏色的多層分割策略,根據(jù)圖中頂點度數(shù)由大到小的順序進(jìn)行圖著色處理,每次選擇度數(shù)大的頂點分割,直至滿足限定條件。

第一次分割如下:

G1=v1∪N(G,v1)

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

?

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

(1)

其中,子圖G1由圖G中度數(shù)最大的頂點v1及其鄰居頂點組成,子圖G2是由圖G中除去頂點v1及其鄰邊后,圖中度數(shù)最大的頂點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)

通過第一次分割策略實現(xiàn)了將復(fù)雜圖G分割為頂點數(shù)目不同、圖密度不等的K個子圖。在K個子圖中,有的子圖頂點較多或者圖密度較大,則求解時間較長需要繼續(xù)分割,有的子圖頂點較少或者圖密度較小,則求解時間較短可以不再分割。因此,將需要繼續(xù)分割的子圖進(jìn)行第二次分割,直至滿足限定條件,完成圖分割過程。

2.1.2 BMT圖劃分策略

本文結(jié)合BMC圖劃分策略中多層劃分方法,提出基于任務(wù)運(yùn)行時間預(yù)測模型的BMT并行圖劃分策略。算法主要考慮到兩個方面:一是實現(xiàn)有效的圖分割,將復(fù)雜圖分割為若干個更小且最大團(tuán)關(guān)系相互獨立的子圖,使得Spark集群中的計算節(jié)點可以獨立計算,降低通信開銷;二是保證集群中各個計算節(jié)點的負(fù)載均衡,通過預(yù)測時間模型估算求解時間,決定圖分割的深度。

依據(jù)最大團(tuán)特性,定理1在最大團(tuán)中任意兩點之間均有邊,若某兩個頂點之間沒有邊相連,則這兩個頂點不會出現(xiàn)在同一個最大團(tuán)中。定理2在最大團(tuán)中若某一頂點的度數(shù)較高,則它出現(xiàn)在最大團(tuán)中的幾率就更大。因此,本文設(shè)計了基于任務(wù)運(yùn)行時間負(fù)載均衡的BMT圖劃分策略。相比于其他圖劃分方法,本文提出的BMT圖劃分方法產(chǎn)生的子圖數(shù)目更少,子圖之間最大團(tuán)關(guān)系保持獨立,同時運(yùn)行時間預(yù)測模型嚴(yán)格控制子圖范圍的大小,實現(xiàn)集群負(fù)載均衡。

第一次分割如下:

G1=v1∪N(G,v1)

G2=v2∪N(G,v2)

?

GK=vK∪N(G,vK)

(3)

其中,v1,v2,…,vK是圖中相互之間沒有邊連接的若干頂點。根據(jù)定理1可知,v1,v2,…,vK頂點不會出現(xiàn)在同一個最大團(tuán)中。

首先根據(jù)頂點度數(shù)從大到小排列,選擇度數(shù)最大的頂點v1,然后在剩余頂點中,選擇與v1頂點沒有邊相連且度數(shù)最大的頂點v2,依次類推選出互相之間沒有邊連接的頂點v3,v4,…,vK,直至完成第一次分割,實現(xiàn)將圖劃分為最大團(tuán)關(guān)系獨立的若干子圖。

第二次分割過程是在子圖G1,G2,…,GK的基礎(chǔ)上進(jìn)行迭代分割。同時,調(diào)用任務(wù)運(yùn)行時間預(yù)測模型,估算出從每個子圖中求解最大團(tuán)所需的運(yùn)行時間,對于運(yùn)行時間大于平均預(yù)測時間的子圖繼續(xù)進(jìn)行分割,直至滿足計算節(jié)點之間的負(fù)載均衡。

本文BMT圖劃分方法的理論準(zhǔn)確性證明過程如下:

假設(shè)?v1,v2,…,vK∈G,且(vi,vj)?E,i,j∈(1,K)。若第一次分割后得到K個子圖,則K個子圖之間最大團(tuán)關(guān)系相互獨立。

證明在已知第一次分割后,得到分別包含v1,v2,…,vK的K個子圖G1,G2,…,GK,且v1,v2,…,vK之間沒有邊相連。以子圖G1為例,G1中最大團(tuán)S必包含v1頂點。因為子圖G1由頂點v1及其鄰居頂點組成,若鄰居頂點之間能夠形成團(tuán)S′,由于頂點v1與團(tuán)S′中每一個頂點均有邊相連,則根據(jù)最大團(tuán)定義可知,v1可加入團(tuán)S′中,得到子圖G1中的最大團(tuán)S。同理可推,對于子圖G1,G2,…,GK分別會得到包含v1,v2,…,vK頂點的各自子圖中的最大團(tuán)。若最大團(tuán)S中包含頂點v1,則由于v1,v2,…,vK之間沒有邊相連,不會再包含v2,v3,…,vK中任意一個頂點,因此K個子圖之間最大團(tuán)關(guān)系相互獨立,即假設(shè)成立。

BMT圖劃分過程如圖2所示。由圖2(a)經(jīng)過一次分割得到最大團(tuán)關(guān)系相互獨立的子圖,如圖2(b)所示。劃分過程如下:首先,在圖2(a)中按照頂點度數(shù)由大到小排列得到頂點集合{5,1,9,4,6,7,8,2,3},由此可知,圖2(a)中度數(shù)最大的頂點為頂點5,選擇頂點5及其鄰居頂點集合為{1,3,4,6,7,8,9};然后,根據(jù)最大圖獨立關(guān)系,選擇與頂點5沒有邊相連且度數(shù)最大的頂點,在本圖中滿足條件的為頂點2,選擇頂點2及其鄰居頂點集合{6,8,9},此時實現(xiàn)將一個圖2(a)分為最大團(tuán)關(guān)系獨立的兩個子圖,同時無孤立頂點,根據(jù)最大團(tuán)定理1可知,圖2(a)中頂點5與頂點2不會存在于同一個最大團(tuán)中,基于此實現(xiàn)第一次分割;最后,調(diào)用預(yù)測時間模型計算子圖并使用約束規(guī)劃求解需要的時間,從而決定是否繼續(xù)進(jìn)行圖分割。假定圖2(b)中包含頂點2的子圖,頂點數(shù)目少且所需計算時間短,不需要繼續(xù)分割,而包含頂點5的子圖需要進(jìn)行二次分割。第二次分割是在第一次分割得到的子圖基礎(chǔ)上進(jìn)行,重復(fù)式(3)劃分過程。對包含頂點5的子圖進(jìn)行再分割,可得到圖2(c)中兩個子圖。通過以上圖劃分方法實現(xiàn)將多頂點數(shù)、高密度的復(fù)雜圖例分割為頂點數(shù)少、密度低的子圖,降低約束規(guī)劃計算的復(fù)雜度。

圖2 BMT圖劃分過程

2.2 約束規(guī)劃

約束規(guī)劃是人工智能領(lǐng)域的一個重要分支,可解決現(xiàn)實生活中的很多問題,包括計算機(jī)視覺、通信、調(diào)度中的資源分配、電子商務(wù)、機(jī)器學(xué)習(xí)等。約束規(guī)劃是由一組變量集合和一組約束集合組成,公式描述簡單、易于理解,同時可根據(jù)實際問題,求解得出該問題的一個解、所有解或最優(yōu)解[16]。

約束規(guī)劃求解方法是由使用者聲明一組約束條件對問題進(jìn)行建模,Choco約束規(guī)劃求解器主要通過調(diào)整約束過濾算法解決問題,其包括豐富的原語、邏輯和條件約束及全局約束,同時將問題描述和問題求解分離,具有更好的靈活性和通用性[17]。

約束條件:xi+xj≤1,?(i,j)?E

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

(4)

在目標(biāo)函數(shù)中,n值代表圖中頂點數(shù)目,xi代表圖中的每一個頂點;xi+xj≤1,?e(xi,xj)?E為約束條件,即圖中任意兩點之間若無邊,則任意兩點之和不大于1;xi∈(0,1),i={1,2,…,n}表示圖中共n個頂點,每一個頂點的取值為0或1。

2.3 負(fù)載均衡控制策略

負(fù)載均衡是協(xié)調(diào)集群中各個計算節(jié)點運(yùn)行時間,通過控制每個計算節(jié)點得到的子圖大小,使得各個計算節(jié)點運(yùn)行時間接近,將運(yùn)行時間之差控制在可接受范圍內(nèi)。本文中設(shè)置的運(yùn)行時間差為10%,即從集群第一個計算節(jié)點運(yùn)行結(jié)束到整個程序運(yùn)行結(jié)束的時間差,不超過程序運(yùn)行總時間的10%(算法中的運(yùn)行時間差可以根據(jù)實際問題的具體情況更改設(shè)置),即(時間最大值-時間最小值)/時間最大值≤10%。嚴(yán)格控制運(yùn)行時間差,就能最大化提高程序整體運(yùn)行效率,實現(xiàn)集群負(fù)載均衡。

在BMT圖劃分過程中,使用負(fù)載均衡控制策略。在程序運(yùn)行過程中,通過調(diào)用預(yù)測運(yùn)行時間模型計算每個子圖求解最大團(tuán)所需運(yùn)行的時間。假設(shè)集群中有10臺機(jī)器,計算出第一次分割后的子圖個數(shù),如果子圖個數(shù)小于10,則進(jìn)行第二次分割,直到子圖個數(shù)大于或等于集群機(jī)器數(shù)目。在每一次分割后,預(yù)估子圖運(yùn)行時間,同時計算子圖合理分配給集群平臺后每個節(jié)點所需的運(yùn)行時間,并計算求解時間差,若大于閾值,則將預(yù)測時間大于均值的子圖繼續(xù)進(jìn)行分割,其他子圖則等待分配給計算節(jié)點。在每一次分割后,均調(diào)用預(yù)測運(yùn)行時間模型進(jìn)行實時調(diào)整,以確保分割操作后集群系統(tǒng)負(fù)載均衡。

估算運(yùn)行時間模型是在同一實驗環(huán)境中測試不同頂點數(shù)、圖密度的圖例使用約束規(guī)劃求解得到最大團(tuán)所需要的運(yùn)行時間,記錄相關(guān)實驗數(shù)據(jù)并進(jìn)行非線性回歸,計算得出預(yù)測時間模型,同時確定模型中各變量系數(shù)。

由實驗數(shù)據(jù)計算在同一頂點數(shù)下運(yùn)行時間與圖密度變量之間的關(guān)系。以頂點數(shù)100為例,依次測試圖密度從0.1到0.9的圖例數(shù)據(jù),記錄求解時間,實驗結(jié)果如圖3所示。

需求情況：農(nóng)業(yè)方面，當(dāng)前為農(nóng)業(yè)用肥淡季，尿素需求冷清。工業(yè)方面，上周復(fù)合肥企業(yè)和膠合板企業(yè)開工率保持低位，經(jīng)銷商對當(dāng)前尿素高價較為抵觸，需求較前期有所縮減。出口方面，由于國際尿素供給偏緊，價格持續(xù)上漲，但國內(nèi)經(jīng)銷商出口報價目前已經(jīng)低于中東地區(qū)，但仍高于其他主流貨源地，出口量少。

圖3 約束規(guī)劃求解最大團(tuán)問題的運(yùn)行時間

由圖3可知,對于給定頂點數(shù)目的圖,其密度與運(yùn)行時間之間成指數(shù)關(guān)系。因此,預(yù)測時間模型假定為指數(shù)函數(shù),形如T(G)=f(|G|,ρ(G))|G| g(ρ(G)),其中,f(|G|,ρ(G))和g(ρ(G))是關(guān)于頂點數(shù)目和圖密度的多項式函數(shù),g(ρ(G))是關(guān)于圖密度的二次函數(shù),定義為ρ(G)2+bρ(G)+c,同時對函數(shù)f(|G|,ρ(G))進(jìn)行泰勒展開[18],得到預(yù)測時間模型如下:

(5)

其中,k用來控制模型的自由度,即泰勒展開級數(shù),ai,j、b和c為未知變量系數(shù),由實驗數(shù)據(jù)驗證得出。訓(xùn)練運(yùn)行時間模型的圖例數(shù)據(jù)由程序隨機(jī)生成,并測試不同頂點數(shù)目及不同密度的圖使用約束規(guī)劃算法求解最大團(tuán)所需運(yùn)行時間。同時,將得到的訓(xùn)練數(shù)據(jù)信息通過數(shù)學(xué)優(yōu)化分析綜合工具軟件1stOpt[19]進(jìn)行非線性回歸計算,得出模型中參數(shù)的值。

2.4 算法描述與分析

上文已分別介紹BMT圖劃分策略、約束規(guī)劃求解最大團(tuán)方法、任務(wù)運(yùn)行時間預(yù)測模型等。估算運(yùn)行時間模型決定分割的次數(shù)和深度,各計算節(jié)點通過約束規(guī)劃求解提高最大團(tuán)識別準(zhǔn)確度,任務(wù)運(yùn)行時間預(yù)測模型嚴(yán)格控制集群負(fù)載均衡。融合并行約束規(guī)劃的最大團(tuán)識別算法流程如圖4所示。

圖4 最大團(tuán)識別算法流程

本文算法主要包括BMT圖劃分算法、約束規(guī)劃最大團(tuán)求解算法和時間預(yù)測算法。BMT圖劃分算法將復(fù)雜圖分割為簡單圖,方便約束規(guī)劃求解。首先,讀取數(shù)據(jù)集,得到圖信息并以鄰接表Vertex[]的形式存放。然后,對圖數(shù)據(jù)進(jìn)行分割,劃分后的子圖數(shù)據(jù)存放到一個全局變量list中。在分割過程中,調(diào)用時間模型控制負(fù)載均衡,根據(jù)式(3)的分割方法進(jìn)行多深度圖分割。Choco約束規(guī)劃求解最大團(tuán)主要包括問題定義、變量取值范圍描述和約束條件限定。算法偽代碼具體如下:

/*圖劃分函數(shù)*/

1.funcition BMCpartiton(G)

2.GrpahList= {}

3.n=6;/*機(jī)器數(shù)目*/

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

/*約束規(guī)劃函數(shù)*/

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);

/*負(fù)載均衡函數(shù)*/

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 實驗結(jié)果與對比分析

本文實驗的環(huán)境為青云公有云計算平臺[20]。單機(jī)環(huán)境是選擇一臺處理器為4核、運(yùn)行內(nèi)存16 GB的主機(jī)。集群環(huán)境是選擇SparkMR集群,Spark版本為1.6.0,配置為4核16 GB內(nèi)存,包含1個主節(jié)點、6個從節(jié)點。

本文實驗數(shù)據(jù)來源于國際通用的DIMACS基準(zhǔn)圖例庫[21]。DIMACS基準(zhǔn)圖為最大團(tuán)算法的測試提供了統(tǒng)一標(biāo)準(zhǔn),該組圖例是進(jìn)行最大團(tuán)研究的標(biāo)準(zhǔn)圖例,包括頂點數(shù)從125到1 500的不同密度圖數(shù)據(jù)。

3.1 任務(wù)運(yùn)行時間預(yù)測模型的準(zhǔn)確性評價

在擬合實驗中,采用1stOpt數(shù)學(xué)優(yōu)化分析綜合工具軟件,設(shè)置擬合公式和參數(shù)。輸入數(shù)據(jù)包括不同的圖頂點數(shù)、圖密度以及由實際應(yīng)用得出的圖例約束規(guī)劃求解運(yùn)行時間,通過非線性回歸計算,輸出擬合公式中的參數(shù)值和擬合效果圖,如圖5所示,其中相關(guān)系數(shù)R= 0.988 3。

圖5 任務(wù)運(yùn)行時間預(yù)測值與實測值的擬合效果

3.2 BMT與BMC算法的圖劃分結(jié)果對比與分析

在圖劃分對比實驗中,比較本文BMT圖劃分算法與文獻(xiàn)[11]的BMC圖劃分算法,在多層圖分割中產(chǎn)生的子圖數(shù)目和最大子圖頂點數(shù)目變化情況。實驗數(shù)據(jù)為DIMACS基準(zhǔn)圖中的C125.9、C250.9和C500.9,其中,depth代表圖分割次數(shù),n代表子圖數(shù)目,v代表最大子圖頂點數(shù)目,實驗結(jié)果如表2所示。

表2 圖劃分算法實驗結(jié)果比較

從實驗結(jié)果可知,相比于BMC圖劃分算法,由于圖分割策略不同,在第一次分割后,本文BMT圖劃分算法產(chǎn)生的子圖數(shù)目遠(yuǎn)小于BMC算法產(chǎn)生的子圖數(shù)目,最大子圖頂點數(shù)目大于BMC算法產(chǎn)生的最大子圖頂點數(shù)目。其原因在于圖數(shù)據(jù)中所選圖例密度均為0.9,屬于高密度圖,而隨著圖密度的增大,圖中沒有邊相連的頂點數(shù)目減少,因此,在第一次分割后,兩種算法子圖數(shù)目相差較懸殊。但隨著圖分割深度的增加,子圖數(shù)目差距逐步減少。而且在大多數(shù)情況下,經(jīng)過3次分割后,本文算法得到的子圖數(shù)目和最大子圖頂點數(shù)目均小于BMC圖劃分方法。由此可知,本文算法能夠在確保結(jié)果準(zhǔn)確的前提下有效減少子圖數(shù)目,更快地得出最大團(tuán)關(guān)系相互獨立的子圖,降低搜索空間,提高求解效率。

3.3 BMT與BMC算法的并行求解效率對比與分析

在并行算法效率對比實驗中,圖例數(shù)據(jù)包括c1000.9、c2000.9、phat1500-2、C250.9和brock400_2。在不同集群規(guī)模下,比較兩種算法在加速比和求解效率方面的差異。

將本文中的加速比定義為同一個任務(wù)在單處理器系統(tǒng)和并行處理器系統(tǒng)中運(yùn)行消耗的時間比率,用來衡量并行系統(tǒng)或程序并行化的性能和效果。計算公式如下:

(6)

其中,SP是加速比,T1是單處理器下的運(yùn)行時間,TP是在有P個處理器下的運(yùn)行時間。

不同集群規(guī)模下運(yùn)行時間比較如表3所示。其中,“—”表示單個處理器,因此無加速比。從表3中數(shù)據(jù)可以看出,本文BMT算法在求解效率和并行加速比方面均明顯優(yōu)于BMC圖劃分算法。由于多層分割后,本文算法得到的子圖數(shù)目、最大子圖頂點數(shù)目均少于BMC算法,因此在求解效率上優(yōu)于BMC算法。

表3 不同集群規(guī)模下運(yùn)行時間比較

同時,從表3數(shù)據(jù)可知,在處理器數(shù)量為1、3、6的情況下,不同基準(zhǔn)圖得到的加速比不同。對于小規(guī)模基準(zhǔn)圖,如C250.9、brock400_2,并行算法的加速比受集群規(guī)模變化的影響不大。相比于較大規(guī)?；鶞?zhǔn)圖,加速比受集群規(guī)模變化的影響較大。由此可知,無論對于何等規(guī)模的數(shù)據(jù),處理過程中不可避免需要進(jìn)行數(shù)據(jù)傳輸,都會產(chǎn)生通信時間。對于小規(guī)模基準(zhǔn)圖,通信時間對算法的加速比影響更大。所以,對于大規(guī)模的數(shù)據(jù),采用并行處理能夠明顯縮短運(yùn)行時間,提高求解效率,但是對于較小規(guī)模的數(shù)據(jù),并不適合進(jìn)行并行處理。實驗結(jié)果表明,本文提出的基于約束規(guī)劃的最大團(tuán)并行求解算法能夠有效提高復(fù)雜圖例中的最大團(tuán)識別效率,具有較好的靈活性。

4 結(jié)束語

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