復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)若干問題研究.pdf

1、近年來，復(fù)雜網(wǎng)絡(luò)逐漸成為信息科學(xué)、社會學(xué)、物理學(xué)、乃至生命科學(xué)等學(xué)科研究的熱點。所謂復(fù)雜網(wǎng)絡(luò)，是指將自然界中的各個實體抽象為網(wǎng)絡(luò)中的節(jié)點，實體與實體之間的關(guān)系抽象為網(wǎng)絡(luò)中的邊。這使得自然界中的很多系統(tǒng)都可以表示為復(fù)雜網(wǎng)絡(luò)的形式，例如社會關(guān)系網(wǎng)、科學(xué)家合作網(wǎng)、通信網(wǎng)、互聯(lián)網(wǎng)、人類疾病基因網(wǎng)等等。研究發(fā)現(xiàn)，復(fù)雜網(wǎng)絡(luò)具有復(fù)雜的內(nèi)部結(jié)構(gòu)和多樣的結(jié)構(gòu)特征，其中，模塊性（即社區(qū)結(jié)構(gòu)）是復(fù)雜網(wǎng)絡(luò)的一個重要特征，它表現(xiàn)出網(wǎng)絡(luò)中的節(jié)點具有聚集化的特性，即

2、社區(qū)內(nèi)部節(jié)點之間連接稠密、社區(qū)之間的節(jié)點連接稀疏。此外，社區(qū)結(jié)構(gòu)在現(xiàn)實世界中往往是“重疊”的。復(fù)雜網(wǎng)絡(luò)（重疊）社區(qū)結(jié)構(gòu)的發(fā)現(xiàn)對于分析復(fù)雜網(wǎng)絡(luò)的拓撲結(jié)構(gòu)、理解復(fù)雜網(wǎng)絡(luò)的功能、發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的隱藏規(guī)律以及預(yù)測復(fù)雜網(wǎng)絡(luò)的行為具有十分重要的意義。
　　目前，研究者提出了眾多網(wǎng)絡(luò)（重疊）社區(qū)發(fā)現(xiàn)方法，并將之成功應(yīng)用于現(xiàn)實系統(tǒng)的分析中，然而社區(qū)發(fā)現(xiàn)方法存在的問題還有很多，如復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問題與聚類分析問題兩者之間的關(guān)系還有待研究;網(wǎng)絡(luò)社區(qū)發(fā)

3、現(xiàn)算法尤其是重疊社區(qū)發(fā)現(xiàn)算法的精度和效率還有待提高;傳統(tǒng)的劃分評價函數(shù)模塊化Q函數(shù)存在分辨率的限制等等。鑒于復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問題與傳統(tǒng)機器學(xué)習(xí)中的聚類分析問題都是對數(shù)據(jù)進行劃分，并且機器學(xué)習(xí)中的聚類分析研究日趨成熟，本文結(jié)合機器學(xué)習(xí)相關(guān)的技術(shù)和方法，改進并提出了若干發(fā)現(xiàn)網(wǎng)絡(luò)（重疊）社區(qū)的算法，主要貢獻如下:
　　(1)揭示了社區(qū)發(fā)現(xiàn)問題和聚類分析問題之間的區(qū)別和聯(lián)系，利用聚類分析中定義的相似度概念對GN(Girvan and Ne

4、wman)算法進行改進，給出了快速的SGN（GN based on similarity）算法。通過比較和分析，我們發(fā)現(xiàn)，在構(gòu)造了網(wǎng)絡(luò)節(jié)點的相似度矩陣以后，社區(qū)發(fā)現(xiàn)問題就轉(zhuǎn)化為了聚類問題，并利用任意一種可靠的聚類方法對網(wǎng)絡(luò)進行社區(qū)劃分;接著，本文分析和比較了不同的網(wǎng)絡(luò)節(jié)點相似度構(gòu)造方法和不同的聚類算法在發(fā)現(xiàn)社區(qū)時的性能差異，并將相似度計算引入到傳統(tǒng)的GN算法中，取代GN算法中計算非常耗時的介數(shù)計算，得到改進的GN算法SGN，從而降低了G

5、N算法的時間復(fù)雜度。
　　(2)提出了一種基于類原型的復(fù)雜網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)的一般框架，并結(jié)合實際的聚類算法進行應(yīng)用。通過研究，我們發(fā)現(xiàn)，網(wǎng)絡(luò)中的重疊節(jié)點往往位于各個社區(qū)的邊界地區(qū)，即不同社區(qū)的交匯部分?；谶@樣的特征，我們利用類原型聚類算法的思想和概念，通過定義和計算網(wǎng)絡(luò)中節(jié)點的類原型歸屬度信息，設(shè)計了一個基于類原型的復(fù)雜網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)方法的框架，并將該框架應(yīng)用于幾種常見的聚類算法，例如K-means算法、AP(Affinity

6、Propagation)算法、層次聚類算法AL(Average Linkage)和NJW(Ng，Jordanand Weiss)譜聚類算法。基于我們框架的方法不僅能發(fā)現(xiàn)網(wǎng)絡(luò)中的非重疊社區(qū)，而且能夠有效地發(fā)現(xiàn)網(wǎng)絡(luò)中的重疊社區(qū)。
　　(3)提出了基于排序中心度的K-rank算法。類似K-means算法，K-rank算法通過不斷迭代更新各個社區(qū)的中心節(jié)點從而達到收斂。同時，K-rank算法通過計算各個節(jié)點的中心度準則(rank cent

7、rality)找到社區(qū)的中心節(jié)點，避免了K-means算法在迭代過程中容易產(chǎn)生空類的情形。然后對K-rank算法進行擴展，使之能夠應(yīng)用于有向網(wǎng)、加權(quán)網(wǎng)以及重疊社區(qū)網(wǎng)絡(luò)。
　　(4)提出了一個基于貪婪優(yōu)化surprise函數(shù)的社區(qū)發(fā)現(xiàn)方法AGSO(Algorithmbased on Greedy Surprise Optimization)以及它的加速算法FAGSO(Fast-AGSO)。相關(guān)文獻指出，相比傳統(tǒng)的社區(qū)劃分評價標準-模