Degree and connectivity of the Internet's scale-free topology

doi:10.1088/1674-1056/20/4/048902

中国物理B ›› 2011, Vol. 20 ›› Issue (4): 48902-048902.doi: 10.1088/1674-1056/20/4/048902

Degree and connectivity of the Internet's scale-free topology

余建平¹, 张连明², 伍祥生², 邓晓衡³

(1)College of Mathematics and Computer Science, Hunan Normal University, Changsha 410081, China; (2)College of Physics and Information Science, Hunan Normal University, Changsha 410081, China; (3)Institute of Information Science and Engineering, Central South University, Changsha 410083, China

收稿日期:2010-08-14 修回日期:2010-11-27 出版日期:2011-04-15 发布日期:2011-04-15
基金资助:
Project supported by the National Natural Science Foundation of China (Grant Nos. 60973129, 60903058 and 60903168), the Specialized Research Fund for the Doctoral Program of Higher Education (Grant No. 200805331109), the China Postdoctoral Science Foundation (Grant No. 200902324) and the Program for Excellent Talents in Hunan Normal University, China (Grant No. ET10902).

Degree and connectivity of the Internet's scale-free topology

Zhang Lian-Ming(张连明)^a)†, Deng Xiao-Heng(邓晓衡)^b), Yu Jian-Ping(余建平)^c), and Wu Xiang-Sheng(伍祥生)^a)

^a College of Physics and Information Science, Hunan Normal University, Changsha 410081, China; ^b Institute of Information Science and Engineering, Central South University, Changsha 410083, China; ^c College of Mathematics and Computer Science, Hunan Normal University, Changsha 410081, China

Received:2010-08-14 Revised:2010-11-27 Online:2011-04-15 Published:2011-04-15
Supported by:
Project supported by the National Natural Science Foundation of China (Grant Nos. 60973129, 60903058 and 60903168), the Specialized Research Fund for the Doctoral Program of Higher Education (Grant No. 200805331109), the China Postdoctoral Science Foundation (Grant No. 200902324) and the Program for Excellent Talents in Hunan Normal University, China (Grant No. ET10902).

摘要/Abstract

摘要： This paper theoretically and empirically studies the degree and connectivity of the Internet's scale-free topology at an autonomous system (AS) level. The basic features of scale-free networks influence the normalization constant of degree distribution p(k). It develops a new mathematic model for describing the power-law relationships of Internet topology. From this model we theoretically obtain formulas to calculate the average degree, the ratios of the k_min-degree (minimum degree) nodes and the k_max-degree (maximum degree) nodes, and the fraction of the degrees (or links) in the hands of the richer (top best-connected) nodes. It finds that the average degree is larger for a smaller power-law exponent λ and a larger minimum or maximum degree. The ratio of the k_min-degree nodes is larger for larger λ and smaller k_min or k_max. The ratio of the k_max-degree ones is larger for smaller λ and k_max or larger k_min. The richer nodes hold most of the total degrees of Internet AS-level topology. In addition, it is revealed that the increased rate of the average degree or the ratio of the k_min-degree nodes has power-law decay with the increase of k_min. The ratio of the k_max-degree nodes has a power-law decay with the increase of k_max, and the fraction of the degrees in the hands of the richer 27% nodes is about 73% (the '73/27 rule'). Finally, empirically calculations are made, based on the empirical data extracted from the Border Gateway Protocol, of the average degree, ratio and fraction using this method and other methods, and find that this method is rigorous and effective for Internet AS-level topology.

关键词: scale-free networks, power-law distribution, Internet topology, average degree

Abstract: This paper theoretically and empirically studies the degree and connectivity of the Internet's scale-free topology at an autonomous system (AS) level. The basic features of scale-free networks influence the normalization constant of degree distribution p(k). It develops a new mathematic model for describing the power-law relationships of Internet topology. From this model we theoretically obtain formulas to calculate the average degree, the ratios of the k_min-degree (minimum degree) nodes and the k_max-degree (maximum degree) nodes, and the fraction of the degrees (or links) in the hands of the richer (top best-connected) nodes. It finds that the average degree is larger for a smaller power-law exponent λ and a larger minimum or maximum degree. The ratio of the k_min-degree nodes is larger for larger λ and smaller k_min or k_max. The ratio of the k_max-degree ones is larger for smaller λ and k_max or larger k_min. The richer nodes hold most of the total degrees of Internet AS-level topology. In addition, it is revealed that the increased rate of the average degree or the ratio of the k_min-degree nodes has power-law decay with the increase of k_min. The ratio of the k_max-degree nodes has a power-law decay with the increase of k_max, and the fraction of the degrees in the hands of the richer 27% nodes is about 73% (the '73/27 rule'). Finally, empirically calculations are made, based on the empirical data extracted from the Border Gateway Protocol, of the average degree, ratio and fraction using this method and other methods, and find that this method is rigorous and effective for Internet AS-level topology.

Key words: scale-free networks, power-law distribution, Internet topology, average degree

中图分类号: (World Wide Web, Internet)

89.20.Hh

64.60.aq (Networks) 05.10.-a (Computational methods in statistical physics and nonlinear dynamics)

张连明, 邓晓衡, 余建平, 伍祥生. Degree and connectivity of the Internet's scale-free topology[J]. 中国物理B, 2011, 20(4): 48902-048902.

Zhang Lian-Ming(张连明), Deng Xiao-Heng(邓晓衡), Yu Jian-Ping(余建平), and Wu Xiang-Sheng(伍祥生) . Degree and connectivity of the Internet's scale-free topology[J]. Chin. Phys. B, 2011, 20(4): 48902-048902.

参考文献 49

[1]	Dorogovtsev S N, Goltsev A V and Mendes J F F 2008 Rev. Mod. Phys. 80 1275
[2]	Castellano C, Fortunato S and Loreto V 2009 Rev. Mod. Phys. 81 591
[3]	Faloutsos M, Faloutsos P and Faloutsos C 1999 SIGCOMM Comput. Commun. Rev. 29 251
[4]	Jaiswal S, Rosenberg A L and Towsley D 2004 Proceedings of the 12th IEEE International Conference on Network Protocols, Amherst, USA, October 5--8, 2004 p. 294
[5]	Zhou S and Mondragón R J 2004 IEEE Commun. Lett. 8 180
[6]	Newman M E J 2002 Phys. Rev. Lett. 89 208701
[7]	Song C, Havlin S and Makse H A 2005 Nature 433 392
[8]	Milo R, Shen-Orr S, Itzkovitz S, Kashtan N, Chklovskii D and Alon U 2002 Science 298 824
[9]	Watts D J and Strogatz S H 1998 Nature 393 440
[10]	Barabási A L and Albert R 1999 Science 286 509
[11]	Li X and Chen G R 2003 Physica A 328 274
[12]	Ravasz E, Somera A L, Mongru D A, Oltvai Z N and Barabási A L 2002 Science 297 1551
[13]	Liu H, Lu J A, Lü J and Hill D J 2009 Automatica 45 1799
[14]	Lü J and Chen G 2005 IEEE T. Automat. Control 50 841
[15]	Zhou J, Lu J A and Lü J 2006 IEEE T. Automat. Control 51 652
[16]	Lü J, Yu X and Chen G 2004 Physica A 334 281
[17]	Li X, Wang X and Chen G 2004 IEEE T. Circuits-I 51 2074
[18]	Li Y and Liu Z R 2010 Chin. Phys. B 19 110501
[19]	Pastor-Satorras R and Vespignani A 2001 Phys. Rev. Lett. 86 3200
[20]	Moreno Y, Gómez J B and Pacheco A F 2002 Europhys. Lett. 58 630
[21]	Watts D J, Dodds P S and Newman M E J 2002 Science 296 1302
[22]	Adamic L A, Lukose R M, Puniyani A R and Huberman B A 2001 Phys. Rev. E 64 046135
[23]	Krioukov D, Papadopoulos F, Boguna M and Vahdat A 2009 ACM SIGMETRICS Performance Evaluation Review 37 15
[24]	Zhang G Q, Zhang G Q, Yang Q F, Cheng S Q and Zhou T 2008 New J. Phys. 10 123027
[25]	Cohen R and Havlin S 2003 Phys. Rev. Lett. 90 058701
[26]	Mahadevan P, Krioukov D, Fomenkov M, Huffaker B, Dimitropoulos X, Claffy K and Vahdat A 2006 SIGCOMM Comput. Commun. Rev. 36 17
[27]	Albert R and Barabási A L 2000 Phys. Rev. Lett. 85 5234
[28]	Bu T and Towsley D 2002 Proceedings of INFOCOM, New York, USA, June 23--27, 2002 p. 638
[29]	Zhou S and Mondragón R J 2004 Phys. Rev. E 70 066108
[30]	Park S T, Pennock D M and Giles C L 2004 Proceedings of INFOCOM, Hong Kong, China, March 7--11, 2004 p. 1616
[31]	Bar S, Gonen M and Wool A 2004 LNCS 3015 53
[32]	Chen G, Fan Z P and Li X 2005 Complex Dynamics in Communication Networks (Berlin: Springer-Verlag) p. 213
[33]	Winick J, Jin C, Chen Q and Jamin S http://topology.eecs.umich.edu/inet/[2010-08-10]
[34]	Medina A, Lakhina A, Matta I and Byers J 2001 Proceedings of the MASCOTS, Cincinnati, USA, August 15--18, 2001 p. 346
[35]	Porekar J http://www-f1.ijs.si/sim rudi/sola/Random_-Networks.pdf [2010-8-14]
[36]	Wang J W and Rong L L 2009 Physica A 388 1289
[37]	Pastor-Satorras R and Vespignani A 2002 Phys. Rev. E 65 035108R
[38]	Santiago A and Benito R M 2008 Physica A 387 2365
[39]	Newman M E J 2005 Contemp. Phys. 46 323
[40]	Cohen R, Erez K, Ben-Avraham D and Havlin S 2000 Phys. Rev. Lett. 85 4626
[41]	Clauset A, Rohilla Shalizi C and Newman M E J 2009 SIAM Rev. 51 661
[42]	Goldstein M L, Morris S A and Yen G G 2004 Euro. Phys. J. B 41 255
[43]	Xu H L, Deng X H and Zhang L M 2010 Computer Engineering and Applications 46 77 (in Chinese)
[44]	Xiao W J, Peng L M and Parhami B 2009 LNICST 4 118
[45]	Arenas A, Cabrales A, Diaz-Guilera A, Guimera R and Vega-Redondo F 2002 Proceedings of 18th Sitges Conference on Statistical Mechanics: Statistical Mechanics of Complex Networks, Sitges, Spain, June 10--14, 2002 p. 175
[46]	Zhang G Q, Wang D and Li G J 2007 Phys. Rev. E 76 017101
[47]	Bogu ná M, Krioukov D and Claffy K 2009 Nature Phys. 5 74
[48]	Zhang L M 2010 Computer Engineering and Applications 46 4 (in Chinese)
[49]	Tsaparas P http://www.cs.helsinki.fi/u/tsaparas/MACN2006/data-code.html [2010-8-14] endfootnotesize

Degree and connectivity of the Internet's scale-free topology

Degree and connectivity of the Internet's scale-free topology

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献 49

相关文章 14

Metrics

本文评价

推荐阅读 0

[1]	苏桂锋, 李晓温, 张小兵, 张一. Finite density scaling laws of condensation phase transition in zero-range processes on scale-free networks[J]. 中国物理B, 2020, 29(8): 88904-088904.
[2]	濮存来, 李杰, 陈荣斌, 许忠奇. Multiple-predators-based capture process on complex networks[J]. 中国物理B, 2017, 26(3): 38901-038901.
[3]	闭胜, 高剑波. Multifractal modeling of the production of concentrated sugar syrup crystal[J]. 中国物理B, 2016, 25(7): 70502-070502.
[4]	Dávid Szabó, Attila Kőrösi, József Bíró, András Gulyás. Deductive way of reasoning about the internet AS level topology[J]. 中国物理B, 2015, 24(11): 118901-118901.
[5]	艾均, 赵海, Kathleen M. Carleyb, 苏湛, 李辉. Evolution of IPv6 Internet topology with unusual sudden changes[J]. 中国物理B, 2013, 22(7): 78902-078902.
[6]	蔡绍洪, 张达敏, 龚光武, 郭长睿. Integrated systemic inflammatory response syndrome epidemic model in scale-free networks[J]. 中国物理B, 2011, 20(9): 90503-090503.
[7]	周思源, 王开, 张毅锋, 裴文江, 濮存来, 李微. Generalized minimum information path routing strategy on scale-free networks[J]. 中国物理B, 2011, 20(8): 80501-080501.
[8]	闫栋, 董明, Abdelaziz Bouras, 于随然. Poor–rich demarcation of Matthew effect on scale-free systems and its application[J]. 中国物理B, 2011, 20(4): 40205-040205.
[9]	郭进利, 郭曌华, 刘雪娇. Mobile user forecast and power-law acceleration invariance of scale-free networks[J]. 中国物理B, 2011, 20(11): 118902-118902.
[10]	刘锋, 赵寒, 李明, 任丰原, 朱衍波. Adaptive local routing strategy on a scale-free network[J]. 中国物理B, 2010, 19(4): 40513-040513.
[11]	郭进利. S-curve networks and an approximate method for estimating degree distributions of complex networks[J]. 中国物理B, 2010, 19(12): 120503-120503.
[12]	孙巍, 窦丽华. Convergence speed of consensus problems over undirected scale-free networks[J]. 中国物理B, 2010, 19(12): 120513-120513.
[13]	祁伟, 许新建, 汪映海. Improving consensual performance of multi-agent systems in weighted scale-free networks[J]. 中国物理B, 2009, 18(10): 4217-4221.
[14]	吴俊, 谭跃进, 邓宏钟, 朱大智. Normalized entropy of rank distribution: a novel measure of heterogeneity of complex networks[J]. 中国物理B, 2007, 16(6): 1576-1580.