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