GraphLab云計(jì)算平臺(tái)下社會(huì)網(wǎng)絡(luò)的社區(qū)識(shí)別.pdf

1、隨著社會(huì)網(wǎng)絡(luò)的興起和流行，越來越多的人加入到社會(huì)網(wǎng)絡(luò)的分析研究中。一般來說，社會(huì)網(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ū)之間則連接相對(duì)稀疏，社區(qū)結(jié)構(gòu)對(duì)社會(huì)網(wǎng)絡(luò)的分析研究的作用很大。因此，社會(huì)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的識(shí)別已成為社會(huì)網(wǎng)絡(luò)特性分析的研究熱點(diǎn)，并且出現(xiàn)了很多經(jīng)典的社區(qū)識(shí)別算法。隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量不斷增加，很多交友網(wǎng)站如騰訊、新浪微博等用戶人數(shù)

2、已達(dá)到10億。由于經(jīng)典社區(qū)識(shí)別算法大都為單機(jī)迭代算法，往往只適用于小規(guī)模社會(huì)網(wǎng)絡(luò)的社區(qū)識(shí)別，對(duì)于這樣大規(guī)模的社會(huì)網(wǎng)絡(luò)，這些經(jīng)典識(shí)別算法已不能有效地識(shí)別社區(qū)結(jié)構(gòu)。針對(duì)此問題，本文基于GraphLab云計(jì)算平臺(tái)提出了能夠并行計(jì)算的社區(qū)識(shí)別算法。
　　本文首先闡述社會(huì)網(wǎng)絡(luò)和社區(qū)識(shí)別的相關(guān)理論知識(shí)，如靜態(tài)網(wǎng)絡(luò)和動(dòng)態(tài)網(wǎng)絡(luò)的圖表示形式，介紹社區(qū)結(jié)構(gòu)的基本描述方式，并給出社區(qū)質(zhì)量的衡量準(zhǔn)則，用來評(píng)判社區(qū)識(shí)別算法的優(yōu)劣。
　　其次，概述處理

3、大數(shù)據(jù)所需要的并行計(jì)算框架，如 Hadoop框架下的MapReduce模型，基于BSP模型的大圖處理框架 Pregel，并詳細(xì)介紹本文所依賴的圖并行計(jì)算框架 GraphLab，GraphLab作為一種并行的云計(jì)算平臺(tái)，依據(jù)Gather-Apply-Scatter三步計(jì)算模型，能有效進(jìn)行大規(guī)模圖數(shù)據(jù)的計(jì)算。
　　最后，詳細(xì)介紹在 GraphLab并行計(jì)算模型上針對(duì)大規(guī)模靜態(tài)社會(huì)網(wǎng)絡(luò)和動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)而分別提出的社區(qū)識(shí)別算法，即基于重要節(jié)

4、點(diǎn)擴(kuò)展的重疊社區(qū)識(shí)別算法 DOCVN(Detecting the Overlapping Community algorithm based on Vital Node Expanding in GraphLab)以及基于IC算法改進(jìn)的并行動(dòng)態(tài)社區(qū)識(shí)別算法PDCI(Parallel Dynamic Community Identification)。在 DOCVN算法中，提出了通過節(jié)點(diǎn)的PageRank值選取重要節(jié)點(diǎn)并基于節(jié)點(diǎn)到重要節(jié)點(diǎn)

5、的節(jié)點(diǎn)歸屬度值進(jìn)行重要節(jié)點(diǎn)擴(kuò)展的思想來實(shí)現(xiàn)大規(guī)模靜態(tài)網(wǎng)絡(luò)的社區(qū)識(shí)別；而本文所提的PDCI算法，其算法思想是基于IC算法的并行改進(jìn)，根據(jù) IC算法中所定義的增量相關(guān)頂點(diǎn)集以及增量式社區(qū)識(shí)別的評(píng)價(jià)函數(shù)，本算法首先在 Spark并行計(jì)算框架上實(shí)現(xiàn)查找增量相關(guān)頂點(diǎn)集的預(yù)處理，然后在 GraphLab平臺(tái)上并行實(shí)現(xiàn)增量式的社區(qū)識(shí)別。
　　實(shí)驗(yàn)表明本文所提的這兩個(gè)算法可以有效地識(shí)別大規(guī)模靜態(tài)網(wǎng)絡(luò)和動(dòng)態(tài)網(wǎng)絡(luò)的重疊社區(qū)結(jié)構(gòu)，為大規(guī)模社會(huì)網(wǎng)絡(luò)社區(qū)識(shí)