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

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

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.

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!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

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

Cite this article:

Online attention