【文章內(nèi)容簡介】 i 的用度 ik 表示， ik 代表節(jié)點(diǎn) i 所有連接的邊的數(shù)目。表面上，度值大的節(jié)點(diǎn)具有貌似有更重要的功能，第 i 個(gè)節(jié)點(diǎn)的度用下面的公式表示： ??? Nj iji ak （ 27） 網(wǎng)絡(luò)的平均度是指所有的點(diǎn)的度的平均值我們用 ??k 代表，并可以根據(jù)公式來計(jì)算 ?????Ni ikNk 11 （ 28） 網(wǎng)絡(luò)的平均度代表了整個(gè)網(wǎng)絡(luò)的密集程度 ??k 越大的網(wǎng)絡(luò)它的密度越大。 2)節(jié)點(diǎn)度分布 度反應(yīng)了節(jié)點(diǎn)的性質(zhì)，也反應(yīng)了 網(wǎng)絡(luò)某個(gè)單位的特點(diǎn)，只能從細(xì)節(jié)反應(yīng)網(wǎng)絡(luò)不能夠全面的對(duì)網(wǎng)絡(luò)進(jìn)行描述。節(jié)點(diǎn)度的分布可以用函數(shù)來進(jìn)行刻畫 )(kp ，我們理解為任意的節(jié)點(diǎn)有 k 條邊連接的概率。度的分布屬于正態(tài)分布，隨機(jī)網(wǎng)絡(luò)的節(jié)點(diǎn)如果限定了那么它也屬于正態(tài)分布。 )(kp e? !kkkk? （ 29） 圖 (a)正態(tài)分布（ b）冪率分布 其中 k 為隨機(jī)網(wǎng)中節(jié)點(diǎn)度值的平均值，正態(tài)的峰值是 k ，兩邊逐漸的緩慢下降，比平均值高出很多或者小于很多的節(jié)點(diǎn)幾乎不存在，我們叫做隨大流網(wǎng)絡(luò)。 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 10 頁 ， 共 34 頁 在過去的幾十年里，科學(xué)家們把網(wǎng)絡(luò)都當(dāng)做是隨機(jī)網(wǎng)絡(luò)，隨機(jī)圖論就是為了方便研究數(shù)據(jù)網(wǎng)絡(luò)而建立的，最近的研究表明這樣是錯(cuò)誤的：我們生活的網(wǎng)絡(luò)里面大部分都是不遵循正態(tài)分布是，他們的節(jié)點(diǎn)的度的分布更接近于冪率分布 ???kkP )( （ 210） 當(dāng)γ大于 2 小于 3的時(shí)候，冪律分布要比指數(shù)型的網(wǎng)絡(luò)要更為緩和一些，所以節(jié)點(diǎn)可以有很大的度。遵循了冪律分布的網(wǎng)絡(luò)，它們幾點(diǎn)的度值大小相差很多，存在有極大或者極小的。少數(shù)節(jié)點(diǎn)的度值很大，但是這樣的節(jié)點(diǎn)數(shù)量很少，在整個(gè)網(wǎng)絡(luò)咯具有很關(guān)鍵作用，被看做是中心節(jié)點(diǎn)，連接了絕大部分的節(jié)點(diǎn)；很多的節(jié)點(diǎn)度值很小，卻只連接了一個(gè)或者幾個(gè)節(jié)點(diǎn)。在因特網(wǎng)里面度值小于 3的占到整個(gè)網(wǎng)絡(luò) 的 80%。我們得出這樣的結(jié)論：冪指數(shù)越大， 異質(zhì)性就越差；相反，冪指數(shù)越小異質(zhì)性就越是突出。 我們把遵循冪律分布的網(wǎng)絡(luò)叫做無標(biāo)度網(wǎng)絡(luò)，和隨機(jī)網(wǎng)絡(luò)截然不同，這也是無標(biāo)度網(wǎng)絡(luò)的本質(zhì)特點(diǎn)。假如在英特網(wǎng)的度值很大的節(jié)點(diǎn)上進(jìn)行攻擊，那么這樣的攻擊會(huì)造成整個(gè)網(wǎng)絡(luò)的崩潰，所以要保證這些節(jié)點(diǎn)的魯棒性就非常的重要了。 實(shí)際中的網(wǎng)絡(luò)拓?fù)? 大家對(duì) 和 inter 都比較熟悉他們是令我們現(xiàn)在關(guān)注的，在過去的短短幾十年發(fā)展勢如破竹，是人們現(xiàn)在信息生活不可以缺少的。他們改變了人們傳統(tǒng)的信息發(fā)送與接收，對(duì)各個(gè)領(lǐng)域都有重大影 響 。 Inter Inter 是由計(jì)算機(jī)、路由器和其他的網(wǎng)絡(luò)設(shè)備組成，這些硬件為信息傳輸提供了條件， inter 研究是在 AS 和 ROUTER 兩個(gè)層面進(jìn)行的圖 27 所示。在路由層，我們把每個(gè)路由器當(dāng)做是一個(gè)單位，不同路由器之間的連接線路當(dāng)成邊。在 AS 中我們把很多的路由器和計(jì)算機(jī)工作機(jī)看做一個(gè)單位，只要他們間有物理鏈路我們就可以看做他們的一條邊。 Topology Generator 的設(shè)計(jì)是因?yàn)榭茖W(xué)家們要對(duì) inter 特性進(jìn)行研究，但是研究者們對(duì) inter 缺乏很多基本的理解，所以 實(shí)驗(yàn)結(jié)果總是不太滿意。在 1999 年， Faloutsos 等對(duì) Inter 的 AS 和 ROUTER的度分布上做了研究，發(fā)現(xiàn)了度分布滿足 冪律分布 P ( k ) ~ kγ ，并在之前的的 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 11 頁 ， 共 34 頁 兩年里計(jì)算出了度數(shù)在 γ = 和 γ = 之間。 20xx 年， Govindan 和Tangmunarunkit 對(duì) AS 上的 inter 做了更進(jìn)一步的研究求得 γ =，如圖 所示。 Inter 拓?fù)?BA 的發(fā)現(xiàn)對(duì)究者們開發(fā)新的模擬工具帶來巨大的動(dòng)力。 Yook和 PastorSatorras 等人對(duì)自治系統(tǒng)層進(jìn)行了研究，研究結(jié)果表明了英特網(wǎng)的集聚系數(shù)在 到 中間變化，相同條件下 ER 網(wǎng)絡(luò)集聚系數(shù)為 。 圖 英特網(wǎng)的第三層和 AS 層 圖 第三層在英特網(wǎng)上的度的分布 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 12 頁 ， 共 34 頁 WWW 是我們可以獲得網(wǎng)絡(luò)拓?fù)涞淖畲笠粋€(gè)，節(jié)點(diǎn)是網(wǎng)頁，他們的邊就是超鏈接， 如圖 2－ 9。邊有方向性， WWW 是有向網(wǎng)絡(luò)具有向量的特性，目前為止該網(wǎng)絡(luò)的節(jié)點(diǎn)早已經(jīng)大于 80 億了。 它的度分布大概就是由出度 P out ( k )和入度Pin ( k )兩個(gè)部分組成的， P out ( k )表示網(wǎng)頁具有 K 個(gè)對(duì)外發(fā)出連接的概率 ， Pin ( k )表示發(fā)出 K連接都連接到同一個(gè)網(wǎng)頁的幾率大小。他們的冪律分布公式可以用下面的表示 ： Pout ( k ) ~ k outγ , Pin ( k )~k inγ （ 211） 有人利用軟件搜集了很多網(wǎng)頁鏈接數(shù)據(jù)用來實(shí)驗(yàn)，很大的數(shù)據(jù)量表明萬維網(wǎng)的出入度指數(shù)： γout = 和 γin =。 Albert 等人研究了 WWW 的一個(gè)子集，即 域名下的 325, 729 個(gè)節(jié)點(diǎn)，得出 γout = 和 γin =。 20xx 年，又有人利用其他的一些工具收 集了萬維網(wǎng)上數(shù)以億計(jì)的網(wǎng)頁和龐大的連接數(shù)據(jù)，再次得到了新的數(shù)據(jù) γout = 和 γin =，如圖 2－ 3 所示。一個(gè)令人注意的問題是，他們?cè)谘芯窟@個(gè)時(shí)花了接近兩年的時(shí)間，一個(gè)很實(shí)際的問題就是萬維網(wǎng)的數(shù)據(jù)量也增大了接近 5 倍，不過研究結(jié)果表明入度指數(shù)是毫無變化的。 圖 萬維網(wǎng)的出入度 萬維網(wǎng)的邊具有有向性，我們不能直接使用公式 （ 211）去計(jì)算它的集聚系數(shù)，我們可以把有向轉(zhuǎn)變無向，讓單向變成雙 向。 Lada Adamic 研究了深入到了 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 13 頁 ， 共 34 頁 網(wǎng)址層次的 萬維網(wǎng)，把每個(gè)網(wǎng)址作為一個(gè)節(jié)點(diǎn)，只要存在那么一個(gè)指向另一個(gè)，我們就認(rèn)為是相連的。為此他利用了接近 15 萬個(gè)網(wǎng)址以及他們的數(shù)據(jù)，得到網(wǎng)絡(luò)集聚系數(shù) C =。但是包含有一樣節(jié)點(diǎn)數(shù)和平均值的 ER 他們的系數(shù)卻為Crand =。 雖然 WWW 里面節(jié)點(diǎn)數(shù)很大，但是它還是體現(xiàn)了小世界的特性。利用 robot這個(gè)軟件能夠在萬維網(wǎng)里面進(jìn)行路由，統(tǒng)計(jì)里面的連接，根據(jù)他的邊順藤摸瓜的找 到它的出發(fā)點(diǎn)。利用這種方法搜索了接近 33 萬個(gè)網(wǎng)頁，得到結(jié)論研究的這些網(wǎng)絡(luò)他們的平均路徑長度 。得到了一個(gè)公式 L=+ log(N) （ 212） 其他網(wǎng)絡(luò)閱讀概述 我們生活的世界中也有其他不同類型的網(wǎng)絡(luò)，像人際關(guān)系網(wǎng)、食物鏈關(guān)系網(wǎng)、電力系統(tǒng)網(wǎng)、交通運(yùn)輸?shù)群芏嗖煌愋偷木W(wǎng)絡(luò)。很大部分的復(fù)雜網(wǎng)絡(luò)都體現(xiàn)了小世界效應(yīng)和無標(biāo)度效應(yīng)的特點(diǎn)，下圖 和表 所示，不僅如此，在實(shí)際生活里的無標(biāo)度網(wǎng)絡(luò)，他們所擁有的度指數(shù)基本是大于 2小于 3的的區(qū)間。 每個(gè)不同的網(wǎng)絡(luò)，給了很多不同的參數(shù)例如路由器數(shù)、他們連接線的平均度值 k、網(wǎng)絡(luò)連接線平均路徑長度 L 和集聚系數(shù) C 。利用之前的作為對(duì)比，我們利用了和物理網(wǎng)絡(luò)擁有一樣節(jié)點(diǎn)以及平均度值的 ER 網(wǎng)絡(luò) Lrznd 和 Crznd 。 表 幾種網(wǎng)絡(luò)的拓?fù)鋽?shù)據(jù) 下面是幾個(gè)模擬無標(biāo)度網(wǎng)絡(luò)的度指數(shù)。指出復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的路由器個(gè)數(shù)和連接線的平均度值 ??k 。 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 14 頁 ， 共 34 頁 表 幾種網(wǎng)絡(luò)在實(shí)際中的無標(biāo)度指數(shù)： 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 15 頁 ， 共 34 頁 第三章 復(fù)雜網(wǎng)絡(luò)模型 上面那章介紹了 網(wǎng)絡(luò)的拓?fù)涮攸c(diǎn)和路由的基本原則，這個(gè)是我們進(jìn)行研究的前提。想要更深層次研究和處理好這些模型和我們的實(shí)際更加的接近那么久要尋找更加好的方法。就當(dāng)前來說，有學(xué)者已經(jīng)將復(fù)雜網(wǎng)絡(luò)模型規(guī)劃為很多不同的網(wǎng)絡(luò)，仍然有不少的學(xué)者認(rèn)為復(fù)雜網(wǎng)絡(luò)不含有隨機(jī)和規(guī)則這兩種網(wǎng)絡(luò)。 隨機(jī)網(wǎng)絡(luò) a) 全局耦合網(wǎng)絡(luò) b) 最近鄰耦合網(wǎng)絡(luò) 圖 兩種規(guī)則網(wǎng)絡(luò) 在 1930 年左右，研究者們發(fā)現(xiàn)真實(shí)系統(tǒng)他們子系統(tǒng)單元之間的關(guān)系可以用某些規(guī)則的結(jié)構(gòu)代表。這樣被稱為規(guī)則的網(wǎng)絡(luò)模型。如圖 。 所以在有一樣路由器數(shù)的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)里面，有值最小的路由路徑 1?L 和值最大 1?C 。一個(gè)有N 個(gè)點(diǎn)的全局耦合網(wǎng)絡(luò)有 2/)1( ?NN 條邊， 但是我們?cè)趯?shí)際中遇到的很 多大型實(shí)際網(wǎng)絡(luò)都沒有那么密集，他們的連接鏈路數(shù)量最多就是 )( 2NO 。 有個(gè)稀疏模型是經(jīng)過很多研究而得到的實(shí)驗(yàn)結(jié)果，任何一個(gè)節(jié)點(diǎn)會(huì)連接與他相鄰的點(diǎn)，如圖 。最近鄰耦合網(wǎng)絡(luò)由 N 個(gè)路由單位他們圍成了一個(gè)圓形滿足周期邊界的基本因素，任何的路由單位和他相鄰的 2/K 個(gè)鄰節(jié)點(diǎn)連接。在此 K值是一個(gè)很大的偶數(shù)。 N個(gè)節(jié)點(diǎn)組成一個(gè)圓形，任何一個(gè)節(jié)點(diǎn)都和他相鄰連 接的點(diǎn)，這樣的一個(gè)網(wǎng)絡(luò)的聚類系數(shù)可以用公式表示為： 43)1(4 )2(3 ???? KKC （ 31） 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 16 頁 ， 共 34 頁 因此，如此的網(wǎng)絡(luò)的高密度的網(wǎng)絡(luò)。但是，這樣并不是小世界網(wǎng)絡(luò)，針對(duì)于這個(gè)不會(huì)變化的 K 值，這個(gè)網(wǎng)絡(luò)的均值路由連接線長度為： )(2 ????? NkNL （ 32） 規(guī)則網(wǎng)絡(luò)每個(gè)單位包含的連接數(shù)量和方式都是一樣的。 和規(guī)則網(wǎng)絡(luò)對(duì)立的是 ER 網(wǎng)絡(luò)，數(shù)學(xué)家 Edros 和 Renyi 在 20世紀(jì) 60年代制作了一個(gè)典型的 ER 模型，他們指出：設(shè)想一個(gè)網(wǎng)絡(luò)里面有 N個(gè)單位，任何兩個(gè)節(jié)點(diǎn)連接的概率為 P 。這樣就有 P 個(gè)單位，可以估算出接近具有 2/)1( ?NpN 條邊模型圖。隨機(jī)圖演化過程如圖 0?p ?p ?p 圖 隨機(jī)圖的演化示意圖 隨機(jī)圖理論的的目標(biāo)是為了找出到底是哪樣的連接方法才會(huì)得到概率 p 下，讓圖產(chǎn)生一種特定的性質(zhì)。 ER 的的實(shí)驗(yàn)我們發(fā)現(xiàn)了如果在給定的概率下這樣的條件，那么很多圖形都含有一些相同的性質(zhì)，或者是相反的結(jié)果都不含有。 隨機(jī)網(wǎng)絡(luò)的一些特點(diǎn)我們 可以總結(jié)出來有一下這么幾點(diǎn) ： (1)當(dāng) 0?p 時(shí)，連接線就是 0，網(wǎng)絡(luò)里面的單位都是獨(dú)立存在的毫無關(guān)系可言 ??k =0， 0?C ， 0?L ； (2)當(dāng) 1?p 時(shí)，邊數(shù)為 2/)1( ?NN ，網(wǎng)絡(luò)所有的單位都有聯(lián)系相互之間都是直連到網(wǎng)絡(luò)中任何節(jié)點(diǎn)的路徑都是 1； (3)當(dāng) 10 ??p (一般情況 )時(shí)，網(wǎng)絡(luò)連接數(shù)在零和 2/)1( ?NN 之間，網(wǎng)絡(luò)中 節(jié)點(diǎn)度的平均值 pNNpk ????? )1( ， pC? ， ??? kNL ln/ln ， 度分布為：kNkkN ppCkp ??? )1()( （ 33） 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 17 頁 ， 共 34 頁 當(dāng) N 占的比例很大，每條連接線出現(xiàn)或者消失都互不影響，很多路由器單位擁有的度一致，在這個(gè)時(shí) 候 ER 模型的度分布可以用以下公式來表示： !! )()( kkekpNekp kkkpN ???? ???? （ 34） 圖 隨機(jī)網(wǎng)絡(luò)的度度分布 這樣的分布在度的均值出有峰值，兩側(cè)呈指數(shù)遞減，所以該網(wǎng)絡(luò)也被稱作指數(shù)網(wǎng)絡(luò)，因?yàn)?Nln 的值隨 N 增長很慢，這么一來雖然不小的網(wǎng)絡(luò)結(jié)構(gòu)仍然有不大的均值路徑長度。 小世界網(wǎng)絡(luò) 模型的構(gòu)造算法如下： (l)從規(guī)則網(wǎng)絡(luò)開始：設(shè)想有個(gè)比較近的鄰耦合網(wǎng)絡(luò)含有 P 個(gè)單位，所有的單位組成了一個(gè)圓圈，任何節(jié)點(diǎn)和他相鄰的兩個(gè)單位相互連接， K 非奇數(shù)。想要獲得一個(gè)密度不大實(shí)際上又時(shí)刻都是連通狀態(tài)的網(wǎng)絡(luò)，可以想到1ln ?????? NKN 。 (2)隨機(jī)化重連：任意的從網(wǎng)絡(luò)里面選出節(jié)點(diǎn)，一條邊上的一個(gè)節(jié)點(diǎn)不變，連接線的那一頭的節(jié)點(diǎn)再次重新選取。 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 18 頁 ， 共 34 頁 0?p 1?p隨 機(jī) 性 增 加規(guī) 則 小 世 界 隨 機(jī) 圖 WS 模型里面邊的隨機(jī)重連過程 在圖 中，