復雜網絡的魯棒性研究

1網絡脆弱性的概念研究就容易造成全球自本世紀初以來，自然災害和人為災害頻繁發(fā)生，并逐年增加。根據(jù)最近的研究報告，2005年1月至2005年10月，世界上有97900人死亡，其中8811人死亡。根據(jù)圖1（見下頁），從1975年到2005年，災難的數(shù)量和死亡率有逐漸增加，這進一步表明，自1975年以來，世界災難的數(shù)量和影響有所增加。這些災難的發(fā)生對國家的基礎設施網絡以及人們的生活有了巨大的破壞。例如，2005年的臺風卡隆納直接導致812億人的經濟損失和836人的死亡。2008年春節(jié)期間，中國發(fā)生了一場風暴，給國家?guī)砹?20億人的經濟損失。近1.8億人被風暴堵塞回家進行看病的路上。由于系統(tǒng)超載，許多地區(qū)的供水量和食品價格立即上漲。2011年日本的強烈地震嚴重影響了全球供應鏈。世界上三分之一的硅片（原料）直接來自日本，這導致日本主要家電制造商不得不關閉或關閉大部分設備制造商的車間?；A設施網絡是一個國家的命脈,一些極小的因素就有可能造成大范圍的影響.這些基礎設施網絡包括供應鏈、英特網、供電網絡以及交通網絡.如果能對這些網絡的脆弱性(vulnerability)做出準確的估計并采取相應措施,上述的經濟損失和人員傷亡便可減少到最小程度.正是這一特性,激起大量學者對網絡脆弱性的廣泛研究.2網絡集中性的評估近些年來,無尺度網絡(scale-freenetwork)和小世界網絡(small-worldnetwork)學說的提出讓人們對復雜網路的結構和脆弱性有了更深一步的了解.互聯(lián)網,全球航空網絡以及供電網等現(xiàn)實生活中的復雜網絡都被用來作為研究的對象.但值得注意的是,在這些研究中,絕大多數(shù)的文章都是從結構特性出發(fā)來討論網絡的脆弱性,比如對網絡的連接性(connectivity)或網絡平均最短路徑的研究.另外,度數(shù)(degree)、介度(betweenness)以及緊密度(closeness)等一些集中性(centrality)的側度量也是研究中常使用的對象,這些集中性的側度量都是基于Freeman的經典文獻.以下是對這些測度量的簡單分析討論.就像Barrat等所討論的,“確定最中心(mostcentral)的節(jié)點是刻畫網絡各種特性的研究中最主要的問題.”只有認識了哪里是網絡最重要的部分才能夠更好地認識網絡的脆弱性,從而更有效地保護網絡.而網絡的集中性對網絡脆弱性的評估有著很大的意義.一個節(jié)點的度數(shù)就是連接這個節(jié)點的鏈節(jié)數(shù).一個節(jié)點的介度等于穿過這個節(jié)點的最短路徑數(shù)目.如果一個節(jié)點有著很大的度數(shù)和介度,這個節(jié)點就被認為對于這個網絡是很重要的.一個節(jié)點的緊密性是這個節(jié)點到網絡其余節(jié)點的平均最短路徑的倒數(shù).這個量越小,那么這個點就離其它節(jié)點很近,因此就很重要.另外,還有一些其它經常使用到的關于衡量網絡其它方面集中性的側度量.比如,特征向量集中性(eigenvectorcentrality)和流量集中性.如果一個節(jié)點與其它集中性高的點相連,那么它的特征向量集中性也高.如果有相對較高的流量通過一個節(jié)點,那么它的流量集中性也高.除了上面的關于節(jié)點的集中性側度量,有些學者也做出了關于鏈節(jié)的介度的研究.有些學者意識到了單單用網絡結構來刻畫網絡脆弱性是不足的.為此他們提出了給網絡鏈節(jié)加權重的研究方式來獲取更多的網絡信息.比如有些學者用鏈節(jié)流量作為權重.這些加了權重的網絡被稱為加權網絡.正如Barrat等所說,“……網絡不應該僅僅是被結構來描述的,在這些結構上運行變化的流量也提供了重要的信息……在大型的電信網和交通網上,這些流量提供了最根本的信息.”然而這些作者往往只考慮網絡中的節(jié)點而忽略鏈節(jié)的重要性.在對鏈節(jié)的研究中,往往通過用距離和流量的組合來作為鏈節(jié)的權重.但是這些組合明顯忽略了網絡上發(fā)生的擁堵以及因此而導致的個人行為.例如,Barthélemy和Flammini在假設平均網絡旅行成本最小化的前提下對全球空中航行網絡的流量分布情況做出的研究.根據(jù)作者的定義,旅行成本隨著流量的增加而減少,然而這一觀點是不符合交通網絡所特有的擁堵特性的.Latora和Machiori提出了一個嶄新的基于平均網絡最短路徑的倒數(shù)網絡效能指標.作者還定義了網絡節(jié)點和鏈節(jié)的重要性.這個重要性被定義為:在刪除節(jié)點和鏈節(jié)以后網絡效能的相對損失.根據(jù)這個定義,那些重要的節(jié)點或鏈節(jié)的去除將會造成較大的網絡相對效能損失.這個指標在復雜網絡研究領域中造成了較大的影響.Latora和Machiori的指標被用于研究許多實際網絡(包括波士頓公共交通網以及互聯(lián)網)中網絡部件的重要性.盡管這些特性對于理解網絡脆弱性有著很重要的幫助,但是網絡上的流量以及相對應的費用也是不可忽視的重要因素.網絡中那些負載著正流量的鏈節(jié)和路徑以及它們被使用程度對于分析網絡脆弱性是有著很明顯的作用.正由于網絡流量的重要性,著名的復雜網絡研究學者Barabási在他的著作中談到:“若要想真正理解網絡的復雜性,我們必須走出僅僅局限于網絡結構的范疇.我們應該著眼于網絡鏈節(jié)上發(fā)生的變化(流量).網絡不僅是錯綜復雜的骨架,那些在這些骨架上流動的過程才是讓我們的世界運轉起來的動力.”在一些經典的基礎網絡中(包括交通網絡和供應鏈網絡),個人對成本費用的估計將會影響他們的行為從而影響網絡流量的分布.因此,如果要研究網絡的脆弱性,這些因素都應該被考慮在內,而且它們會影響一個網絡的脆弱性的評估.而上述因素卻往往被忽略了.3交通網絡魯棒性的研究魯棒性的概念已經被計算機科學和工程學廣為研究.根據(jù)美國電氣工程師協(xié)會的介紹,魯棒性可以被定義為“對于系統(tǒng)或組件在無效輸入或存在壓力環(huán)境的條件下能夠正確運作的程度”.Gribble把系統(tǒng)魯棒定義為“一個系統(tǒng)在一系列不同的操作條件下繼續(xù)正確運行的能力,并且這個系統(tǒng)應該在這些條件外故障發(fā)生率很低.”Ali等從資源分配的角度討論了魯棒性.他們認為如果一個資源分配的方案“在其組成部分行為或其周圍環(huán)境有所波動下仍然能保證維持某些系統(tǒng)所需特性,”那么這個分配方案具有魯棒性.Schillo等提出魯棒性的研究應該在確定有關于效能指標的一些定義的前提下.根據(jù)Holmegren的觀點,“魯棒性意味著當接觸到微擾,該系統(tǒng)將保留其系統(tǒng)結構(或者功能)完好無損(維持不變或幾乎不變)的能力”.復雜網絡的學者也開始對網絡的魯棒性做出了研究.但很遺憾的是,這些研究中缺乏一個明確的量化的網絡魯棒性的指標定義.此外,大多數(shù)研究主要集中于網絡特定布局分布或者某些的節(jié)點在網絡中的刪除.例如,Gergana等(2006)通過研究節(jié)點的度和介度的分布來研究中國國內航線的魯棒性.這些作者還提出了網絡的健康指標的概念.這個指標被用來評估航空網絡在一些中心被破壞以后的連接性,那些仍舊具有連接性的航空網絡被認為是有較好的魯棒性.近來,越來越多的學者開始關注交通網絡魯棒性的研究.例如,Sakakibara以及Scott等試圖去解決交通運輸網絡的魯棒性.Sakakibara提出了交通網絡的機構布局指數(shù)的概念.作者們認為如果根據(jù)每個節(jié)點上的鏈節(jié)數(shù)量呈現(xiàn)分散態(tài)勢,那么交通網絡具有魯棒性.另一方面,Scott通過分析移除某些網絡成員后的整個網絡的成本增加來檢驗交通運輸網絡的魯棒性.以上的成本是在用戶最佳模式(user-optimal)下的成本,這些成本的增加被定義為交通網絡魯棒性指數(shù).我們認為這些指數(shù)更適合作為一個鏈節(jié)的重要性的測量標準而非網絡魯棒性的度量.此外,這些成本也缺乏網絡系統(tǒng)最佳模式(system-optimal)情況下的魯棒性定義.Ukkusuri等提出在不確定性需求的情況下,從網絡容量設計方面研究網絡的魯棒性.他們的研究是通過在給均值和方差分配不同的權重的前提下,網絡在用戶最佳模式下的總旅行成本的變化來進行的.供應鏈網絡風險管理的目的是減少網絡中斷所產生的影響.這種目的也可以被稱為增加供應鏈的魯棒性.在供應鏈魯棒性研究中,定量的研究很少.Bundschun等從供應鏈的可靠性和魯棒性方面討論了供應鏈的最優(yōu)設計.以上作者所用的供應鏈模型規(guī)定了每個公司必須向大于一定數(shù)目的供應商獲取貨物,從而把冗余性和可靠性變相建立在模型里.Snyder等從工廠選址方面來研究了供應鏈易損性.但是,就像Snyder等所述:“盡管這些研究是多處選址問題,但是它們僅僅是局限于那些供應鏈中斷的本地影響.”如果讀者感興趣,Tang中對供應鏈風險模型有一個比較全面得概述.綜上所述,大部分供應鏈的風險研究僅僅局限于本地效應.而且大多數(shù)是著眼于單一的供應商與單一的零售商的簡單組合.很少有文章從多個供應商和零售商的競爭和配合的角度出發(fā)來研究供應鏈的風險管理.而這些正是現(xiàn)代供應鏈所應具備