网络脆弱性以及鲁棒性理论的近期研究发展

强 强

(宾夕法尼亚州立大学职业研究生学院,马尔文PA 19355)

1 研究网络脆弱性的意义

自本世纪初,自然灾害和人为灾害频发,并在近几年里继续呈上升趋势.根据一项近期的研究报告显示,在2005年1月至2005年10月期间,全球有97 490人死于灾害,其中88 117人死于自然灾害[1].图1[2](见下页)所示的1975年至2005年间,呈多项式增长的灾难次数和死伤人数,进一步证实了从1975年以来,全球灾害发生次数和受影响人数呈多项式增长,这些灾难的发生对于一个国家的基础设施网络以及人的生命均造成了巨大的危害.如2005年的飓风卡特琳娜直接导致了812亿美元的经济损失以及1 836人的死亡[3].2008年春节期间发生在中国的暴风雪,给国家造成了120亿美元的经济损失[4],有近1.8亿人被这场突如其来的暴风雪阻断在回家探亲的途中,交通系统的瘫痪使居民所需的燃料和食品无法送达目的地,从而引起大部分地区断水断电以及食品价格的飞速上涨[5].2011年的日本大地震对全球的供应链造成了巨大的创伤.由于全球五分之一的硅片(半导体的原材料)来自于日本,此次地震造成了全球众多电子产品制造商减产甚至停产.同时,日本是全球大量汽车制造厂商的零部件供货源,地震直接导致部分汽车制造商被迫停产,其中包括美国最大的汽车制造商通用公司,致使通用公司关闭了其在路易斯安娜州的生产厂[6].

图1 呈多项式增长的灾难次数和死伤人数(1975-2004)Fig.1 Polynomial trendsill numbers of natural disasters persons killed and persons dffected(1975-2004)

基础设施网络是一个国家的命脉,一些极小的因素就有可能造成大范围的影响.这些基础设施网络包括供应链、英特网、供电网络以及交通网络.如果能对这些网络的脆弱性(vulnerability)做出准确的估计并采取相应措施,上述的经济损失和人员伤亡便可减少到最小程度.正是这一特性,激起大量学者对网络脆弱性的广泛研究.

2 复杂网络理论中对网络脆弱性的研究

近些年来,无尺度网络(scale-free network)和小世界网络(small-world network)学说的提出[7-8]让人们对复杂网路的结构和脆弱性有了更深一步的了解.互联网,全球航空网络以及供电网等现实生活中的复杂网络都被用来作为研究的对象[9-11].但值得注意的是,在这些研究中,绝大多数的文章都是从结构特性出发来讨论网络的脆弱性,比如对网络的连接性(connectivity)或网络平均最短路径的研究.另外,度数(degree)、介度(betweenness)以及紧密度(closeness)等一些集中性(centrality)的侧度量也是研究中常使用的对象,这些集中性的侧度量都是基于Freeman[12]的经典文献.以下是对这些测度量的简单分析讨论.

就像Barrat等[13]所讨论的,“确定最中心(most central)的节点是刻画网络各种特性的研究中最主要的问题.”只有认识了哪里是网络最重要的部分才能够更好地认识网络的脆弱性,从而更有效地保护网络.而网络的集中性对网络脆弱性的评估有着很大的意义.一个节点的度数就是连接这个节点的链节数.一个节点的介度等于穿过这个节点的最短路径数目.如果一个节点有着很大的度数和介度,这个节点就被认为对于这个网络是很重要的.一个节点的紧密性是这个节点到网络其余节点的平均最短路径的倒数.这个量越小,那么这个点就离其它节点很近,因此就很重要.

另外,还有一些其它经常使用到的关于衡量网络其它方面集中性的侧度量.比如,特征向量集中性(eigenvector centrality)[14]和流量集中性[15].如果一个节点与其它集中性高的点相连,那么它的特征向量集中性也高.如果有相对较高的流量通过一个节点,那么它的流量集中性也高.除了上面的关于节点的集中性侧度量,有些学者也做出了关于链节的介度的研究[16-17].

有些学者意识到了单单用网络结构来刻画网络脆弱性是不足的.为此他们提出了给网络链节加权重的研究方式来获取更多的网络信息.比如有些学者用链节流量作为权重[18-20].这些加了权重的网络被称为加权网络.正如Barrat等[13]所说,“……网络不应该仅仅是被结构来描述的,在这些结构上运行变化的流量也提供了重要的信息……在大型的电信网和交通网上,这些流量提供了最根本的信息.”

然而这些作者往往只考虑网络中的节点而忽略链节的重要性.在对链节的研究中,往往通过用距离和流量的组合来作为链节的权重.但是这些组合明显忽略了网络上发生的拥堵以及因此而导致的个人行为.例如,Barthélemy和Flammini[20]在假设平均网络旅行成本最小化的前提下对全球空中航行网络的流量分布情况做出的研究.根据作者的定义,旅行成本随着流量的增加而减少,然而这一观点是不符合交通网络所特有的拥堵特性的[21-23].Latora和Machiori提出了一个崭新的基于平均网络最短路径的倒数网络效能指标.作者还定义了网络节点和链节的重要性.这个重要性被定义为:在删除节点和链节以后网络效能的相对损失.根据这个定义,那些重要的节点或链节的去除将会造成较大的网络相对效能损失.这个指标在复杂网络研究领域中造成了较大的影响.Latora和Machiori的指标被用于研究许多实际网络(包括波士顿公共交通网以及互联网)中网络部件的重要性[24-25].

尽管这些特性对于理解网络脆弱性有着很重要的帮助,但是网络上的流量以及相对应的费用也是不可忽视的重要因素.网络中那些负载着正流量的链节和路径以及它们被使用程度对于分析网络脆弱性是有着很明显的作用.正由于网络流量的重要性,著名的复杂网络研究学者Barabási在他的著作[26]中谈到:“若要想真正理解网络的复杂性,我们必须走出仅仅局限于网络结构的范畴.我们应该着眼于网络链节上发生的变化(流量).网络不仅是错综复杂的骨架,那些在这些骨架上流动的过程才是让我们的世界运转起来的动力.”

在一些经典的基础网络中(包括交通网络和供应链网络),个人对成本费用的估计将会影响他们的行为从而影响网络流量的分布.因此,如果要研究网络的脆弱性,这些因素都应该被考虑在内,而且它们会影响一个网络的脆弱性的评估.而上述因素却往往被忽略了[27-28].

3 关于网络鲁棒性的研究

鲁棒性的概念已经被计算机科学和工程学广为研究.根据美国电气工程师协会的介绍,鲁棒性可以被定义为“对于系统或组件在无效输入或存在压力环境的条件下能够正确运作的程度”.Gribble[29]把系统鲁棒定义为“一个系统在一系列不同的操作条件下继续正确运行的能力,并且这个系统应该在这些条件外故障发生率很低.”Ali等[30]从资源分配的角度讨论了鲁棒性.他们认为如果一个资源分配的方案“在其组成部分行为或其周围环境有所波动下仍然能保证维持某些系统所需特性,”那么这个分配方案具有鲁棒性.Schillo等[31]提出鲁棒性的研究应该在确定有关于效能指标的一些定义的前提下.根据Holmegren[11]的观点,“鲁棒性意味着当接触到微扰,该系统将保留其系统结构(或者功能)完好无损(维持不变或几乎不变)的能力”.

复杂网络的学者也开始对网络的鲁棒性做出了研究.但很遗憾的是,这些研究中缺乏一个明确的量化的网络鲁棒性的指标定义.此外,大多数研究主要集中于网络特定布局分布或者某些的节点在网络中的删除[32-36].例如,Gergana等(2006)通过研究节点的度和介度的分布来研究中国国内航线的鲁棒性.这些作者还提出了网络的健康指标的概念.这个指标被用来评估航空网络在一些中心被破坏以后的连接性,那些仍旧具有连接性的航空网络被认为是有较好的鲁棒性.

近来,越来越多的学者开始关注交通网络鲁棒性的研究.例如,Sakakibara[37]以及Scott等[38]试图去解决交通运输网络的鲁棒性.Sakakibara[37]提出了交通网络的机构布局指数的概念.作者们认为如果根据每个节点上的链节数量呈现分散态势,那么交通网络具有鲁棒性.另一方面,Scott[38]通过分析移除某些网络成员后的整个网络的成本增加来检验交通运输网络的鲁棒性.以上的成本是在用户最佳模式(user-optimal)下的成本,这些成本的增加被定义为交通网络鲁棒性指数.我们认为这些指数更适合作为一个链节的重要性的测量标准而非网络鲁棒性的度量.此外,这些成本也缺乏网络系统最佳模式(system-optimal)情况下的鲁棒性定义.Ukkusuri等[39]提出在不确定性需求的情况下,从网络容量设计方面研究网络的鲁棒性.他们的研究是通过在给均值和方差分配不同的权重的前提下,网络在用户最佳模式下的总旅行成本的变化来进行的.

供应链网络风险管理的目的是减少网络中断所产生的影响.这种目的也可以被称为增加供应链的鲁棒性.在供应链鲁棒性研究中,定量的研究很少. Bundschun等[40]从供应链的可靠性和鲁棒性方面讨论了供应链的最优设计.以上作者所用的供应链模型规定了每个公司必须向大于一定数目的供应商获取货物,从而把冗余性和可靠性变相建立在模型里.Snyder等[41]从工厂选址方面来研究了供应链易损性.但是,就像Snyder等[42]所述:“尽管这些研究是多处选址问题,但是它们仅仅是局限于那些供应链中断的本地影响.”如果读者感兴趣,Tang[43]中对供应链风险模型有一个比较全面得概述.

综上所述,大部分供应链的风险研究仅仅局限于本地效应.而且大多数是着眼于单一的供应商与单一的零售商的简单组合[44-45].很少有文章从多个供应商和零售商的竞争和配合的角度出发来研究供应链的风险管理[46].而这些正是现代供应链所应具备的特征.

4 结论和今后研究前瞻

由于近期自然灾难对基础设施网络的损害,越来越多的研究致力于如何正确地检验网络的脆弱性从而能够更加有效地保护这些和人们生活息息相关的网络.现存的网络易损性的研究往往着眼于网络的结构特征.这些特征往往忽略了其它一些重要的因素,比如用户的行为、网络的流量以及网络成本等,以至于往往会造成不合理的结果.因此,我们期待看到更多的关于网络脆弱性和鲁棒性方面的研究.

[1] BRAINE T.Was 2005 the year of natural disasters? [J].Bulletin of the World Health Organization,2006, 84:1-80.

[2] World Health Organization.Emergency Event Database[EB/OL].http:∥www.who.int/bulletin/volumes/84/1/news_figure_0106/en/index.html,2005 -06-01/2011-05-01.

[3] US Department ofCommerce.HurricaneKatrina service assessment report[EB/OL].www.weather. gov/os/assessments/pdfs/Katrina.pdf,2006-06/ 201 1-05-01.

[4] BBC N.China freeze has cost billions[EB/OL].http:∥news.bbc.co.uk/2/hi/asia-pacific/7221456.stm, 2008-02/2011-05-01.

[5] BBC N.Food warnings amid China freeze[EB/OL]. http:∥ news.bbc.co.uk/2/hi/asia-pacific/ 7219092.stm,2008-01-31/2011-05-01.

[6] HOOKWAY J,POON,A.Crisis tests supply chain's weak links,Wall Street Journal[EB/OL].http:∥online.wsj.com/article/SB10001424052748703818 204576206170102048018.html,2011-03-18/2011 -05-01.

[7] WATTS D J ST ROGA TZ S H.Collective dynamics of‘small-world'networks[J].Nature,1998,393 (6684):440-442.

[8] BARABASI A L,ALBERT A L R.Emergence of scaling in random networks[J].Science,1999,286 (5439):509-512.

[9] BARABASI A L,ALBERT R,JEONG H.Scale-free characteristics of random networks:The topology of the worldwide web[J].Physical A,2000,281:69-77.

[10] AM ARAL L A N,SCALA A,BARTHELEMY A,et al.Classes of small-world networks[J].Proceedings of the National Academy of Sciences of the United States of America,2000,97(21):11149-11152.

[11] HOLMGREN A J.A framework for vulnerability assessment of electric power systems[C]∥MURRAY A,GRUBESIC T.In Critical Infrastructure-Reliability and vulnerability.Berlin:Springer,2007:31-55.

[12] FREEMAN L.Centrality in social networks conceptual clarification[J].Social Networks,1979,1(3): 215-239.

[13] BARRAT A,BARTHELEMY M,PASTOR-SATORRAS R,et al.The architecture of complex weighted networks[J].Proceedings of the National Academy of Sciences USA,2004,101:3747-3752.

[14] BONACICH P.Factoring and weighting approaches to status scores and clique identification[J].Journal of Mathematical Sociology,1972,2:13-20.

[15] FREEMAN L C,BORGA TTI S P,WHITE D R. Centrality in valued graphs:A measure of betweenness based on network flow[J].Social Networks, 1991,13:141-154.

[16] GIRVAN M,NEWM AN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America,2002,99(12):7821-7826.

[17] HOLME P,KIM B J.Vertex overload breakdown in evolving networks[J].Physical Review E,2002, 65:066109.

[18] BARRAT A,BARTHELEMY M,PASTOR-SATORRAS R,et al.The effects of spatial constraints on the evolution of weighted complex networks[J]. Journal of Statistical Mechanics:Theory and Experiment,2005:P05003.

[19] DALL'ASTA L,BARRAT A,BARTHELEMY M, et al.Vulnerability of weighted networks[J].Journal of Statistical Mechanics,2006:P04006.

[20] BARTHELEMY M,FLAM MINI A.Optimal traffic flows[J].Journal of Statistical Mechanics:Theory and Experiment,2006:L07002.

[21] BECKMANN M J,MCGUIRE C B,WINSTEN C B. Studies in the Economics of Transportation[R].New Haven:Yale University Press,1956.

[22] DAFERMOS S C,SPARROW F T.The traffic assignment problem for a general network[J].Journal of Research of the National Bureau of Standards, 1969,73B:91-118.

[23] NAGURNEY A.Network Economics:A Variational Inequality Approach(2nd and revised edition)[R]. Dordrecht:Kluwer Academic Publishers,1999.

[24] LATORA V,MARCHIORI M.Is the Boston subway a small-world network[J]Physica A,2002,314:109-113.

[25] LATORA V,MARCHIORI M.How the science of complex networks can help developing strategies against terrorism[J].Chaos.Solitons and Fractals, 2004,20:69-75.

[26] BARABASI A-L.Linked:how everything is connected to everything else and what it means[R].New York:The Penguin Group,2003.

[27] NAGURNEY A,QIANG Q.A network efficiency measure for congested networks[J].Europhysics Letters,2007,79:38005.

[28] NAGURNEY A,QIANG Q.A network efficiency measure with application to critical infrastructure networks[J].Journal of Global Optimization,2008,40: 261-275.

[29] GRIBBLE S D.Robustness in complex systems[J]. Proceedings of the 8th Work Shop on Hot Topics in Operating Systems,2001,(HotOS-VIII),21-26.

[30] ALI S,MACIEJEWSKI A A,SIEGEL H J,et al. Definition of a robustness metric for resource allocation[J].Parallel and Distributed Processing Symposium,2003,42:1-10.

[31] SCHILLO M,BURCHERT H,FISCHER K,et al. Towards a definition of robustness for market-style open multi-agent systems[C]∥Proceedings of 5th International Conferenceon Autonomous Agents. Montrenl:2001:75-76.

[32] CALLAWAY D,NEWMAN M,ST ROGATZ S,et al.Network robustness and fragility:Percolation on random graphs[J].Physical Review Letters,2000,85 (25):5468-5471.

[33] ALBERT R,JEONG H,BARABASI A L.Attack and error tolerance of complexnetworks[J],Nature, 2000,401:130-131.

[34] NEWM AN M E J.The structure and function of complex networks[J].SIAM Review,2003,45:167 -256.

[35] ALBERT R,ALBERT I,NAKARADO G L.Structural vulnerability of the North American power grid [J].Physical Review E,2004,69:025103.

[36] HOLME P,KIM B J,YOON C N,et al.Attack vulnerability of complex networks[J].Physical Review E,2002,65:056109.

[37] SAKAKIBA RA H,KAJITAN Y,OKADA N.Road network robustness for avoiding functional isolation in disasters[J].Journal of Transportation Engineering,2004,130(5):560-567.

[38] SCOTT D,NOVAK D,AU LTMAN-HALL L,et al.Network robustness index:A new method for identifying critical links and evaluating the performance of transportation networks[J].Journal of Transport Geography,2006,14(3):215-227.

[39] UKKUSURI S V,MAT HEW T V,WA LLER S T. Robust transportation network design under demand uncertainty[J].Computer-Aided Civil and Infrastructure Engineering,2007,22(1):6-18.

[40] BUNDSCHUH M,KLABJAN D,THURSTON D L. Modeling robust and reliable supply chains[EB/OL]. Optimization Online e-print,www.optimizationonline.org,2003-06/2009-10.

[41] SNYDER L V,DASKIN M S.Reliability models for facility location:The expected failure cost case[J]. T ransportation Science,2005,39(3):400-416.

[42] SNYDER L V,SHEN Z M.Managing disruptions to supply chains[J].The Bridge,2006,36(4):39-45.

[43] TANG C S.Perspectives in supply chain risk management[J].International Journal of Production Economics,2006,103:451-488.

[44] GUPTA D.The(Q;r)inventory system with an unreliable supplier[J].INFOR,1996,34:59-76.

[45] PARLAR M.Continuous review inventory problem with random supply interruptions[J].European Journal of Operations Research,1997,99:366-385.

[46] TOMLIN B T.On the value of mitigation and contingency strategies for managing supply chain disruption risks[J].Management Science,2006,52:639-657.