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

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

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

3、絡分析中實現(xiàn)高效并行計算的需求。
　　本文針對相關程度矩陣的計算，提出了一種基于節(jié)點動態(tài)閾值調節(jié)的優(yōu)化方式，不僅解決了現(xiàn)有算法收斂速度較慢的問題，同時引入了節(jié)點自身特性輔助閾值設置，提升了算法準確性。在權重設計方面，考慮原算法中相關程度矩陣各個組成部分的重要程度不同，進行了有區(qū)分度的權重設置，并增加了算法對加權圖的支持。
　　針對非重疊社區(qū)，提出了兩個社區(qū)發(fā)現(xiàn)算法：基于關鍵節(jié)點的社區(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ū)結構導致社區(qū)間錯誤合并的問題，引入了點介數(shù)算法輔助篩選出關鍵節(jié)點，利用關鍵節(jié)點在多個社區(qū)間起橋梁作用這一特性，將其作為劃分社區(qū)的分界節(jié)點，結合BFS算法實現(xiàn)非重疊社區(qū)。通過仿真可以證明，CKE算法能夠準確

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

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