復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)劃分算法研究.pdf

1、社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)普遍而又重要的拓?fù)鋵傩灾唬哂袌F(tuán)內(nèi)連接緊密、團(tuán)間連接稀疏的特點(diǎn)。揭示網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)對(duì)分析復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、理解其功能、發(fā)現(xiàn)其隱含模式以及預(yù)測(cè)網(wǎng)絡(luò)行為都有十分重要的理論意義和廣泛的應(yīng)用前景。
　　 近年來(lái)，針對(duì)不同類型的大規(guī)模復(fù)雜網(wǎng)絡(luò)，人們提出了許多劃分社團(tuán)結(jié)構(gòu)的算法。本文在總結(jié)復(fù)雜網(wǎng)絡(luò)的基本概念、社團(tuán)結(jié)構(gòu)定義的基礎(chǔ)上，比較和分析了復(fù)雜網(wǎng)絡(luò)領(lǐng)域一些具有代表性的社團(tuán)結(jié)構(gòu)劃分算法，并展望了該領(lǐng)域的未來(lái)研究方向。然而

2、，早期基于全局信息劃分整個(gè)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)的算法，很難適應(yīng)于規(guī)模較大的復(fù)雜網(wǎng)絡(luò)，而現(xiàn)實(shí)生活中有很多情況卻只需要關(guān)注網(wǎng)絡(luò)的局部社團(tuán)結(jié)構(gòu)，為此，需要尋找新的方法進(jìn)行網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的劃分。本文針對(duì)上述問(wèn)題進(jìn)行了深入研究。
　　 本論文所做的主要工作如下：
　　 首先，針對(duì)大型復(fù)雜網(wǎng)絡(luò)信息不易獲取、現(xiàn)有算法時(shí)間復(fù)雜度高的缺陷以及對(duì)劃分節(jié)點(diǎn)局部社團(tuán)的現(xiàn)實(shí)需求，我們提出了一種利用邊連接強(qiáng)度改進(jìn)局部模塊度的局部社團(tuán)劃分算法--LCD-Li

3、nkS算法。該算法利用網(wǎng)絡(luò)局部信息，以局部模塊度作為標(biāo)準(zhǔn)貪婪地選擇節(jié)點(diǎn)進(jìn)行社團(tuán)劃分。該算法僅需要知道節(jié)點(diǎn)的局部信息，其時(shí)間復(fù)雜度為O(k2d4)，而且劃分的社團(tuán)模塊度高。
　　 其次，提出了節(jié)點(diǎn)和社團(tuán)之間關(guān)系的度量方法，即節(jié)點(diǎn)貢獻(xiàn)度。節(jié)點(diǎn)貢獻(xiàn)度由兩部分組成，節(jié)點(diǎn)和社團(tuán)的連邊數(shù)目和社團(tuán)自身的稠密度。并在此基礎(chǔ)上給出了一種比較型的社團(tuán)結(jié)構(gòu)定義?；诠?jié)點(diǎn)貢獻(xiàn)度的社團(tuán)定義和其他僅比較節(jié)點(diǎn)同社團(tuán)連接頻數(shù)的定義相比較，前者更符合無(wú)標(biāo)度網(wǎng)絡(luò)的

4、特性。
　　 再次，針對(duì)基于社團(tuán)吸引力的劃分算法存在節(jié)點(diǎn)歧義性問(wèn)題，提出了一種基于節(jié)點(diǎn)貢獻(xiàn)度的快速社團(tuán)劃分算法--FCD-NodeC算法。該算法根據(jù)節(jié)點(diǎn)貢獻(xiàn)度及社團(tuán)的定義，通過(guò)網(wǎng)絡(luò)社團(tuán)自形成過(guò)程進(jìn)行全局網(wǎng)絡(luò)社團(tuán)劃分。該算法的復(fù)雜度為O(Lnd2/2)，當(dāng)d<　　 最后，針對(duì)LCD-LinkS和FCD-NodeC算法，在基準(zhǔn)網(wǎng)絡(luò)、經(jīng)典的社會(huì)關(guān)系網(wǎng)絡(luò)College Football networ