基于節(jié)點關(guān)系的社團識別算法研究.pdf

1、自然界中存在大量的復(fù)雜系統(tǒng)，如生態(tài)系統(tǒng)、網(wǎng)絡(luò)系統(tǒng)、通信系統(tǒng)和經(jīng)濟系統(tǒng)等。這些復(fù)雜系統(tǒng)往往是由多個交互的單元組成，這些單元之間存在一定的聯(lián)系。為了了解復(fù)雜系統(tǒng)的功能和行為、各個單元的相互作用方式，必須借助網(wǎng)絡(luò)進行研究。復(fù)雜系統(tǒng)中的單元對應(yīng)為網(wǎng)絡(luò)中的點，而各個單元間的聯(lián)系則對應(yīng)為網(wǎng)絡(luò)中的邊，由于復(fù)雜系統(tǒng)節(jié)點數(shù)目龐大，對應(yīng)網(wǎng)絡(luò)中節(jié)點數(shù)目較多，這樣的網(wǎng)絡(luò)被稱為復(fù)雜網(wǎng)絡(luò)。隨著復(fù)雜網(wǎng)絡(luò)研究的深入，研究學(xué)者們發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)有較多結(jié)構(gòu)特征，而社團結(jié)構(gòu)是其

2、最重要特征之一。復(fù)雜網(wǎng)絡(luò)的社團結(jié)構(gòu)不僅能夠幫助我們理解大規(guī)模網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，還能反映其對應(yīng)的現(xiàn)實復(fù)雜系統(tǒng)中各單元、模塊的功能，為現(xiàn)實世界中復(fù)雜系統(tǒng)的復(fù)雜性研究提供十分重要的意義。因此，復(fù)雜網(wǎng)絡(luò)中社團結(jié)構(gòu)的識別成為研究復(fù)雜網(wǎng)絡(luò)的熱點話題之一。
　　目前研究學(xué)者們已提出很多社團結(jié)構(gòu)識別算法并將其應(yīng)用到實際網(wǎng)絡(luò)中，但是算法還存在一定的不足。本文主要從算法的時間復(fù)雜度、算法識別效果以及算法初始條件方面進行改進：
　　(1)基于中心節(jié)

3、點的局部社團識別算法。算法首先計算網(wǎng)絡(luò)中各節(jié)點的度和聚集系數(shù)，選取網(wǎng)絡(luò)中度最大且聚集系數(shù)也最大的節(jié)點作為中心節(jié)點，并將其作為獨立的起始社團，同時將其加入已訪問節(jié)點集合。然后更新當(dāng)前社團的鄰居節(jié)點集合，計算鄰居集合中節(jié)點與社團的連接強度，通過不斷地將連接強度最大的節(jié)點加入社團，網(wǎng)絡(luò)的局部社團結(jié)構(gòu)被識別出。該算法只需要知道少量的網(wǎng)絡(luò)局部信息就能將社團識別出，時間復(fù)雜度較低，將該算法應(yīng)用到人工網(wǎng)絡(luò)和社團結(jié)構(gòu)較為明顯的實際網(wǎng)絡(luò)，識別出的社團效果

4、較好，實驗分析驗證了算法的可行性。
　　(2)基于相鄰節(jié)點相似度的社團結(jié)構(gòu)識別算法。針對已有相似度構(gòu)造方法的不足而提出改進的相鄰節(jié)點相似度，該算法將相鄰節(jié)點相似度與社團強度的量化定義結(jié)合，通過不斷刪除相似度矩陣中最小值元素對應(yīng)的邊，最終將網(wǎng)絡(luò)中符合要求的社團識別出。將本文算法與其他算法作比較，可知算法識別出的社團結(jié)構(gòu)效果較好，同時算法開始時不需要提前知道社團的數(shù)目，時間復(fù)雜度較低。將算法應(yīng)用到人工網(wǎng)絡(luò)和現(xiàn)實網(wǎng)絡(luò)中，實驗分析驗證算法