Please wait a minute...
Chin. Phys. B, 2011, Vol. 20(4): 048902    DOI: 10.1088/1674-1056/20/4/048902
INTERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY Prev   Next  

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
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 kmin-degree (minimum degree) nodes and the kmax-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 kmin-degree nodes is larger for larger λ and smaller kmin or kmax. The ratio of the kmax-degree ones is larger for smaller λ and kmax or larger kmin. 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 kmin-degree nodes has power-law decay with the increase of kmin. The ratio of the kmax-degree nodes has a power-law decay with the increase of kmax, 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.
Keywords:  scale-free networks      power-law distribution      Internet topology      average degree  
Received:  14 August 2010      Revised:  27 November 2010      Accepted manuscript online: 
PACS:  89.20.Hh (World Wide Web, Internet)  
  64.60.aq (Networks)  
  05.10.-a (Computational methods in statistical physics and nonlinear dynamics)  
Fund: 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).

Cite this article: 

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

[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
[1] Constructing refined null models for statistical analysis of signed networks
Ai-Wen Li(李艾纹), Jing Xiao(肖婧, and Xiao-Ke Xu(许小可). Chin. Phys. B, 2021, 30(3): 038901.
[2] Finite density scaling laws of condensation phase transition in zero-range processes on scale-free networks
Guifeng Su(苏桂锋), Xiaowen Li(李晓温), Xiaobing Zhang(张小兵), Yi Zhang(张一). Chin. Phys. B, 2020, 29(8): 088904.
[3] Multiple-predators-based capture process on complex networks
Rajput Ramiz Sharafat, Cunlai Pu(濮存来), Jie Li(李杰), Rongbin Chen(陈荣斌), Zhongqi Xu(许忠奇). Chin. Phys. B, 2017, 26(3): 038901.
[4] Multifractal modeling of the production of concentrated sugar syrup crystal
Sheng Bi(闭胜), Jianbo Gao(高剑波). Chin. Phys. B, 2016, 25(7): 070502.
[5] Deductive way of reasoning about the internet AS level topology
Dávid Szabó, Attila Kőrösi, József Bíró, András Gulyás. Chin. Phys. B, 2015, 24(11): 118901.
[6] Evolution of IPv6 Internet topology with unusual sudden changes
Ai Jun (艾均), Zhao Hai (赵海), Kathleen M. Carleyb, Su Zhan (苏湛), Li Hui (李辉). Chin. Phys. B, 2013, 22(7): 078902.
[7] Integrated systemic inflammatory response syndrome epidemic model in scale-free networks
Cai Shao-Hong(蔡绍洪), Zhang Da-Min(张达敏), Gong Guang-Wu(龚光武), and Guo Chang-Rui(郭长睿) . Chin. Phys. B, 2011, 20(9): 090503.
[8] Generalized minimum information path routing strategy on scale-free networks
Zhou Si-Yuan(周思源), Wang Kai(王开), Zhang Yi-Feng(张毅锋) Pei Wen-Jiang(裴文江) Pu Cun-Lai(濮存来), and Li Wei(李微) . Chin. Phys. B, 2011, 20(8): 080501.
[9] Poor–rich demarcation of Matthew effect on scale-free systems and its application
Yan Dong(闫栋), Dong Ming(董明), Abdelaziz Bouras, and Yu Sui-Ran(于随然) . Chin. Phys. B, 2011, 20(4): 040205.
[10] Mobile user forecast and power-law acceleration invariance of scale-free networks
Guo Jin-Li(郭进利), Guo Zhao-Hua(郭曌华), and Liu Xue-Jiao(刘雪娇) . Chin. Phys. B, 2011, 20(11): 118902.
[11] Adaptive local routing strategy on a scale-free network
Liu Feng(刘锋) Zhao Han(赵寒), Li Ming(李明), Ren Feng-Yuan(任丰原), and Zhu Yan-Bo(朱衍波). Chin. Phys. B, 2010, 19(4): 040513.
[12] S-curve networks and an approximate method for estimating degree distributions of complex networks
Guo Jin-Li(郭进利). Chin. Phys. B, 2010, 19(12): 120503.
[13] Convergence speed of consensus problems over undirected scale-free networks
Sun Wei(孙巍) and Dou Li-Hua(窦丽华). Chin. Phys. B, 2010, 19(12): 120513.
[14] Modelling the spread of sexually transmitted diseases on scale-free networks
Liu Mao-Xing(刘茂省) and Ruan Jiong(阮炯). Chin. Phys. B, 2009, 18(6): 2115-2120.
[15] Improving consensual performance of multi-agent systems in weighted scale-free networks
Qi Wei(祁伟), Xu Xin-Jian(许新建), and Wang Ying-Hai(汪映海). Chin. Phys. B, 2009, 18(10): 4217-4221.
No Suggested Reading articles found!