A Small-World Model of Scale-Free Networks: Features and Verifications

Abstract:

It is now well known that many large-sized complex networks obey a scale-free power-law vertex-degree distribution. Here, we show that when the vertex degrees of a large-sized network follow a scale-free power-law distribution with exponent  2, the number of degree-1 vertices, if nonzero, is of order N and the average degree is of order lower than log N, where N is the size of the network. Furthermore, we show that the number of degree-1 vertices is divisible by the least common multiple of , , . . ., , and l is less than log N, where l = < is the vertex-degree sequence of the network. The method we developed here relies only on a static condition, which can be easily verified, and we have verified it by a large number of real complex networks.

• Periodical: Applied Mechanics and Materials (Volumes 50-51)
• Pages: 166-170
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.50-51.166
• Online since: February 2011
• Authors: Wen Jun Xiao, Shi Zhong Jiang, Guan Rong Chen
• Keywords: Complex Network, Computer Network, Scale-Free Network, Small-World Network, Software Network

References

[1] Barabási, A. -L., Albert, R: Emergence of scaling in random networks, Science, vol. 286(1999), pp.509-512.

[2] Watts, D. J., Strogatz, S. H: Collective dynamics of small-world' networks, Nature, vol. 393(1998) , pp.440-442.

DOI: 10.1038/30918

[3] Albert, R., Barabási, A. -L: Statistical mechanics of complex networks, Rev. Mod. Phys., vol. 74(2002), pp.47-97.

DOI: 10.1103/revmodphys.74.47

[4] Newman, M. E. J: The structure and function of complex networks, SIAM Rev., vol. 45(2003), pp.167-256.

[5] Xiao, W. J., Parhami, B: Cayley graphs as models of deterministic small-world networks, Information Processing Letters, vol. 97(2006), pp.115-117.

DOI: 10.1016/j.ipl.2005.10.001

[6] Biggs, N: Algebraic Graph Theory (Cambridge University Press, 1993).

[7] Newman, M. E. J: Scientific collaboration networks, I: Network construction and fundamental results, Phys. Rev. E, vol. 64(2001), 016131.

[8] Myers, C. R: Software systems as complex networks: Structure, function and evolvability of software collaboration graphs, Phys. Rev. E, vol. 68(2003), 046116.

DOI: 10.1103/physreve.68.046116

[9] Adamic, L. A, et al: Search in power-law networks, Phys. Rev. E, vol. 64(2001), 046135. Appendix Data of 7 complex networks used in this paper Network N M l log N n1 n4 kl nl.

[1] Xmms 971 1802.

[28] 9. 923 300.

[95] [36] [1] [2] abiword 1035 1719.

[29] 10. 015 447.

[64] [89] [1] [3] mysql2 1480 4190.

[43] 10. 531 258 140 220.

[1] [4] Linux 5285 11352.

[51] 12. 368 1200 615 1058.

[1] [5] ncstrlwg2 6396 15872.

[42] 12. 643 894 741.

[79] [1] [6] 2004Internet 18408 33963 121 14. 168 6505 667 2303.

[1] [7] 2009Internet 31164 63226 172 14. 928 11325 1299 2283 1.