復(fù)雜網(wǎng)絡(luò)上的社團(tuán)結(jié)構(gòu)探測研究.pdf

1、近年來復(fù)雜網(wǎng)絡(luò)研究受到了來自物理以及其它學(xué)科的研究者的廣泛關(guān)注，成為當(dāng)今的一個研究熱點(diǎn)。大量研究已經(jīng)表明在真實世界中各種不同的復(fù)雜網(wǎng)絡(luò)具有許多共同的結(jié)構(gòu)特征，例如小世界性質(zhì)、無標(biāo)度性、社團(tuán)結(jié)構(gòu)等。我們對復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)及其探測方法進(jìn)行了研究。在復(fù)雜網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的存在意味著網(wǎng)絡(luò)通常由若干個社團(tuán)組成，在這些社團(tuán)內(nèi)節(jié)點(diǎn)之間的連接相對緊密，而各個社團(tuán)之間的連接則比較的稀疏。網(wǎng)絡(luò)的這種結(jié)構(gòu)特征對網(wǎng)絡(luò)的動力學(xué)有著重要影響，并且在真實網(wǎng)絡(luò)中這些社

2、團(tuán)通常對應(yīng)著某種功能單元如社會網(wǎng)絡(luò)中真實的社會分組、WWW 上內(nèi)容相關(guān)的網(wǎng)頁、或論文引用網(wǎng)絡(luò)中關(guān)于某個主題的論文。因此，探測分析網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)對我們認(rèn)識和理解真實復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)以及功能有著重要意義。目前，已經(jīng)有許多研究者投身到社團(tuán)結(jié)構(gòu)探測的研究當(dāng)中并提出了各種各樣的算法以便能夠快速而準(zhǔn)確的找到網(wǎng)絡(luò)中的社團(tuán)，但是探測算法的時間復(fù)雜度和準(zhǔn)確性之間的矛盾仍然是大規(guī)模復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)分析面臨的重要問題。在本文中，我們系統(tǒng)分析了已有的社團(tuán)探測算

3、法，然后設(shè)計了一種改進(jìn)社團(tuán)探測算法準(zhǔn)確性的方案，并根據(jù)這個方案，提出了一類改進(jìn)的社團(tuán)探測算法。
　　 本文共分為五章。在第一章我們對復(fù)雜網(wǎng)絡(luò)的研究進(jìn)行了回顧，并介紹了本文的主要研究內(nèi)容。在第二章，我們介紹了復(fù)雜網(wǎng)絡(luò)的主要結(jié)構(gòu)特征，并系統(tǒng)介紹了復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，包括社團(tuán)的定義、社團(tuán)結(jié)構(gòu)探測、以及社團(tuán)劃分的評價。在第三章中我們系統(tǒng)分析了已有的一些社團(tuán)探測算法及其性能。同時，根據(jù)研究的需要我們研究了這些算法如何擴(kuò)展到加權(quán)網(wǎng)絡(luò)，以及在

4、考慮加權(quán)網(wǎng)絡(luò)的內(nèi)在邊權(quán)之后算法的探測能力的變化。根據(jù)前一章的分析，我們在第四章中首先設(shè)計了一個改進(jìn)社團(tuán)探測算法精度的方案，然后據(jù)此提出了一類改進(jìn)的Girvan-Newman 算法，并在計算機(jī)產(chǎn)生的具有已知社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)以及一些真實網(wǎng)絡(luò)上測試了這些算法。測試的結(jié)果顯示無論是在計算機(jī)產(chǎn)生的網(wǎng)絡(luò)上還是在真實網(wǎng)絡(luò)上改進(jìn)后的算法都要比原算法有更優(yōu)異的表現(xiàn)。另外，我們還將改進(jìn)的算法擴(kuò)展到了具有內(nèi)在權(quán)重的網(wǎng)絡(luò)；測試的結(jié)果顯示同樣是考慮了內(nèi)在邊權(quán)，改進(jìn)