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

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

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

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

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