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

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

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

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

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

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

6、Propagation)算法、層次聚類(lèi)算法AL(Average Linkage)和NJW(Ng，Jordanand Weiss)譜聚類(lèi)算法?；谖覀兛蚣艿姆椒ú粌H能發(fā)現(xiàn)網(wǎng)絡(luò)中的非重疊社區(qū)，而且能夠有效地發(fā)現(xiàn)網(wǎng)絡(luò)中的重疊社區(qū)。
　　(3)提出了基于排序中心度的K-rank算法。類(lèi)似K-means算法，K-rank算法通過(guò)不斷迭代更新各個(gè)社區(qū)的中心節(jié)點(diǎn)從而達(dá)到收斂。同時(shí)，K-rank算法通過(guò)計(jì)算各個(gè)節(jié)點(diǎn)的中心度準(zhǔn)則(rank cent

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