發(fā)布時(shí)間：2017-12-29 07:27

  本文關(guān)鍵詞：基于通信負(fù)載均衡的社交網(wǎng)絡(luò)圖分割算法研究與實(shí)現(xiàn)　出處：《太原理工大學(xué)》2017年碩士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 社交網(wǎng)絡(luò) 圖論 圖分割 分布式計(jì)算 負(fù)載均衡

【摘要】：海量社交網(wǎng)絡(luò)數(shù)據(jù)中蘊(yùn)含著豐富的信息,圖論是挖掘這些信息的重要方法之一。面對日益增多的圖數(shù)據(jù),分布式計(jì)算成為處理大規(guī)模圖數(shù)據(jù)的有效手段。在分布式圖計(jì)算中,通信所消耗的時(shí)間占有很大的比例,通過圖分割算法的設(shè)計(jì)可以有效地降低通信量并實(shí)現(xiàn)負(fù)載均衡,從而提高分布式圖計(jì)算的效率,典型的例子包括Metis圖分割算法。但是,用現(xiàn)有的圖分割算法處理非均衡圖數(shù)據(jù)會造成各個(gè)子圖之間通信量不均衡,從而影響了計(jì)算效率。為解決這一問題,本文針對社交網(wǎng)絡(luò)圖數(shù)據(jù)特點(diǎn)進(jìn)行了深入研究,并以傳統(tǒng)圖分割模型為基礎(chǔ),建立了實(shí)現(xiàn)通信負(fù)載和存儲負(fù)載雙重平衡的圖分割模型。以通信負(fù)載均衡圖分割方法為理論依據(jù),設(shè)計(jì)并實(shí)現(xiàn)了通信均衡標(biāo)簽交換算法(Communication Balanced Lable Exchanging method),同時(shí)為進(jìn)一步減小貪婪算法模型帶來的局部優(yōu)化影響,本文使用模擬退火算法對CBLE算法進(jìn)行深入優(yōu)化。本文最后使用Hash方法,Metis方法與本文中的CBLE算法進(jìn)行實(shí)驗(yàn)分析,分別在通信邊數(shù)量,頂點(diǎn)規(guī)模均衡度,通信邊分布均衡度指標(biāo)對三個(gè)算法進(jìn)行比較,CBLE算法整體具有明顯優(yōu)勢。為更加有力證明本文算法在提升分布式圖計(jì)算框架處理社交網(wǎng)絡(luò)數(shù)據(jù)的效率方面的優(yōu)勢,本文最后將CBLE算法應(yīng)用于Apache開源圖計(jì)算框架Hama中,使用Twitter大規(guī)模社交網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行測試。其結(jié)果表明分割子圖的通信負(fù)載均衡對分布式圖計(jì)算框架處理社交網(wǎng)絡(luò)數(shù)據(jù)的效率提升有一定的效果,并且隨著集群資源利用率的提高,本文算法的分割結(jié)果對圖計(jì)算效率有10%到15%的提升。
[Abstract]:......
【學(xué)位授予單位】：太原理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：O157.5

【參考文獻(xiàn)】

相關(guān)期刊論文 前6條

1 唐德權(quán);吳紹兵;凌志剛;;一種新的圖聚類算法研究[J];計(jì)算機(jī)應(yīng)用與軟件;2014年06期

2 吳信東;李毅;李磊;;在線社交網(wǎng)絡(luò)影響力分析[J];計(jì)算機(jī)學(xué)報(bào);2014年04期

3 周爽;鮑玉斌;王志剛;冷芳玲;于戈;鄧超;郭磊濤;;BHP:面向BSP模型的負(fù)載均衡Hash圖數(shù)據(jù)劃分[J];計(jì)算機(jī)科學(xué)與探索;2014年01期

4 王浩成;馬靜;;高效的大型圖聚類方法研究[J];小型微型計(jì)算機(jī)系統(tǒng);2013年06期

5 于戈;谷峪;鮑玉斌;王志剛;;云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)[J];計(jì)算機(jī)學(xué)報(bào);2011年10期

6 馬永剛;譚國真;楊際祥;潘東;;一種改進(jìn)的并行計(jì)算圖劃分模型[J];小型微型計(jì)算機(jī)系統(tǒng);2011年03期

，

本文編號：1349326