無標(biāo)度網(wǎng)絡(luò)及其應(yīng)用研究.pdf

1、在過去的十多年中，Internet和WWW的飛速發(fā)展改變了社會(huì)信息傳播與交流的方式，深刻地影響著人們的日常工作與生活，人類社會(huì)進(jìn)入了網(wǎng)絡(luò)信息時(shí)代。但是，人們對(duì)Internet和WWW的拓?fù)浣Y(jié)構(gòu)、組織層次以及發(fā)生在它們之上的各種行為等還知之甚少。事實(shí)上，Internet和WWW與現(xiàn)實(shí)中的許多網(wǎng)絡(luò)模型一樣，例如科學(xué)合作網(wǎng)、科技引文網(wǎng)、國家電力網(wǎng)、社會(huì)關(guān)系網(wǎng)、生物捕食網(wǎng)等等，都具有復(fù)雜網(wǎng)絡(luò)的特征。復(fù)雜網(wǎng)絡(luò)的復(fù)雜性體現(xiàn)在如下三個(gè)方面：結(jié)構(gòu)復(fù)雜性

2、、節(jié)點(diǎn)復(fù)雜性以及各種復(fù)雜性的相互作用與影響。 多年來，隨機(jī)圖模型、小世界網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)等重要復(fù)雜網(wǎng)絡(luò)模型的提出與研究，激起了物理學(xué)、數(shù)學(xué)、生物學(xué)、社會(huì)學(xué)和工程界等眾多學(xué)科研究者們的興趣，掀起了研究復(fù)雜網(wǎng)絡(luò)的熱潮。在隨機(jī)圖模型中，每對(duì)節(jié)點(diǎn)有邊相連的概率為一個(gè)常數(shù)，該模型的許多重要性質(zhì)都是突然涌現(xiàn)的。在小世界網(wǎng)絡(luò)中，其平均最短路長度與網(wǎng)絡(luò)尺寸的對(duì)數(shù)同階，且具有較大的聚類系數(shù)。度分布滿足冪律分布特性的網(wǎng)絡(luò)稱為無標(biāo)度網(wǎng)絡(luò)，無標(biāo)度網(wǎng)絡(luò)的

3、兩個(gè)基本演化機(jī)理為：增長性和擇優(yōu)連接性。 由于現(xiàn)實(shí)中眾多復(fù)雜網(wǎng)絡(luò)均具有無標(biāo)度特性，因此有必要對(duì)其進(jìn)行深入研究。本文首先在分析無標(biāo)度網(wǎng)絡(luò)演化規(guī)則的基礎(chǔ)上，著重研究了各種演化網(wǎng)絡(luò)的加速模型。然后，應(yīng)用宏觀調(diào)控的原則方法，給出了一種調(diào)控?zé)o標(biāo)度網(wǎng)絡(luò)度分布的方法。最后，我們分析了無標(biāo)度網(wǎng)絡(luò)的三種應(yīng)用：無標(biāo)度網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)、基于重尾分布的排隊(duì)模型及基于無標(biāo)度特性的Internet虛擬用戶網(wǎng)絡(luò)的分析。 本文所取得的主要成果如下：

4、 (1)在歸納無標(biāo)度網(wǎng)絡(luò)研究?jī)?nèi)容的基礎(chǔ)上，提出了關(guān)于無標(biāo)度網(wǎng)絡(luò)研究的三個(gè)層次，即無標(biāo)度網(wǎng)絡(luò)的拓?fù)溲莼?、無標(biāo)度網(wǎng)絡(luò)的宏觀調(diào)控、無標(biāo)度網(wǎng)絡(luò)的應(yīng)用。其中，無標(biāo)度網(wǎng)絡(luò)的宏觀調(diào)控銜接了無標(biāo)度網(wǎng)絡(luò)的拓?fù)溲莼c無標(biāo)度網(wǎng)絡(luò)的應(yīng)用，具有重要的研究意義。 (2)分析了無標(biāo)度網(wǎng)絡(luò)的演化規(guī)則，著重考慮了網(wǎng)絡(luò)的加速演化特點(diǎn)，提出了按演化周期加速的概念，并把網(wǎng)絡(luò)加速演化分成兩類，即按網(wǎng)絡(luò)規(guī)則加速與按演化周期加速。 (3)考慮了基于Barabási

5、和Albert的BA無標(biāo)度網(wǎng)絡(luò)加速演化模型，利用速率方程方法得到了按演化周期加速時(shí)演化模型及考慮兩種加速演化方式下演化模型的度分布、平均最短路長度和聚類系數(shù)。這兩種模型的度分布均服從冪律分布，且具有小世界特性。通過理論分析與仿真實(shí)驗(yàn)，合理地分析了研究者們往往忽略按演化周期加速這種加速演化模式的三點(diǎn)原因。 (4)研究了基于Ad hoc網(wǎng)絡(luò)的加速演化模型，證明了該網(wǎng)絡(luò)的度分布具有普遍性，是BA無標(biāo)度網(wǎng)絡(luò)、8R(Sarshar and

6、 Roychowdhury)網(wǎng)絡(luò)等的推廣模型，并得到了節(jié)點(diǎn)增加概率與刪除概率的合理取值范圍。 (5)對(duì)權(quán)重網(wǎng)絡(luò)的定義進(jìn)行了分類，比較了靜態(tài)與動(dòng)態(tài)權(quán)重網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特點(diǎn)，并著重研究了動(dòng)態(tài)方法形成的權(quán)重網(wǎng)絡(luò)的加速演化模型。研究表明，對(duì)于靜態(tài)方法形成的權(quán)重網(wǎng)絡(luò)，其強(qiáng)度分布對(duì)于不同權(quán)重定義有較大差別；對(duì)于動(dòng)態(tài)方法形成的權(quán)重網(wǎng)絡(luò)，其度分布與初始權(quán)重定義沒有必然聯(lián)系，只要在演化過程中滿足“強(qiáng)度擇優(yōu)性”，就可得到冪律分布。另外，只要權(quán)重網(wǎng)絡(luò)的

7、邊權(quán)重服從某一概率分布，則在演化過程中強(qiáng)度擇優(yōu)連接與度擇優(yōu)連接對(duì)于網(wǎng)絡(luò)的度分布沒有影響，且與具體的概率分布無關(guān)。 (6)研究了無標(biāo)度網(wǎng)絡(luò)宏觀調(diào)控的目的、一般原則與方法，并給出了一種調(diào)控?zé)o標(biāo)度網(wǎng)絡(luò)度分布的方法，即使用全局信息獲取能力的節(jié)點(diǎn)占整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的比例來調(diào)節(jié)網(wǎng)絡(luò)的冪律指數(shù)。此方法能有效地調(diào)節(jié)網(wǎng)絡(luò)冪律指數(shù)的取值，并使之在合理的范圍內(nèi)變動(dòng)。 (7)研究了無標(biāo)度網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)，給出了基于Laplace矩陣譜分解方法中歐氏距