基于點(diǎn)分割的平衡圖劃分算法研究及其在Spark上的實(shí)現(xiàn).pdf

1、近年來(lái)，隨著數(shù)據(jù)量的爆發(fā)式增長(zhǎng)，相應(yīng)地興起了對(duì)大數(shù)據(jù)處理平臺(tái)的研究熱潮，Hadoop的出現(xiàn)使人們從傳統(tǒng)的并行計(jì)算模型轉(zhuǎn)向?qū)apreduce計(jì)算模型的研究。為了滿足數(shù)據(jù)挖掘和交互式實(shí)時(shí)查詢的計(jì)算需求，進(jìn)一步提高數(shù)據(jù)處理能力和效率，UC berkeley大學(xué)高性能計(jì)算實(shí)驗(yàn)室開(kāi)發(fā)了Spark計(jì)算平臺(tái)，Spark引入了RDD（Resilient Distributed Datasets）數(shù)據(jù)模型，大大提高了交互式計(jì)算和迭代計(jì)算的計(jì)算速度，使得

2、Spark成為大數(shù)據(jù)處理的利器。
　　大數(shù)據(jù)的核心處理之一就是圖數(shù)據(jù)的處理，其中平衡圖劃分是圖數(shù)據(jù)處理的一個(gè)重要組成部分。眾所周知，平衡圖劃分是一個(gè)NP完全問(wèn)題，應(yīng)用非常廣泛，研究領(lǐng)域包括生物網(wǎng)絡(luò)，大規(guī)模集成電路設(shè)計(jì)，并行編程，負(fù)載均衡以及在線社交網(wǎng)絡(luò)分析等。傳統(tǒng)的圖劃分算法很多屬于全局算法，即算法執(zhí)行過(guò)程中需要遍歷全圖，過(guò)于依賴全圖知識(shí)，不適合對(duì)大規(guī)模圖數(shù)據(jù)的處理?；趯?duì)全圖訪問(wèn)代價(jià)過(guò)大的考慮，2013年由 Rahimian等人

3、提出的一個(gè)去中心局部搜索算法JA-BE-JA，不需要進(jìn)行中央?yún)f(xié)調(diào)，只通過(guò)局部知識(shí)來(lái)進(jìn)行圖的劃分，極大的減少了集群中節(jié)點(diǎn)的通信開(kāi)銷，大大提高了該算法的可擴(kuò)展性和對(duì)大規(guī)模圖數(shù)據(jù)的處理能力。
　　然而，JA-BE-JA算法仍然基于邊分割的設(shè)計(jì)思想，最近研究發(fā)現(xiàn)對(duì)于自然圖的處理，通過(guò)邊分割雖然保證了各子集中節(jié)點(diǎn)數(shù)的平衡，但是各個(gè)子集中邊的數(shù)量相差較大，同時(shí)該算法在多次迭代過(guò)程中容易陷入局部最優(yōu)解。于是本文提出了基于點(diǎn)分割的改進(jìn)算法 JA-

4、BE-JA-VC(Vertex-Cut)，新的算法采用了點(diǎn)分割的思想，子集的平衡性由每個(gè)分區(qū)中邊的個(gè)數(shù)來(lái)維持，而不是單純把節(jié)點(diǎn)數(shù)來(lái)作為平衡性的標(biāo)準(zhǔn)。新的算法在對(duì)自然圖劃分時(shí)，劃分產(chǎn)生的子集規(guī)模更加平衡。同時(shí)引入了模擬退火技術(shù)，增加了算法求解過(guò)程中的概率突跳性，避免陷入局部最優(yōu)陷阱。本文最后對(duì)算法進(jìn)行了評(píng)估，結(jié)果表明新算法不僅能夠維持分區(qū)規(guī)模的平衡，同時(shí)對(duì)點(diǎn)的切分次數(shù)也相對(duì)較低，尤其對(duì)于服從冪律分布的現(xiàn)實(shí)數(shù)據(jù)進(jìn)行處理時(shí)，基于點(diǎn)分割的算法設(shè)