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

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

研究與開發(fā)

LGP-SA：分布式環(huán)境下基于模擬退火的大規(guī)模圖劃分算法

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

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

針對(duì)大規(guī)模圖數(shù)據(jù)的分布式計(jì)算，首先需要進(jìn)行圖劃分。當(dāng)前大規(guī)模圖劃分方法采用頂點(diǎn)轉(zhuǎn)移策略來減少分區(qū)間的邊割數(shù)以降低通信開銷，但容易陷入局部最優(yōu)，引入模擬退火的方法進(jìn)行頂點(diǎn)轉(zhuǎn)移后，極大地避免了局部最優(yōu)的陷阱，也極大地防止了頂點(diǎn)無效轉(zhuǎn)移，更好地降低了通信開銷。對(duì)比實(shí)驗(yàn)顯示，本算法劃分大規(guī)模圖的邊割率有了極大的改進(jìn)，并用PageRank算法驗(yàn)證了算法的有效性和可行性。

圖劃分；Giraph；模擬退火；大規(guī)模圖；BSP

1 引言

近年來，隨著互聯(lián)網(wǎng)的普及，網(wǎng)絡(luò)中用戶規(guī)模的不斷擴(kuò)大，與之對(duì)應(yīng)的網(wǎng)絡(luò)圖動(dòng)輒有數(shù)十億個(gè)頂點(diǎn)和上萬億條邊。普通的計(jì)算機(jī)由于內(nèi)存的限制無法正常處理，這給常見的圖計(jì)算（如尋找連通分量、計(jì)算三角形和PageRank）帶來了巨大挑戰(zhàn)，解決這個(gè)問題的最好方法就是分布式計(jì)算。為了提高不同分區(qū)間的并行速度，需要使這些子圖的規(guī)模均衡，而且通信開銷要小［1］，因此，大規(guī)模圖劃分的工作就顯得非常迫切和必要。已有的大規(guī)模圖劃分算法為了減少通信開銷主要采用頂點(diǎn)轉(zhuǎn)移策略，即根據(jù)頂點(diǎn)的鄰居所在的分區(qū)將它轉(zhuǎn)移到鄰居數(shù)最多的那個(gè)分區(qū)上，達(dá)到最小邊割的目的。然而，這種頂點(diǎn)轉(zhuǎn)移策略容易陷入局部最優(yōu)的陷阱，并沒有盡量減少通信開銷。

本文針對(duì)傳統(tǒng)頂點(diǎn)轉(zhuǎn)移策略的不足和局限性，提出了基于模擬退火的大規(guī)模圖劃分（large-scale graph partition based on simulated annealing，LGP-SA）算法。該算法在局部轉(zhuǎn)移頂點(diǎn)的過程中引入模擬退火的思想，允許以一定的概率增加分區(qū)間的邊割數(shù)，從而很大程度上避免了局部最優(yōu)的陷阱，并且分析了頂點(diǎn)無效轉(zhuǎn)移的情況，通過限制頂點(diǎn)轉(zhuǎn)移次數(shù)來避免無效轉(zhuǎn)移。本文在大規(guī)模圖數(shù)據(jù)環(huán)境下實(shí)現(xiàn)了LGP-SA算法，它既保證了分區(qū)間負(fù)載均衡又考慮了圖的內(nèi)部結(jié)構(gòu)。通過實(shí)驗(yàn)將LGP-SA算法和其他算法進(jìn)行了比較，實(shí)驗(yàn)結(jié)果顯示了LGP-SA算法的有效性和可行性。

2 相關(guān)工作與Giraph平臺(tái)

2.1 圖劃分定義和相關(guān)工作

圖劃分定義：對(duì)于一個(gè)圖G=（V，E），V代表圖中的頂點(diǎn)集，E代表圖中邊集，P=｛V1，…，Vk}表示將圖劃分成k個(gè)部分，它是頂點(diǎn)的一個(gè)劃分，其中Vi≠，Vi∩Vj=，∪Vi=V，i，j=1，…，k，i≠j。

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

圖劃分算法在圖數(shù)據(jù)處理系統(tǒng)中至關(guān)重要，然而它是一個(gè)NP難問題，集中式圖劃分算法已經(jīng)研究了相當(dāng)長(zhǎng)一段時(shí)間。由于這些算法具有較高的時(shí)間復(fù)雜度，隨著圖數(shù)據(jù)規(guī)模的增大，它們處理時(shí)間增長(zhǎng)得特別快，甚至超過圖計(jì)算的時(shí)間。因此，目前大規(guī)模圖劃分算法基本都是采用簡(jiǎn)單的方法（如散列算法）或者啟發(fā)式方法（如流圖算法）。

從圖劃分目的上主要有兩類，第一類是控制負(fù)載均衡，主要的算法有散列劃分（Giraph［2］、Pregel［3］等）、BHP算法［4］和Mizan算法［5］等，這類算法沒考慮圖的內(nèi)部結(jié)構(gòu)，導(dǎo)致劃分后各分區(qū)間邊割數(shù)量大，因此子圖間的通信開銷大；第二類主要是控制分區(qū)間交互邊，主要的算法有BLP算法［6］、xdgp算法［7］、x-pergel［8］和gps［9］等，這類圖劃分算法一般采用頂點(diǎn)轉(zhuǎn)移策略來降低分區(qū)間的邊割，也就是根據(jù)頂點(diǎn)的鄰居所在的分區(qū)將它轉(zhuǎn)移到鄰居數(shù)最多的那個(gè)分區(qū)上，達(dá)到最小化邊割的目的，從而減小通信開銷，然而它們都是根據(jù)頂點(diǎn)的局部信息來進(jìn)行頂點(diǎn)轉(zhuǎn)移的，因此這種頂點(diǎn)轉(zhuǎn)移策略是貪婪的，容易陷入局部最優(yōu)。但它們的側(cè)重點(diǎn)不同［1］：BLP算法側(cè)重于頂點(diǎn)轉(zhuǎn)移中采用線性規(guī)劃函數(shù)來決定轉(zhuǎn)移頂點(diǎn)數(shù)，每次轉(zhuǎn)移頂點(diǎn)之前都需要建立線性規(guī)劃函數(shù)，時(shí)間效率不高；xdgp側(cè)重點(diǎn)在于動(dòng)態(tài)圖，頂點(diǎn)隨著時(shí)間而加入或刪除，對(duì)圖劃分的效果影響不大，因此也說明了頂點(diǎn)轉(zhuǎn)移策略能夠很好地應(yīng)用在動(dòng)態(tài)圖上；x-pregel側(cè)重點(diǎn)在于無效轉(zhuǎn)移，它是利用時(shí)間代價(jià)來減少無效轉(zhuǎn)移，代價(jià)很大。gps側(cè)重點(diǎn)在于負(fù)載均衡。

這些頂點(diǎn)轉(zhuǎn)移策略［6-9］判斷一個(gè)頂點(diǎn)是否進(jìn)行轉(zhuǎn)移由它的局部信息決定，即將該頂點(diǎn)轉(zhuǎn)移到鄰居數(shù)最多的那個(gè)分區(qū)上。這種頂點(diǎn)轉(zhuǎn)移策略存在兩個(gè)不足：一是由于每次轉(zhuǎn)移僅僅考慮該頂點(diǎn)的鄰居信息，所以會(huì)陷入局部最優(yōu)，對(duì)冪律圖的效果尤其不好；二是因?yàn)樗秦澙匪惴?，所以?huì)出現(xiàn)無效轉(zhuǎn)移，參考文獻(xiàn)［8］提出了共享鄰接表和每次只有一個(gè)worker轉(zhuǎn)移頂點(diǎn)的方法解決這個(gè)問題，共享鄰接表方法耗時(shí)，而每次僅有一個(gè)worker轉(zhuǎn)移則收斂慢，迭代時(shí)間長(zhǎng)。如圖1所示，按照參考文獻(xiàn)［6-9］的頂點(diǎn)轉(zhuǎn)移策略，圖1（a）是一個(gè)原始圖狀態(tài)，按照傳統(tǒng)頂點(diǎn)轉(zhuǎn)移策略則頂點(diǎn)4會(huì)轉(zhuǎn)移出去，因?yàn)樗诒镜胤謪^(qū)的鄰居為0，而在非本地分區(qū)的鄰居為2，形成圖1（b）的狀態(tài)，達(dá)到穩(wěn)定，但這是一個(gè)局部最優(yōu)狀態(tài)，而全局最優(yōu)狀態(tài)（即邊割數(shù)最少的狀態(tài)）如圖1（c）所示。按照傳統(tǒng)的頂點(diǎn)轉(zhuǎn)移策略，只能達(dá)到圖1（b）的局部穩(wěn)定狀態(tài)，無法達(dá)到圖1（c）的全局穩(wěn)定狀態(tài)。而采用本文提出的基于模擬退火的大規(guī)模圖劃分算法將有很大概率達(dá)到圖1（c）的穩(wěn)定狀態(tài)。

圖1 定點(diǎn)轉(zhuǎn)移算法效果對(duì)比

對(duì)于傳統(tǒng)頂點(diǎn)轉(zhuǎn)移策略的第二個(gè)不足，無效轉(zhuǎn)移分為兩種，一種就是一個(gè)頂點(diǎn)轉(zhuǎn)移數(shù)次之后又回到之前的分區(qū)中，這種無效轉(zhuǎn)移稱為“良性”無效轉(zhuǎn)移，它肯定會(huì)發(fā)生，不可避免；第二種無效轉(zhuǎn)移稱為循環(huán)無效轉(zhuǎn)移，即頂點(diǎn)相互來回轉(zhuǎn)移，出現(xiàn)死循環(huán)，不會(huì)停止。如圖2所示，頂點(diǎn)1和頂點(diǎn)4都會(huì)相互轉(zhuǎn)移到對(duì)方的分區(qū)中，當(dāng)然這種情況的頂點(diǎn)數(shù)不多，如圖2（b）中頂點(diǎn)1和頂點(diǎn)4又會(huì)進(jìn)行轉(zhuǎn)移，這樣如此循環(huán)下去，不會(huì)結(jié)束。本文提出的LGP-SA算法主要針對(duì)局部最優(yōu)進(jìn)行解決，在一定程度上緩解了無效轉(zhuǎn)移的產(chǎn)生。

圖2 循環(huán)無效轉(zhuǎn)移

2.2 云計(jì)算平臺(tái)Giraph

Giraph［2］是Pregel［3］的開源，采用BSP（bulk synchronous parallel）模型［10］，BSP模型是Valiant在1990年提出來的一種基于消息傳遞的并行執(zhí)行模型，由一系列超步（superstep）組成，如圖3（a）所示，每個(gè)超步的最后均有個(gè)全局同步機(jī)制，它的優(yōu)點(diǎn)就是可以避免死鎖和數(shù)據(jù)競(jìng)爭(zhēng)問題。超步與超步之間是串行執(zhí)行的，而超步內(nèi)部的本地計(jì)算是并行執(zhí)行的，由worker（工作機(jī)）的數(shù)目決定并行程度。每個(gè)超步包括本地計(jì)算、通信、全局同步3個(gè)階段，是一個(gè)高擴(kuò)展性的交互圖形處理系統(tǒng)。Giraph的基礎(chǔ)結(jié)構(gòu)由ZooKeeper、JobTracker和TaskTracker組成，其中ZooKeeper是用來實(shí)現(xiàn)同步的，而JobTracker就是master節(jié)點(diǎn)（主節(jié)點(diǎn)），TaskTracker是slave節(jié)點(diǎn)（從節(jié)點(diǎn)），每個(gè)slave節(jié)點(diǎn)里面又可以包含多個(gè)worker，如圖3（b）所示。

圖3 Giraph的模型結(jié)構(gòu)和通信流程

Giraph中的同步是通過ZooKeeper來控制的，ZooKeeper分布式服務(wù)框架是Apache Hadoop［11］的一個(gè)子項(xiàng)目，它主要是用來解決分布式應(yīng)用中經(jīng)常遇到的一些數(shù)據(jù)管理問題，在Giraph中主要實(shí)現(xiàn)的是選擇master和超步結(jié)束后的同步。除了超步結(jié)束后的同步，還有很多協(xié)調(diào)worker和master的同步工作，例如檢查worker是否健康、協(xié)調(diào)數(shù)據(jù)剛開始的分片等。master主要是指導(dǎo)worker工作，包括為worker分配數(shù)據(jù)，協(xié)調(diào)同步，收集聚集值，檢查worker是否健康；worker主要執(zhí)行本地計(jì)算，發(fā)送、接收消息。Giraph避免了MapReduce模型頻繁的讀寫磁盤和數(shù)據(jù)混亂，其獨(dú)有的全局同步機(jī)制，使迭代處理更加方便靈活，更適用于大規(guī)模圖處理。

3 基于模擬退火的大規(guī)模圖劃分算法

3.1 LGP-SA算法描述

現(xiàn)有的大規(guī)模圖劃分算法存在分區(qū)間邊割數(shù)無法達(dá)到全局優(yōu)化的缺陷，沒有盡量減小通信開銷。本文將模擬退火算法引入頂點(diǎn)轉(zhuǎn)移策略中，提出了在分布式環(huán)境下的LGP-SA算法，使邊割率達(dá)到近似全局最優(yōu)的效果。在頂點(diǎn)轉(zhuǎn)移的過程中，不僅接受邊割數(shù)下降的頂點(diǎn)轉(zhuǎn)移，也以一定的概率接受導(dǎo)致邊割數(shù)上升的頂點(diǎn)轉(zhuǎn)移，使得分區(qū)間的總邊割數(shù)能逃離局部最小，從而減少了分區(qū)間的邊割，降低了算法的通信開銷。并且分析了頂點(diǎn)無效轉(zhuǎn)移的情況，LGP-SA算法雖然一定程度地避免了頂點(diǎn)的無效轉(zhuǎn)移，但是沒有從根本上避免頂點(diǎn)無效轉(zhuǎn)移，所以本文通過限制頂點(diǎn)轉(zhuǎn)移次數(shù)，來進(jìn)一步避免無效轉(zhuǎn)移。

模擬退火算法［12］是根據(jù)熔融金屬中粒子的統(tǒng)計(jì)力學(xué)與復(fù)雜的組合最優(yōu)化問題的求解過程的相似性提出的，是一種在一個(gè)大的搜尋空間內(nèi)尋找最優(yōu)解的通用概率演算法。它的搜索過程引入了隨機(jī)因素，根據(jù)Metropolis準(zhǔn)則以一定的概率接受一個(gè)比當(dāng)前解差的解，因此有很大可能會(huì)跳出這個(gè)局部的最優(yōu)解以達(dá)到全局最優(yōu)解。正是由于Metropolis準(zhǔn)則，模擬退火算法才能夠成為全局尋優(yōu)的算法。具體流程如圖4所示。

圖4 模擬退火算法流程

圖5是模擬退火算法例子，就像爬山一樣，當(dāng)前處于C的位置，根據(jù)貪婪算法，會(huì)找到局部最高點(diǎn)A，就會(huì)停止搜索，因?yàn)锳點(diǎn)無論向哪個(gè)方向小幅度移動(dòng)都不能得到更優(yōu)的解。如果應(yīng)用模擬退火算法則會(huì)以一定的概率接受到B的移動(dòng)，最終就很有可能達(dá)到最高點(diǎn)D，跳出局部最優(yōu)解A。

圖5 模擬退火爬山例子

本文中傳統(tǒng)頂點(diǎn)轉(zhuǎn)移策略導(dǎo)致局部最優(yōu)的根本原因就是頂點(diǎn)每次都會(huì)朝著減少邊割數(shù)的方向走，沒有加入隨機(jī)因素，所以相對(duì)全局優(yōu)化來說，性能肯定低。因此本文將模擬退火算法與傳統(tǒng)頂點(diǎn)轉(zhuǎn)移策略相結(jié)合，既接受邊割數(shù)減少，又以一定概率接受邊割數(shù)增加，由于它以一定的概率接受比當(dāng)前情況要差的解，所以也一定程度地緩解了局部最優(yōu)，從而達(dá)到比較好的全局優(yōu)化。將模擬退火算法應(yīng)用到頂點(diǎn)轉(zhuǎn)移策略上，主要目的就是最大化地減少分區(qū)間的邊割，所以可以將邊割數(shù)作為目標(biāo)函數(shù)E的因子，將頂點(diǎn)在其他分區(qū)上的邊數(shù)和頂點(diǎn)在本地分區(qū)上的邊數(shù)之差作為?E。

判斷一個(gè)頂點(diǎn)是否進(jìn)行轉(zhuǎn)移，首先要看這個(gè)頂點(diǎn)的鄰居頂點(diǎn)信息，如果鄰居頂點(diǎn)在非本地分區(qū)的數(shù)目大于本地分區(qū)的數(shù)目，就將其無條件轉(zhuǎn)移過去，否則依據(jù)式（2）和式（3）計(jì)算它的轉(zhuǎn)移概率，來決定它是否進(jìn)行轉(zhuǎn)移。

（1）目標(biāo)函數(shù)：

（2）能量差：

（3）轉(zhuǎn)移概率：

對(duì)于wj分區(qū)的頂點(diǎn)v，S1是頂點(diǎn)v轉(zhuǎn)移到非本地分區(qū)，S0是頂點(diǎn)不進(jìn)行轉(zhuǎn)移，nj是本地分區(qū)的鄰居數(shù)，ni是頂點(diǎn)在非本地分區(qū)wi的鄰居數(shù)，其中E（S1）是頂點(diǎn)在非本地分區(qū)wi中的邊數(shù)（wi是頂點(diǎn)在非本地分區(qū)中具有最多鄰居數(shù)的分區(qū)），E（S0）是頂點(diǎn)在本地分區(qū)wj中的邊數(shù)，r是防止兩個(gè)分區(qū)中鄰居數(shù)相等時(shí)設(shè)置的一個(gè)閾值，是一個(gè)常數(shù)。

采用隨機(jī)數(shù)據(jù)生成器來產(chǎn)生一個(gè)隨機(jī)數(shù)α∈［0，1］，如果P＞α則接受這個(gè)狀態(tài)并改變當(dāng)前狀態(tài)，否則保持當(dāng)前狀態(tài)不變。隨著溫度變化，頂點(diǎn)v以P的概率接受向不比當(dāng)前邊割數(shù)少的方向移動(dòng)，以逃離局部最優(yōu)。當(dāng)初始溫度很高時(shí)，概率P就會(huì)很大。這時(shí)頂點(diǎn)轉(zhuǎn)移是無序的，逃離局部最優(yōu)的可能性最大；當(dāng)溫度T漸漸下降時(shí)，頂點(diǎn)的轉(zhuǎn)移概率也會(huì)變?。豁旤c(diǎn)轉(zhuǎn)移數(shù)量就會(huì)減少，最終當(dāng)T很小的時(shí)候，轉(zhuǎn)移概率就會(huì)接近于0，頂點(diǎn)只會(huì)朝著邊割率減少的方向轉(zhuǎn)移，此時(shí)就演變成傳統(tǒng)頂點(diǎn)轉(zhuǎn)移策略。開始時(shí)頂點(diǎn)轉(zhuǎn)移相對(duì)較多，隨著溫度的下降，頂點(diǎn)逐漸趨于傳統(tǒng)頂點(diǎn)轉(zhuǎn)移時(shí)的狀態(tài)，即不接受比較差的解。采用了模擬退火算法的頂點(diǎn)轉(zhuǎn)移策略既可以一定程度地逃離局部最優(yōu)，還能在溫度下降到很小時(shí)和傳統(tǒng)方法保持一致，接受好的頂點(diǎn)轉(zhuǎn)移，從而控制逃離局部最優(yōu)的可能。

3.2 LGP-SA算法的實(shí)現(xiàn)

本文主要分析了傳統(tǒng)頂點(diǎn)轉(zhuǎn)移策略的缺點(diǎn)，即局部最優(yōu)，正是由于它僅僅考慮頂點(diǎn)的局部信息，只要在它僅僅考慮頂點(diǎn)局部信息基礎(chǔ)上添加一個(gè)隨機(jī)擾動(dòng)，就能使得它能夠比之前的算法更多地減少分區(qū)間的邊割，當(dāng)然這個(gè)擾動(dòng)一定要有理論依據(jù)，然而本文算法也不一定能夠達(dá)到全局最優(yōu)，因?yàn)槿绻_(dá)到全局最優(yōu)，邊割率雖然降低到極限，但是其轉(zhuǎn)移頂點(diǎn)數(shù)、收斂時(shí)間等額外開銷使得全局最優(yōu)的代價(jià)太大，本文算法是達(dá)到一個(gè)近似全局最優(yōu)的性能。實(shí)驗(yàn)也證明了此方法的有效性和可行性。

（1）與傳統(tǒng)模擬退火的區(qū)別

大規(guī)模圖數(shù)據(jù)環(huán)境下，根據(jù)模擬退火算法來決定頂點(diǎn)是否轉(zhuǎn)移，在純貪心算法（傳統(tǒng)頂點(diǎn)轉(zhuǎn)移策略）里添加了一定的隨機(jī)性，使得性能比傳統(tǒng)頂點(diǎn)轉(zhuǎn)移策略更優(yōu)。傳統(tǒng)的模擬退火算法參數(shù)設(shè)置以初始溫度足夠高、降溫速度足夠慢為原則［13］，來逃離局部最優(yōu)。對(duì)于小規(guī)模的數(shù)據(jù)，這樣的設(shè)置能夠達(dá)到很好的效果，但是在大規(guī)模圖數(shù)據(jù)環(huán)境下這樣的參數(shù)設(shè)置會(huì)需要很多次迭代，導(dǎo)致轉(zhuǎn)移頂點(diǎn)數(shù)過大，這樣即使能夠達(dá)到很好的性能，但是它帶來的開銷會(huì)遠(yuǎn)遠(yuǎn)超過其最終帶來的性能。本文采用啟發(fā)式模擬退火算法，以盡量使轉(zhuǎn)移頂點(diǎn)的數(shù)量少為原則，這也正是與傳統(tǒng)模擬退火算法不同的特點(diǎn)，通過設(shè)置初始溫度和降溫函數(shù)，使得在大規(guī)模圖情況下也會(huì)達(dá)到很好的效果。其中初始溫度不宜過高，如果初始溫度過高，則概率過大，轉(zhuǎn)移頂點(diǎn)數(shù)過多，導(dǎo)致開銷大。降溫參數(shù)也不宜過大，本文采用快速降溫函數(shù)，使得算法既能夠逃離比較差的局部最優(yōu)，又能夠達(dá)到比較好的效果。

（2）負(fù)載均衡

負(fù)載均衡是大數(shù)據(jù)并行計(jì)算非常重要的原則，每個(gè)超步需要等待所有的分區(qū)執(zhí)行完之后才會(huì)進(jìn)入下一個(gè)超步。如果分區(qū)的負(fù)載相差很大，負(fù)載多的分區(qū)執(zhí)行時(shí)間長(zhǎng)，而負(fù)載少的分區(qū)執(zhí)行時(shí)間短，就會(huì)產(chǎn)生大量的等待和空閑時(shí)間浪費(fèi)，計(jì)算效率低。LGP-SA算法的負(fù)載均衡是通過在超步內(nèi)限制分區(qū)內(nèi)數(shù)據(jù)量和頂點(diǎn)轉(zhuǎn)移數(shù)目來進(jìn)行控制的。每個(gè)分區(qū)的數(shù)據(jù)量為S，用公式表示為：，其中S為每個(gè)分區(qū)中的頂點(diǎn)數(shù)范圍，V是圖中所有的頂點(diǎn)數(shù)，k是分區(qū)數(shù)，平衡因子λ。初始迭代時(shí)頂點(diǎn)轉(zhuǎn)移數(shù)目較多，可能會(huì)出現(xiàn)性能瓶頸，可以設(shè)置每個(gè)分區(qū)里最大轉(zhuǎn)移頂點(diǎn)數(shù)，如果超過這個(gè)最大轉(zhuǎn)移頂點(diǎn)數(shù)就不再轉(zhuǎn)出頂點(diǎn)。

（3）無效轉(zhuǎn)移

無效轉(zhuǎn)移的根本原因在于只考慮頂點(diǎn)局部信息，如果不僅僅考慮頂點(diǎn)的局部信息，還增加頂點(diǎn)轉(zhuǎn)移的隨機(jī)性，也就是允許以一定概率朝著增加邊割數(shù)的方向轉(zhuǎn)移，會(huì)在很大程度上緩解無效轉(zhuǎn)移。雖然加入隨機(jī)因素之后，無效轉(zhuǎn)移的頂點(diǎn)數(shù)會(huì)大部分減少，但是還是存在頂點(diǎn)無效轉(zhuǎn)移。對(duì)于循環(huán)無效轉(zhuǎn)移，實(shí)驗(yàn)設(shè)置如果該頂點(diǎn)轉(zhuǎn)移的次數(shù)超過一個(gè)閾值β，就認(rèn)為這個(gè)頂點(diǎn)是循環(huán)無效轉(zhuǎn)移，以后將不再對(duì)這個(gè)頂點(diǎn)進(jìn)行轉(zhuǎn)移，有效地避免了無效轉(zhuǎn)移。這個(gè)閾值如果設(shè)置過大，則與沒有控制無效頂點(diǎn)轉(zhuǎn)移差不多，效率沒有什么改進(jìn)，如果設(shè)置過小，一定程度上影響了模擬退火算法的性能。因此，本文采用一個(gè)折中的閾值。

引入模擬退火后的頂點(diǎn)轉(zhuǎn)移策略的LGP-SA算法主要步驟和流程（如圖6所示）如下。

步驟1初始圖：散列劃分初始狀態(tài)、溫度初始值T以及降溫函數(shù)T（m）；

步驟2對(duì)于wj分區(qū)中的頂點(diǎn)v，根據(jù)頂點(diǎn)v的鄰居信息和式（2）計(jì)算能量差；

步驟3如果?E＞0，則無條件接受S1。否則，以一定概率P接受S1；

步驟4控制該溫度的迭代次數(shù)L，若小于迭代次數(shù)L則轉(zhuǎn)步驟2，否則進(jìn)行步驟5；

步驟5利用降溫函數(shù)T（m），計(jì)算下一個(gè)溫度值；

步驟6控制溫度最小值，如達(dá)到溫度最小值則退火過程結(jié)束，否則轉(zhuǎn)步驟2。

圖6 一次超步流程

引入模擬退火算法之前，對(duì)于圖1（a）中的頂點(diǎn)1和頂點(diǎn)2，按照傳統(tǒng)頂點(diǎn)轉(zhuǎn)移策略是不轉(zhuǎn)移的，在引入模擬退火策略之后，這兩個(gè)頂點(diǎn)可能發(fā)生轉(zhuǎn)移，隨著迭代次數(shù)的增加，這個(gè)轉(zhuǎn)移概率會(huì)越來越小。只要有一個(gè)頂點(diǎn)轉(zhuǎn)移出去，另一個(gè)頂點(diǎn)也會(huì)跟著轉(zhuǎn)移出去，從而達(dá)到圖1（c）中的全局最優(yōu)狀態(tài)，因此有很大概率能夠達(dá)到全局優(yōu)化。

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)在32臺(tái)PC組成的集群上進(jìn)行，其中1臺(tái)作為master節(jié)點(diǎn)，其余31臺(tái)作為slave節(jié)點(diǎn)。每臺(tái)PC配置相同：CPU為Intel Core i3 3.4 GHz，8 GB內(nèi)存，操作系統(tǒng)為CentOS 6.5，Hadoop版本為0.20.203，JDK版本為1.6，Giraph版本為1.0。數(shù)據(jù)集使用見表1，本文數(shù)據(jù)集均來自真實(shí)數(shù)據(jù)snap，其中前兩個(gè)數(shù)據(jù)集是冪律圖，其他都是普通圖。

將在Giraph上實(shí)現(xiàn)傳統(tǒng)頂點(diǎn)轉(zhuǎn)移策略的算法稱為大規(guī)模圖劃分算法（large-scale graph partition algorithm，LGP），也是本文的比較算法。實(shí)驗(yàn)首先根據(jù)實(shí)驗(yàn)效果和大規(guī)模圖數(shù)據(jù)特點(diǎn)，設(shè)置了關(guān)于模擬退火的一些參數(shù)，使得邊割率和運(yùn)行時(shí)間達(dá)到一個(gè)比較好的臨界點(diǎn)；其次，驗(yàn)證了理想情況下基于模擬退火算法的頂點(diǎn)轉(zhuǎn)移策略的有效性，即在不控制負(fù)載均衡的情況下將LGP-SA算法與LGP算法進(jìn)行比較，觀察邊割率變化情況；由于圖處理系統(tǒng)僅僅降低通信開銷是不夠的，還需要保證負(fù)載均衡，因此本文再通過控制負(fù)載均衡比較這兩種算法對(duì)于減少邊割率的影響；最后，通過運(yùn)行PageRank算法，對(duì)比每個(gè)超步的運(yùn)行時(shí)間來驗(yàn)證其效果。因?yàn)閳D規(guī)模不同，所以邊割數(shù)差異也很大，導(dǎo)致效果不太容易觀看，本文的性能是用邊割率來衡量的，邊割率就是本地迭代的邊割數(shù)除以剛開始的邊割數(shù)，將邊割數(shù)歸一化成為邊割率r。

本實(shí)驗(yàn)剛開始采用散列劃分，剛開始的邊割數(shù)就是散列劃分產(chǎn)生的邊割數(shù)。

4.2 實(shí)驗(yàn)結(jié)果和分析

4.2.1 LGP-SA算法參數(shù)設(shè)定

在大規(guī)模圖環(huán)境下，應(yīng)當(dāng)以盡量減少頂點(diǎn)轉(zhuǎn)移數(shù)目為原則，表2顯示了不同的初始溫度對(duì)最終邊割率的影響。本實(shí)驗(yàn)采用快速降溫的策略，降溫函數(shù)為：T＇=T/k，T是上個(gè)超步的溫度值，T＇是本超步的溫度值，k是一個(gè)自增參數(shù)，每次需要降溫時(shí)就會(huì)增加1。取初始溫度T為10、30、50、70、90時(shí)各運(yùn)行10次的結(jié)果。觀察表2溫度對(duì)邊割率的影響，溫度設(shè)置為30比較折中。后面實(shí)驗(yàn)的初始溫度都取為30?？幢?發(fā)現(xiàn)溫度T達(dá)到30之后，邊割率雖然在減小，但是減小的程度很少，但是它帶來的頂點(diǎn)轉(zhuǎn)移概率、頂點(diǎn)轉(zhuǎn)移數(shù)目、頂點(diǎn)轉(zhuǎn)移時(shí)間都相對(duì)大幅增加，因此將溫度設(shè)置為30是比較優(yōu)化的選擇。

表1 數(shù)據(jù)集介紹

表2 溫度對(duì)邊割率的影響

本文采用快速降溫函數(shù)，需要設(shè)置溫度迭代步長(zhǎng)，見表3。溫度迭代步長(zhǎng)L同樣要依據(jù)減少頂點(diǎn)轉(zhuǎn)移數(shù)的原則，因此溫度迭代步長(zhǎng)不宜過長(zhǎng)，使得模擬退火既能夠快速收斂，也能夠達(dá)到很好的效果。下面實(shí)驗(yàn)采用L=（1，3，5，7，9），L=7以上的收斂次數(shù)太長(zhǎng)，會(huì)導(dǎo)致額外開銷很多，因此都不對(duì)其進(jìn)行考慮。由表3可知只要L達(dá)到3之后邊割率就會(huì)很穩(wěn)定，后面變化并不是很明顯，因此本實(shí)驗(yàn)中取L=3。

表3 溫度步長(zhǎng)對(duì)邊割率的影響

LGP-SA算法與LGP算法對(duì)不同圖的最終出現(xiàn)無效轉(zhuǎn)移頂點(diǎn)數(shù)目變化如圖7所示，由圖7可知LGP-SA算法一定程度地改進(jìn)了無效頂點(diǎn)轉(zhuǎn)移的數(shù)目，因?yàn)樵斐蔁o效頂點(diǎn)轉(zhuǎn)移現(xiàn)象的根本原因是轉(zhuǎn)移過程中只考慮頂點(diǎn)的局部信息，而LGP-SA算法加入了一定的隨機(jī)因素，致使頂點(diǎn)無效轉(zhuǎn)移數(shù)目降低。本文的LGP-SA算法不僅很大程度減少了無效頂點(diǎn)轉(zhuǎn)移數(shù)，還通過控制閾值（LGP-SA-β）的方式進(jìn)一步減少無效頂點(diǎn)轉(zhuǎn)移數(shù)。

圖7 不同圖的最終無效頂點(diǎn)轉(zhuǎn)移數(shù)目變化對(duì)比

4.2.2 不考慮負(fù)載均衡時(shí)的邊割率

LGP-SA算法與傳統(tǒng)轉(zhuǎn)移頂點(diǎn)算法的最終目的都是降低分區(qū)間的邊割數(shù)，本文首先將LGP-SA算法與傳統(tǒng)轉(zhuǎn)移頂點(diǎn)算法相比較，通過比較它們減少的邊割數(shù)就可以知道算法的有效性。在不控制負(fù)載均衡的情況下，觀察兩種算法的效果差異。如圖8所示，前兩列顯示的冪律圖，其他列都是普通圖，由圖8可知LGP-SA算法對(duì)于這兩類圖的效果都很明顯，LGP-SA算法比LGP算法好，特別是非冪律圖。而冪律圖的效果和其他圖相比較要差一點(diǎn)。因?yàn)閮缏蓤D本身就很傾斜，所以不控制復(fù)雜均衡的情況下，冪律圖的分區(qū)負(fù)載差異會(huì)很大，實(shí)驗(yàn)中也正是如此。

圖8 邊割率對(duì)比

圖9表示LGP-SA算法與傳統(tǒng)LGP算法每個(gè)超步的邊割率變化。由于LGP-SA算法在傳統(tǒng)LGP算法不轉(zhuǎn)移頂點(diǎn)的時(shí)候，以一定的概率轉(zhuǎn)移該頂點(diǎn)，而一開始的時(shí)候頂點(diǎn)的轉(zhuǎn)移概率高，所以開始的時(shí)候邊割可能會(huì)增加，這也正是模擬退火算法逃離局部最優(yōu)的必經(jīng)之路，之后頂點(diǎn)轉(zhuǎn)移概率隨著迭代次數(shù)增加而降低，最終和傳統(tǒng)算法一致。但是它最終下降的最低點(diǎn)比LGP算法更低。這就是剛開始以概率轉(zhuǎn)移的好處。

圖9 每個(gè)超步邊割率的變化比較

4.2.3 負(fù)載均衡下的邊割率

圖10和圖11用的數(shù)據(jù)都是as-Skitter。雖然不控制負(fù)載均衡情況下LGP-SA算法的效果很好，但是圖劃分的原則之一就是控制負(fù)載均衡，所以接下來的實(shí)驗(yàn)都是在控制負(fù)載均衡的條件下進(jìn)行的。對(duì)于一個(gè)圖分別對(duì)它進(jìn)行控制平衡與不控制平衡的比較，發(fā)現(xiàn)控制平衡因子的算法效果沒有不控制平衡因子效果好，因?yàn)榭刂曝?fù)載均衡就一定地限制了轉(zhuǎn)移頂點(diǎn)的自由，因此效果會(huì)變差，但是LGP-SA算法仍然比LGP算法好。圖11是每個(gè)超步的邊割率變化情況，圖9和圖11進(jìn)行比較得知，控制負(fù)載均衡的邊割率收斂得慢一點(diǎn)。

圖10 控制平衡因子對(duì)邊割率的變化情況比較

圖11 總邊割率變化

圖12是從不同規(guī)模的圖來驗(yàn)證算法有效性。其中Ego-Facebook和Email-Enron都是冪律圖，而其他的都是非冪律圖，由圖12可以看出冪律的平均邊割減少得沒有非冪律圖多。因?yàn)閮缏蓤D本身就是很傾斜的，不管圖怎么劃分，它都會(huì)導(dǎo)致分區(qū)間的邊割數(shù)較多。而其他圖算法比較都差不多，都比傳統(tǒng)方法好。

圖12 不同圖的邊割率

4.2.4 PageRank算法的運(yùn)行結(jié)果

判斷系統(tǒng)性能最有說服力的是運(yùn)行時(shí)間，將PageRank算法運(yùn)行到該系統(tǒng)上，來證明算法的可行性。圖13是運(yùn)行PageRank算法的超步運(yùn)行時(shí)間圖，初始劃分是散列劃分。剛開始的時(shí)候由于LGP-SA方法轉(zhuǎn)移的頂點(diǎn)數(shù)比傳統(tǒng)方法多，所以響應(yīng)時(shí)間比LGP算法時(shí)間長(zhǎng)，隨著溫度的降低，頂點(diǎn)轉(zhuǎn)移概率降低，邊割數(shù)也會(huì)漸漸趨于穩(wěn)定狀態(tài)，通信開銷也會(huì)趨于穩(wěn)定。大概在第50個(gè)超步的時(shí)候LGP算法就會(huì)追平散列劃分的時(shí)間。在第60個(gè)超步的時(shí)候LGP-SA算法就會(huì)追平LGP算法的運(yùn)行時(shí)間。隨著迭代次數(shù)的增加，算法的效果會(huì)越來越好。

圖13 PageRank每個(gè)超步的運(yùn)行時(shí)間

5 結(jié)束語(yǔ)

隨著大規(guī)模圖數(shù)據(jù)的出現(xiàn)，圖劃分也極具挑戰(zhàn)性，傳統(tǒng)的集中式劃分算法已經(jīng)處理不了大規(guī)模圖數(shù)據(jù)，因此涌現(xiàn)了很多分布式并行框架，如Pregel、Giraph、GraphLab［14，15］、Spark等。本文首先對(duì)Pregel的開源框架Giraph進(jìn)行了分析，針對(duì)傳統(tǒng)分布式圖劃分算法中采用轉(zhuǎn)移頂點(diǎn)來降低分區(qū)間的邊割，分析了這種方法的不足，由此提出了基于模擬退火的LGP-SA算法，并通過實(shí)驗(yàn)驗(yàn)證了其有效性和可行性。由于強(qiáng)制性控制負(fù)載均衡會(huì)使LGP-SA算法效率效果變差，希望接下來對(duì)這方面進(jìn)行優(yōu)化改進(jìn)。

［1］許金鳳，董一鴻，王詩(shī)鉻，等.大規(guī)模圖數(shù)據(jù)劃分算法綜述［J］.電信科學(xué)，2014，30（7）：100-106.XU J F，DONG Y H，WANG S Y，et al.Summary of large-scale graph partitioning algorithms［J］.Telecommunications Science，2014，30（7）：100-106.

［2］CHING A.Giraph：Large-scale graph processing infrastructure on Hadoop［C］/Hadoop Summit 2011，Santa Clara，CA，USA.［S.1.：s.n.］，2011.

［3］MALEWICZ G，AUSTEN MH，BIK A J C，et al.Pregel：a system for large-scale graph processing［C］/2010 ACM SIGMOD International Conference on Management of data，June 6-10，2010，Indianapolis，Indiana，USA.New York：ACM Press，2010：135-146.

［4］周爽，鮑玉斌，王志剛，等.BHP：面向BSP模型的負(fù)載均衡Hash圖數(shù)據(jù)劃分［J］.計(jì)算機(jī)科學(xué)與探索，2014，8（1）：40-50.ZHOU S，BAO Y B，WANG Z G，et al.BHP：BSP model oriented Hash graph data partition with load balancing［J］.Journal of Frontiers of Computer Scienceamp;Technology，2014，8（1）：40-50.

［5］KHAYYAT Z，AWARA K，ALONAZI A，et al.Mizan：a system for dynamic load balancing in large-scale graph processing［C］//The 8th ACM European Conference on Computer Systems，April 15-17，2013，Prague，Czech.New York：ACM Press，2013：169-182.

［6］UGANDER J，BACKSTROM L.Balanced label propagation for partitioning massive graphs［C］/The 6th ACM International Conference on Web Search and Data Mining，F(xiàn)ebruary 6-8，2013，Rome，Italy.New York：ACM Press，2013：507-516.

［7］VAQUERO L，CUADRADO F，LOGOTHETIS D，et al.xDGP：a dynamic graph processing system with adaptive partitioning［J］.Eprint Arxiv，2013（9）.

［8］BAO N T，SUZUMURA T.Towards highly scalable pregel-based graph processing platform with x10［C］/The 22nd International Conference on World Wide Web Companion，May 13-17，2013，Rio de Janeiro，Brazil.Geneva：International World Wide Web Conferences Steering Committee，2013：501-508.

［9］SALIHOGLU S，WIDOM J.GPS：A graph processing system［C］/The 25th International Conference on Scientific and Statistical Database Management，July 29-31，2013，Baltimore，Maryland，USA.New York：ACM Press，2013.

［10］VALIANT L G.A bridging model for parallel computation［J］.Communications of the ACM，1990，33（8）：103-111.

［11］WHITE T.Hadoop：The Definitive Guide［M］.Cambridge：O’Reilly Media，Inc.，2012.

［12］RUTENBAR R.Simulated annealing algorithms：an overview［J］.IEEE Circnit and Devices Magazine，1989：19-26.

［13］KUMAR V.Algorithm for constraint satisfaction problem：a survey［J］.AI Magazine，1992，13（1）：32-44.

［14］LOW Y，GONZALEZ J，KYROLA A，et al.GraphLab：a new framework for parallel machine learning［C］/The 26th Conference on Uncertainty in Artificial Intelligence（UAI’10），Jul 8-11，2010，Catalina Island，California，USA.［S.1.：s.n.］，2010：340-349.

［15］LOW Y，BICKSON D，GONZALEZ J，et al.Distributed GraphLab：a framework for machine learning and data mining in the cloud［J］.Proceedings of the VLDB Endowment，2012，5（8）：716-727.

LGP-SA：Graph partition algorithm based on simulated annealing in large-scale graph processing

XU Jinfeng，DONG Yihong，WANG Shiyi，HE Xianmang，CHEN Huahui
College of Information Science and Engineering，Ningbo University，Ningbo 315211，China

Distributed computing for large-scale graph data need to partition the graph firstly.The current methods of large-scale graph partitioning is to reduce the edge cut in order to lessen communication overhead by using vertex transfer strategies，but easily to fall into local optimum.Simulated annealing has a great probability to avoid the trap of local optimum and prevent vertices from invalid transfer which was introduced to transfer vertices.This method decreased communication overhead greatly.Comparative experiments show that the proposed algorithm has made a great improvement in reducing edge cut rates in large scale graph partition field.PageRank algorithm was also used to verify the effectiveness and feasibility of this method.

graph partition，Giraph，simulated annealing，large-scale graph，BSP

s：Zhejiang Provincial Natural Science Foundation of China（No.LY16F020003），The National Natural Science Foundation of China（No.61572266）

TP391

A

10.11959/j.issn.1000-0801.2016078

2015-04-07；

2016-02-04

浙江省自然科學(xué)基金資助項(xiàng)目（No.LY16F020003）；國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61572266）

許金鳳（1990-），女，寧波大學(xué)碩士生，主要研究方向?yàn)榇髷?shù)據(jù)、數(shù)據(jù)挖掘。

董一鴻（1969-），男，博士，寧波大學(xué)教授，主要研究方向?yàn)榇髷?shù)據(jù)、數(shù)據(jù)挖掘和人工智能。

王詩(shī)懿（1989-），女，寧波大學(xué)碩士生，主要研究方向?yàn)榇髷?shù)據(jù)、數(shù)據(jù)挖掘。

何賢芒（1981-），男，寧波大學(xué)講師，主要研究方向?yàn)榇髷?shù)據(jù)、數(shù)據(jù)挖掘、隱私保護(hù)。

陳華輝（1964-），男，博士，寧波大學(xué)教授，主要研究方向?yàn)閿?shù)據(jù)流與數(shù)據(jù)挖掘。