社區(qū)網(wǎng)絡(luò)中社團(tuán)發(fā)現(xiàn)機(jī)制的研究.pdf

1、復(fù)雜網(wǎng)絡(luò)一般是指節(jié)點(diǎn)數(shù)量多且節(jié)點(diǎn)間交互關(guān)系復(fù)雜的網(wǎng)絡(luò)。社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的拓?fù)涮攸c(diǎn)之一，整個(gè)網(wǎng)絡(luò)由若干社區(qū)構(gòu)成，社區(qū)內(nèi)部節(jié)點(diǎn)的交互頻繁，社區(qū)間節(jié)點(diǎn)的交互較弱。如何從復(fù)雜網(wǎng)絡(luò)中解構(gòu)出社區(qū)結(jié)構(gòu)，已成為復(fù)雜系統(tǒng)研究領(lǐng)域中一大熱點(diǎn)。
　　隨著網(wǎng)絡(luò)規(guī)模的逐漸增大，特別是Facebook、Twitter、微博等社交網(wǎng)絡(luò)的崛起，復(fù)雜網(wǎng)絡(luò)的規(guī)模指數(shù)上漲，不僅對社區(qū)發(fā)現(xiàn)算法的計(jì)算復(fù)雜度提出了苛刻的要求，同時(shí)也引入了對算法并行化的要求。在不考慮重疊社

2、區(qū)的情況下，雖然目前已經(jīng)提出了一些線性時(shí)間復(fù)雜度的算法，但由于這些算法通常采用較為激進(jìn)的貪婪策略，因此在網(wǎng)絡(luò)規(guī)模較大且稠密的圖拓?fù)渲薪Y(jié)果并不可靠。在重疊社區(qū)發(fā)現(xiàn)算法中，現(xiàn)有方案通常需要經(jīng)過多次計(jì)算來獲得最佳的社團(tuán)數(shù)，計(jì)算開銷過大。同時(shí)，由于文獻(xiàn)中多數(shù)社區(qū)發(fā)現(xiàn)算法均不具備并行能力，無法基于分割后的局部點(diǎn)集實(shí)現(xiàn)算法邏輯，這將很難滿足復(fù)雜網(wǎng)絡(luò)下海量數(shù)據(jù)的計(jì)算需求?；诖?，本文分別針對非重疊社區(qū)和重疊社區(qū)，提出兩個(gè)社區(qū)發(fā)現(xiàn)算法，以滿足在大規(guī)模網(wǎng)

3、絡(luò)分析中實(shí)現(xiàn)高效并行計(jì)算的需求。
　　本文針對相關(guān)程度矩陣的計(jì)算，提出了一種基于節(jié)點(diǎn)動態(tài)閾值調(diào)節(jié)的優(yōu)化方式，不僅解決了現(xiàn)有算法收斂速度較慢的問題，同時(shí)引入了節(jié)點(diǎn)自身特性輔助閾值設(shè)置，提升了算法準(zhǔn)確性。在權(quán)重設(shè)計(jì)方面，考慮原算法中相關(guān)程度矩陣各個(gè)組成部分的重要程度不同，進(jìn)行了有區(qū)分度的權(quán)重設(shè)置，并增加了算法對加權(quán)圖的支持。
　　針對非重疊社區(qū)，提出了兩個(gè)社區(qū)發(fā)現(xiàn)算法：基于關(guān)鍵節(jié)點(diǎn)的社區(qū)發(fā)現(xiàn)算法CKE（Community Det

4、ection based on Key Nodes Extracting）和基于譜聚類的社區(qū)發(fā)現(xiàn)算法SKC（SpectralKMeans Cluster based Detection）。CKE算法為了解決原算法中將連通組成部分作為社區(qū)結(jié)構(gòu)導(dǎo)致社區(qū)間錯誤合并的問題，引入了點(diǎn)介數(shù)算法輔助篩選出關(guān)鍵節(jié)點(diǎn)，利用關(guān)鍵節(jié)點(diǎn)在多個(gè)社區(qū)間起橋梁作用這一特性，將其作為劃分社區(qū)的分界節(jié)點(diǎn)，結(jié)合BFS算法實(shí)現(xiàn)非重疊社區(qū)。通過仿真可以證明，CKE算法能夠準(zhǔn)確

5、找到關(guān)鍵節(jié)點(diǎn)，得到有效的社區(qū)劃分。SKC算法則是利用了聚類思想，通過譜聚類將相關(guān)程度矩陣轉(zhuǎn)換為效用矩陣，以完成社區(qū)劃分。針對現(xiàn)有算法中K值和初心難以預(yù)估的問題，引入Canopy聚類輔助設(shè)置。
　　針對重疊社區(qū)，提出了兩個(gè)社區(qū)發(fā)現(xiàn)算法：基于點(diǎn)聚集的社區(qū)發(fā)現(xiàn)算法 CCO（Core-clique Combination Optimization detection algorithm）和基于擴(kuò)散標(biāo)記的社區(qū)發(fā)現(xiàn)算法IMB（Iterativ

6、e diffusion Markbased on high-Betweennes）。CCO算法以發(fā)掘高內(nèi)聚度的點(diǎn)聚集為核心，通過在其上提取重疊節(jié)點(diǎn)完成社區(qū)發(fā)現(xiàn)。常規(guī)的重疊點(diǎn)發(fā)現(xiàn)策略通常以聚類密度進(jìn)行判定，其計(jì)算復(fù)雜度較高，針對這一問題在CCO算法中提出了簡化的解決策略。IMB算法則是通過擴(kuò)散標(biāo)記思想實(shí)現(xiàn)重疊社區(qū)的發(fā)現(xiàn)。為了保證不同規(guī)模的社區(qū)結(jié)構(gòu)均能被提取，IMB算法引入了基準(zhǔn)閾值?作為標(biāo)準(zhǔn)，利用其能夠度量節(jié)點(diǎn)與鄰接節(jié)點(diǎn)間緊密程度這一特性