【正文】 當(dāng)網(wǎng)絡(luò)的信息獲取為零時(shí)，網(wǎng)絡(luò)具有較強(qiáng)的南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 32 頁 共 35 頁 抗毀性。而只需要獲取 30%的邊信息 ,對網(wǎng)絡(luò)的攻擊就近似于故意攻擊 ,攻擊 30%的邊 ,網(wǎng)絡(luò)的效率就會(huì)下降到 10%左右 ,網(wǎng)絡(luò)幾乎崩潰。 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 28 頁 共 35 頁 圖 ??? 時(shí)， R 隨 f 的變化情況 圖 給出的是 ??? 時(shí) ,即網(wǎng)絡(luò)采取優(yōu)先信息獲取時(shí)連通節(jié)點(diǎn)對的變化 ,從圖上可以看出 ,當(dāng) 1a? 時(shí) ,當(dāng)刪除 20%的邊 ,網(wǎng)絡(luò)中連通節(jié)點(diǎn)對數(shù)量已經(jīng)下降到 5%左右 ,當(dāng) 0a? 時(shí) ,刪除 20%的邊 ,網(wǎng)絡(luò)中仍有超過 一半 的節(jié)點(diǎn)處于連通狀態(tài)。為了避免已知區(qū)域的隨機(jī)性 ,對于給定的網(wǎng)絡(luò)配置參數(shù) ,我們執(zhí)行 10 次配置模型 ,對每個(gè)網(wǎng)絡(luò)均對立確定 5 次己知區(qū)域 ,最后計(jì)算平均值連通節(jié)點(diǎn)對和最短路徑 ,然后根據(jù)平均路徑長計(jì)算網(wǎng)絡(luò)的效率。 I 代表了受到攻擊的那個(gè)邊的介數(shù)，可它以表明該邊 于網(wǎng)絡(luò)中所擔(dān)當(dāng)?shù)慕巧悄先A大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 26 頁 共 35 頁 否重要。 圖 RB 攻擊下 1R 隨 f 變化的曲線 圖 RB 攻擊下 2R 隨 f 變化的曲線 RB 攻擊初始階段網(wǎng)絡(luò)效率的變化如圖 所示：在早期階段，權(quán)重系數(shù)?? 的網(wǎng)絡(luò)效率對于節(jié)點(diǎn)移除的敏感性最低，抗毀性最強(qiáng)。若取定網(wǎng)絡(luò)的連通性閡值為 90%，則在移除比例小于 5%之前，權(quán)重系數(shù)的變化對于網(wǎng)絡(luò)連通性的影響不大，僅在節(jié)點(diǎn)移除比例大于 5%時(shí)有細(xì)微的差別。因此，采用數(shù)值仿真的方法來研究加權(quán)復(fù)雜網(wǎng)絡(luò)的抗毀性與網(wǎng)絡(luò)參數(shù)的關(guān)系。對初始網(wǎng)絡(luò)按節(jié)點(diǎn)的度大小順序來移除節(jié)點(diǎn)或邊。邊權(quán)的這種賦值方式是建立在實(shí)際網(wǎng)絡(luò)的觀測數(shù)據(jù)基礎(chǔ)上的，另外，在加權(quán)網(wǎng)絡(luò)中，邊的介數(shù)和其兩端節(jié)點(diǎn)度的乘積呈正相關(guān)的關(guān)系。一般用權(quán)重鄰接南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 19 頁 共 35 頁 矩陣 nmijW ?? )w( 表示加權(quán)網(wǎng)絡(luò)的權(quán)重，其中元素 ijw 表示節(jié)點(diǎn) iv 與 jv 為端點(diǎn)的邊 ije的權(quán)重，權(quán)重，當(dāng)網(wǎng)絡(luò)中各條邊的權(quán)值都相同時(shí)，加權(quán)網(wǎng)絡(luò)即退化為無權(quán)網(wǎng)絡(luò)。并且，在不同尺度上觀察因特網(wǎng)，可以發(fā)現(xiàn)其結(jié)構(gòu)具有自相似性。遞階結(jié)構(gòu)使得網(wǎng)絡(luò)節(jié)點(diǎn)之間具有關(guān)聯(lián)，因而關(guān)聯(lián)性是因特網(wǎng)不容忽視的一個(gè)特性。在自治系統(tǒng)層因特網(wǎng)的平均路徑長度介于 和 之間。 我們所熟悉的 WWW 是定義在 Hyperspace 上的虛擬網(wǎng)絡(luò)，而因特網(wǎng)不同于WWW，它是由路由器、計(jì)算機(jī)以及其連接其中的其他通訊設(shè)備組成的硬件網(wǎng)絡(luò)，在這個(gè)硬件網(wǎng)絡(luò)中，由光纖等物理鏈路將這些路由器與各設(shè)備連接起來。每種攻擊又包括四種不同的策略： ID 移除策略（對初始網(wǎng)絡(luò)按節(jié)點(diǎn)或邊的度大小順序來移除節(jié)點(diǎn)南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 15 頁 共 35 頁 或邊）、 IB 移除策略 (對初始網(wǎng)絡(luò)按照節(jié)點(diǎn)或邊的介數(shù)大小順序來移除節(jié)點(diǎn)或邊 )、 RD 移除策略（每次移除的節(jié)點(diǎn)或邊是當(dāng)前網(wǎng)絡(luò)中節(jié)點(diǎn)或邊的度最大的節(jié)點(diǎn)）和 RB 移除策略（每次移除的節(jié)點(diǎn)或邊是當(dāng)前網(wǎng)絡(luò)中節(jié)點(diǎn)或邊介數(shù)最大的節(jié)點(diǎn)）。之后的布羅德等人又通過對 的實(shí)證研究得出在目標(biāo)性的打擊下，網(wǎng)絡(luò)會(huì)表現(xiàn)出比平時(shí)更為強(qiáng)大的抗毀性。反之，網(wǎng)絡(luò)傳輸效率越高。網(wǎng)絡(luò)魯棒性用來衡量網(wǎng)絡(luò)遭受攻擊時(shí)剩余節(jié)點(diǎn)之間仍能保持連通的能力。偶然因素包括軟件的錯(cuò)誤，硬件錯(cuò)誤，以及人為失誤。在該定義中，抗毀性可以視為系統(tǒng)在某一環(huán)境中可以提供的具體服務(wù)的概率。 (2)定量的定義 定義 3： Knight 和 Sullivan 針對信息系統(tǒng)提出 :如果一個(gè)系統(tǒng)滿足抗毀性規(guī)范，則認(rèn)為這個(gè)系統(tǒng)是抗毀的。這也是人們在研究一個(gè)新的特性時(shí)常用的定義方法，這樣可以讓后來者對其有更加清晰的認(rèn)識(shí)。圖中將 )(pC 和 )(pL 做了歸一化處理，即 )0(/)( CpC 和 )0(/)( LpL ，這樣就可以使兩個(gè)變量在 0?p 時(shí)的最大值都為 1。并且以節(jié)點(diǎn)和節(jié)點(diǎn)間沒有重復(fù)的邊并且不會(huì)自行成環(huán)為約束條件。所以也將 ER 隨機(jī)圖稱作泊松隨機(jī)圖。所以提出了介數(shù)之一概念來反映節(jié)點(diǎn)或邊的重要程度。基本上所有的網(wǎng)絡(luò) 拓?fù)浣Y(jié)構(gòu)都是主要按照其節(jié)點(diǎn)度分布來進(jìn)行分類的。對于現(xiàn)實(shí)網(wǎng)絡(luò)而言，研究復(fù)雜網(wǎng)絡(luò)對于研究其穩(wěn)定性、容錯(cuò)性和抗攻擊能力等，都具有決定性意義。在之后的內(nèi)容中將為大家 詳細(xì)介紹 ER 模型以及其他的一些復(fù)雜網(wǎng)絡(luò)的模型。重點(diǎn)說明網(wǎng)絡(luò)抗毀性的定義以及之前人們對于研究網(wǎng)絡(luò)抗毀性所做的仿真分析和實(shí)證分析。 (2)在實(shí)際的許多網(wǎng)絡(luò)中，破壞一個(gè)或少數(shù)幾個(gè)關(guān)鍵節(jié)點(diǎn)可能會(huì)引起級聯(lián)失效嚴(yán)重時(shí)甚 至?xí)?dǎo)致整個(gè)網(wǎng)絡(luò)崩潰。因此，怎樣對實(shí)際復(fù)雜系統(tǒng)的脆弱性和魯棒 性進(jìn)行較為系統(tǒng)地大范圍地研究，成為了時(shí)下對于復(fù)雜網(wǎng)絡(luò)的研究中最重要的問題之一。 復(fù)雜網(wǎng)絡(luò)遍布在生活各處，從因特網(wǎng)到萬維網(wǎng)， 從細(xì)胞神經(jīng)網(wǎng)絡(luò)到蛋白質(zhì)相互作用網(wǎng)絡(luò)，從城市公路交通網(wǎng)到航空路線圖等。 因特網(wǎng)從出現(xiàn)到如今的快速發(fā)展，整個(gè)過程十分迅猛。 small world。而不同信息條件下基于邊的因特網(wǎng)抗毀性仿真結(jié)果表明：當(dāng)網(wǎng)絡(luò)信息獲取為隨機(jī)獲取時(shí)，網(wǎng) 絡(luò)的抗毀性取決于網(wǎng)絡(luò)信息量的獲取程度。 其次概述了復(fù)雜網(wǎng)絡(luò)抗毀性研究現(xiàn)狀。 然后 利用仿真軟件 Matlab，基于經(jīng)典的加權(quán)無標(biāo)度網(wǎng)絡(luò)模型對因特網(wǎng)抗毀性開展仿真研究。其中，當(dāng)網(wǎng)絡(luò)的信息獲取為零時(shí)，網(wǎng)絡(luò)具有較強(qiáng)的抗毀性。 invulnerability 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 1 頁 共 35 頁 第一章 緒論 研究背景及意義 自從上世紀(jì)九十年代以來，由于總體經(jīng)濟(jì)的高速發(fā)展，人們逐漸進(jìn)入了一個(gè)以因特網(wǎng)為代表的網(wǎng)絡(luò)時(shí)代，并且在生活中的各個(gè)領(lǐng)域因特網(wǎng)都廣為普及，與我們的日常生活緊密相關(guān)。它源于最早的有小型計(jì)算機(jī)連接而成的實(shí)驗(yàn)網(wǎng)絡(luò)，經(jīng)過多年的演變發(fā)展，成為了今天十 分成熟的大型高效網(wǎng)絡(luò)。并且 人們對于復(fù)雜網(wǎng)絡(luò)的探究已經(jīng)逐漸進(jìn)入數(shù)理和工程科學(xué)范疇當(dāng)中，在這個(gè)以信息為主導(dǎo)的年代進(jìn)一步深入探索復(fù)南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 2 頁 共 35 頁 雜網(wǎng)絡(luò)的各種特性及功能，已然在科學(xué)界演變成為了一個(gè)極富挑戰(zhàn)性的課題，有的研究者甚至將其作為網(wǎng)絡(luò)的新科學(xué)來進(jìn)行鉆研。 脆弱性和穩(wěn)健型是無標(biāo)度網(wǎng)絡(luò)的一個(gè)雙重特征，這就使得病毒或黑客只需要破壞少數(shù)核心節(jié)點(diǎn)便可以徹底擊垮整個(gè)的網(wǎng)絡(luò)系統(tǒng)，因而，越來越多的科研機(jī)構(gòu)開始關(guān)注復(fù)雜網(wǎng)絡(luò)的抗毀性問題。這種網(wǎng)絡(luò)中的相繼故障原理使得提高了對于因特網(wǎng)故障的重視，對于預(yù)防因特網(wǎng)遭遇外界攻擊破壞以及阻止在網(wǎng)絡(luò)遭到破壞后受到更大的損失都具有十分重要的現(xiàn)實(shí)意義。 第四章 ，因特網(wǎng)抗毀性分析。與其他的數(shù)學(xué)家相同，隨機(jī)圖論的提出者 Erdos 研究的也是基于經(jīng)典圖論的網(wǎng)絡(luò)模型，而隨著一系列復(fù)雜網(wǎng)絡(luò)如萬維網(wǎng)等的出現(xiàn)，一大批研究者開始思考傳統(tǒng)網(wǎng)絡(luò)模型以外的問題，像諸如互聯(lián)網(wǎng)之類的復(fù)雜網(wǎng)絡(luò)，它們的網(wǎng)絡(luò)結(jié)構(gòu)會(huì)是什么樣子的呢？ 在對社會(huì)網(wǎng)絡(luò)進(jìn)行了近半個(gè)世紀(jì) 的研究后，人們?nèi)〉昧孙@著地成果。 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 5 頁 共 35 頁 復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù) 復(fù)雜網(wǎng)絡(luò)是涉及到很多交叉學(xué)科的的一門新科學(xué)，近幾年來吸引著越來越多的來自各領(lǐng)域的研究者，主要有社會(huì)學(xué)、生物學(xué)、數(shù)學(xué)、物理學(xué)等學(xué)科。 !)( kkekP kk?? () 網(wǎng)絡(luò)的平均度指的是全部節(jié)點(diǎn)度的平均值，記為 ??k ， ?????Ni ikNk 11 () 度是網(wǎng)絡(luò)節(jié)點(diǎn)的屬性，反映的是網(wǎng)絡(luò)中個(gè)體的屬性，屬于微觀層面，不能反映整體特性，可以通過微觀量的分布來研究宏觀特性，由此引出度分布。節(jié)點(diǎn) u 的介數(shù)定義為網(wǎng)絡(luò)中所有的最短路徑之中，經(jīng)過 u 的數(shù)量所占的比例，它反映了節(jié)點(diǎn) u 在整個(gè)網(wǎng)絡(luò)中的影響力。如下圖所示：黑色圓點(diǎn)表明的是 15???k 時(shí)的度分布，而實(shí)線部分則表示的是與其相似的泊松分布。WS 模型由一個(gè)規(guī)則網(wǎng)絡(luò)經(jīng)過一些演變而成的，經(jīng)過逐步地一邊接一邊的重新連接，直到演化為隨機(jī)網(wǎng)絡(luò)。 其中： )(pC 表示平均聚集系數(shù)， )(pL 表示平均最短路徑， p 表示重連概率。下面從這兩個(gè)角度來說明一下什么是抗毀性。這個(gè)抗毀性規(guī)范是一個(gè)四元 M}P,R,{E, 。 定義 4:對于分布式網(wǎng)絡(luò)，抗毀性定義必須包括一下幾個(gè)方面： 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 12 頁 共 35 頁 1)系統(tǒng)定位：對于不同的網(wǎng)絡(luò)系統(tǒng)，抗毀性是不同的。故意或惡意的威脅包括故意毀壞，黑客入侵，以及恐怖襲擊。由此，網(wǎng)絡(luò)魯棒性可定義為移除任意節(jié)點(diǎn)后，網(wǎng)絡(luò)中仍連通的節(jié)點(diǎn)對 與網(wǎng)絡(luò)總節(jié)點(diǎn)對的比值。 實(shí)證分析與仿真分析 復(fù)雜網(wǎng)絡(luò)抗毀性研究最早開始于 20xx 年 Albert 等的工作，他們開始關(guān)注拓?fù)浣Y(jié)構(gòu)對復(fù)雜網(wǎng)絡(luò)抗毀性的影響。由于前人的研究使得后來人愈來愈對這方面感興趣，吸引著他們不斷對其進(jìn)行學(xué)習(xí)和探討，并且所得結(jié)論與 艾伯特的大體相同。ER 模型對節(jié)點(diǎn)的基于度的攻 擊比基于介數(shù)的攻擊效果好，使用重新計(jì)算的信息比基于原始信息的危害性更強(qiáng)；而對邊的攻擊 RB 遠(yuǎn)比其他策略更具破壞性。人們研究了兩個(gè)不同層次的因特網(wǎng)拓?fù)浣Y(jié)構(gòu)，它們分別是 自治系統(tǒng)層與路由器層。 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 17 頁 共 35 頁 圖 Inter 的路由器層和自制系統(tǒng)層 圖 路由器層上 Inter 的度分布 在所有的因特網(wǎng)拓?fù)涮卣餮芯砍晒?，最重要的發(fā)現(xiàn)就是因特網(wǎng)是一個(gè)典型的無標(biāo)度網(wǎng)絡(luò)。此外，在因特網(wǎng)中，當(dāng)加入新的連接時(shí)，路由器總是樂意通過最短距離進(jìn)行連接，從而導(dǎo)致在同一個(gè)地區(qū)的路由器之間有更多的連接，而不同地區(qū)路由器之間的連接相對來說比較少。 鑒于因特網(wǎng)是具有無標(biāo)度網(wǎng)絡(luò)的特性的，接下來對于因特網(wǎng)的研究都以無標(biāo)度網(wǎng)絡(luò)為模型來進(jìn)行分析。 加權(quán)網(wǎng)絡(luò)研究需要考慮的第一個(gè)問題就是邊權(quán)的賦予方式。 其次，選取攻擊方式。 (2)IB 移除策略。 局部信息下的抗毀性仿真結(jié)果 節(jié)點(diǎn)的度刻畫的是節(jié)點(diǎn)的局部特性，基于局部信息的攻擊方式就是依據(jù)度值對節(jié)點(diǎn)進(jìn)行攻擊，其中又分為初始節(jié)點(diǎn)度 （ ID)和重新計(jì)算節(jié)點(diǎn)度 (RD)2 種方式。 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 22 頁 共 35 頁 圖 ID 攻擊初始階段 2R 隨 f 變化的 曲線 全局信息下的抗毀性仿真結(jié)果 節(jié)點(diǎn)的介數(shù)刻畫的是節(jié)點(diǎn)的全局影響力，基于全局信息的攻擊方式就是依據(jù)介數(shù)對節(jié)點(diǎn)進(jìn)行攻擊，其中又分為初始節(jié)點(diǎn)介數(shù) (IB)和重新計(jì)算的節(jié)點(diǎn)介數(shù) (RB） 2種。 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 第 25 頁 共 35 頁 圖 RB 攻擊初始階段的 1R 隨 f 變化的曲線 考慮信息條件下因特網(wǎng)的加權(quán)網(wǎng)絡(luò)基于邊的抗毀性分析 抗毀性模型 由于網(wǎng)絡(luò)中邊的承載能力及在網(wǎng)絡(luò)中的作用也不同 ,因此在對一個(gè)網(wǎng)絡(luò)進(jìn)行攻擊時(shí) ,攻擊不同的邊對網(wǎng)絡(luò)的影響也是不同的 ,例如如果攻擊的是一條核心的邊 ,承擔(dān)著網(wǎng)絡(luò)中較多的流量 ,則攻擊該邊將會(huì)對網(wǎng)絡(luò)產(chǎn)生較大的影響。在特定的打擊下， f 為已被破壞的邊的數(shù)目與總邊數(shù)的比值， f 愈大則網(wǎng)絡(luò)的抗毀性愈不好。其中，圖 到圖 中， f 表示邊刪除比例， R 表示節(jié)點(diǎn)連通對比例。由此可知 ,如果能夠獲取 20%的重要邊的信息 ,對網(wǎng)絡(luò)的抗毀性就會(huì)有致命的影響。在故意攻擊下 ,攻擊 20%的邊 ,網(wǎng)絡(luò)的效率就下降到 5%左右 ,因此可 以看出 ,為了提高網(wǎng)絡(luò)的效率 ,可以有針對性地對重要的邊進(jìn)行保護(hù) ,保護(hù)約20%的重要邊就可以大大提高網(wǎng)絡(luò)的抗毀性。在網(wǎng)絡(luò)信息為優(yōu)先獲取情況下，只需要獲取少量重要的邊信息就會(huì)導(dǎo)致網(wǎng)絡(luò)變得異 常脆弱。 在基于邊的抗毀性仿真中，可以得出：當(dāng)網(wǎng)絡(luò)信息獲取為隨機(jī)獲取時(shí)，網(wǎng)絡(luò)的抗毀性取決于網(wǎng)絡(luò)信息量的獲取程度。 圖 ??? 時(shí)， R 隨 f 的變化情況 從圖 上可以看出 ,在信息優(yōu)先獲取條件下 ,網(wǎng)絡(luò)表現(xiàn)的極為脆弱 ,只要?jiǎng)h除 20%的邊 ,網(wǎng)絡(luò)的效率己經(jīng)下降為 4%