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

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

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

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

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