人们普遍认为,对于一般的网络图而言,当网络弧在生长时将有益于网络可靠性的增强。然而事实证明该论断并不完全正确。对于某些注重最短路径长度的网络而言:(1) 当网络>G受到随机攻击时,以网络最短路熵作为网络可靠性的判断依据,分别计算在增加一条弧前后网络结点或网络弧受到攻击而失效时的网络最短路熵,比较网络最短路熵的大小,熵值越大,可靠性越弱;(2) 当网络G受到恶意攻击时,根据悲观原则定义了一种新的可靠性指标,该指标值越大,网络可靠性越强。结果表明:(1) 当G与G'的最短路径长度相等时,G'的可靠性不弱于G;(2)当G与G'的最短路径长度不相等时,G与G'的可靠性相对大小关系不唯一。对该问题的研究有助于人们清楚的认识到网络弧生长对网络可靠性的影响。最后用简化的江苏省城市间高速公路网络图为例来说明该研究的有效性与实用性。
It is commonly recognized that, as to a general network, the network reliability will be increasingly enhanced when network arcs are growing. However, this argument is not entirely correct. For some researches on networks that mainly focus on shortest path length, the conclusions can be got as follows. First, if network G suffers from random attacks, the network shortest path entropy is utilized as a criterion judging the network reliability and will be computed before and after an extra arc is added when the network node or arc is attacked and thus fails. In this case, the larger the entropy value is, the weaker the reliability becomes. Second, if network G suffers from malicious attacks, a newly-defined reliability indicator is applied in accordance with pessimistic principle, which is positively correlated with network reliability. The result further shows that: when G is identical to G' in the shortest path length, then the reliability of G' is not weaker than G's; when G is not equal to G' in the shortest path length, their reliability's relative value is not unique. This study helps cultivate an in-depth understanding of the influence of network arc's growth on the network's reliability. Finally, a simplified inter-city expressway network graph of Jiangsu province is exemplified to demonstrate the effectiveness and practicability of this approach.
[1] Erdös P, Rényi A. On random graphs I [J]. Publicacions Matemtiques, 1959, (6): 290-297.
[2] Watts D J, Strogatz S H. Collective of "small-world" networks[J]. Nature, 1998, 393(6684) :440-442.
[3] Barabási A L, Albert R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512.
[4] Satyanarayana A. A unified formula for analysis of some network reliability problems[J]. IEEE Transactions on Reliability. 1982,31(1):23-32.
[5] 何时,陈国华,江俊,等.一种基于拓扑结构的网络两终端可靠性评估方法[J].计算机科学,2011,38 (12):96-99.
[6] Hardy G, Lucet C, Limnios N. K-terminal network reliability measures with binary decision diagrams[J].IEEE Transactions on Reliability, 2007, 56(3):506-515.
[7] 吴俊,谭跃进.复杂网络抗毁性测试研究[J].系统工程学报,2005,20(2):128-131.
[8] 谭跃进,吴俊,邓宏钟.复杂网络抗毁性研究进展[J].上海理工大学学报,2011,33(6):653-668.
[9] 邓宏钟,吴俊,李勇,等.复杂网络拓扑结构对系统抗毁性影响研究[J].系统工程与电子技术,2008, 30(12):2425-2428.
[10] Main H,Kawai H. Mathematics for reliability analysis[M]. Tokyo:Asakurashoten,1982.
[11] 冯海林,刘三阳,宋月.通信网全端可靠性界的一种计算方法[J].电子学报,2004,32(11):1868-1870.
[12] 侯立文,蒋馥.基于路网可靠性的路网服务水平[J].系统工程理论方法应用,2003,12(3):248-252.
[13] Wang Dianhai, Qi Hongsheng, Xu Cheng. Reviewing traffic reliability research[J]. Journal of Transportation Systems Engineering and Information Technology, 2010,10(5):12-21.
[14] Yin Yafeng, Madanat S M, Lu Xiaoyun. Robust improvement schemes for road networks under demand uncertainty[J]. European Journal of Operational Research, 2009,198(2):470-479.
[15] 李英,周伟,郭世进.上海公共交通网络复杂性分析[J].系统工程,2007,25(1):38-41.
[16] Jenelius E, Petersen T, Mattsson L G. Importance and exposure in road network vulnerability analysis[J]. Transportation Research Part A:Policy and Practice,2006,40(7):537-560.
[17] 王伟,刘军,李海鹰.铁路网抗毁性分析[J].铁道学报,2010,32(4):18-22.
[18] Fang Shuming, Wakabayashi H.Cost-benefit analysis for traffic network reliability improvement[J].Procedia - Social and Behavioral Sciences,2012,54:696-705.
[19] 李勇,吴俊,谭跃进.容量均匀分布的物流保障网络级联失效抗毁性[J].系统工程学报,2010,25 (6):853-860.
[20] 陈德良.物流网络可靠性的关键问题与应用研究[D].长沙:中南大学,2010.
[21] Shao Fangming, Zhao Lianchang. Optimal design improving a communication network reliability[J]. Microelectronics Reliability, 1997,37(4):591-595.
[22] 包学才,戴伏生,韩卫占.基于拓扑的不相交路径抗毁性评估方法[J].系统工程与电子技术,2012, 34(1):168-174.
[23] Kansal M L, Sunita D. An improved algorithm for connectivity analysis of distribution networks[J]. Reliability Engineering and System Safety,2007,42(10):1295-1302.
[24] Lin Y K, Yeh C T. Maximal network reliability for a stochastic power transmission network [J]. Reliability Engineering and System Safety,2011,96(10):1332-1339.
[25] 邱菀华.管理决策熵学及其应用[M].北京:中国电力出版社,2011.
[26] 马丽仪,邱菀华,杨亚琴.大型复杂项目风险建模与熵决策[J].北京航空航天大学学报,2010, (2):184-187.
[27] 周荣喜,刘善存,邱菀华.熵在决策分析中的应用综述[J].控制与决策,2008,23(4):361- 366.
[28] Wang Bing, Tang Huanwen, Guo Chonghui, et al. Entropy optimization of scale-free networks' robustness to random failures[J]. Physica A:Statistical Mechanics and its Applications,2006,363(12):591-596.
[29] 张义荣,鲜明,王国玉. 一种基于网络熵的计算机网络攻击效果定量评估方法[J]. 通信学报, 2004,25 (11):158-165.
[30] Demetrius L, Manke T. Robustness and network evolution-an entropic principle[J]. Physica A:Statistical Mechanics and its Applications,2005,346(13): 682-696.
[31] 吴六三,谭清美.基于网络熵的应急物流网络可靠性研究[J].当代财经,2012,(7):60-68.
[32] Latora V, Marchiori M. Efficient behavior of small-world networks [J]. Physical Review Latters, 2001, 87(19): 1-5.
