隨著信息時代的到來,人們在現(xiàn)實生活中積累了大量的圖結構數(shù)據(jù),分布式圖計算框架通過將大規(guī)模圖數(shù)據(jù)劃分至多臺機器上進行并行處理以獲得高效的計算效率。圖數(shù)據(jù)的劃分作為分布式計算的基礎,劃分結果的優(yōu)劣嚴重影響著分布式圖計算的性能,因此,面向分布式圖計算的圖劃分算法成為學者們研究的熱點問題。已有的圖劃分算法根據(jù)劃分方式的不同可被分為離線圖劃分算法和流式圖劃分算法,其中離線圖劃分算法劃分精度較高,但需要依賴完整的圖數(shù)據(jù)信息進行劃分操作,而流式圖劃分算法僅依賴部分圖數(shù)據(jù)信息進行劃分,但劃分精度較低。本文針對以上問題對圖劃分算法進行了深入研究并設計新的圖劃分算法,使得在基于局部圖數(shù)據(jù)信息的情況下可以得到較高的圖劃分精度。本文研究主要包括以下兩個方面:（1）提出兩階段局部圖劃分算法。針對已有圖劃分算法的缺點,本文設計了一種新的圖劃分思想:局部圖劃分。該劃分思想可基于局部圖數(shù)據(jù)信息進行劃分操作,同時在劃分過程中至多只需保存單個分區(qū)的數(shù)據(jù)信息,有效的降低了對機器性能的要求,更適合大規(guī)模圖數(shù)據(jù)的劃分問題�；谠搫澐炙枷�,本文提出了一種兩階段局部圖劃分算法。該算法引入模塊度的概念以量化每個分區(qū)的結構緊密程度,并... 

【文章來源】：合肥工業(yè)大學安徽省 211工程院校 教育部直屬院校

【文章頁數(shù)】：62 頁

【學位級別】：碩士

【部分圖文】：

圖2.1分布式圖計算框架中的PageRank一次迭代Fig2.1OneiterationofPageRankindistributedgraphcomputationsystem通過以上分析可以看出，在分布式圖計算框架中，初始圖劃分的結果會直接影響系統(tǒng)的運行效率

合肥工業(yè)大學專業(yè)碩士研究生學位論文邊分割算法相對易于調度，只需通過跨分區(qū)邊進行數(shù)據(jù)的傳。但是邊分割算法同樣存在一些不可避免的缺陷：因為在現(xiàn)實通常要遠大于節(jié)點的數(shù)目，因此邊分割方式在進行數(shù)據(jù)傳輸?shù)木W(wǎng)絡開銷，降低了系統(tǒng)的運行效率；同時在分布式圖計算框負載通常與各分區(qū)的邊數(shù)相關而非節(jié)點的數(shù)目，因此點分割分區(qū)的計算負載，避免系統(tǒng)資源的浪費。因此在后文的圖劃分能相對較優(yōu)的點分割方式進行圖數(shù)據(jù)的劃分。

邊分割算法相對易于調度，只需通過跨分區(qū)邊進行數(shù)據(jù)的傳。但是邊分割算法同樣存在一些不可避免的缺陷：因為在現(xiàn)實通常要遠大于節(jié)點的數(shù)目，因此邊分割方式在進行數(shù)據(jù)傳輸?shù)木W(wǎng)絡開銷，降低了系統(tǒng)的運行效率；同時在分布式圖計算框負載通常與各分區(qū)的邊數(shù)相關而非節(jié)點的數(shù)目，因此點分割分區(qū)的計算負載，避免系統(tǒng)資源的浪費。因此在后文的圖劃分能相對較優(yōu)的點分割方式進行圖數(shù)據(jù)的劃分。圖 2.2 圖劃分中邊分割方式Fig 2.2 Edge-cut in graph partitioning

【參考文獻】：
期刊論文
[1]MapReduce與Spark用于大數(shù)據(jù)分析之比較[J]. 吳信東,嵇圣硙.  軟件學報. 2018(06)
[2]分布式圖處理系統(tǒng)技術綜述[J]. 王童童,榮垂田,盧衛(wèi),杜小勇.  軟件學報. 2018(03)



本文編號：3236964