【摘要】：隨著社會網(wǎng)絡(luò)的興起和流行,越來越多的人加入到社會網(wǎng)絡(luò)的分析研究中。一般來說,社會網(wǎng)絡(luò)由節(jié)點(diǎn)相互連接而成,整個(gè)網(wǎng)絡(luò)以社區(qū)結(jié)構(gòu)的形式呈現(xiàn),可看作由多個(gè)社區(qū)結(jié)構(gòu)組成,社區(qū)結(jié)構(gòu)內(nèi)部的節(jié)點(diǎn)之間連接稠密,社區(qū)之間則連接相對稀疏,社區(qū)結(jié)構(gòu)對社會網(wǎng)絡(luò)的分析研究的作用很大。因此,社會網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的識別已成為社會網(wǎng)絡(luò)特性分析的研究熱點(diǎn),并且出現(xiàn)了很多經(jīng)典的社區(qū)識別算法。隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大,社會網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量不斷增加,很多交友網(wǎng)站如騰訊、新浪微博等用戶人數(shù)已達(dá)到10億。由于經(jīng)典社區(qū)識別算法大都為單機(jī)迭代算法,往往只適用于小規(guī)模社會網(wǎng)絡(luò)的社區(qū)識別,對于這樣大規(guī)模的社會網(wǎng)絡(luò),這些經(jīng)典識別算法已不能有效地識別社區(qū)結(jié)構(gòu)。針對此問題,本文基于Graph Lab云計(jì)算平臺提出了能夠并行計(jì)算的社區(qū)識別算法。本文首先闡述社會網(wǎng)絡(luò)和社區(qū)識別的相關(guān)理論知識,如靜態(tài)網(wǎng)絡(luò)和動態(tài)網(wǎng)絡(luò)的圖表示形式,介紹社區(qū)結(jié)構(gòu)的基本描述方式,并給出社區(qū)質(zhì)量的衡量準(zhǔn)則,用來評判社區(qū)識別算法的優(yōu)劣。其次,概述處理大數(shù)據(jù)所需要的并行計(jì)算框架,如Hadoop框架下的Map Reduce模型,基于BSP模型的大圖處理框架Pregel,并詳細(xì)介紹本文所依賴的圖并行計(jì)算框架Graph Lab,Graph Lab作為一種并行的云計(jì)算平臺,依據(jù)Gather-Apply-Scatter三步計(jì)算模型,能有效進(jìn)行大規(guī)模圖數(shù)據(jù)的計(jì)算。最后,詳細(xì)介紹在Graph Lab并行計(jì)算模型上針對大規(guī)模靜態(tài)社會網(wǎng)絡(luò)和動態(tài)社會網(wǎng)絡(luò)而分別提出的社區(qū)識別算法,即基于重要節(jié)點(diǎn)擴(kuò)展的重疊社區(qū)識別算法DOCVN(Detecting the Overlapping Community algorithm based on Vital Node Expanding in Graph Lab)以及基于IC算法改進(jìn)的并行動態(tài)社區(qū)識別算法PDCI(Parallel Dynamic Community Identification)。在DOCVN算法中,提出了通過節(jié)點(diǎn)的Page Rank值選取重要節(jié)點(diǎn)并基于節(jié)點(diǎn)到重要節(jié)點(diǎn)的節(jié)點(diǎn)歸屬度值進(jìn)行重要節(jié)點(diǎn)擴(kuò)展的思想來實(shí)現(xiàn)大規(guī)模靜態(tài)網(wǎng)絡(luò)的社區(qū)識別;而本文所提的PDCI算法,其算法思想是基于IC算法的并行改進(jìn),根據(jù)IC算法中所定義的增量相關(guān)頂點(diǎn)集以及增量式社區(qū)識別的評價(jià)函數(shù),本算法首先在Spark并行計(jì)算框架上實(shí)現(xiàn)查找增量相關(guān)頂點(diǎn)集的預(yù)處理,然后在Graph Lab平臺上并行實(shí)現(xiàn)增量式的社區(qū)識別。實(shí)驗(yàn)表明本文所提的這兩個(gè)算法可以有效地識別大規(guī)模靜態(tài)網(wǎng)絡(luò)和動態(tài)網(wǎng)絡(luò)的重疊社區(qū)結(jié)構(gòu),為大規(guī)模社會網(wǎng)絡(luò)社區(qū)識別提供了新的思想和方法。
[Abstract]:......
【學(xué)位授予單位】：寧波大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：TP391.41;TP393.09

【參考文獻(xiàn)】

相關(guān)碩士學(xué)位論文 前1條

1 李軍華;云計(jì)算及若干數(shù)據(jù)挖掘算法的MapReduce化研究[D];電子科技大學(xué);2010年

，

本文編號：2484452