DEGREE SEQUENCES BEYOND POWER LAWS IN COMPLEX NETWORKS

Zhanying Zhang; Wenjun Xiao; Guanrong Chen

doi:10.11948/2016072

2016 Volume 6 Issue 4

Article Contents

Article navigation > Journal of Applied Analysis & Computation > 2016 > 6(4): 1105-1113

Next Article Previous Article

Zhanying Zhang, Wenjun Xiao, Guanrong Chen. DEGREE SEQUENCES BEYOND POWER LAWS IN COMPLEX NETWORKS[J]. Journal of Applied Analysis & Computation, 2016, 6(4): 1105-1113. doi: 10.11948/2016072

Citation:

Zhanying Zhang, Wenjun Xiao, Guanrong Chen. DEGREE SEQUENCES BEYOND POWER LAWS IN COMPLEX NETWORKS[J]. Journal of Applied Analysis & Computation, 2016, 6(4): 1105-1113. doi: 10.11948/2016072

DEGREE SEQUENCES BEYOND POWER LAWS IN COMPLEX NETWORKS

1 School of Computer Science and Engineering South China University of Technology, Guangzhou 510006, China;
2 School of Software Engineering South China University of Technology, Guangzhou 510006, China;
3 Department of Electronic Engineering City University of Hong Kong, Kowloon, Hong Kong SAR, China

Fund Project:

Abstract

Abstract

Many complex networks possess vertex-degree distributions in a power-law form of ck^-γ, where k is the degree variable and c and γ are constants. To better understand the mechanism of power-law formation in realworld networks, it is effective to analyze their degree variable sequences. We had shown before that, for a scale-free network of size N,if its vertex-degree sequence is k₁ < k₂ <…< k_l, where {k₁, k₂,…, k_l} is the set of all unequal vertex degrees in the network, and if its power exponent satisfies γ>1, then the length l of the vertex-degree sequence is of order logN. In the present paper, we further study complex networks with more general distributions and prove that the same conclusion holds even for non-network type of complex systems. In addition, we support the conclusion by verifying many real-world network and system examples. We finally discuss some potential applications of the new finding in various fields of science, technology and society.
- Network /
- degree variable sequence /
- power-law distribution /
- general distribution
MSC: 05C82;05C07

FullText(HTML)

References

[1]	R. Albert and A.-L.Barabsi, Statistical mechanics of complex networks, Rev. Mod. Phys., 74(2002)(1), 47-91. Google Scholar
[2]	A.-L. Barabsi and R. Albert, Emergence of scaling in random networks, Science, 286(1999), 509-512. Google Scholar
[3]	R. F. I. Cancho and R. V. Sole, The small world of human language, Proceedings:Biological Sciences, 268(2001)(1482), 2261-2265. Google Scholar
[4]	A. Clauset, C. R. Shalizi and M. E. J. Newman, Power-law distributions in empirical data, SIAM Review, 51(2009)(4), 661C-703. Google Scholar
[5]	F. Comellas, G. Fertin and A. Raspaud, Recursive graphs with small-world scale-free properties, Phys. Rev. E, 69(2004)(3), 037104. Google Scholar
[6]	H. Ebel, L. I. Mielsch and S. Bornholdt, Scale-free topology of e-mail networks, Phys. Rev. E, 66(2002)(3), 1-4. Google Scholar
[7]	R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, 1985. Google Scholar
[8]	M. A. Jovanovic, F. S. Annexstein and K. A. Berman, Scalability Issues in Large Peer-to-peer Networks-A Case Study of Gnutella, Tech. Rep., University of Cincinnati, 2001. Google Scholar
[9]	M. Newman, Scientific collaboration networks.I.Network construction and fundamental results, Phys. Rev. E, 64(2001)(1), 2001, 016131. Google Scholar
[10]	M. Newman, The structure and function of complex networks, SIAM Rev., 45(2003)(2), 167-256. Google Scholar
[11]	M. Newman, Scientific collaboration networks. Ⅱ. Shortest paths, weighted networks, and centrality, Phys. Rev. E, 64(2001)(1), 016132. Google Scholar
[12]	M. Newman, S. Strogatz and D. Watts, Random graphs with arbitrary degree distributions and their applications, Phys. Rev. E, 64(2001)(2), 026118. Google Scholar
[13]	R. Pastor-Satorras and A. Vespignani, Epidemic spreading in scale-free networks, Phys. Rev. Lett., 86(2001)(14), 3200-3203. Google Scholar
[14]	S. H. Strogatz, Exploring complex networks, Nature, 410(2001), 268-276. Google Scholar
[15]	D. J. Watts and S. H. Strogatz, Collective dynamics of small-world networks, Nature, 393(1998), 440-442. Google Scholar
[16]	W. J. Xiao, Y. Liu and G. R. Chen, Characterizingvertex-degree sequences in scale-free networks, Physica A, 404(2014), 291-295. Google Scholar
[17]	W. J. Xiao, W. D. Chen and B. Parhami, On necessary conditions for scalefreedom in complex networks,with applications to computer communication systems, Int. J. of Systems Science, 42(2011)(6), 951-958. Google Scholar
[18]	W. J. Xiao, S. Z. Jiang and G. R. Chen, A small-world model of scale-free networks:Features and verifications, Applied Mechanics and Materials, 50-51(2011), 166-170. Google Scholar
[19]	V. M. Yakovenko and J. B. Rosser, Colloquium:Statistical mechanics of money, wealth, and income, Reviews of Modern Physics, 2009, arXiv:0905.1518. Google Scholar