【正文】 能夠作為丁琳老師的學(xué)徒我感到很榮幸。掌握這些情況對(duì)網(wǎng)絡(luò)建設(shè)會(huì)有巨大幫助，這些已成為了研究者們密切關(guān)注的問題，值得我們?yōu)橹畬Ｑ?。隨機(jī)網(wǎng)絡(luò)和它對(duì)立的小世界網(wǎng)絡(luò)還有具有前兩者的特性的無標(biāo)度網(wǎng)絡(luò)作為本次實(shí)驗(yàn)的代表，基本上能夠滿足需求。基于此，我們還需要更多的實(shí)驗(yàn)進(jìn)一步去研究和發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)里面的信息路由情況。如果出現(xiàn)了一定比例的邊失效了，重新路由信息流到鄰近的邊超過了那些邊的承受力，信息的路由得不到正確的處理被滯留、丟失等，那么整個(gè)網(wǎng)絡(luò)就會(huì)發(fā)生崩潰，信息無法到達(dá)目的網(wǎng)絡(luò)的信息路由魯棒性就很差。重連概率為 時(shí)侯比概率為 的時(shí)候路由魯棒性要強(qiáng)。如果新增加進(jìn)來的邊負(fù)載能力較強(qiáng)，那么網(wǎng)絡(luò)魯棒性就會(huì)稍微的強(qiáng)一些，當(dāng)新增加的邊負(fù)載能力較弱，即使容錯(cuò)系數(shù)較大，那么整個(gè)網(wǎng) 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 26 頁 ， 共 34 頁 絡(luò)的路由魯棒性仍然表現(xiàn)為若，這就是整個(gè)圖所表現(xiàn)出來的情況， 隨著容錯(cuò)系數(shù)的增加，網(wǎng)絡(luò)的路由魯棒性會(huì)時(shí)強(qiáng)時(shí)若，但是最終當(dāng)容錯(cuò)系數(shù)在 的時(shí)候，網(wǎng)絡(luò)的路由魯棒性就很強(qiáng)。 (3)隨機(jī)網(wǎng)絡(luò)：先選取 N 個(gè)節(jié)點(diǎn)，任意的兩個(gè)點(diǎn)他 們會(huì)連接在一起的概率大小為 P=，依照這個(gè)規(guī)則來生成一個(gè)具有 1000 個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)，通過改變連接的概率讓網(wǎng)絡(luò)的平均度為 ，這樣的隨機(jī)網(wǎng)絡(luò)包含了 1997 條邊。我們用下面的公式來衡量網(wǎng)絡(luò)的抵抗 攻擊的能力，用指標(biāo)最大連通子圖中邊的尺寸 Ge ： NeNGe e39。就目前而言，我們國家很多時(shí)候把 matlab 用作網(wǎng)絡(luò)的模擬研究，但是這個(gè)軟件在這方面還是有一定缺陷，他只能生成結(jié)果。 MATLAB 擁有的這些數(shù)據(jù)算法囊括了最簡(jiǎn)單的函數(shù)，研究對(duì)象。目前比較新的 matlab 是以 C++為基礎(chǔ)，但是比前者更為的簡(jiǎn)單，適合了研究者的編寫習(xí)慣。把我們可以考慮到的都用一個(gè)易懂的圖形表示出來，這樣的一個(gè)軟件為許多的科研都提供了諸多方便，為人們打開了一扇新的大門，不利用程序設(shè)計(jì)語言的編程模式，簡(jiǎn)單而高效，這樣的一個(gè)軟件體現(xiàn)了現(xiàn)在世界上軟件的高水平。不管是 BA 模型還是之前的，沒有任何一個(gè)是大家都覺得符合條件的，所以這樣的結(jié)果并不是很理想的。圖 表明了當(dāng) 20 ??mm 這個(gè)值 BA 網(wǎng)絡(luò)的變化經(jīng)歷。 )0(/)( LpL )0(/)( CpCP 圖 WS 小世界模型的聚類系數(shù)和平均路徑長(zhǎng)度隨重連概率 p 的變化關(guān)系 上面的算法我們可以知道 )(pC 和 )(pL 的參數(shù)特性，有了這兩個(gè)特點(diǎn)我們就可以把這樣看做是重連的結(jié)果 ，圖 代表了網(wǎng)絡(luò)的 )(pC 和 )(pL 會(huì)跟著重連概率 p 的改變而改變 。隨機(jī)圖演化過程如圖 0?p ?p ?p 圖 隨機(jī)圖的演化示意圖 隨機(jī)圖理論的的目標(biāo)是為了找出到底是哪樣的連接方法才會(huì)得到概率 p 下，讓圖產(chǎn)生一種特定的性質(zhì)。一個(gè)有N 個(gè)點(diǎn)的全局耦合網(wǎng)絡(luò)有 2/)1( ?NN 條邊， 但是我們?cè)趯?shí)際中遇到的很 多大型實(shí)際網(wǎng)絡(luò)都沒有那么密集，他們的連接鏈路數(shù)量最多就是 )( 2NO 。指出復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的路由器個(gè)數(shù)和連接線的平均度值 ??k 。 雖然 WWW 里面節(jié)點(diǎn)數(shù)很大，但是它還是體現(xiàn)了小世界的特性。他們的冪律分布公式可以用下面的表示 ： Pout ( k ) ~ k outγ , Pin ( k )~k inγ （ 211） 有人利用軟件搜集了很多網(wǎng)頁鏈接數(shù)據(jù)用來實(shí)驗(yàn)，很大的數(shù)據(jù)量表明萬維網(wǎng)的出入度指數(shù)： γout = 和 γin =。 Topology Generator 的設(shè)計(jì)是因?yàn)榭茖W(xué)家們要對(duì) inter 特性進(jìn)行研究，但是研究者們對(duì) inter 缺乏很多基本的理解，所以 實(shí)驗(yàn)結(jié)果總是不太滿意。我們得出這樣的結(jié)論：冪指數(shù)越大， 異質(zhì)性就越差；相反，冪指數(shù)越小異質(zhì)性就越是突出。 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)行描述。設(shè)定無向無權(quán)網(wǎng) ),( EVG? 包含了點(diǎn)的數(shù)量為 N，邊的數(shù)量為 E 。 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 7 頁 ， 共 34 頁 vvvv ...21 （ 21） A(G)= vvvv...21??????????????vvvvvvaaaaaaaaa.....................212222111211 （ 22） 下圖表示了 關(guān)聯(lián)矩陣， v 1 v2v3…v r代表的是點(diǎn)的序號(hào) e1 e2e3…er代表圖形里面邊的序列。 一般情況下，一個(gè)圖的頂點(diǎn)可以用平面的一個(gè)點(diǎn)進(jìn)行描述，網(wǎng)絡(luò)的一條邊可以在平面上用一條線段來描述，就像下面的圖所描繪的。隨機(jī)網(wǎng)絡(luò)、無標(biāo)度網(wǎng)絡(luò)和小世界網(wǎng)絡(luò)就成為了最重要的復(fù)雜網(wǎng)絡(luò)模型，因?yàn)樗麄兪茄芯恐泻苡写硇缘摹ｔ敯粜匝芯康挠?jì)算時(shí)，包含了一些參數(shù)變量，如一定的邊的傳輸路由效率，在實(shí)驗(yàn)的某個(gè)區(qū)域選取一些樣本，每個(gè)單位都路由一個(gè)數(shù)據(jù)流到下一跳看 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 5 頁 ， 共 34 頁 看整個(gè)實(shí)驗(yàn)對(duì)象失效的流量大小反應(yīng)了邊是否處于路由狀態(tài)，成功路由信息后的這些邊占之前路由變得總數(shù)比，這樣的一個(gè)比值就反應(yīng)了網(wǎng)絡(luò)的連通率，網(wǎng)絡(luò)的連通率會(huì)影響到信息路由魯棒性。第三種，在研究他們拓?fù)渖系囊恍┓庆o態(tài)，針對(duì)那些不同結(jié)構(gòu)他們之間發(fā)生的相互作用的特點(diǎn)。從這些經(jīng)驗(yàn)里我們慢慢發(fā)現(xiàn)了問題，網(wǎng)絡(luò)傳輸能力的改變的級(jí)聯(lián)問題，得到它出現(xiàn)故障的最開始以及到結(jié)束的時(shí)候時(shí)間長(zhǎng)度，整個(gè)過程會(huì)延續(xù)多久。 Crutcitti 把網(wǎng)絡(luò)的效率當(dāng)做是一個(gè)參數(shù)，如果節(jié)點(diǎn)的傳輸能力已經(jīng)超 過所能承受的限度時(shí)，這個(gè)節(jié)點(diǎn)不被移除，讓它繼續(xù)保持擁塞的情況，那么計(jì)劃會(huì)通過這個(gè)節(jié)點(diǎn)的數(shù)據(jù)被分別傳輸?shù)狡渌墓?jié)點(diǎn)上。一般情況下，一個(gè)網(wǎng)絡(luò)里面的節(jié)點(diǎn)還有他們之間的路徑的信息流量有最大值，在網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生改變后，原來的信息流量分配大小會(huì)產(chǎn)生變化路由就會(huì)發(fā)生改變，在某些節(jié)點(diǎn)和路徑上可能就會(huì)有很少的流量通過，當(dāng)然也有節(jié)點(diǎn)和路徑上會(huì)接受很多的流量以至于超過了他們自身所能控制的能力。人們渴望有所處在的這些網(wǎng)絡(luò)有很高的安全性和可靠性，這樣一來就使得研究者們對(duì)信息路由魯棒性的熱情投入。當(dāng)這些故障發(fā)生在 這些邊上的時(shí)候，網(wǎng)絡(luò)就會(huì)發(fā)生級(jí)聯(lián)故障，由于一條邊受到了影響，它輸送信息流的能力和攻擊前相比肯定是降低了，里面的信息流無法保證正確的傳輸?shù)较乱粋€(gè)點(diǎn)。 Message routing。 本文首先概述了復(fù)雜網(wǎng)絡(luò)上信息路由的魯棒性研究現(xiàn)狀。其次介紹了復(fù)雜網(wǎng)絡(luò)的基本理論，如拓?fù)浣Y(jié)構(gòu)參數(shù)和典型的網(wǎng)絡(luò)模型。 robustness。因此，會(huì)對(duì)這些信息流進(jìn)行重新路由，重新路由后，這些信息流到達(dá)了新的邊，這些邊的輸送能力是固定的也許大也許小，當(dāng)超過了自身的負(fù)載能力時(shí)就會(huì)發(fā)生和剛才失效的那些邊一樣，這樣級(jí)聯(lián)故障就進(jìn)一步的擴(kuò)大了。通過這些研究得出網(wǎng)絡(luò)結(jié)構(gòu)和其上的信息路由魯棒性之間的相關(guān)性。這樣一來，負(fù)載變大的節(jié)點(diǎn)和路徑就會(huì)變得特別擁塞甚至出現(xiàn)節(jié)點(diǎn)和鏈路的崩潰，網(wǎng)絡(luò)的路由魯棒性就變得糟糕。該實(shí)驗(yàn)證明了傳輸分布越是不平均化的網(wǎng)絡(luò)結(jié)構(gòu)，就算移除了傳輸能力較強(qiáng)的節(jié)點(diǎn)，這樣仍然會(huì)對(duì)網(wǎng)絡(luò)的效率造成影響，最終導(dǎo)致整個(gè)網(wǎng)絡(luò)的級(jí)聯(lián)故障。在這個(gè)級(jí)聯(lián)故障的整個(gè)過程里面，每個(gè)時(shí)間段又是體現(xiàn)了怎么樣的特點(diǎn)。拓?fù)浣Y(jié)構(gòu)是研究這方面的基石，舉個(gè)例子我們要模擬病毒在網(wǎng)絡(luò)里面的傳播途徑，在我們使用的網(wǎng)絡(luò)里進(jìn)行研究是不實(shí)際的，我們只能在一個(gè)模擬的環(huán)境中進(jìn)行。 雖然在我們生活的環(huán)境中，復(fù)雜網(wǎng)絡(luò)到處都會(huì)存在，但是我們?cè)讷@取他們研究數(shù)據(jù)的時(shí)候會(huì)受到一些限制，就很難得到 真實(shí)的數(shù)據(jù)。 論文從以下三個(gè)大方 向展開了研究： 1） 闡述復(fù)雜網(wǎng)絡(luò)的基本理論，主要包括復(fù)雜網(wǎng)絡(luò)的 拓?fù)鋮?shù)，基本的網(wǎng)絡(luò)模型 及其性質(zhì)。左邊的代表頂點(diǎn)的平面點(diǎn)的位置具有隨機(jī)性，在一個(gè)圖里可以體現(xiàn)出很多種不同的圖示，右邊的圖又是另外一種體現(xiàn)方式 圖 邊的表示方法 不管是用計(jì)算機(jī)還是數(shù)學(xué)的方式對(duì)圖 形進(jìn)行描繪，都需要一種具體的方法才能夠表現(xiàn)出來。在節(jié)點(diǎn)的量在固定不變的情況下，關(guān)聯(lián)矩陣所占用的存儲(chǔ)大小和邊的數(shù)量又關(guān)聯(lián)，這樣空間的復(fù)雜系數(shù)為 )(NMO ， N 表示節(jié)點(diǎn)的總數(shù)， M 代表邊的數(shù)目。加入有 N 個(gè)點(diǎn)里面任意的兩個(gè)節(jié)點(diǎn)都只有一條邊進(jìn)行了連接 ，那么邊的數(shù)量就是 C2N C=2NCE=)1(2 ?NN E （ 26） 當(dāng)網(wǎng)絡(luò)中點(diǎn)之間的連接密度越大，那么整個(gè)網(wǎng)絡(luò)的連通性就越完善如下圖 圖 聚類系數(shù)和網(wǎng)絡(luò)連通性的聯(lián)系 (a) ?C ,(b) ?C ， (c) 1?C 當(dāng)聚類系數(shù)等于 1的時(shí)候，網(wǎng)絡(luò)極速一個(gè)完全的圖。節(jié)點(diǎn)度的分布可以用函數(shù)來進(jìn)行刻畫 )(kp ，我們理解為任意的節(jié)點(diǎn)有 k 條邊連接的概率。 我們把遵循冪律分布的網(wǎng)絡(luò)叫做無標(biāo)度網(wǎng)絡(luò)，和隨機(jī)網(wǎng)絡(luò)截然不同，這也是無標(biāo)度網(wǎng)絡(luò)的本質(zhì)特點(diǎn)。在 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ù)在 γ = 和 γ = 之間。 Albert 等人研究了 WWW 的一個(gè)子集，即 域名下的 325, 729 個(gè)節(jié)點(diǎn)，得出 γout = 和 γin =。利用 robot這個(gè)軟件能夠在萬維網(wǎng)里面進(jìn)行路由，統(tǒng)計(jì)里面的連接，根據(jù)他的邊順藤摸瓜的找 到它的出發(fā)點(diǎn)。 南華大學(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)行研究的前提。 有個(gè)稀疏模型是經(jīng)過很多研究而得到的實(shí)驗(yàn)結(jié)果，任何一個(gè)節(jié)點(diǎn)會(huì)連接與他相鄰的點(diǎn)，如圖 。 ER 的的實(shí)驗(yàn)我們發(fā)現(xiàn)了如果在給定的概率下這樣的條件，那么很多圖形都含有一些相同的性質(zhì)，或者是相反的結(jié)果都不含有。通過實(shí)驗(yàn)還了解到，如果概率 P 值比較小，他們的平均路徑反而變小更為突出。 圖 BA 無尺度網(wǎng)絡(luò)的演化 頂點(diǎn)的度為冪律分布。沒有一個(gè)比較理想比較完美的框架，那么得到的結(jié)果始終會(huì)偏離真實(shí)的結(jié)果，在這一方面科學(xué)家們正在深入研究找到最適合的模型來解決現(xiàn)在的問題，理想的模型會(huì)將更加接近真實(shí)的答案，更合理的揭示復(fù)雜網(wǎng)絡(luò)里面 信息的傳輸狀況。 一個(gè)良好的平臺(tái)和編譯環(huán)境，很多實(shí)用的工具都是圖形用戶界面組合成了matlab。即使不是計(jì)算機(jī)專業(yè)的人員也可以很容易上手，該語言的移植性也相當(dāng)?shù)牟诲e(cuò)，并且可以以此為基礎(chǔ)繼續(xù)擴(kuò)展。還有層次較高一點(diǎn)的傅里葉矩陣的演變，這些算法能夠解決目前科研的大部分工作。要得到理想的答案，我們還是要自己去生成網(wǎng)絡(luò)結(jié)構(gòu)，自己去建模和編寫程序來進(jìn)行模擬實(shí)驗(yàn)。? （ 42） 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 24 頁 ， 共 34 頁 從這個(gè)公式里面我們可以看出 Ge 可以認(rèn)為是容錯(cuò)數(shù) ? 的函數(shù)參數(shù)， Ne 代表受攻擊前連通的邊的數(shù)量，與之對(duì)應(yīng)的則是攻擊后連通的邊的數(shù)目，兩者比值越接近 1那么網(wǎng)絡(luò)呈現(xiàn)的魯棒性越強(qiáng)。 隨機(jī)網(wǎng)絡(luò)的的信息路由魯棒性仿真 在網(wǎng)絡(luò)里面對(duì)邊進(jìn)行蓄意攻擊模擬實(shí)驗(yàn)，在蓄意攻擊下，對(duì)負(fù)載較強(qiáng)的邊進(jìn)行攻擊后信息被重新分配，那些負(fù)載較差的邊接收到信息后就很難處理大量的信息。 小世界網(wǎng)絡(luò)的信息路由魯棒性仿真 在對(duì)小世界網(wǎng)絡(luò)的邊進(jìn)行蓄意攻擊下，考慮到邊的重連概率不同情況下我們?nèi)蓚€(gè)重連概率不同的小世界網(wǎng)絡(luò)進(jìn)行研究。 圖 小世界網(wǎng)絡(luò)在蓄意攻擊下 p = 時(shí)的連通子圖邊尺寸 Ge 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 27 頁 ， 共 34 頁 圖 小世界網(wǎng)絡(luò)在蓄意攻擊下 p = 時(shí)的連通子圖邊尺寸 Ge 當(dāng)對(duì)小世界網(wǎng)絡(luò)進(jìn)行隨 機(jī)攻擊的時(shí)候，因?yàn)檫叺闹剡B概率不同所以網(wǎng)絡(luò)的路由魯棒性也不一樣。 在容錯(cuò)系數(shù) ? 慢慢增加到 的時(shí)候， Ge 就陡然上升，失效的邊得到補(bǔ)充和恢復(fù)，信息被 重新分配路由到另一些邊上，攻擊后的網(wǎng)絡(luò)連通性趨于完整，整個(gè)網(wǎng)絡(luò)的路由魯棒性變強(qiáng)。在隨機(jī)攻擊的前提下，三種網(wǎng)絡(luò)的信息路 由魯棒性都不同，具有可比性。 這次設(shè)計(jì)在開始就歸納了網(wǎng)絡(luò)的基本理論，簡(jiǎn)單介紹了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，網(wǎng)