復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法的研究及其應(yīng)用.pdf

1、復(fù)雜網(wǎng)絡(luò)是復(fù)雜系統(tǒng)的表現(xiàn)形式，由于這樣的網(wǎng)絡(luò)其節(jié)點數(shù)量規(guī)模較大，而且節(jié)點與節(jié)點之間的聯(lián)系較為復(fù)雜，所以這樣的網(wǎng)絡(luò)就被稱為“復(fù)雜網(wǎng)絡(luò)”。近年來，隨著對復(fù)雜網(wǎng)絡(luò)特性的分析不斷深入，探索網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)逐漸成為研究熱點。揭示網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)，對于了解網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、分析網(wǎng)絡(luò)特性、理解網(wǎng)絡(luò)中各個部分的功能、發(fā)現(xiàn)網(wǎng)絡(luò)中隱藏的規(guī)律和預(yù)測網(wǎng)絡(luò)的行為都尤為重要，而揭示社團(tuán)結(jié)構(gòu)的方法就是利用網(wǎng)絡(luò)中所已知的特性和信息，將看似無規(guī)律的網(wǎng)絡(luò)劃分出隱藏在其中的結(jié)構(gòu)

2、。
　　 由于現(xiàn)存的大部分社團(tuán)發(fā)現(xiàn)算法是基于網(wǎng)絡(luò)的整體進(jìn)行計算和劃分，其缺點為時間復(fù)雜度相對較高，并且其針對性也相對較弱。本論文認(rèn)為，根據(jù)已知的網(wǎng)絡(luò)局部信息所劃分出的“局部社團(tuán)結(jié)構(gòu)”將對于一些網(wǎng)絡(luò)的研究更加有針對性。在本文中所提到的“局部社團(tuán)結(jié)構(gòu)”是指根據(jù)提供的網(wǎng)絡(luò)局部信息，按照某種規(guī)則而劃分出的社團(tuán)結(jié)構(gòu)，該結(jié)構(gòu)對所給出的局部信息有著特殊的意義。本文提出了兩種針對不同情況的局部社團(tuán)劃分算法：
　　 (1)基于二部圖的社團(tuán)

3、劃分算法。二部圖結(jié)構(gòu)相對簡單，將原網(wǎng)絡(luò)抽象成為二部圖結(jié)構(gòu)的形式，并將原網(wǎng)絡(luò)的節(jié)點作為二部圖中的“下集節(jié)點”。在已知某兩點的條件下，通過二部圖得到其對應(yīng)的初始社團(tuán)結(jié)構(gòu)，利用初始社團(tuán)結(jié)構(gòu)在“下集投影”中利用Aaron Clauset算法和邊介數(shù)等概念，劃分出與已知節(jié)點相關(guān)的“相似性社團(tuán)”結(jié)構(gòu)。由于在進(jìn)行局部社團(tuán)劃分時并不需要對整個網(wǎng)絡(luò)進(jìn)行計算，該算法在對隨機給出的節(jié)點進(jìn)行計算時，有比較好的即時性。此方法適用于發(fā)現(xiàn)與已知節(jié)點相關(guān)的“相似性社團(tuán)

4、”。
　　 (2)基于中心度發(fā)現(xiàn)社團(tuán)將度中心度與流介數(shù)中心度相結(jié)合，首先計算出節(jié)點的度中心度和流介數(shù)中心度，得出網(wǎng)絡(luò)中的幾何中心點和信息、物質(zhì)或能量在網(wǎng)絡(luò)上傳輸時經(jīng)過路徑最多的節(jié)點，并將這兩個指標(biāo)作為一個整體考慮，得到這兩個指標(biāo)相對比較大的節(jié)點，再在這些節(jié)點和其鄰居節(jié)點上利用派系過濾算法(CPM)，從而發(fā)現(xiàn)網(wǎng)絡(luò)中的“中心社團(tuán)”。此方法可以發(fā)現(xiàn)網(wǎng)絡(luò)中相對“重要”的社團(tuán)，這對復(fù)雜網(wǎng)絡(luò)上的傳播機理、相繼故障等分析都有一定的意義。隨后利