【文章內容簡介】 隨機圖開始受到 科學家的喜愛，這種網絡圖模型能夠更為簡潔明了地實現復雜網絡的模擬。在那個年代，很多研究者都提出了自己獨有的模型，而這些模型中最為突出的要數 Erods 和 Renyi 所建立的隨機圖模型，后人簡稱為 ER 模型。根據隨機圖模型（ ER 模型），以 N 個節(jié)點開始以概率連接各節(jié)點，創(chuàng)建出約 2/)1( ?NpN 個隨機分布的鏈路。 網絡中度分布的均值為 )1( ???? Npk ,在平均度 ??k 固定的情形下，當 N 很大時， )1/( ???? Nkp 就會變得很小。所以也將 ER 隨機圖稱作泊松隨機圖。如下圖所示：黑色圓點表明的是 15???k 時的度分布，而實線部分則表示的是與其相似的泊松分布。同時該圖還表明大多數的節(jié)點有著近似相同數目的鏈路。 !! )()( kkekpNekP kkkpN ???? ???? （泊松分布函數） () 圖 ER 隨機圖的度分布與泊松分布的比較 南華大學計算機科學與技術學院畢業(yè)設計（論文） 第 8 頁 共 35 頁 隨機圖的連通性有兩種極端情況： 0?p 時對應 N 個孤立的節(jié)點； 1?p 時對應全耦合網絡。直觀上看來，連邊概率 p 增加則所生成的隨機圖的變數也會隨著增加，網絡的連通性也就越好。下圖給出了不同的 p 值下所生成的隨機圖的例子。粗略地算一下，若 1000?N ，則每次生成的 ER 隨機圖會有邊數大約為 pNpNM 50 002/)1( ????? () 圖 不同連接概率的隨機圖實例 (2)小世界網絡 小世界模型 (WS)是由 Watts 和 Strogatz(WS)建立的，描述了一個局部有序的系統(tǒng)是如何轉化成為隨機網絡 的。小世界模型是從包含 N 個節(jié)點的一維網絡開始的，網絡中的節(jié)點和距離它最近和以及次近的鄰點連在一起，每個邊再根據概率 p 從新進行連接起來。并且以節(jié)點和節(jié)點間沒有重復的邊并且不會自行成環(huán)為約束條件。WS 模型由一個規(guī)則網絡經過一些演變而成的，經過逐步地一邊接一邊的重新連接，直到演化為隨機網絡。如下圖： 南華大學計算機科學與技術學院畢業(yè)設計（論文） 第 9 頁 共 35 頁 當 0?p 時，對應的是規(guī)則網絡圖。兩節(jié)點的平均距離 ??L 與節(jié)點 數目 N 之間是成線性相關的，當 N 增加后 ??L 也跟著變大，同時集群系數也會跟著變大； 當 1?p 時，對應的是隨機圖，此時 ??L 與 N 成對數關系，隨著 ??L 的增加而以對數的程度變大，而由于 N 的不斷增加，集群系數 也會逐漸增大。 當 p 在（ 0,1）之間時，系統(tǒng)表現為小世界特征，此時， ??L 的值近似和隨機網絡的相同，網絡表現出高度集群性質。 0?p 1?p隨 機 性 增 加規(guī) 則 小 世 界 隨 機 圖 WS 模型中邊的隨機重連過程 嚴格來說，即使是在 1?p 時 WS 模型與包含同樣節(jié)點和邊數的 ER 模型還是會有區(qū)別的：在 WS 模型中每個節(jié)點的度至少是 2/k ,但是在 ER 隨機圖中，并沒有對單個節(jié)點的度的最小值進行任何限制。 如果要使得 WS 模型在 1?p 時等同于 ER隨機圖，則要在 WS 的生成算法中完全隨機地對選取的每一條邊的兩個節(jié)點進行重新配置。 下圖為給定參數 101000 ?? kN ， 的情況下， )(pC 和 )(pL 的變化情況。圖中將 )(pC 和 )(pL 做了歸一化處理，即 )0(/)( CpC 和 )0(/)( LpL ，這樣就可以使兩個變量在 0?p 時的最大值都為 1。 其中： )(pC 表示平均聚集系數， )(pL 表示平均最短路徑， p 表示重連概率。 南華大學計算機科學與技術學院畢業(yè)設計（論文） 第 10 頁 共 35 頁 1)0(/)( LpL)0(/)( CpCP 圖 WS 小世界模型的 )(pC 和 )(pL 隨 p 的變化關系 (3)無標度網絡 上個世紀九十年代以來，科學技術取得了巨大進步，這就使得 研究大規(guī)模的實際網絡成為一種可能，人們可以借助計算機對真實網絡進行模擬。在先進技術的支持下，人們逐漸意識到真正存在于我們身邊的網絡多數都存在另外的一些統(tǒng)計特性而并非是徹底隨機的并且在構造的過程中它們會遵循某種規(guī)律并且具有隨機網絡模型所不具有的網絡動力學特性，而在這些個迥異特性中當屬小世界與冪律分布最為獨特。無標度網絡模型是由 Barabasi 與 Albert （ BA） 聯(lián)合建立 的，實際網絡中的無標度特征來自 2 種普遍的形成機制：第一，由于添加新節(jié)點而使得網絡不斷擴大；第二，新節(jié)點會優(yōu)先與度最大的節(jié)點連接。受到這兩點的啟發(fā) BA 模型得到了建立，這網絡研究史上最先闡明了節(jié)點度分布符合冪律函數的模型，因而意義非凡。實際網絡中的許多信息交換網、社交網、生物網絡都遵循冪律分布特性。 南華大學計算機科學與技術學院畢業(yè)設計（論文） 第 11 頁 共 35 頁 第三章 復雜網絡抗毀性 網絡抗毀性的定義 雖然抗毀性應用極為廣泛，但其定義大致可從兩個角度進行表述：定性和定量。這也是人們在研究一個新的特性時常用的定義方法，這樣可以讓后來者對其有更加清晰的認識。 下面從這兩個角度來說明一下什么是抗毀性。 (1)定性的定義 定義 1： Ellision 等人針對信息系統(tǒng)的抗毀性提出：網絡的抗毀性是在網絡遭受意外事故、故障或者攻擊時，系統(tǒng)能夠及時提供完成其關鍵任務的能力。 定義 2。Louca 等人針對通信網絡提出：網絡的抗毀性包括兩方面內容 : 1)在出現故障情況下，系統(tǒng)還能夠維持或恢復到被用戶所接受的性能的能力。 2)組織或轉移潛在服務故障的能力。 上述定義給出了抗毀性的定性描述，但是并未給出精確地描述，缺乏相應的具體性能指標，難以準確的判定系統(tǒng)的抗毀性。因此，針對這種情況，又有 了定量的抗毀性定義。 (2)定量的定義 定義 3： Knight 和 Sullivan 針對信息系統(tǒng)提出 :如果一個系統(tǒng)滿足抗毀性規(guī)范，則認為這個系統(tǒng)是抗毀的。這個抗毀性規(guī)范是一個四元 M}P,R,{E, 。 1) E 是抗毀系統(tǒng)運行環(huán)境的描述。 2) R 是網絡提供的、具有可接受服務質量的指標集。 3) P 是遍布指標集 R 的概率分布，并且其概率之和是 1。 4) M 是一個有限狀態(tài)機，用四元組 ?? TVSS , 0 來表示。在 M 中， S 表示有限狀態(tài)的集合； 0S 表示初始狀態(tài)或者優(yōu)選狀態(tài)； V 表示用戶值的集合； T 表示轉移狀態(tài)矩陣。 該四元組明確的定義了網絡什么時候以及如何從正在提供的一種服務狀態(tài)轉移到另外一種服務狀態(tài)。在該定義中，抗毀性可以視為系統(tǒng)在某一環(huán)境中可以提供的具體服務的概率。 定義 4:對于分布式網絡，抗毀性定義必須包括一下幾個方面： 南華大學計算機科學與技術學院畢業(yè)設計（論文） 第 12 頁 共 35 頁 1)系統(tǒng)定位：對于不同的網絡系統(tǒng)，抗毀性是不同的。如果抗毀性定義有變化，那么必須要說明。例如，在 軍事網絡中，抗毀性定義為：在遭受敵人攻擊時，能夠保持軍事武器或設備或其他軍事力量性能的能力。而在通信網絡系統(tǒng)中，抗毀性定義為：網絡容錯并持續(xù)提供服務的能力。另外，系統(tǒng)是有界還是無界的也要說明。 2)威脅： 對網絡的威脅可能會影響網絡（系統(tǒng)）在規(guī)定時間內繼續(xù)為它的用戶提供服務。網絡的威脅可以歸為偶然的、故意或惡意的和災害的這三類。偶然因素包括軟件的錯誤，硬件錯誤，以及人為失誤。故意或惡意的威脅包括故意毀壞，黑客入侵，以及恐怖襲擊。災害威脅指的是由于自然災害（洪水，臺風，颶風，雷電，地震，海嘯等）、戰(zhàn)爭行為和停 電事故的發(fā)生，造成了物理設備的損壞，致使網絡沒有辦法再給用戶提供服務。 3)適應性：在系統(tǒng)受到威脅時，系統(tǒng)應該有適應能力和繼續(xù)提供服務的能力。例如，電力系統(tǒng)應有能力適應短期內局部過載等突發(fā)狀況，防止大面積停電事故的發(fā)生。 4)服務的持續(xù)性：服務對用戶應該是可用的，即使在破壞發(fā)生時，網絡的性 能不應該退化。 5)時效性：服務應該在系統(tǒng)要求的時間內讓用戶接收到。 網絡抗毀性分析 抗毀性度量指標 (1)魯棒性度量 連通性是網絡的重要性能指標之一。網絡魯棒性用來衡量網絡遭受攻擊時剩余節(jié)點之間仍能保持 連通的能力。由此，網絡魯棒性可定義為移除任意節(jié)點后，網絡中仍連通的節(jié)點對與網絡總節(jié)點對的比值。用 39。G 來表示受到節(jié)點刪除后的網絡，網絡的魯棒性 ? 有如下表示： ?????? ijGji ijln ,)1(n1? () 南華大學計算機科學與技術學院畢業(yè)設計（論文） 第 13 頁 共 35 頁 ijl 為連通系數，若 i 和 j 之間連通，當節(jié)點 iv 和 jv 之間連通時， 1l ?ij ，否則 ijl =0。網絡魯棒性 ? 描述了網絡在遭受外界干擾或破壞時的連通性，反映了網絡結構本身對于攻擊的抵御能力，克服了最大連通子圖的相對大小不能反映網絡受到攻擊后子網絡的連通情況的缺點。均存在某種程度上的損壞幾率，所以要讓魯棒性高至峰值，縱然網絡能夠做到全連通也是不可能的。 (2)網絡效率度量 有效性度 量說明的是網絡在某時段內能夠正常運轉并發(fā)揮功效的程度，可以刻畫出網絡傳遞信息的效率。計算全網效率的方法如下： ijGijGiE dn1)1(n 1 ???????? () 上式反映出：信息傳遞的路程越長，傳輸距離 ijd 越大傳播過程所消耗的時間越多，網絡的傳輸效率就越低。反之，網絡傳輸效率越高。 實證分析與仿真分析 復雜網絡抗毀性研究最早開始于 2020 年 Albert 等的工作，他們開始關注拓撲結構對復雜網絡抗毀性的影響。他們分別把隨機網絡（ ER 模型）和無標度網絡（ BA 模型）至于兩種類型的打擊策略之下：一是隨機失效，在這種打擊中，隨機移除網絡中的節(jié)點，這與網絡中的隨機故障相對應；二是選擇性攻擊，按照節(jié)點連接度從大到小的順序移除節(jié)點，即僅僅拿掉網絡中的活動中心。 Albert 等分別研究了不同網絡面對不同打擊條件下極大連通片尺寸與網絡規(guī)模之比 S 、極大聯(lián)通片平均最短路徑 l 與節(jié)點移除比例 f 的關系，研究結果如下圖 所示。 南華大學計算機科學與技術學院畢業(yè)設計（論文） 第 14 頁 共 35 頁 圖 不同網絡面對不同打擊條件下 S 和 l 與 f 的關系 從上圖可以看出， 在第一種打擊手段下，無標度網絡明顯有著更好的抗毀性。而在第二種方式下，相比于隨機網絡而言，無標度網絡會更加迅速地走向了崩潰，并且一旦刪除那些關鍵節(jié)點就會致使網絡進入癱瘓狀態(tài)。對比之下會發(fā)現此時的它異常脆弱。后來人們在 WWW 和 Inter 上所做的實證分析證實了艾伯特的這一論斷。之后的布羅德等人又通過對 的實證研究得出在目標性的打擊下，網絡會表現出比平時更為強大的抗毀性。由于前人的研究使得后來 人愈來愈對這方面感興趣，吸引著他們不斷對其進行學習和探討，并且所得結論與艾伯特的大體相同。而仿真研究方面，最為權威的當是以霍姆為首的科研工作者所做的。他在前人的基礎上又進行了移除邊的實驗，在攻擊方法上又新增了這對介數的打擊，也取得了可喜的成就，為該領域的研究做出了不小的貢獻。 此后，很多學者對其他現實世界中的復雜網絡抗毀性問題進行了研究，總體結構幾乎均與 Albert 等的結果一致，大多數為了對于隨機的節(jié)點刪除都表現出抗毀性，而面對以最大度節(jié)點為目標的選擇性攻擊就相當脆弱。例如 Jeong 等的蛋白質網絡研究， Dunne 等的食物鏈網絡研究， Newman 等的電子郵件網絡研究， Magoni等的 Inter， Samant 等的 P2P 網絡研究。 有關攻擊策略對復雜網絡抗毀性影響的仿真研究中，比較全面的要數 Holme等的研究工作。他們將攻擊策略分為節(jié)點攻擊與邊攻擊兩種方式。每種攻擊又包括四種不同的策略： ID 移除策略（對初始網絡按節(jié)點或邊的度大小順序來移除節(jié)點南華大學計算機科學與技術學院畢業(yè)設計（論文） 第 15 頁 共 35 頁 或邊）、 IB 移除策略 (對初始網絡按照節(jié)點或邊的介數大小順序來移除節(jié)點或邊 )、 RD 移除策略（每次移除的節(jié)點或邊是當前網絡中節(jié)點或邊的度最大的節(jié)點）和 RB 移除策略（每次移除的 節(jié)點或邊是當前網絡中節(jié)點或邊介數最大的節(jié)點）。ER 模型對節(jié)點的基于度的攻擊比基于介數的攻擊效果好，使用重新計算的信息比基于原始信息的危害性更強；而對邊的攻擊 RB 遠比其他策略更具破壞性。無尺度網絡對節(jié)點移除比 ER 模型更敏感，在攻擊初期四種策略的差異性不明顯，隨著移除的繼續(xù)進行，攻擊對網絡的破壞程度按以下順序排列： RBRDIDIB；而且對邊的攻擊情況同節(jié)點攻擊相似。他們還對 因特網 等真實網絡作了數字分析，驗證了