【正文】 在基于局部拓?fù)湫畔⒌母鞣N攻擊策略下，權(quán) 重系數(shù)越大，節(jié)點(diǎn)移除對(duì)于網(wǎng)絡(luò)效率和連通性的影響越小，網(wǎng)絡(luò)的抗毀性越強(qiáng)。 圖 2?? 時(shí)， R 隨 f 的變化情況 圖 給出的是?；谝陨鲜聦?shí)，可以設(shè)計(jì)如下模型來(lái)探索基于邊的網(wǎng)絡(luò)抗毀性。 由圖 和 可知，在確定權(quán)重系數(shù) ? 的情況下，網(wǎng)絡(luò)效率和連通性隨著節(jié)點(diǎn)移除比例的增大而不斷下降。節(jié)點(diǎn)的度和介數(shù)是網(wǎng)絡(luò)節(jié)點(diǎn)重要性的兩個(gè)常用測(cè)度，而介數(shù)較大的節(jié)點(diǎn)對(duì)于保持網(wǎng)絡(luò)的傳輸效率具有重要作用。加權(quán)網(wǎng)絡(luò)為描述節(jié)點(diǎn)之間的關(guān)系和相互作用提供了更加細(xì)致的刻畫(huà)手段，且權(quán)重及其分布也會(huì)對(duì)網(wǎng)絡(luò)的性質(zhì)和功能產(chǎn)生重要影響。隨著時(shí)間的推移，盡管系統(tǒng)中的節(jié)點(diǎn)和邊在不斷增加，但網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特性卻不會(huì)發(fā)生很大的變化，網(wǎng)絡(luò)中必然存在一些連接數(shù)遠(yuǎn)遠(yuǎn)高于平均連接數(shù)的集散節(jié)點(diǎn)，從而形成了因特網(wǎng)的無(wú)尺度特征。 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 16 頁(yè) 共 35 頁(yè) 第四章 因特網(wǎng)抗毀性分析 因特網(wǎng)的拓?fù)浣Y(jié)構(gòu)及加權(quán)網(wǎng)絡(luò)介紹 (1)因特網(wǎng)的拓?fù)浣Y(jié)構(gòu) 因特網(wǎng) 是按照一個(gè)統(tǒng)一的標(biāo)準(zhǔn)將不同規(guī)模和類型、不同地理位置的網(wǎng)絡(luò)連接在一起所組成的一個(gè)整體，可以相互之間進(jìn)行各種信息的交換。 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 14 頁(yè) 共 35 頁(yè) 圖 不同網(wǎng)絡(luò)面對(duì)不同打擊條件下 S 和 l 與 f 的關(guān)系 從上圖可以看出， 在第一種打擊手段下，無(wú)標(biāo)度網(wǎng)絡(luò)明顯有著更好的抗毀性。例如，電力系統(tǒng)應(yīng)有能力適應(yīng)短期內(nèi)局部過(guò)載等突發(fā)狀況，防止大面積停電事故的發(fā)生。 3) P 是遍布指標(biāo)集 R 的概率分布，并且其概率之和是 1。無(wú)標(biāo)度網(wǎng)絡(luò)模型是由 Barabasi 與 Albert （ BA） 聯(lián)合建立的，實(shí)際網(wǎng)絡(luò)中的無(wú)標(biāo)度特征來(lái)自 2 種普遍的形成機(jī)制：第一，由于添加新節(jié)點(diǎn)而 使得網(wǎng)絡(luò)不斷擴(kuò)大；第二，新節(jié)點(diǎn)會(huì)優(yōu)先與度最大的節(jié)點(diǎn)連接。直觀上看來(lái)，連邊概率 p 增加則所生成的隨機(jī)圖的變數(shù)也會(huì)隨著增加，網(wǎng)絡(luò)的連通性也就越好。節(jié)點(diǎn) i的聚類系數(shù)的定義如下： )1(2i ?? ii ikk nC () in 表示節(jié)點(diǎn) i 與 ik 個(gè)鄰居節(jié)點(diǎn)之間相互關(guān)聯(lián)的鏈路數(shù)目。 1990 年 10 月 15 日，由美國(guó)圣母大學(xué)教授 聯(lián)合發(fā)表了一篇論文《 Emergence of Scaling in Random Networks》 .這篇論文指出了復(fù)雜網(wǎng)絡(luò)中的無(wú)標(biāo)度性質(zhì)，并提出了無(wú)標(biāo)度模型（ BA 模型），該模型的度分布符合冪律分布。 本文的組織結(jié)構(gòu) 本 文后續(xù)部分內(nèi)容如下： 第二章 ，復(fù)雜網(wǎng)絡(luò)背景知識(shí)。后來(lái)，由于計(jì)算機(jī)領(lǐng)域相關(guān)技術(shù)的繼續(xù)發(fā)展，使得人們可以收集和研究構(gòu)造龐大的復(fù)雜系統(tǒng)的數(shù)據(jù)，人們開(kāi)始了對(duì)復(fù)雜網(wǎng)絡(luò)的更為深入地研究。例如，人們平 時(shí)搜集信息、網(wǎng)上購(gòu)物、存儲(chǔ)數(shù)據(jù)等等，都與因特網(wǎng)有關(guān)。從不同角度對(duì)因特網(wǎng)抗毀性進(jìn)行了仿真，有基于節(jié)點(diǎn)的抗毀性仿真和基于邊的抗毀性仿真。其中，在基于節(jié)點(diǎn)的抗毀性仿真中，研究了局部信息條件下遭遇 ID 攻擊（對(duì)初始網(wǎng)絡(luò)按節(jié)點(diǎn)的度大小順序來(lái)移除節(jié)點(diǎn)）時(shí)網(wǎng)絡(luò)的抗毀性，以及全局信息條件下遭遇 IB 攻擊（對(duì)初 始網(wǎng)絡(luò)按照節(jié)點(diǎn)的介數(shù)大小順序來(lái)移除節(jié)點(diǎn)）和 RB 攻擊（ 每次移除的節(jié)點(diǎn)是當(dāng)前網(wǎng)絡(luò)中節(jié)點(diǎn)或邊介數(shù)最大的節(jié)點(diǎn) ）時(shí)網(wǎng)絡(luò)的抗毀性；在基于邊的抗毀性仿真中，研究了不同信息獲取情況下網(wǎng)絡(luò)的抗毀性。還有對(duì)于銀行、政府等重要機(jī)構(gòu)而言，因特網(wǎng)的重要性更是不言而喻。隨著網(wǎng)絡(luò)的不斷進(jìn)步與發(fā)展，其重要性也日益突出，越來(lái)越多的研究人員開(kāi)始投身于對(duì)網(wǎng)絡(luò)的可靠性的研究當(dāng)中來(lái)。首先介復(fù)雜網(wǎng)絡(luò)的相關(guān)基礎(chǔ)知識(shí)。他們指出了實(shí)際網(wǎng)絡(luò)中的兩個(gè)重要特性：網(wǎng)絡(luò)的規(guī)?？偸遣粩嘣谠鲩L(zhǎng)的、新加入到網(wǎng)路中的節(jié)點(diǎn)比較傾向于連接到度大的節(jié)點(diǎn)。所以，平均聚類系數(shù)可以定義為： ?????Ni iCNC 11 () (3)網(wǎng)絡(luò)的平均路徑長(zhǎng)度 在大部分的網(wǎng)絡(luò)中，隨意 2 個(gè)節(jié)點(diǎn)間可能不單單連著 1 條通路，而最短的那一個(gè)通路的長(zhǎng)度是一個(gè)非常有用的測(cè)度。下圖給出了不同的 p 值下所生成的隨機(jī)圖的例子。受到這兩點(diǎn)的啟發(fā) BA 模型得到了建立，這網(wǎng)絡(luò)研究史上最先闡明了節(jié)點(diǎn)度分布符合冪律函數(shù)的模型，因而意義非凡。 4) M 是一個(gè)有限狀態(tài)機(jī)，用四元組 ?? TVSS , 0 來(lái)表示。 4)服務(wù)的持續(xù)性：服務(wù)對(duì)用戶應(yīng)該是可用的，即使在破壞發(fā)生時(shí)，網(wǎng)絡(luò)的性 能不應(yīng)該退化。而在第二種方式下，相比于隨機(jī)網(wǎng)絡(luò)而言，無(wú)標(biāo)度網(wǎng)絡(luò)會(huì)更加迅速地走向了崩潰，并且一旦刪除那些關(guān)鍵節(jié)點(diǎn)就會(huì)致使網(wǎng)絡(luò)進(jìn)入癱瘓狀態(tài)。 這是個(gè)由數(shù)十萬(wàn)網(wǎng)絡(luò)連接而構(gòu)成并呈現(xiàn)出一致性的復(fù)雜網(wǎng)絡(luò)形式。 另外，因特網(wǎng)還具有遞階結(jié)構(gòu)。因此，加權(quán)網(wǎng)絡(luò)已經(jīng)成為復(fù)雜網(wǎng)絡(luò)的一個(gè)重要的研究領(lǐng)域。因此，攻擊者通常會(huì)選擇度和介數(shù)作為節(jié)點(diǎn)重要性度量指標(biāo)，對(duì)加權(quán)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行重要性排序并依此進(jìn)行攻擊。在大約移除 45%的節(jié)點(diǎn)后，網(wǎng)絡(luò)的效率和連通性均下降 0。 對(duì)于一個(gè)有 N 個(gè)節(jié)點(diǎn)， M 條邊的加權(quán)網(wǎng)絡(luò)，定義基于邊的網(wǎng)絡(luò)抗毀性模型為： ),a( fIF?? () 其中， a 的值為已知信息的邊數(shù)與總邊數(shù)的比值 ,并且 a 值愈大，表示網(wǎng)絡(luò)被攻擊者了解愈多的信息。 2?? 時(shí) ,在不等概率信息獲取情況下 ,網(wǎng)絡(luò)的連通節(jié)點(diǎn)對(duì)比例隨著邊刪除比例的變化。在基于全局拓?fù)湫畔⒌墓舨呗韵拢W(wǎng)絡(luò)應(yīng)對(duì)對(duì)節(jié)點(diǎn)移除的魯棒性相比于基于局部信息的攻擊策略要差，且權(quán)重系數(shù)為 的網(wǎng)絡(luò)在攻擊初始階段表現(xiàn)出最強(qiáng)的魯棒性。通過(guò)仿真發(fā)現(xiàn)： 在基于節(jié)點(diǎn)的抗毀性仿真中，可以得出：在不同的信息條件下，加權(quán)網(wǎng)絡(luò)的抗毀性表現(xiàn)是不同的。而當(dāng)1a? 時(shí) ,當(dāng)刪除 40%的邊時(shí) ,網(wǎng)絡(luò)的連通節(jié)點(diǎn)對(duì)大概只剩下了 10%,這說(shuō)明信息量的多少對(duì)網(wǎng)絡(luò)的魯棒性有著顯著的影響。另外在實(shí)際對(duì)網(wǎng)絡(luò)進(jìn)行打擊時(shí) ,掌握的網(wǎng)絡(luò)信息的多少對(duì)網(wǎng)絡(luò)的攻擊策略的制定也有一定的影響。其中，記 f 為移除節(jié)點(diǎn)的比例 , 1R 為網(wǎng)絡(luò)效率下降比率， 2R 為網(wǎng)絡(luò)連通性。根據(jù)攻擊者對(duì)網(wǎng)絡(luò)信息的掌握程度，把攻擊方式劃分為兩類：基于網(wǎng)絡(luò)局部信息和全局信息攻擊。給網(wǎng)絡(luò)中的每條邊都賦予相應(yīng)的權(quán)值，無(wú)權(quán)網(wǎng)絡(luò)就成為加權(quán)網(wǎng)絡(luò)。新加入的路由器總是傾向于連接那些連接數(shù)較多的路由器，以南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 18 頁(yè) 共 35 頁(yè) 便獲得到其它路由器最短的距離和較大的帶寬；因特網(wǎng)的新用戶也更傾向于訪問(wèn)知名度較高的網(wǎng)站。他們還對(duì) 因特網(wǎng) 等真實(shí)網(wǎng)絡(luò)作了數(shù)字分析，驗(yàn)證了Albert 等的結(jié)論。 Albert 等分別研究了不同網(wǎng)絡(luò)面對(duì)不同打擊條件下極大連通片尺寸與網(wǎng)絡(luò)規(guī)模之比 S 、極大聯(lián)通片平均最短路徑 l 與節(jié)點(diǎn)移除比例 f 的關(guān)系，研究結(jié)果如下圖 所示。 3)適應(yīng)性：在系統(tǒng)受到威脅時(shí)，系統(tǒng)應(yīng)該有適應(yīng)能力和繼續(xù)提供服務(wù)的能力。 2) R 是網(wǎng)絡(luò)提供的、具有可接受服務(wù)質(zhì)量的指標(biāo)集。 在先進(jìn)技術(shù)的支持下，人們逐漸意識(shí)到真正存在于我們身邊的網(wǎng)絡(luò)多數(shù)都存在另外的一些統(tǒng)計(jì)特性而并非是徹底隨機(jī)的并且在構(gòu)造的過(guò)程中它們會(huì)遵循某種規(guī)律并且具有隨機(jī)網(wǎng)絡(luò)模型所不具有的網(wǎng)絡(luò)動(dòng)力學(xué)特性，而在這些個(gè)迥異特性中當(dāng)屬小世界與冪律分布最為獨(dú)特。 !! )()( kkekpNekP kkkpN ???? ???? （泊松分布函數(shù)） () 圖 ER 隨機(jī)圖的度分布與泊松分布的比較 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 8 頁(yè) 共 35 頁(yè) 隨機(jī)圖的連通性有兩種極端情況： 0?p 時(shí)對(duì)應(yīng) N 個(gè)孤立的節(jié)點(diǎn)； 1?p 時(shí)對(duì)應(yīng)全耦合網(wǎng)絡(luò)。 (2)網(wǎng)絡(luò)的聚類系數(shù) 在實(shí)際系統(tǒng)中，節(jié)點(diǎn)往往會(huì)顯示出集群傾向，此時(shí)網(wǎng)絡(luò)的特性可以用聚類系數(shù)來(lái)進(jìn)行量化，集聚類特性這一拓?fù)錅y(cè)度可以反映出網(wǎng)絡(luò)上的某一節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)之間的連接程度。美國(guó)康奈爾大學(xué)的博士生導(dǎo)師Steven 和其學(xué)生 Duncan 聯(lián)合發(fā)表了一篇論文：《 Collective dynamics of‘small world’works》，在這片文章中首次提出了小世界模型（ WS 模型），該模型從規(guī)則網(wǎng)絡(luò)出發(fā)，以概率 p （重連概率）將每條邊斷開(kāi)并重新連接到網(wǎng)絡(luò)上的其他節(jié)點(diǎn)，如果改變 p 的大小，網(wǎng)絡(luò)將會(huì)發(fā)生變化，由規(guī)則網(wǎng)絡(luò)（ 0?p ）向復(fù)雜網(wǎng)絡(luò)（ p 在 到 之間）變化，最后會(huì)向著隨機(jī)網(wǎng)絡(luò)（ 1?p ）變化。 本文的主要工作 結(jié)合已有的研究成果，本文主要從以下幾方面對(duì)研究因特網(wǎng)的抗毀性展開(kāi)了工作： (1)系統(tǒng)介紹復(fù)雜網(wǎng)絡(luò)理 論的基礎(chǔ)知識(shí)（主要包括復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)度量、經(jīng)典拓?fù)淠Ｐ图捌湫再|(zhì)、結(jié)構(gòu)抗毀性）； (2)介紹已提出的經(jīng)典因特網(wǎng)拓?fù)淠Ｐ?、攻擊模型及抗毀性測(cè)度指標(biāo)； (3)介紹復(fù)雜網(wǎng)絡(luò)的抗毀性及已有的抗毀性仿真與實(shí)證分析； (4)利用 Matlab 仿真工具，基于經(jīng)典的模型網(wǎng)絡(luò)對(duì)不同信息條件下的加權(quán)復(fù)雜網(wǎng)絡(luò)抗毀性進(jìn)行仿真分析，主要有 考慮信息條件的加權(quán)因特網(wǎng)基于節(jié)點(diǎn)的抗毀性分析、考慮信息條件的加權(quán)因特網(wǎng)基于邊的抗毀性分析、考慮信息條件的加權(quán)因特網(wǎng)基于節(jié)點(diǎn)的抗毀性分析、考慮成本和性能的加權(quán)因特網(wǎng)抗毀性分析。然而受到實(shí)驗(yàn)條件的制約，加之缺乏實(shí)驗(yàn)數(shù)據(jù)和一定的對(duì)于數(shù) 據(jù)統(tǒng)計(jì)分析能力，人們并不了解所研究的復(fù)雜網(wǎng)絡(luò)的具體拓?fù)湫畔?。離開(kāi)了因特網(wǎng)，人們會(huì)感到無(wú)所適從。研究關(guān)注于網(wǎng)絡(luò)在不同的信息條件和攻擊方式下的抗毀性表現(xiàn)。 不同信息條件下基于節(jié)點(diǎn)的因特網(wǎng)抗毀性仿真結(jié)果表明：在基于局部拓?fù)湫畔⒌母鞣N攻擊策略下，權(quán)重系數(shù)越大，節(jié)點(diǎn)移除對(duì)于網(wǎng)絡(luò)效率和連通性的影響越小，網(wǎng)絡(luò)的抗毀性越強(qiáng)。一旦有重要數(shù)據(jù)流失或泄露將會(huì)造成不能挽回的損失。 “魯棒而脆弱”是復(fù)雜網(wǎng)絡(luò)中最重要但又最基本的特性之一。其中重點(diǎn)介紹了因特網(wǎng)的三個(gè)典型模型：隨機(jī)圖模型，小世界模型， BA 無(wú)標(biāo)度模型。 以上的兩篇文章都提出了較為簡(jiǎn)單易懂的模型和嚴(yán)格的數(shù)學(xué)推導(dǎo)來(lái)給我們展示復(fù)雜網(wǎng)絡(luò)的生成機(jī)制，同時(shí)闡述了復(fù)雜網(wǎng)路的基本特征，這兩篇論文的發(fā)表標(biāo)志著對(duì)于復(fù)雜網(wǎng)絡(luò)的研究 從此走進(jìn)了一個(gè)全新的時(shí)代。平均路徑長(zhǎng)度的定義如下，其中， ijl 表示最短路徑長(zhǎng)度， i 和 j 表示任意兩個(gè)節(jié)點(diǎn)： ?????? ji ijlNNl )1(2 () (4)介數(shù) 節(jié)點(diǎn)的度雖然能夠在一定程度上 反映一個(gè)節(jié)點(diǎn)的重要性，但是兩個(gè)度相同的節(jié)點(diǎn)其重要性在實(shí)際網(wǎng)絡(luò)中的差別可能會(huì)很大，例如一個(gè)節(jié)點(diǎn)的度很小，但是它是網(wǎng)絡(luò)中的一個(gè)割點(diǎn)，刪除它以后會(huì)將網(wǎng)絡(luò)分割成不連通的兩部分，因此這個(gè)度很小的節(jié)點(diǎn)在網(wǎng)絡(luò)中的作用十分關(guān)鍵。粗略地算一下，若 1000?N ，則每次生成的 ER 隨機(jī)圖會(huì)有邊數(shù)大約為 pNpNM 50 002/)1( ????? () 圖 不同連接概率的隨機(jī)圖實(shí)例 (2)小世界網(wǎng)絡(luò) 小世界模型 (WS)是由 Watts 和 Strogatz(WS)建立的，描述了一個(gè)局部有序的系統(tǒng)是如何轉(zhuǎn)化成為隨機(jī)網(wǎng)絡(luò)的。實(shí)際網(wǎng)絡(luò)中的許多信息交換網(wǎng)、社交網(wǎng)、生物網(wǎng)絡(luò)都遵循冪律分布特性。在 M 中， S 表示有限狀態(tài)的集合； 0S 表示初始狀態(tài)或者優(yōu)選狀態(tài)； V 表示用戶值的集合； T 表示轉(zhuǎn)移狀態(tài)矩陣。 5)時(shí)效性：服務(wù)應(yīng)該在系統(tǒng)要求的時(shí)間內(nèi)讓用戶接收到。對(duì)比之下會(huì)發(fā)現(xiàn)此時(shí)的它異常脆弱。 由 于在因特網(wǎng)上主機(jī)有隨機(jī)接入和斷開(kāi)的情況，所以因特網(wǎng)的整體拓?fù)錂C(jī)構(gòu)就應(yīng)該隨之具有均勻分布的特征，進(jìn)而因特網(wǎng)各節(jié)點(diǎn)的從表面上看起來(lái)像是均勻分布的。這種結(jié)構(gòu)通常可以分為 4 層：國(guó)際網(wǎng)絡(luò)，國(guó)家中樞網(wǎng)絡(luò)，區(qū)域網(wǎng)絡(luò)以及局域網(wǎng)絡(luò)。 加權(quán)網(wǎng)絡(luò)可以用圖 G=(V,E)來(lái)表示，其中， G 是一個(gè)無(wú)向連通圖，有 n 個(gè)節(jié)點(diǎn)和 m 條帶權(quán)重的邊。 本節(jié)根據(jù)霍姆等提出的四種攻擊策略分別對(duì)加權(quán)網(wǎng)絡(luò)抗毀性進(jìn)行仿真，顯然，當(dāng)網(wǎng)絡(luò)受到攻擊時(shí)，網(wǎng)絡(luò)效率及連通性都會(huì)減小，在一定的節(jié)點(diǎn)移除比例下，其減小的幅度越小，則說(shuō) 明網(wǎng)絡(luò)的抗毀性越強(qiáng)。 圖 ID 攻擊下 1R 隨 f 變化的曲線 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 21 頁(yè) 共 35 頁(yè) 圖 ID 攻擊下 2R