大規(guī)模動態(tài)自適應(yīng)圖劃分算法.pdf

1、近年來，隨著互聯(lián)網(wǎng)的快速發(fā)展，網(wǎng)絡(luò)用戶數(shù)量的不斷增加，進而形成了很多大規(guī)模網(wǎng)絡(luò)圖，對其進行處理便成為網(wǎng)絡(luò)研究的一個發(fā)展趨勢。由于計算機內(nèi)存空間的限制，單機環(huán)境下無法正常處理大規(guī)模網(wǎng)絡(luò)圖，解決該問題的最好方法是對網(wǎng)絡(luò)圖進行分布式處理，由此出現(xiàn)了一系列大規(guī)模圖處理平臺。大規(guī)模圖處理平臺需要將整個大規(guī)模圖劃分成多個子圖并放入每個節(jié)點中，使得節(jié)點能夠并行執(zhí)行任務(wù)。為了提高分布式系統(tǒng)的計算效率，在進行圖劃分時需要保證子圖規(guī)模相對均衡，還要盡量減少

2、節(jié)點間的通信開銷即分區(qū)間相連的邊數(shù)足夠小。但是目前常見的大規(guī)模圖處理平臺在圖劃分時基本采用哈希算法，該算法雖然能夠滿足子圖規(guī)模均衡，但會產(chǎn)生很大的通信開銷，影響大規(guī)模圖處理平臺的運行效率，因此對大規(guī)模圖劃分算法的研究也成為大規(guī)模圖處理中的熱點問題。本文針對大規(guī)模圖數(shù)據(jù)劃分算法進行了詳細的分析，主要從以下幾個方面進行研究：
　　首先，針對降低分布式圖處理系統(tǒng)的通信開銷進行研究。近些年，關(guān)于大規(guī)模圖劃分算法研究中，多數(shù)算法通過轉(zhuǎn)移頂點

3、來降低通信開銷，本文在頂點轉(zhuǎn)移的基礎(chǔ)上提出了將模擬退火思想啟發(fā)式地應(yīng)用在上述算法之上，進一步降低了分布式系統(tǒng)的通信開銷，從而提升了分布式系統(tǒng)的運行效率。
　　其次，針對分布式圖處理系統(tǒng)的負載均衡方面進行研究。近些年，關(guān)于大規(guī)模圖劃分算法負載均衡研究中，多數(shù)算法是通過控制分區(qū)中的頂點數(shù)來強制性地實現(xiàn)分區(qū)間的負載均衡，并沒有考慮大規(guī)模圖的內(nèi)部結(jié)構(gòu)。本文將分區(qū)間的負載和圖的拓撲結(jié)構(gòu)結(jié)合在一起，通過監(jiān)測超步運行時間來控制分區(qū)的負載均衡并針