大規(guī)模圖數(shù)據(jù)劃分算法綜述*

許金鳳，董一鴻，王詩懿，何賢芒，陳華輝

（寧波大學(xué)信息科學(xué)與工程學(xué)院 寧波 315211）

* 國家自然科學(xué)基金資助項(xiàng)目(No.61202007)，寧波市自然科學(xué)基金資助項(xiàng)目(No.2013A610063)

1 引言

近年來，隨著互聯(lián)網(wǎng)的普及，網(wǎng)絡(luò)用戶數(shù)快速增加。據(jù)CNNIC統(tǒng)計(jì)，全球最大的社交網(wǎng)絡(luò)Facebook目前已有近10億用戶。如果將用戶看作圖中的頂點(diǎn)，而用戶與用戶之間的關(guān)系看作圖中的邊，那么整個(gè)網(wǎng)絡(luò)就可看作一張網(wǎng)絡(luò)圖。隨著網(wǎng)絡(luò)中用戶規(guī)模的不斷擴(kuò)大，與之對應(yīng)的網(wǎng)絡(luò)圖動輒有數(shù)十億個(gè)頂點(diǎn)和上萬億條邊，普通的計(jì)算機(jī)由于內(nèi)存的限制無法正常處理，這給常見的圖計(jì)算 （如尋找連通分量、計(jì)算三角形和pagerank）帶來了巨大挑戰(zhàn)。解決這一問題的最好方法就是分布式計(jì)算，即將大規(guī)模圖數(shù)據(jù)劃分成多個(gè)子圖裝載到分區(qū)中，利用大型的分布式系統(tǒng)進(jìn)行處理。為了提高不同分區(qū)間的并行速度需要使這些子圖的規(guī)模均衡，同時(shí)減少通信開銷，所以不同分區(qū)之間相連的邊數(shù)應(yīng)當(dāng)足夠小?；谶@個(gè)因素，圖劃分的工作就顯得非常迫切和必要。

國內(nèi)外對圖劃分及其相關(guān)問題進(jìn)行了廣泛深入的研究，主要包括2個(gè)方面。

（1）集中式圖劃分算法

集中式圖劃分算法已經(jīng)研究了相當(dāng)長一段時(shí)間，它可以處理頂點(diǎn)數(shù)和邊數(shù)不是很多的圖，已有的算法包括局部改進(jìn)圖劃分算法和全局圖劃分算法，其中局部改進(jìn)圖劃分算法比較經(jīng)典的是KL(Kernighan-Lin)算法[1]和FM(Fiduccia-Mattheyses)算法[2]；全局圖劃分算法比較經(jīng)典的是Laplace圖特征值譜二分法[3]和多層圖劃分算法[4]。這些算法具有較高的時(shí)間復(fù)雜度，無法處理頂點(diǎn)數(shù)為百萬以上的圖，因此這些算法不適用于現(xiàn)實(shí)生活中大規(guī)模的圖處理。

（2）分布式圖劃分算法

分布式圖劃分算法是針對近些年出現(xiàn)的大規(guī)模網(wǎng)絡(luò)圖而研究的，本文將已有的算法分為靜態(tài)圖劃分算法和動態(tài)圖劃分算法，其中靜態(tài)圖劃分算法的工作比較多，主要包括散列劃分、BHP算法[5]、靜態(tài) Mizan算法[6]、BLP算法[7]等；動態(tài)圖劃分算法經(jīng)典的主要包括動態(tài)Mizan算法[8]和xDGP 算法[9]等。

本文將詳細(xì)闡述分布式圖劃分算法，分析它們的性能特點(diǎn)并做出比較，從而總結(jié)出各個(gè)算法的優(yōu)勢與不足，同時(shí)展望圖劃分算法未來的發(fā)展方向，使讀者能系統(tǒng)而全面地了解圖劃分領(lǐng)域的研究狀況與發(fā)展趨勢。

2 圖劃分定義和評價(jià)指標(biāo)

定義1 交互邊。一對互為鄰居的頂點(diǎn)，它們被劃分到不同的子圖中，它們的邊稱為交互邊。

定義2 圖劃分。給定圖G(V，E)，正整數(shù)k，將頂點(diǎn)集V劃分為互不相交的k個(gè)集合V1,V2,…,Vk。

圖劃分方法需要滿足兩個(gè)主要原則：子圖與子圖之間相連的邊數(shù)盡量小，即交互邊數(shù)少；二是子圖與子圖的規(guī)模應(yīng)當(dāng)相差不大，即負(fù)載均衡。其滿足以下條件。

（2）交互邊數(shù)盡量少。該圖劃分問題的優(yōu)化策略是在保證分區(qū)負(fù)載均衡的前提下，最小化交互邊總數(shù)。

針對以上兩個(gè)原則，定義了評價(jià)函數(shù)[10]：

其中，P=(V1,…,Vk)，表示頂點(diǎn)集的一個(gè)劃分，墜e(P)表示所有分區(qū)間總的交互邊，λ是一個(gè)大于或等于1的常量，n為總負(fù)載。根據(jù)原則（1）（負(fù)載均衡），理想情況下應(yīng)是|Vi|=n/k，考慮到實(shí)際情況應(yīng)加一個(gè)參數(shù)λ。根據(jù)原則（2）（交叉邊最少），即

3 大規(guī)模圖數(shù)據(jù)的圖劃分

隨著互聯(lián)網(wǎng)的普及，圖數(shù)據(jù)的規(guī)模日趨龐大，如Web圖數(shù)據(jù)至少有1萬億的鏈接，Twitter有超過4 000萬的用戶和15億的社交鏈接等。這些不可預(yù)測的大規(guī)模圖數(shù)據(jù)給圖計(jì)算帶來了嚴(yán)峻的挑戰(zhàn)。解決這問題的最好方法就是分布式計(jì)算，即將大規(guī)模圖數(shù)據(jù)劃分成多個(gè)子圖裝載到分區(qū)中，然后利用大型的分布式系統(tǒng)來處理它們。

3.1 大規(guī)模圖數(shù)據(jù)劃分算法的難點(diǎn)

大規(guī)模圖數(shù)據(jù)劃分的不平衡因素主要有3個(gè)源頭：圖結(jié)構(gòu)、算法本身和動態(tài)圖。圖結(jié)構(gòu)分為兩類，冪律圖和非冪律圖。冪律圖是小部分頂點(diǎn)的度很高，大部分頂點(diǎn)的度很低。圖1顯示了3種最常見的劃分算法（基于散列劃分、基于范圍劃分、最小割劃分[11]）在不同圖數(shù)據(jù)上的運(yùn)行結(jié)果，結(jié)果表示沒有任何一種算法適用于所有圖。所以要設(shè)計(jì)一個(gè)針對所有圖都有效的劃分算法并不容易。

圖1 運(yùn)行時(shí)間[8]

第二種不平衡因素是算法本身，一部分算法會在運(yùn)行過程中影響計(jì)算節(jié)點(diǎn)間的負(fù)載均衡。參考文獻(xiàn)[10]根據(jù)超步間通信特點(diǎn)將算法分為動態(tài)算法和靜態(tài)算法。在靜態(tài)算法中，每個(gè)超步的活動節(jié)點(diǎn)接收和發(fā)送的消息是相同的，既沒有增加或減少邊，輸入和輸出也都是相同的地址（圖的結(jié)構(gòu)不變），例如pagerank、直徑評估、尋找連通分量等。動態(tài)算法是輸出消息的大小和目標(biāo)地址一直在變，如分布式最小生成樹（DMST）、圖查詢（如 top k問題）、廣告推薦等，在每個(gè)超步中，這些變化都會產(chǎn)生負(fù)載不平衡影響系統(tǒng)效率。圖2顯示了不同算法運(yùn)行時(shí)接收消息的變化趨勢，Total為總的消息數(shù)，Max是此刻最大的消息數(shù)。由此可見，要設(shè)計(jì)一個(gè)針對所有算法都有效的劃分算法是非常困難。

第三個(gè)不平衡的來源是動態(tài)圖。很多在線應(yīng)用如Facebook、Skype和Twitter等需要實(shí)時(shí)響應(yīng)。它們每時(shí)每刻都會產(chǎn)生新用戶或者刪除舊用戶，圖的拓?fù)浣Y(jié)構(gòu)就會隨時(shí)改變，這種圖稱為動態(tài)圖。如何有效地處理動態(tài)圖是一個(gè)具有挑戰(zhàn)性的新問題。如圖3所示，其中HSH是散列取模算法，DGT[12]是一種圖流算法，ADP[9]是動態(tài)圖劃分算法。隨著圖拓?fù)浣Y(jié)構(gòu)一直變化，可看出靜態(tài)或者圖流算法的劃分質(zhì)量一直在惡化，而動態(tài)圖劃分算法性能變化不大，因此需要設(shè)計(jì)一個(gè)好的動態(tài)圖算法來解決以上3個(gè)不平衡來源。

圖2 消息數(shù)量[8]

圖3 不同算法隨著時(shí)間的推移的邊割變化[9]

3.2 大規(guī)模圖的計(jì)算模型（MapReduce模型和BSP模型）

常見的高性能分布式的計(jì)算模型主要有MapReduce模型和BSP模型。

MapReduce[13]是目前大規(guī)模數(shù)據(jù)環(huán)境中最廣泛使用的模型。MapReduce使用經(jīng)典的“分而治之”策略，將對大規(guī)模數(shù)據(jù)集的操作，分發(fā)給一個(gè)主節(jié)點(diǎn)管理下的各個(gè)分節(jié)點(diǎn)共同完成，然后將各個(gè)分節(jié)點(diǎn)的中間結(jié)果融合在一起，得到最后結(jié)果。Hadoop[14]和HOP系統(tǒng)[15]都是基于MapReduce模型的分布式并行處理系統(tǒng)，它可以應(yīng)用于各種大規(guī)模數(shù)據(jù)處理，由于Hadoop不適用于迭代，很多研究者優(yōu)化改進(jìn)了 Hadoop 平臺，如 HaLoop[16]、Twister[17]、Prlter[18]。BSP（bulk synchronous parallel model）[19]是 Valiant早在 1990 年就提出來的一種基于消息傳遞的并行執(zhí)行模型。計(jì)算由一系列超步組成，每個(gè)超步的最后均有一個(gè)全局同步機(jī)制，它的優(yōu)點(diǎn)就是可以避免死鎖和數(shù)據(jù)競爭問題?；贐SP模型最著名的就是Pregel[20]平臺。它是Google為了滿足圖迭代計(jì)算而提出來的分布式并行處理系統(tǒng)。由于Pregel不開源，Yahoo提出了Pregel的開源版本：Giraph[21]。

大數(shù)據(jù)環(huán)境下主要采用以上兩種模型實(shí)現(xiàn)大規(guī)模圖處理，MapReduce主要針對大數(shù)據(jù)的分布式處理，而圖數(shù)據(jù)具有一些獨(dú)有的特點(diǎn)，如點(diǎn)與點(diǎn)之間的關(guān)系。BSP模型是基于消息傳遞的，它處理圖計(jì)算有著如下優(yōu)點(diǎn)。

·極少的磁盤讀寫，因?yàn)橹挥凶罱K結(jié)果才會寫到磁盤上。而MapReduce的串行任務(wù)之間以磁盤和數(shù)據(jù)復(fù)制作為交換介質(zhì)和接口，所以需要頻繁地讀寫磁盤，導(dǎo)致I/O開銷很大。

·用消息傳遞機(jī)制代替了迭代計(jì)算模型，每次迭代每個(gè)頂點(diǎn)獨(dú)立地計(jì)算狀態(tài)，只傳遞更新狀態(tài)需要的消息，而MapReduce需要對全體數(shù)據(jù)進(jìn)行復(fù)制傳遞。

·改善了數(shù)據(jù)局部性，頂點(diǎn)的所有信息基本上在同一分區(qū)里。

BSP模型避免了MapReduce模型頻繁地讀寫磁盤和數(shù)據(jù)混亂，其獨(dú)有的全局同步機(jī)制，使迭代處理更加方便靈活，更適用于大規(guī)模圖處理。

3.3 大規(guī)模圖數(shù)據(jù)的靜態(tài)圖劃分方法

大規(guī)模圖劃分的靜態(tài)算法典型的有散列算法、BHP算法、靜態(tài)Mizan算法和BLP算法，這些算法的特點(diǎn)是圖的結(jié)構(gòu)不變，沒有頂點(diǎn)添加和刪除，不需要實(shí)時(shí)響應(yīng)。

3.3.1 散列劃分

最經(jīng)典的大規(guī)模圖劃分算法是散列劃分，即每個(gè)頂點(diǎn)首先賦予唯一的ID號，將圖的頂點(diǎn)散列劃分到相應(yīng)的分區(qū)中。采用散列方法進(jìn)行圖劃分的優(yōu)勢在于簡單且易于實(shí)現(xiàn)，不需要額外的開銷，負(fù)載是均衡的。但是散列方法沒有考慮到圖的內(nèi)部結(jié)構(gòu)，頂點(diǎn)會被隨機(jī)地劃分到分區(qū)中，這樣分區(qū)與分區(qū)之間的交互邊會很大，會產(chǎn)生巨大的通信開銷。

3.3.2 BHP算法

BHP算法保留了傳統(tǒng)散列算法的優(yōu)點(diǎn)，將實(shí)際分區(qū)劃分成多個(gè)虛擬桶，通過重組虛擬桶來減少分區(qū)間邊割。BHP算法首先確定虛擬桶的數(shù)量t（t是分區(qū)數(shù)的倍數(shù)），然后將t個(gè)虛擬桶重組為k個(gè)，方法是：如果虛擬桶到某個(gè)實(shí)際分區(qū)的出邊數(shù)與該虛擬桶總邊數(shù)的比值超過一定的閾值，則將該虛擬桶歸屬到這個(gè)實(shí)際分區(qū)。在重組過程中通過貪婪算法保證每個(gè)分區(qū)的數(shù)據(jù)量均衡。由于一個(gè)分區(qū)只能分配給一個(gè)任務(wù)，根據(jù)該實(shí)際分區(qū)上的數(shù)據(jù)來自哪個(gè)任務(wù)最多，就將這個(gè)實(shí)際分區(qū)交由這個(gè)任務(wù)執(zhí)行。數(shù)據(jù)的本地化一定程度上降低了通信開銷。BHP算法和散列算法差不多，都沒有考慮圖的內(nèi)部結(jié)構(gòu)，沒有挖掘圖內(nèi)部“團(tuán)”結(jié)構(gòu)。

3.3.3 靜態(tài)Mizan算法

針對Mapreduce框架效率低的問題，靜態(tài)Mizan算法采用了類似Pregel的框架，分析了Pregel框架不考慮圖的結(jié)構(gòu)性的缺陷。將圖分為冪律圖和非冪律圖。對于冪律圖，實(shí)現(xiàn)了Mizan-α。對于非冪律圖，實(shí)現(xiàn)了Mizan-γ。

（1）Mizan-α

對于冪律圖，圖中小部分頂點(diǎn)的度很高，大部分頂點(diǎn)的度很低，肯定不適合散列劃分，因?yàn)樯⒘袆澐譀]有考慮到邊的局部性，即圖的內(nèi)部結(jié)構(gòu)，而最小割算法有很好的劃分，可以最小化分區(qū)間的邊數(shù)。但是計(jì)算最小割是一個(gè)NP難問題，所以使用并行圖劃分工具ParMETIS。對于冪律圖雖然最小割的開銷很大，但是它帶來的效益好。

（2）Mizan-γ

最小割劃分不適用于非冪律圖，因?yàn)樗鼛淼拈_銷比帶來的效益大。對于非冪律圖使用任意隨機(jī)劃分，這樣預(yù)處理沒有開銷，但是分區(qū)間的邊割數(shù)會很多。如果繼續(xù)使用點(diǎn)對點(diǎn)消息傳遞，那么通信開銷將會很大，針對非冪律圖的特點(diǎn)，消息傳遞采用虛擬覆蓋環(huán)。如分區(qū)PE1，PE2，…，PEm，將它們組成虛擬環(huán)：PE1→PE2→…PEm-1→PEm→PE1，每個(gè)PE從它的前驅(qū)接收消息，發(fā)送給它的后繼。每個(gè)消息M都要進(jìn)入環(huán)，它們沒有具體的目的地PE，需要此消息的分區(qū)會接收它。虛擬覆蓋環(huán)從以下兩個(gè)方面降低了開銷：減少了物理鏈路上消息傳遞的數(shù)量；每個(gè)分區(qū)PE僅需要兩條鏈路，前驅(qū)和后繼，而點(diǎn)對點(diǎn)需要多個(gè)鏈路導(dǎo)致高CPU開銷。

靜態(tài)Mizan算法對冪律圖采用parMetis劃分，雖然考慮了邊的局部性，但是最小割劃分的時(shí)間開銷很大，不適用于很大的圖。非冪律圖使用隨機(jī)劃分和虛擬覆蓋環(huán)來傳遞消息，虛擬覆蓋環(huán)消息傳遞機(jī)制會帶來時(shí)延，因?yàn)楹芏嘞⒌竭_(dá)目的地之前需要傳遞整個(gè)環(huán)。

3.3.4 BLP算法

BLP算法是將標(biāo)簽傳遞算法應(yīng)用到圖劃分上，將凹優(yōu)化問題轉(zhuǎn)化為線性規(guī)劃問題，在保證分區(qū)均衡的情況下，很好地減少了分區(qū)間交互邊。

首先將圖頂點(diǎn)隨機(jī)劃分到分區(qū)中。由于某些分區(qū)的訪問很頻繁，所以通過頂點(diǎn)轉(zhuǎn)移再定位，轉(zhuǎn)移那些最有增益的節(jié)點(diǎn)。比如頂點(diǎn)u初始化到分區(qū)i，由于它在分區(qū)j上的鄰居比本地多，根據(jù)規(guī)則將會被分到分區(qū)j，頂點(diǎn)u在本地的鄰居數(shù)就會增加，形成頂點(diǎn)的增益。每次迭代將要轉(zhuǎn)移的k個(gè)頂點(diǎn)按照增益進(jìn)行降序排序，表示從分區(qū)i轉(zhuǎn)到分區(qū)j的第k個(gè)頂點(diǎn)的增益。表示從分區(qū)i轉(zhuǎn)移x個(gè)頂點(diǎn)到分區(qū)j的總的增益函數(shù)由于增益是降序的，所以增益函數(shù)是遞增的凹函數(shù)。將這個(gè)問題轉(zhuǎn)化為線性規(guī)劃問題：

xij是指從分區(qū)i轉(zhuǎn)移到分區(qū)j的頂點(diǎn)數(shù)。假設(shè)圖G有一個(gè)固定的度，目標(biāo)函數(shù)是一個(gè)線性分段凹函數(shù)，根據(jù)參考文獻(xiàn)[22]將其轉(zhuǎn)化為線性規(guī)劃問題。算法迭代過程如下。

（1）確定每個(gè)頂點(diǎn)是否進(jìn)行轉(zhuǎn)移，并確定每個(gè)頂點(diǎn)的增益。

（2）對頂點(diǎn)增益進(jìn)行排序。

（3）解線性規(guī)劃，決定分區(qū)間應(yīng)該轉(zhuǎn)移多少頂點(diǎn)。

（4）轉(zhuǎn)移這些頂點(diǎn)。

BLP算法解決了標(biāo)簽傳遞算法應(yīng)用到圖劃分上的難題（分區(qū)大小約束），它將一個(gè)最大凹優(yōu)化問題轉(zhuǎn)化為線性規(guī)劃問題，既保證了分區(qū)平衡，又保證了邊的局部性。但線性規(guī)劃的時(shí)間復(fù)雜度高，每次迭代都需要解線性規(guī)劃問題。BLP算法適用于靜態(tài)圖分區(qū)，因?yàn)轫旤c(diǎn)的變化，就需要重新設(shè)計(jì)和計(jì)算線性規(guī)劃函數(shù)。

3.4 大規(guī)模圖數(shù)據(jù)的動態(tài)圖劃分算法

很多場合需要實(shí)時(shí)響應(yīng)，例如在線應(yīng)用Facebook、Skype和Twitter。它們每時(shí)每刻都會產(chǎn)生新用戶或者刪除用戶，圖的拓?fù)浣Y(jié)構(gòu)就會隨時(shí)改變，這種圖稱為動態(tài)圖。如何有效地處理動態(tài)圖是一個(gè)具有挑戰(zhàn)的新問題。通常一段時(shí)間過后，其他靜態(tài)算法和圖流算法的劃分性能都快速降低，這樣就需要重劃分整個(gè)圖，導(dǎo)致很大的計(jì)算開銷。下面介紹的兩個(gè)動態(tài)算法都是通過轉(zhuǎn)移頂點(diǎn)來進(jìn)行圖劃分的，動態(tài)Mizan算法主要是為了負(fù)載均衡，而xDGP算法主要是為了減少分區(qū)間邊割，類似的還有GPS算法[23]和x-pregel[24]算法。

3.4.1 動態(tài)Mizan算法

由于算法本身具有動態(tài)性，頻繁改變圖結(jié)構(gòu)，通信需求不可預(yù)測。動態(tài)Mizan算法監(jiān)視頂點(diǎn)運(yùn)行時(shí)的特點(diǎn)，檢查計(jì)算節(jié)點(diǎn)負(fù)載是否均衡，如果不均衡，每次迭代通過轉(zhuǎn)移頂點(diǎn)來平衡計(jì)算節(jié)點(diǎn)間的負(fù)載。

動態(tài)Mizan算法是一個(gè)基于BSP模型的圖處理系統(tǒng)，采用散列對圖進(jìn)行初始劃分，在所有計(jì)算節(jié)點(diǎn)間動態(tài)實(shí)現(xiàn)負(fù)載均衡。該算法監(jiān)視每個(gè)頂點(diǎn)的3個(gè)主要信息。

·頂點(diǎn)輸出遠(yuǎn)程消息數(shù)，即頂點(diǎn)向不同計(jì)算節(jié)點(diǎn)的鄰居發(fā)送的消息數(shù)。

·頂點(diǎn)輸入消息。

·頂點(diǎn)執(zhí)行時(shí)間，頂點(diǎn)開始處理輸入消息到結(jié)束的時(shí)間段。每個(gè)計(jì)算節(jié)點(diǎn)保存一個(gè)高度濃縮這些信息的版本，簡稱高縮信息。

頂點(diǎn)的3個(gè)主要信息中任何一個(gè)值很高都可能表示頂點(diǎn)有很差的布局，這就需要尋找造成負(fù)載不平衡的原因并轉(zhuǎn)移部分頂點(diǎn)。轉(zhuǎn)移時(shí)間是在一個(gè)超步結(jié)束之后，下一個(gè)超步開始之前，如圖4所示。轉(zhuǎn)移計(jì)劃分為以下5步。

（1）根據(jù)高縮信息，確定不平衡的來源，即確定此超步中哪個(gè)計(jì)算節(jié)點(diǎn)不均衡。

（2）利用關(guān)聯(lián)度公式選擇轉(zhuǎn)移對象。

（3）每個(gè)計(jì)算節(jié)點(diǎn)根據(jù)第（2）步確定的轉(zhuǎn)移對象創(chuàng)建一個(gè)有序列表，將負(fù)載大的計(jì)算節(jié)點(diǎn)A與負(fù)載小的計(jì)算節(jié)點(diǎn)B匹配，頂點(diǎn)轉(zhuǎn)移時(shí)就將節(jié)點(diǎn)A上的頂點(diǎn)轉(zhuǎn)移到頂點(diǎn)B上。

（4）選擇頂點(diǎn)轉(zhuǎn)移，轉(zhuǎn)移頂點(diǎn)的數(shù)量是由被匹配的計(jì)算節(jié)點(diǎn)的轉(zhuǎn)移對象的差距決定的。

（5）計(jì)算節(jié)點(diǎn)將選擇的頂點(diǎn)轉(zhuǎn)移到目的節(jié)點(diǎn)，每個(gè)頂點(diǎn)編碼成流（頂點(diǎn)ID、狀態(tài)、邊信息、接收的信息），轉(zhuǎn)移頂點(diǎn)（在BSP同步之后又指定轉(zhuǎn)移同步）。

圖4 Mizan的BSP轉(zhuǎn)移模型[10]

實(shí)現(xiàn)分布式頂點(diǎn)轉(zhuǎn)移有三大難題。

·維護(hù)頂點(diǎn)所有權(quán)，使得頂點(diǎn)自由地在計(jì)算節(jié)點(diǎn)間轉(zhuǎn)換，提出了DHT（分布式散列表）來實(shí)現(xiàn)分布式查找頂點(diǎn)位置。DHT 存儲的是鍵值對（key，value），key代表的是頂點(diǎn)ID，value代表的是頂點(diǎn)當(dāng)前物理位置，存放在固有節(jié)點(diǎn)上（每個(gè)頂點(diǎn)有唯一一個(gè)節(jié)點(diǎn)存放它的最新位置）。

·當(dāng)頂點(diǎn)轉(zhuǎn)移后要快速更新頂點(diǎn)所有權(quán)信息，當(dāng)頂點(diǎn)轉(zhuǎn)移后，目標(biāo)計(jì)算節(jié)點(diǎn)將該頂點(diǎn)的新位置發(fā)送給該頂點(diǎn)的固有節(jié)點(diǎn)。

·通過延遲頂點(diǎn)轉(zhuǎn)移來最小化頂點(diǎn)轉(zhuǎn)移開銷。

3.4.2 xDGP算法

由于動態(tài)圖結(jié)構(gòu)一直變化，如果分區(qū)不更新的話，額外的通信開銷和不平衡的分區(qū)使得性能不斷降低。為了適應(yīng)圖結(jié)構(gòu)變化，xDGP算法根據(jù)局部信息提出了迭代頂點(diǎn)轉(zhuǎn)移算法，分區(qū)間的頂點(diǎn)轉(zhuǎn)移目的是最小化邊割，同時(shí)也需要在結(jié)構(gòu)變化的情況下分區(qū)容量不溢出。如圖3所示，其中HSH是散列取模算法，DGT是一種圖流算法，ADP是xDGP算法。隨著圖結(jié)構(gòu)一直變化，靜態(tài)或者圖流算法的劃分質(zhì)量一直在惡化。

（1）貪婪頂點(diǎn)轉(zhuǎn)移

采用散列初始化分區(qū)，再使用貪婪啟發(fā)式方法進(jìn)行重劃分。比如一個(gè)頂點(diǎn)添加后，根據(jù)散列取模將其劃分到一個(gè)分區(qū)，啟發(fā)式方法將該頂點(diǎn)轉(zhuǎn)移到它的鄰居數(shù)最多的那個(gè)分區(qū)上，即每次迭代頂點(diǎn)將決定去具有鄰居數(shù)最多的那個(gè)分區(qū)。頂點(diǎn)只要知道它的鄰居位置就可以選擇分區(qū)，在實(shí)際系統(tǒng)中這個(gè)信息是可知的，因?yàn)槊看蔚臅r(shí)候頂點(diǎn)向它的鄰居發(fā)送消息。

（2）分區(qū)容量限制

對于一個(gè)分區(qū)來說，每次迭代有很多頂點(diǎn)從不同分區(qū)轉(zhuǎn)移進(jìn)來，容量很可能超過分區(qū)原本的容量。算法為每個(gè)分區(qū)設(shè)置一個(gè)容量限制，每次迭代分區(qū)的使用容量不得超過分區(qū)的最大容量，將分區(qū)的剩余容量均分。這種方法減少了轉(zhuǎn)移的頂點(diǎn)數(shù)，在實(shí)際的系統(tǒng)中有一定的影響，轉(zhuǎn)移頂點(diǎn)的開銷很大，頂點(diǎn)數(shù)轉(zhuǎn)移過多會造成瓶頸，因此一定量的頂點(diǎn)轉(zhuǎn)移會保證每次迭代的額外開銷。

（3）確保收斂

轉(zhuǎn)移決策的獨(dú)立性會影響啟發(fā)式方法的收斂，局部對稱性會導(dǎo)致無效的轉(zhuǎn)移，一對互為鄰居的頂點(diǎn)，在同一次迭代中，兩頂點(diǎn)可能相互轉(zhuǎn)移到對方的分區(qū)中。該算法采用一個(gè)隨機(jī)函數(shù)來決定是否轉(zhuǎn)移，每次迭代時(shí)每個(gè)頂點(diǎn)轉(zhuǎn)移的概率為s(0

3.5 性能歸納

綜上所述，大規(guī)模圖數(shù)據(jù)的劃分算法中，散列算法的優(yōu)點(diǎn)是負(fù)載均衡，算法簡單易實(shí)現(xiàn)且易確定頂點(diǎn)位置。但是它打破了圖的內(nèi)部結(jié)構(gòu)，導(dǎo)致分區(qū)間的邊割較多，通信開銷很大，一般用作初始劃分。BHP和靜態(tài)Mizan可以作為圖的預(yù)處理，其中BHP算法僅考慮負(fù)載均衡，沒有考慮到圖的拓?fù)浣Y(jié)構(gòu)，通信開銷沒有優(yōu)化，靜態(tài)Mizan算法是針對不同的圖，采用不同的劃分策略。對冪率圖使用最小割劃分，最小割的代價(jià)很大，一般圖劃分不使用它；對非冪率圖使用虛擬覆蓋環(huán)來傳遞消息，但會帶來時(shí)延，因?yàn)楹芏嘞⒃谟龅剿哪康牡刂靶枰獋鬟f整個(gè)環(huán)，不利于圖的擴(kuò)展性。BLP算法解決了標(biāo)簽傳遞算法應(yīng)用到圖劃分上的難題（分區(qū)大小約束），它將一個(gè)最大凹優(yōu)化問題轉(zhuǎn)化為線性規(guī)劃問題，既保證了分區(qū)平衡，又保證了邊的局部性。但線性規(guī)劃的時(shí)間復(fù)雜度高，每次迭代都需要解線性規(guī)劃問題。BLP算法適用于靜態(tài)圖分區(qū)，因?yàn)樾伦⑷胍恍╉旤c(diǎn)，就需要重新設(shè)計(jì)和計(jì)算線性規(guī)劃函數(shù)。動態(tài)Mizan算法和xDGP算法主要為了解決動態(tài)圖拓?fù)浣Y(jié)構(gòu)隨時(shí)變化而設(shè)計(jì)的。性能方面，xDGP算法優(yōu)于動態(tài)Mizan算法，因?yàn)閯討B(tài)Mizan算法僅僅平衡了各計(jì)算節(jié)點(diǎn)間的負(fù)載而沒有考慮到節(jié)點(diǎn)間邊的局部性，所以通信開銷沒有很好地解決，xDGP則充分考慮了邊的局部性，所以邊割可以達(dá)到局部最優(yōu)，但是它達(dá)不到全局最優(yōu)，且xDGP算法只考慮到不超過每個(gè)分區(qū)的總?cè)萘慷鴽]有考慮到嚴(yán)格意義上的負(fù)載均衡。綜上所述，目前靜態(tài)圖算法最好的是BLP算法，動態(tài)圖算法最好的是xDGP算法。

表1 算法比較

表1對靜態(tài)和動態(tài)大規(guī)模圖劃分算法的性能進(jìn)行了歸納總結(jié)。

4 結(jié)束語

大數(shù)據(jù)時(shí)代的到來，不僅帶來了機(jī)遇，也迎來一系列的困難和挑戰(zhàn)。在社交網(wǎng)絡(luò)日益發(fā)展的今天，集中式環(huán)境下的圖劃分算法已經(jīng)難以適應(yīng)當(dāng)前應(yīng)用的需求，分布式并行環(huán)境下大規(guī)模圖數(shù)據(jù)的劃分算法的研究日益迫切，具有重大的現(xiàn)實(shí)意義。大規(guī)模圖數(shù)據(jù)劃分的研究剛剛起步，未來的研究將在動態(tài)圖、數(shù)據(jù)流圖、有向圖以及帶權(quán)圖和概率圖的并行環(huán)境下進(jìn)行圖的劃分算法的研究，運(yùn)用圖論、機(jī)器學(xué)習(xí)、統(tǒng)計(jì)分析和散列等各種技術(shù)展開，具有極大的挑戰(zhàn)性和現(xiàn)實(shí)意義。

1 Dutt S. New faster kernighan-lin-type graph-partitioning algorithms.IEEE/ACM International Conference on IEEE,Santa Clara,CA,USA,1993:370～377

2 Fiduccia C M,Mattheyses R M.A linear-time heuristic for improving network partitions.19th Conference on IEEE,Las Vegas,NV,USA，1982:175～181

3 Pothen A,Simon H D,Liou K P.Partitioning sparse matrices with eigenvectors of graphs.SIAM Journal on Matrix Analysis and Applications,1990,11(3):430～452

4 Karypis G,Kumar V.A fast and high quality multilevel scheme for partitioning irregular graphs.SIAM Journal on scientific Computing,1998,20(1):359～392

5 周爽，鮑玉斌，王志剛等.BHP：面向BSP模型的負(fù)載均衡Hash圖數(shù)據(jù)劃分.計(jì)算機(jī)科學(xué)與探索,2014,8(1):40～50

6 Kalnis P,Khayyat Z,Awara K,etal.Mizan:optimizing graph mining in large parallel systems.http://www.academia.edu/2601716/Mizan_Optimizing_Graph_Mining_in_Large_Parallel_Systems

7 Ugander J,Backstrom L.Balanced label propagation for partitioning massive graphs.Proceedings of the sixth ACM International Conference on Web Search and Data Mining.ACM,Rome,Italy,2013:507～516

8 Khayyat Z,Awara K,Alonazi A,et al.Mizan:a system for dynamic load balancing in large-scale graph processing.Proceedings of the 8th ACM European Conference on Computer Systems,Prague,Czech Republic,2013

9 Vaquero L,Cuadrado F,Logothetis D,et al.xdgp:a dynamic graph processing system with adaptive partitioning.http://www.researchgate.net/publication/256423219_xDGP_A_Dynamic_Graph_Processing_System_with_Adaptive_Partitioning

10 Tsourakakis C E,Gkantsidis C,Radunovic B,et al.Fennel:Streaming Graph Partitioning for Massive Scale Graphs.Microsoft Technical Report MSR-TR-2012-113,2012

11 Karypis G,Kumar V.Metis-unstructured graph partitioning and sparse matrix ordering system,version 2.0.http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.376

12 Stanton I,Kliot G.Streaming graph partitioning for large distributed graphs.Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Beijing,China,2012

13 Dean J,Ghemawat S.MapReduce:simplified data processing on large clusters.Communications ofthe ACM,2008,51(1):107～113

14 White T.Hadoop:The Definitive Guide.O'Reilly Media,Inc,2012

15 Condie T,Conway N,Alvaro P,et al.MapReduce Online.NSDI 2010,San Jose,USA,2010

16 Bu Y,Howe B,Balazinska M,et al.HaLoop:efficient iterative data processing on large clusters.Proceedings of the VLDB Endowment,2010,3(1-2):285～296

17 Ekanayake J,Li H,Zhang B,et al.Twister:a runtime for iterative MapReduce.Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing,New York,NY,USA,2010

18 Zhang Y,Gao Q,Gao L,et al.Priter:a distributed framework for prioritized iterative computations.Proceedings of the 2nd ACM Symposium on Cloud Computing,San Jose,USA,2011

19 Valiant L G.A bridging model for parallel computation.Communications of the ACM,1990,33(8):103～111

20 Malewicz G,Austern M H,Bik A J C,et al.Pregel:a system for large-scale graph processing.Proceedings of the 2010 ACM SIGMOD International Conference on Management of data,Snowbird,UT,USA,2010:135～146

21 Avery C.Giraph:large-scale graph processing infrastructure on Hadoop.Proceedings of the Hadoop Summit,Santa Clara,USA,2011

22 Boyd S P,Vandenberghe L.Convex Optimization.Cambridge:Cambridge University Press,2004

23 Salihoglu S,Widom J.GPS:A Graph Processing System.Technical Report,Stanford University

24 Bao N T,Suzumura T.Towards highly scalable pregel-based graph processing platform with x10.Proceedings of the 22nd International Conference on World Wide Web Companion,International World Wide Web Conferences Steering Committee,Seoul,Korea,2013:501～508