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

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

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

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