GraphLab云計算平臺下社會網(wǎng)絡(luò)的社區(qū)識別.pdf

1、隨著社會網(wǎng)絡(luò)的興起和流行，越來越多的人加入到社會網(wǎng)絡(luò)的分析研究中。一般來說，社會網(wǎng)絡(luò)由節(jié)點相互連接而成，整個網(wǎng)絡(luò)以社區(qū)結(jié)構(gòu)的形式呈現(xiàn)，可看作由多個社區(qū)結(jié)構(gòu)組成，社區(qū)結(jié)構(gòu)內(nèi)部的節(jié)點之間連接稠密，社區(qū)之間則連接相對稀疏，社區(qū)結(jié)構(gòu)對社會網(wǎng)絡(luò)的分析研究的作用很大。因此，社會網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的識別已成為社會網(wǎng)絡(luò)特性分析的研究熱點，并且出現(xiàn)了很多經(jīng)典的社區(qū)識別算法。隨著網(wǎng)絡(luò)規(guī)模的擴大，社會網(wǎng)絡(luò)中節(jié)點的數(shù)量不斷增加，很多交友網(wǎng)站如騰訊、新浪微博等用戶人數(shù)

2、已達到10億。由于經(jīng)典社區(qū)識別算法大都為單機迭代算法，往往只適用于小規(guī)模社會網(wǎng)絡(luò)的社區(qū)識別，對于這樣大規(guī)模的社會網(wǎng)絡(luò)，這些經(jīng)典識別算法已不能有效地識別社區(qū)結(jié)構(gòu)。針對此問題，本文基于GraphLab云計算平臺提出了能夠并行計算的社區(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)劣。
　　其次，概述處理

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

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

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