云平臺下基于復雜網絡的社團發(fā)現方法研究.pdf

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

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

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

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