Evolution of the Internet AS-level topology:From nodes and edges to components

doi:10.1088/1674-1056/27/12/120501

中国物理B ›› 2018, Vol. 27 ›› Issue (12): 120501-120501.doi: 10.1088/1674-1056/27/12/120501

• SPECIAL TOPIC—Recent advances in thermoelectric materials and devices • 上一篇下一篇

Evolution of the Internet AS-level topology:From nodes and edges to components

Xiao Liu(刘晓), Jinfa Wang(王进法), Wei Jing(景薇), Menno de Jong, Jeroen S Tummers, Hai Zhao(赵海)

1 College of Computer Science and Engineering, Northeastern University, Shenyang 110000, China;
2 School of Biosciences, Durham University, Durham, DH1 3LE, UK;
3 School of Information Engineering, Shenyang University, Shenyang 110000, China

收稿日期:2018-06-22 修回日期:2018-09-20 出版日期:2018-12-05 发布日期:2018-12-05
通讯作者: Jinfa Wang E-mail:jinfa.wang@mervin.me
基金资助:
Project supported by the National Natural Science Foundation of China (Grant No. 61671142).

Evolution of the Internet AS-level topology:From nodes and edges to components

Xiao Liu(刘晓)^1,2, Jinfa Wang(王进法)², Wei Jing(景薇)³, Menno de Jong¹, Jeroen S Tummers¹, Hai Zhao(赵海)²

1 College of Computer Science and Engineering, Northeastern University, Shenyang 110000, China;
2 School of Biosciences, Durham University, Durham, DH1 3LE, UK;
3 School of Information Engineering, Shenyang University, Shenyang 110000, China

Received:2018-06-22 Revised:2018-09-20 Online:2018-12-05 Published:2018-12-05
Contact: Jinfa Wang E-mail:jinfa.wang@mervin.me
Supported by:
Project supported by the National Natural Science Foundation of China (Grant No. 61671142).

摘要/Abstract

摘要：

Studying the topology of infrastructure communication networks (e.g., the Internet) has become a means to understand and develop complex systems. Therefore, investigating the evolution of Internet network topology might elucidate disciplines governing the dynamic process of complex systems. It may also contribute to a more intelligent communication network framework based on its autonomous behavior. In this paper, the Internet Autonomous Systems (ASes) topology from 1998 to 2013 was studied by deconstructing and analysing topological entities on three different scales (i.e., nodes, edges and 3 network components:single-edge component M1, binary component M2 and triangle component M3). The results indicate that:a) 95% of the Internet edges are internal edges (as opposed to external and boundary edges); b) the Internet network consists mainly of internal components, particularly M2 internal components; c) in most cases, a node initially connects with multiple nodes to form an M2 component to take part in the network; d) the Internet network evolves to lower entropy. Furthermore, we find that, as a complex system, the evolution of the Internet exhibits a behavioral series, which is similar to the biological phenomena concerned with the study on metabolism and replication. To the best of our knowledge, this is the first study of the evolution of the Internet network through analysis of dynamic features of its nodes, edges and components, and therefore our study represents an innovative approach to the subject.

关键词: complex system, Internet AS-level topology, evolution, network component

Abstract:

Key words: complex system, Internet AS-level topology, evolution, network component

中图分类号: (Computational methods in statistical physics and nonlinear dynamics)

05.10.-a

05.90.+m (Other topics in statistical physics, thermodynamics, and nonlinear dynamical systems) 64.60.aq (Networks) 89.20.Hh (World Wide Web, Internet)

刘晓, 王进法, 景薇, Menno de Jong, Jeroen S Tummers, 赵海. Evolution of the Internet AS-level topology:From nodes and edges to components[J]. 中国物理B, 2018, 27(12): 120501-120501.

Xiao Liu(刘晓), Jinfa Wang(王进法), Wei Jing(景薇), Menno de Jong, Jeroen S Tummers, Hai Zhao(赵海). Evolution of the Internet AS-level topology:From nodes and edges to components[J]. Chin. Phys. B, 2018, 27(12): 120501-120501.

参考文献 39

[1]	Faloutsos M, Faloutsos P and Faloutsos C 1999 Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, August 30-September 3, 1999, Cambridge, Massachusetts, USA, p. 251
[2]	Alderson D, Li L, Willinger W and Doyle J C 2005 IEEE/ACM Transactions on networking 13 6
[3]	Barabási A L 2009 Science 325 5939
[4]	Barabási A L 2013 Phil. Trans. R. Soc. A 371 1987
[5]	Shen-Orr S S, Milo R, Mangan S and Alon U 2002 Nat. Genetics 31 1
[6]	Park, Kihong and Williger W 2005 The Internet As a Large-Scale Complex System. (Oxford: Oxford University Press) p. 3:1
[7]	Ma R T B, Lui J C S and Misra V 2015 IEEE/ACM Transactions on Networking 23 1 doi: 10.1109/TNET.2013.2292851
[8]	Zhou S and Mondragón R J 2005 Proceedings of the 8th ACM SIGCOMM conference on Internet measurement, March 29-April 1, 2005, Hong Kong, China, pp. 163-167
[9]	Guo H, Bu Y J, Lan J L and Liu L K 2011 J. Syst. Eng. 26 2
[10]	Eiben A E and Smith J E 2003 Introduction to evolutionary computing (Heidelberg: Springer)
[11]	Pastor-Satorras R and Vespignani A 2007 Evolution and structure of the Internet: A statistical physics approach (Cambridge: Cambridge University Press) pp. 226-228
[12]	Dhamdhere A and Dovrolis C 2008 Proceedings of the 8th ACM SIGCOMM conference on Internet measurement, October 2008, Vouliagmeni, Greece, pp. 183-196
[13]	Dhamdhere A and Dovrolis C 2011 IEEE/ACM Trans. Netw. 19 5
[14]	Pastor-Satorras R, Vázquez A and Vespignani A 2001 Phys. Rev. Lett. 87 25
[15]	Vázquez A, Pastor-Satorras R and Vespignani A 2002 Phys. Rev. E 65 6
[16]	Zhang G Q, Quoitin B and Zhou S 2011 Comput. Commun. 34 5
[17]	Ai J, Zhao H, Carley K M, Su Z and Li H 2013 Chin. Phys. B 22 078902 doi: 10.1088/1674-1056/22/7/078902
[18]	Moore C, Ghoshal G and Newman M E J 2006 Phys. Rev. E 74 3
[19]	Oliveira R V, Zhang B and Zhang L 2007 ACM SIGCOMM Comput. Commun. Rev. 37 4
[20]	Kuramochi M and Karypis G 2004 IEEE Transactions on Knowledge Data Engineering 16 9
[21]	Estrada E and Rodriguez-Velazquez J A 2005 Phys. Rev. E 71 5
[22]	Li F, Wei L, Zhao H and Hu F 2013 Discret. Dyn. Nat. Soc. 2013 5
[23]	Maslov S, Sneppen K and Zaliznyak A 2004 Physica A, Stat. Mech. Its Appl. 333 1 doi: 10.1016/j.physa.2003.10.046
[24]	Kiremire A R, Brust M R and Phoha V V 2014 Comput. Netw. 72 14 doi: 10.1016/j.comnet.2014.07.005
[25]	Mitchell J “Autonomous System (AS) Reservation for Private Use [EB/OL]” http://tools.ietf.org/html/rfc6996
[26]	Liu Z, Xiao Q, Zhan Q, Gu C and Yang H 2017 Physica A: Stat. Mech. Its Appl. 478 837
[27]	Leskovec J, Rajaraman A and Ullman J D 2014 Mining of massive datasets (Cambridge: Cambridge University Press) pp. 68-70
[28]	Lv C C, Si S B, Duan D L and Zhan R J 2017 Physica A: Stat. Mech. Appl. 471 837 doi: 10.1016/j.physa.2016.12.066
[29]	Heylighen F 2008 Encyclopedia of library and information sciences 3 1215
[30]	Wang J B, Wang L and Li X 2016 IEEE Trans. Cybern. 46 2782 doi: 10.1109/TCYB.2015.2489702
[31]	Wang L, Li X, Zhang Y Q, Zhang Y and Zhang K 2011 PloS ONE 6 e21197
[32]	Demetrius L and Manke T 2005 Physica A: Stat. Mech. Its Appl. 346 682 doi: 10.1016/j.physa.2004.07.011
[33]	Yan Y, Zhang S, Tang J and Wang X 2017 Physica A: Stat. Mech. Its Appl. 477 149 doi: 10.1016/j.physa.2017.02.040
[34]	McGraw-Hill 2004 Concise encyclopedia of chemistry (New York: McGraw-Hill Professional)
[35]	Sethna J 2006 Statistical mechanics: entropy, order parameters, and complexity (Oxford: Oxford University Press) p. 78
[36]	Ulanowicz R E 2012 Growth and development: ecosystems phenomenology (Berlin: Springer Sci. & Business Media) p. 21
[37]	Huxley J 1955 “Evolution and Genetics” in What Is Science? ed. Newman J R (New York, Simon and Schuster) p. 278
[38]	Mayr E 1970 Populations Species and Evolution (Harvard: Harvard University Press) p. 106
[39]	Ofek E, Eli and Richardson M 2003 The Journal of Finance 58 3

Evolution of the Internet AS-level topology:From nodes and edges to components

Evolution of the Internet AS-level topology:From nodes and edges to components

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献 39

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	Xian-Jia Wang(王先甲) and Lin-Lin Wang(王琳琳). Evolution of donations on scale-free networks during a COVID-19 breakout[J]. 中国物理B, 2022, 31(8): 80204-080204.
[2]	Guo-Shuai Fu(付国帅), Hong-Zhi Gao(高宏志), Guo-Wei Yang(杨国伟), Peng Yu(于鹏), and Pu Liu(刘璞). Laser fragmentation in liquid synthesis of novel palladium-sulfur compound nanoparticles as efficient electrocatalysts for hydrogen evolution reaction[J]. 中国物理B, 2022, 31(7): 77901-077901.
[3]	Lin-Feng Wang(王林锋), Yi Dong(董义), Min-Hao Hu(胡旻昊), Jing Tao(陶静), Jin Li(李进), and Zhen-Dong Dai(戴振东). Evolution of surfaces and mechanisms of contact electrification between metals and polymers[J]. 中国物理B, 2022, 31(6): 66202-066202.
[4]	Jinming Du(杜金铭). Voter model on adaptive networks[J]. 中国物理B, 2022, 31(5): 58902-058902.
[5]	Awen Liu(刘阿文), Hefei Huang(黄鹤飞), Jizhao Liu(刘继召), Zhenbo Zhu(朱振博), and Yan Li(李燕). Helium bubble formation and evolution in NiMo-Y₂O₃ alloy under He ion irradiation[J]. 中国物理B, 2022, 31(4): 46102-046102.
[6]	Hai-Jun Yu(余海军) and Hong-Yi Fan(范洪义). Time evolution law of a two-mode squeezed light field passing through twin diffusion channels[J]. 中国物理B, 2022, 31(2): 20301-020301.
[7]	Wei Xu(许伟), WenWu Xu(许文武), and Xiangmei Duan(段香梅). C₉N₄ as excellent dual electrocatalyst: A first principles study[J]. 中国物理B, 2021, 30(9): 96802-096802.
[8]	Ren-Jie Liu(刘仁杰), Jia-Jie Lin(林家杰), N Daghbouj, Jia-Liang Sun(孙嘉良), Tian-Gui You(游天桂), Peng Gao(高鹏), Nie-Feng Sun(孙聂枫), and Min Liao(廖敏). Mechanism of defect evolution in H⁺ and He⁺ implanted InP[J]. 中国物理B, 2021, 30(8): 86104-086104.
[9]	Xian-Wu Xiu(修显武), Wen-Cheng Zhang(张文程), Shu-Ting Hou(侯淑婷), Zhen Li(李振), Feng-Cai Lei(雷风采), Shi-Cai Xu(许士才), Chong-Hui Li(李崇辉), Bao-Yuan Man(满宝元), Jing Yu(郁菁), and Chao Zhang(张超). Role of graphene in improving catalytic behaviors of AuNPs/MoS₂/Gr/Ni-F structure in hydrogen evolution reaction[J]. 中国物理B, 2021, 30(8): 88801-088801.
[10]	Hefei Huang(黄鹤飞), Jizhao Liu(刘继召), Guanhong Lei(雷冠虹), Ondrej Muránsky, Tao Wei, and Mihail Ionescu. Effect of tellurium (Te⁴⁺) irradiation on microstructure and associated irradiation-induced hardening[J]. 中国物理B, 2021, 30(5): 56108-056108.
[11]	Zhe Wang(王喆) and Wenguang Zhu(朱文光). Metal substrates-induced phase transformation of monolayer transition metal dichalcogenides for hydrogen evolution catalysis[J]. 中国物理B, 2021, 30(11): 116401-116401.
[12]	Man Zhao(赵嫚), Mingxu Zhang(张明旭), Tao Wang(王韬), Jiangtao Zhao(赵江涛), Pan Dong(董攀), Zhen Yang(杨振), and Tieshan Wang(王铁山). Hydrogen isotopic replacement and microstructure evolution in zirconium deuteride implanted by 150 keV protons[J]. 中国物理B, 2021, 30(10): 106104-106104.
[13]	Bo Sun(孙博), Dong He(贺栋), Hongbo Wang(王宏博), Jiangchao Liu(刘江超), Zunjian Ke(柯尊健), Li Cheng(程莉), and Xiangheng Xiao(肖湘衡). Oxygen vacancies and V co-doped Co₃O₄ prepared by ion implantation boosts oxygen evolution catalysis[J]. 中国物理B, 2021, 30(10): 106102-106102.
[14]	梁成斌, 宋晏蓉, 董自凯, 吴云峰, 田金荣, 徐润亲. Pulse generation in Yb-doped polarization-maintaining fiber laser by nonlinear polarization evolution[J]. 中国物理B, 2020, 29(7): 74206-074206.
[15]	刘振, 贾维国, 王红玉, 汪洋, 门克内木乐, 张俊萍. Effect of dark soliton on the spectral evolution of bright soliton in a silicon-on-insulator waveguide[J]. 中国物理B, 2020, 29(6): 64212-064212.