復雜網(wǎng)絡中的社區(qū)發(fā)現(xiàn)算法研究.pdf

1、隨著復雜網(wǎng)絡研究的興起，從復雜網(wǎng)絡的角度研究復雜系統(tǒng)受到了越來越多的關注。現(xiàn)實世界中大量的復雜系統(tǒng)均可以用復雜網(wǎng)絡來描述。社區(qū)結構作為復雜網(wǎng)絡的重要特性之一，引起了研究者的廣泛關注。社區(qū)發(fā)現(xiàn)即為挖掘復雜網(wǎng)絡中的模塊化的社區(qū)結構的過程，這對于理解復雜網(wǎng)絡的功能、發(fā)現(xiàn)復雜網(wǎng)絡中隱藏的規(guī)律和預測復雜網(wǎng)絡的行為具有重要的意義。然而，隨著網(wǎng)絡規(guī)模不斷擴大，網(wǎng)絡結構更加復雜，社區(qū)發(fā)現(xiàn)也變得異常困難。目前，已有的社區(qū)發(fā)現(xiàn)算法還存在以下問題：（1）現(xiàn)有

2、的社區(qū)發(fā)現(xiàn)算法難以準確地發(fā)現(xiàn)穩(wěn)定的重疊社區(qū)結構；（2）基于節(jié)點的社區(qū)發(fā)現(xiàn)算法難以發(fā)現(xiàn)網(wǎng)絡中重疊度較高的社區(qū)結構；（3）傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法僅僅關注網(wǎng)絡中的模塊化社區(qū)結構，無法進一步識別社區(qū)中的層次關系。本文針對上述問題展開研究，主要工作和研究成果如下：
　　1.提出了一種基于非重疊極大子團的標簽傳播社區(qū)發(fā)現(xiàn)算法。該算法在標簽傳播算法的基礎上，對其進行三個方面的改進：在標簽初始化階段，通過查找網(wǎng)絡中非重疊的極大子團結構，賦予每個非重疊

3、的極大子團唯一的標簽；在標簽傳播階段，通過選取具有最大標簽傳播率的標簽來更新節(jié)點標簽；在社區(qū)調(diào)整階段，通過合并相似度較高的社區(qū)來提升社區(qū)發(fā)現(xiàn)的質量。將該算法分別應用于計算機生成網(wǎng)絡和真實的社會網(wǎng)絡，實驗結果表明：該算法很好地解決了標簽傳播算法的魯棒性問題，并能準確地發(fā)現(xiàn)網(wǎng)絡中的重疊社區(qū)。
　　2.提出了一種基于核心鏈路的重疊社區(qū)發(fā)現(xiàn)算法。相較于當前的基于節(jié)點的重疊社區(qū)發(fā)現(xiàn)算法，該算法從鏈路的角度出發(fā)，通過選取核心鏈路，并根據(jù)鏈路影

4、響力的強弱不斷吸引外層鏈路進而形成鏈路社區(qū)結構；再將鏈路社區(qū)轉化為節(jié)點社區(qū)，經(jīng)過節(jié)點社區(qū)調(diào)整后，得到全局最優(yōu)的重疊社區(qū)結構。該算法是一種無監(jiān)督算法，無需輸入額外參數(shù)。將該算法分別應用于計算機生成網(wǎng)絡和真實的社會網(wǎng)絡，實驗結果表明，相較于其它算法，該算法能夠更好地發(fā)現(xiàn)重疊度較高的社區(qū)結構。
　　3.提出了一種基于種子節(jié)點集的社區(qū)層次結構發(fā)現(xiàn)算法。該算法通過選取種子節(jié)點，并根據(jù)余弦相似度的大小添加其最近鄰節(jié)點共同構成種子節(jié)點集；再由種