復雜網絡的社團探測：基于節(jié)點相似度的新算法.pdf

1、隨著復雜網絡理論不斷完善與應用研究的深入開展，網絡科學已經逐步發(fā)展成為當前備受關注的熱點課題。作為各類復雜系統(tǒng)一個共有的重要性質，社團結構對于理解網絡系統(tǒng)的結構與功能具有重要的理論意義與應用價值，是網絡科學研究的一個重要內容。理論上，社團探測是一個NP難題，其有效算法無法回避時間復雜度與計算精確度之間的矛盾。這一矛盾隨著大數(shù)據(jù)時代的到來而變得更加尖銳。發(fā)展快速而準確的社團探測算法是目前社團結構研究的一個重點。
　　本論文首先回顧了

2、復雜網絡的拓撲性質與社團結構特征，總結和分析了傳統(tǒng)的社團探測算法。其次，基于經典的GN算法，我們提出了一種改進的GN算法來探測無本征邊權的網絡，然后拓展到加權網絡中。將改進的算法應用于人工和真實網絡，測試結果表明：在無權和加權網絡中，該算法均能夠更有效地探測到社團結構。此外，改進算法中的邊介數(shù)加權迭代方案可以直接應用于其它的社團探測算法中。
　　基于模塊度優(yōu)化的社團探測方法是一類廣泛應用且有效的社團結構探測策略。考慮到網絡理論中的

3、節(jié)點相似度與社團結構探測的關聯(lián)，我們針對模塊度優(yōu)化算法提出了基于局部拓撲相似度的社團探測算法。其算法的關鍵技術是：利用局部節(jié)點相似度將無權網絡加權或者將加權網絡重新權重化，然后再基于模塊度優(yōu)化方法實現(xiàn)網絡的社團結構探測。我們將上述方案與三種傳統(tǒng)的社團結構探測算法相結合，在均勻網絡和異構網絡中進行測試，比較分析了局部相似性指標對基于模塊化的探測算法的影響。結果表明：各種局部相似性指標對改進的基于模塊化的算法是起了至關重要的作用，在保證比較