云平臺下基于復(fù)雜網(wǎng)絡(luò)的社團發(fā)現(xiàn)方法研究.pdf

1、復(fù)雜網(wǎng)絡(luò)是指具有動力學(xué)特征和復(fù)雜拓撲結(jié)構(gòu)的大規(guī)模網(wǎng)絡(luò)。不同于隨機網(wǎng)絡(luò)，復(fù)雜網(wǎng)絡(luò)具有小世界、無標(biāo)度、超家族等特性。利用這些特性可以更好地指導(dǎo)復(fù)雜網(wǎng)絡(luò)的研究。社團是復(fù)雜網(wǎng)絡(luò)中非常重要的結(jié)構(gòu)特征。相同社團的點聯(lián)系緊密，特征相似;不同社團的點聯(lián)系稀疏，特征相異。挖掘社團信息可以更加深刻地理解網(wǎng)絡(luò)結(jié)構(gòu)。然而隨著互聯(lián)網(wǎng)和移動終端技術(shù)的突飛猛進，以虛擬社交網(wǎng)絡(luò)為代表的復(fù)雜網(wǎng)絡(luò)規(guī)模迅速擴大，在對這些網(wǎng)絡(luò)進行社團劃分時，傳統(tǒng)串行劃分方法效率十分低下，無法

2、滿足實時處理需求。
　　近些年，云計算成為了一種處理海量數(shù)據(jù)新的技術(shù)和服務(wù)模式，可以為用戶提供大量具有高擴展、高可靠、完善容錯機制的計算資源和存儲資源。Hadoop和Spark是其中兩個應(yīng)用最廣的平臺。兩個平臺各有特色，Hadoop擅長進行大規(guī)模數(shù)據(jù)的批量處理，而Spark平臺更適合進行中量數(shù)據(jù)的迭代計算。本文將兩種云平臺與復(fù)雜網(wǎng)絡(luò)社團發(fā)現(xiàn)問題相結(jié)合，進行了以下幾部分工作:
　　1.提出了基于云平臺實現(xiàn)的靜態(tài)社團發(fā)現(xiàn)處理框架

3、，主要包含三步:并行粗化預(yù)處理、并行社團劃分、反粗化調(diào)優(yōu)。實現(xiàn)了以三角形作為粗化源的并行粗化預(yù)處理和反粗化調(diào)優(yōu)。實驗證明粗化預(yù)處理可以在保證原圖信息不丟失的前提下，縮小圖規(guī)模;反粗化調(diào)優(yōu)可以在并行劃分社團后進一步優(yōu)化劃分結(jié)果。
　　2.研究了基于Hadoop平臺實現(xiàn)的多層社團并行劃分算法。整個劃分過程分為Q值優(yōu)化與層聚合兩個階段。Q值優(yōu)化負責(zé)在某一層得到最理想的社區(qū)結(jié)構(gòu)，層聚合負責(zé)將該結(jié)構(gòu)合并，形成下一層的拓撲圖。兩個階段反復(fù)進行

4、直到全局Q值不再提升。實驗證明了該劃分算法的可靠性和在處理大規(guī)模數(shù)據(jù)集時的速度優(yōu)勢。
　　3.針對復(fù)雜網(wǎng)絡(luò)中經(jīng)常出現(xiàn)小規(guī)模變化的問題，研究了社團發(fā)現(xiàn)增量算法。算法將圖變化分成四類處理:增加邊、刪除邊、增加單個點、增加批量點。在處理增加批量點時，設(shè)計基于Spark平臺的并行處理方案。實驗證明，相比于重新運行靜態(tài)劃分算法，增量算法可以保證模塊度在幾乎不降低的情況下將劃分速度提高數(shù)倍。
　　4.搭建社團發(fā)現(xiàn)結(jié)果可視化展示系統(tǒng)。系統(tǒng)