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

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

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

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

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