基于复杂网络的美国航空线路网络的抗毁性研究
|
摘要
本文基于复杂网络的理论基础,以美国航空线路网络为主要研究对象,以复杂网络的抗毁性为研究目标,以两种常见的典型复杂网络模型(SW小世界网络和BA无标度网络)为对比对象,分析了在静态和动态条件下,不同网络的抗毁性仿真结果,并对结果进行了分析。
通过使用复杂网络分析软件pajek对美国航空线路网络进行了实证研究,实证结果发现美国航空线路网络的度分布近似服从幂律分布,即度分布P(k)∞k-r,其中幂指数r=1-8,是一个无标度网络,另外整个网络的平均路径长度L≈2.74,很明显美国航空飞行线路网络具备小世界网络的特性。
在静态条件下,通过不同攻击模式(随机攻击和蓄意攻击)在美国航空线路网络、SW小世界网络和BA无标度网络上分别进行了抗毁性实验,结果发现,对于随机攻击,美国航空线路网络、BA无标度网络的抗毁性比SW小世界网络要强,在蓄意攻击模式下,SW小世界网络的抗毁性最强,美国航空线路网络和BA无标度网络的抗毁性区别不大,美国航空线路网络的抗毁性要差一些。
在动态条件下,本文提出了一种新的相继故障模型,节点i的初始负荷Li定义为Li=(BiKi)α,其中Bi代表节点的介数,Ki代表节点的度值,α表示可调参数。并美国航空线路网络、SW小世界网络和BA无标度网络上分别进行了相继故障的仿真研究,仿真结果表明SW小世界网络存在阈值αc,当a值小于阈值αc,网络不会发生相继故障,否则就会发生相继故障,而BA无标度网络和美国航空线路网络则不存在这样的阈值αc。SW小世界网络的抗毁性大于美国航空线路网络,美国航空线路网络的抗毁性大于BA无标度网络。另外一个重要发现为在现实当中的BA无标度网络中,虽说可以通过花费更多的成本来增加网络节点的抗毁性,但是a值较大时,再想通过增加λ值来大幅度的降低相继故障的规模不可能的。
Based on the complex networks theory, this thesis takes the US Air line network as the main research object, takes the robustness of complex networks as research target. With the two most common types of typical complex network model (SW small world network and BA scale-free network) for comparison, according to the static and dynamic conditions, we get the simulation results of different networks and analysis them.
With Complex network analysis software pajek, we carry on the empirical research of the US Air line network. The empirical results imply that the degree distribution of the US Air line network follows a power law, p(k)∝k-r, degree exponent r≈1.8. So it is a scale-free network. In addition, the Average path length of the US Air line network is2.74, obviously the US Air line network gets Small world network characteristics.
In the static condition, through the different attack modes (random perturbations and intentional attacks), we conduct the experiment for getting the robustness results of SW small world network, BA scale-free network and the US Air line network. The results show that under random perturbations, the robustness between BA scale-free network and the US Air line network is higher than SW small world network; under intentional attacks, the robustness of SW small world network is the highest, There is not much difference between BA scale-free network and the US Air line network, precisely speaking, the robustness of the US Air line network is smaller than BA scale-free network.
In the dynamic condition, we propose a new cascading failure model, Adopting the initial load of a node i to be Lj=(BjKj)α with Ki and Bi being the degree and the betweenness of the node i, respectively, where a is a tunable parameter and governs the strength of the initial load of a node. We conduct cascading failure simulation research on the US Air line network, SW small world network and BA scale-free network. The results show that SW small world network have a threshold value a,when parameter a is smaller than ac, cascading failure won't happen, otherwise, it happen. Threshold value α,don't exist between the US Air line network is smaller than BA scale-free network, the robustness of SW small world network is higher than the US Air line network, the robustness of the US Air line. network is higher than BA scale-free network. Another important discovery is that in BA scale-free network, although it is feasible through Spending more cost to increase the robustness, when a is more, that's impossible.
通过使用复杂网络分析软件pajek对美国航空线路网络进行了实证研究,实证结果发现美国航空线路网络的度分布近似服从幂律分布,即度分布P(k)∞k-r,其中幂指数r=1-8,是一个无标度网络,另外整个网络的平均路径长度L≈2.74,很明显美国航空飞行线路网络具备小世界网络的特性。
在静态条件下,通过不同攻击模式(随机攻击和蓄意攻击)在美国航空线路网络、SW小世界网络和BA无标度网络上分别进行了抗毁性实验,结果发现,对于随机攻击,美国航空线路网络、BA无标度网络的抗毁性比SW小世界网络要强,在蓄意攻击模式下,SW小世界网络的抗毁性最强,美国航空线路网络和BA无标度网络的抗毁性区别不大,美国航空线路网络的抗毁性要差一些。
在动态条件下,本文提出了一种新的相继故障模型,节点i的初始负荷Li定义为Li=(BiKi)α,其中Bi代表节点的介数,Ki代表节点的度值,α表示可调参数。并美国航空线路网络、SW小世界网络和BA无标度网络上分别进行了相继故障的仿真研究,仿真结果表明SW小世界网络存在阈值αc,当a值小于阈值αc,网络不会发生相继故障,否则就会发生相继故障,而BA无标度网络和美国航空线路网络则不存在这样的阈值αc。SW小世界网络的抗毁性大于美国航空线路网络,美国航空线路网络的抗毁性大于BA无标度网络。另外一个重要发现为在现实当中的BA无标度网络中,虽说可以通过花费更多的成本来增加网络节点的抗毁性,但是a值较大时,再想通过增加λ值来大幅度的降低相继故障的规模不可能的。
Based on the complex networks theory, this thesis takes the US Air line network as the main research object, takes the robustness of complex networks as research target. With the two most common types of typical complex network model (SW small world network and BA scale-free network) for comparison, according to the static and dynamic conditions, we get the simulation results of different networks and analysis them.
With Complex network analysis software pajek, we carry on the empirical research of the US Air line network. The empirical results imply that the degree distribution of the US Air line network follows a power law, p(k)∝k-r, degree exponent r≈1.8. So it is a scale-free network. In addition, the Average path length of the US Air line network is2.74, obviously the US Air line network gets Small world network characteristics.
In the static condition, through the different attack modes (random perturbations and intentional attacks), we conduct the experiment for getting the robustness results of SW small world network, BA scale-free network and the US Air line network. The results show that under random perturbations, the robustness between BA scale-free network and the US Air line network is higher than SW small world network; under intentional attacks, the robustness of SW small world network is the highest, There is not much difference between BA scale-free network and the US Air line network, precisely speaking, the robustness of the US Air line network is smaller than BA scale-free network.
In the dynamic condition, we propose a new cascading failure model, Adopting the initial load of a node i to be Lj=(BjKj)α with Ki and Bi being the degree and the betweenness of the node i, respectively, where a is a tunable parameter and governs the strength of the initial load of a node. We conduct cascading failure simulation research on the US Air line network, SW small world network and BA scale-free network. The results show that SW small world network have a threshold value a,when parameter a is smaller than ac, cascading failure won't happen, otherwise, it happen. Threshold value α,don't exist between the US Air line network is smaller than BA scale-free network, the robustness of SW small world network is higher than the US Air line network, the robustness of the US Air line. network is higher than BA scale-free network. Another important discovery is that in BA scale-free network, although it is feasible through Spending more cost to increase the robustness, when a is more, that's impossible.
引文
[1]方锦清,汪小帆,郑志刚,毕桥,狄增如,李翔.一门崭新的交叉科学：网络科学(上)[J].物理学进展.2007,27(03)：239-343
[2]方锦清,汪小帆,郑志刚,李翔,狄增如,毕桥.一门崭新的交叉科学：网络科学(下篇)[J].物理学进展.2007,27(04)：361-444
[3]赵彦姜,虹羽,刘燕.南方冰雪灾害中输电电网破坏的原因及对策研究[J].防灾科技学院.2008,10(2)：32-34
[4]张土乔,康会宾,毛根海.城市给水管网可靠性分析初探[J].浙江大学学报(自然科学版).1998,32(03)：1-8
[5]潘勇.通信网可靠性指标研究[J].电子产品可靠性与环境试验.2006,24(01)：1-5
[6]刘宏鲲,周涛.中国城市航空网络的实证研究与分析[J].物理学报.2007,56(01)：106-113
[7]高自友,吴建军,毛保华等.交通运输网络复杂性及其相关问题的研究[J].交通运输工程与信息.2005,4(15)：79-84
[8]王新成.银行网络安全讲座(五)我国银行网络安全现状分析及改造[J].中国金融电脑.1999,(11)：51-54
[9]白宏.商业模式必须与商业网络相契合[J].企业管理.2010,(09)：99-101
[10]Albert R, Jeong H, Barabasi A-L. Error and attack tolerance of complex networks[J].Nature,2000,406:378-382
[11]Dunne J A, Williams R J, Martinez N D. Network structure and biodiversity loss in food webs:robustness increases with connectance[J].Ecology Letters.2002,5:558-567
[12]Jeong H, Mason S, Barabasi A-L, et al. Lethality and centrality in protein networks[J].Nature.2001,411:41-42
[13]Samanta K, Bhattacharya S. Proceedings of the Hawaii International Conference on System Sciences[C].IEEE Computer Society.2004
[14]Magoni D. Tearing down the internet [J].IEEE J. Sel. Areas Commun.2003, 21(6):949-960
[15]Newman M E J, Forrest S, Balthrop J. Email networks and the spread of computer viruses[J].Phys.Rev.E.2002,66(3):035101
[16]Holme P, Kim B J. Vertex overload breakdown in evolving networks[J].Phys. Rev. E, 2002,65:066109
[17]Buldyrev S V, Sergey V, et al. Catastrophic cascade of failures in interdependent networks[J].Natrue.2010,464:1025-1028
[18]汪小帆,李翔,陈关荣.复杂网络—理论与应用[M].北京：清华大学出版社,2006：93-123
[19]Moreno Y, Gomez J B, Pacheco A F. Instability of scale-free networks under node-breaking avalanches[J].Europhys. Lett.2002,58(4):630-636
[20]Motter A E, Nishikawa T, Lai Y C. Cascade-based attacks on complex networks. Phys. Rev.E.2002,66:065102(R)
[21]Carreras B A, Lynch V E, et al. Critical points and transitions in an electric power transmission model for cascading failure blackouts[J].Chaos.2002,12(4):985-994
[22]Holme P, Kim B J. Attack vulnerability of complex networks[J]. Phys. Rev.E. 2002,65(5):056109
[23]Moreno Y, Pastor-Satorras R, Vazquez A, Vespignani A. Critical load and congestion instabilities in scale-free networks[J].Europhys. Lett.2003,62(02):292-298
[24]Zhao L, Park K, Lai Y C. Attack vulnerability of scale-free networks due to cascading breakdown[J].Phys. Rev. E.2004,70(3):035101
[25]Crucitti P, Latora V, Marchiori M. Model for cascading failures in complex networks[J].Phys. Rev. E.2004,69(4):045104(R)
[26]Zhao L, Park K, Lai Y C, Ye N. Tolerance of scale-free networks against attack-induced cascades[J].Phys. Rev. E.2005,72:025104(R)
[27]Wang B, Kim B J. A high-robustness and low-cost model for cascading failures[J]. Europhys. Lett.2007,78:48001
[28]Zheng H F, Gao Z Y, Zhao X M. Modeling cascading failures in congested complex networks[J].Physica A.2007,385(2):700-706
[29]Wang W X, Chen G R. Universal robustness characteristic of weighted networks against cascading failure [J].Phys. Rev. E.2008,77:026101 (R)
[30]Wang J, Rong L, Zhang L, Zhang Z. Attack vulnerability of scale-free networks due to cascading failures [J].Physics A.2008,387:6671-6678
[31]Hu K, Hu T, Tang Y. Cascade Defense via Control of the Fluxes in Complex Networks[J].J. Stat. Phys.2010,141(3):555-565
[32]Erdos P, Renyi A. On the evolution of random graphs[M]. Publ. Math. Inst. Hung. Acad. Sci.1960,5:17-60
[33]Watts D J, Strogatz S. Collective dynamics of 'Small-World' networks[J].Nature.1998,393:440-442
[34]Barabasi A-L, Albert R. Emergence of scaling in random networks[J].Science.1999,286:509-512
[35]Newman M E J. The structure and function of complex networks[J].SIAM Review.2003,45(2):167-256
[36]Albert R, Barabasi A-L. Statistical mechanics of complex networks[J]. Rev. Mod. Phys.2002,74:47-97
[37]Boccaletti S, Latora V, et al. Complex networks:Structure and dynamics[J].Phys Rep.2006,424(4-5):175-308
[38]Girvan M, Newman M E J. Community structure in social and biological networks [J].Proc. Natl. Acad. Sci. USA.2002,99 (12):7821-7826
[39]Wang X F. Complex networks:Topology, dynamics and synchronization[J].Int. J. Bifurcation and Chaos.2002,21(5):885-916
[40]王建伟,荣莉莉,王铎.基于节点局域特征的复杂网络上相继故障模型[J].管理科学学报.2010,13(8)：42-49.
[41]杨阳,荣智海,李翔.复杂网络演化博弈理论研究综述[J].复杂系统与复杂性科学.2008,5(4)：47-55
[42]高自友,赵小梅,黄海军等.复杂网络理论与城市交通系统复杂性问题的相关研究[J].交通运输系统工程与信息.2006,,3(6)：41-47
[43]付宏睿,俞建宁,张建刚.复杂网络的混沌同步及一种新的保密通信系统[J].2011,35(5)：473-478
[44]许丹,李翔,汪小帆.复杂网络理论在互联网病毒传播研究中的应用[J].复杂系统与复杂性科学.2004,1(3)：10-26
[45]张成才,齐小刚.基于复杂网络理论的无线传感器网络特征度量分析[J].计算机科学.2010,37(11)：44-46,49
[46]余传明,周丹.情感词汇共现网络的复杂网络特性分析[J].情报学报.2010,29(5)：906-914
[47]Balthrop J, Forrest S, Newman M E J, Williamson M M. Technological networks and the spread of computer viruses[J].Science.2004,304:527-529
[48]Bollobas B. Random Graphs[M].2nd ed. New York:Academic Press,2001
[49]Fan J, Wang X F. A wavelet view of small-world networks[J].IEEE Trans. Circuits &Systems-II.2005,52(5):238-242
[50]谭跃进,吴俊,邓宏钟,朱大智.复杂网络抗毁性研究综述[J].系统工程.2006,24(10)：1-5
[2]方锦清,汪小帆,郑志刚,李翔,狄增如,毕桥.一门崭新的交叉科学：网络科学(下篇)[J].物理学进展.2007,27(04)：361-444
[3]赵彦姜,虹羽,刘燕.南方冰雪灾害中输电电网破坏的原因及对策研究[J].防灾科技学院.2008,10(2)：32-34
[4]张土乔,康会宾,毛根海.城市给水管网可靠性分析初探[J].浙江大学学报(自然科学版).1998,32(03)：1-8
[5]潘勇.通信网可靠性指标研究[J].电子产品可靠性与环境试验.2006,24(01)：1-5
[6]刘宏鲲,周涛.中国城市航空网络的实证研究与分析[J].物理学报.2007,56(01)：106-113
[7]高自友,吴建军,毛保华等.交通运输网络复杂性及其相关问题的研究[J].交通运输工程与信息.2005,4(15)：79-84
[8]王新成.银行网络安全讲座(五)我国银行网络安全现状分析及改造[J].中国金融电脑.1999,(11)：51-54
[9]白宏.商业模式必须与商业网络相契合[J].企业管理.2010,(09)：99-101
[10]Albert R, Jeong H, Barabasi A-L. Error and attack tolerance of complex networks[J].Nature,2000,406:378-382
[11]Dunne J A, Williams R J, Martinez N D. Network structure and biodiversity loss in food webs:robustness increases with connectance[J].Ecology Letters.2002,5:558-567
[12]Jeong H, Mason S, Barabasi A-L, et al. Lethality and centrality in protein networks[J].Nature.2001,411:41-42
[13]Samanta K, Bhattacharya S. Proceedings of the Hawaii International Conference on System Sciences[C].IEEE Computer Society.2004
[14]Magoni D. Tearing down the internet [J].IEEE J. Sel. Areas Commun.2003, 21(6):949-960
[15]Newman M E J, Forrest S, Balthrop J. Email networks and the spread of computer viruses[J].Phys.Rev.E.2002,66(3):035101
[16]Holme P, Kim B J. Vertex overload breakdown in evolving networks[J].Phys. Rev. E, 2002,65:066109
[17]Buldyrev S V, Sergey V, et al. Catastrophic cascade of failures in interdependent networks[J].Natrue.2010,464:1025-1028
[18]汪小帆,李翔,陈关荣.复杂网络—理论与应用[M].北京：清华大学出版社,2006：93-123
[19]Moreno Y, Gomez J B, Pacheco A F. Instability of scale-free networks under node-breaking avalanches[J].Europhys. Lett.2002,58(4):630-636
[20]Motter A E, Nishikawa T, Lai Y C. Cascade-based attacks on complex networks. Phys. Rev.E.2002,66:065102(R)
[21]Carreras B A, Lynch V E, et al. Critical points and transitions in an electric power transmission model for cascading failure blackouts[J].Chaos.2002,12(4):985-994
[22]Holme P, Kim B J. Attack vulnerability of complex networks[J]. Phys. Rev.E. 2002,65(5):056109
[23]Moreno Y, Pastor-Satorras R, Vazquez A, Vespignani A. Critical load and congestion instabilities in scale-free networks[J].Europhys. Lett.2003,62(02):292-298
[24]Zhao L, Park K, Lai Y C. Attack vulnerability of scale-free networks due to cascading breakdown[J].Phys. Rev. E.2004,70(3):035101
[25]Crucitti P, Latora V, Marchiori M. Model for cascading failures in complex networks[J].Phys. Rev. E.2004,69(4):045104(R)
[26]Zhao L, Park K, Lai Y C, Ye N. Tolerance of scale-free networks against attack-induced cascades[J].Phys. Rev. E.2005,72:025104(R)
[27]Wang B, Kim B J. A high-robustness and low-cost model for cascading failures[J]. Europhys. Lett.2007,78:48001
[28]Zheng H F, Gao Z Y, Zhao X M. Modeling cascading failures in congested complex networks[J].Physica A.2007,385(2):700-706
[29]Wang W X, Chen G R. Universal robustness characteristic of weighted networks against cascading failure [J].Phys. Rev. E.2008,77:026101 (R)
[30]Wang J, Rong L, Zhang L, Zhang Z. Attack vulnerability of scale-free networks due to cascading failures [J].Physics A.2008,387:6671-6678
[31]Hu K, Hu T, Tang Y. Cascade Defense via Control of the Fluxes in Complex Networks[J].J. Stat. Phys.2010,141(3):555-565
[32]Erdos P, Renyi A. On the evolution of random graphs[M]. Publ. Math. Inst. Hung. Acad. Sci.1960,5:17-60
[33]Watts D J, Strogatz S. Collective dynamics of 'Small-World' networks[J].Nature.1998,393:440-442
[34]Barabasi A-L, Albert R. Emergence of scaling in random networks[J].Science.1999,286:509-512
[35]Newman M E J. The structure and function of complex networks[J].SIAM Review.2003,45(2):167-256
[36]Albert R, Barabasi A-L. Statistical mechanics of complex networks[J]. Rev. Mod. Phys.2002,74:47-97
[37]Boccaletti S, Latora V, et al. Complex networks:Structure and dynamics[J].Phys Rep.2006,424(4-5):175-308
[38]Girvan M, Newman M E J. Community structure in social and biological networks [J].Proc. Natl. Acad. Sci. USA.2002,99 (12):7821-7826
[39]Wang X F. Complex networks:Topology, dynamics and synchronization[J].Int. J. Bifurcation and Chaos.2002,21(5):885-916
[40]王建伟,荣莉莉,王铎.基于节点局域特征的复杂网络上相继故障模型[J].管理科学学报.2010,13(8)：42-49.
[41]杨阳,荣智海,李翔.复杂网络演化博弈理论研究综述[J].复杂系统与复杂性科学.2008,5(4)：47-55
[42]高自友,赵小梅,黄海军等.复杂网络理论与城市交通系统复杂性问题的相关研究[J].交通运输系统工程与信息.2006,,3(6)：41-47
[43]付宏睿,俞建宁,张建刚.复杂网络的混沌同步及一种新的保密通信系统[J].2011,35(5)：473-478
[44]许丹,李翔,汪小帆.复杂网络理论在互联网病毒传播研究中的应用[J].复杂系统与复杂性科学.2004,1(3)：10-26
[45]张成才,齐小刚.基于复杂网络理论的无线传感器网络特征度量分析[J].计算机科学.2010,37(11)：44-46,49
[46]余传明,周丹.情感词汇共现网络的复杂网络特性分析[J].情报学报.2010,29(5)：906-914
[47]Balthrop J, Forrest S, Newman M E J, Williamson M M. Technological networks and the spread of computer viruses[J].Science.2004,304:527-529
[48]Bollobas B. Random Graphs[M].2nd ed. New York:Academic Press,2001
[49]Fan J, Wang X F. A wavelet view of small-world networks[J].IEEE Trans. Circuits &Systems-II.2005,52(5):238-242
[50]谭跃进,吴俊,邓宏钟,朱大智.复杂网络抗毁性研究综述[J].系统工程.2006,24(10)：1-5
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |