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

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

研究與開發(fā)

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

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

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

2.2 云計算平臺Giraph

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

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

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

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

3.1 LGP-SA算法描述

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

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

圖4 模擬退火算法流程

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

圖5 模擬退火爬山例子

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

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

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

（2）能量差：

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

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

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

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

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

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

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

（2）負載均衡

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

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

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

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

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

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

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

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

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

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

圖6 一次超步流程

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

4 實驗

4.1 實驗設(shè)置

實驗在32臺PC組成的集群上進行，其中1臺作為master節(jié)點，其余31臺作為slave節(jié)點。每臺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ù)據(jù)snap，其中前兩個數(shù)據(jù)集是冪律圖，其他都是普通圖。

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

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

4.2 實驗結(jié)果和分析

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

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

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

表2 溫度對邊割率的影響

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

表3 溫度步長對邊割率的影響

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

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

4.2.2 不考慮負載均衡時的邊割率

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

圖8 邊割率對比

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

圖9 每個超步邊割率的變化比較

4.2.3 負載均衡下的邊割率

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

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

圖11 總邊割率變化

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

圖12 不同圖的邊割率

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

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

圖13 PageRank每個超步的運行時間

5 結(jié)束語

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

［1］許金鳳，董一鴻，王詩鉻，等.大規(guī)模圖數(shù)據(jù)劃分算法綜述［J］.電信科學，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模型的負載均衡Hash圖數(shù)據(jù)劃分［J］.計算機科學與探索，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

浙江省自然科學基金資助項目（No.LY16F020003）；國家自然科學基金資助項目（No.61572266）

許金鳳（1990-），女，寧波大學碩士生，主要研究方向為大數(shù)據(jù)、數(shù)據(jù)挖掘。

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

王詩懿（1989-），女，寧波大學碩士生，主要研究方向為大數(shù)據(jù)、數(shù)據(jù)挖掘。

何賢芒（1981-），男，寧波大學講師，主要研究方向為大數(shù)據(jù)、數(shù)據(jù)挖掘、隱私保護。

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