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

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

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

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

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