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

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

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

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