Random evolving networks under the diameter and average connectivity constraint

Abstract

In this paper, under the constraint that the average distance and the average degree 〈k〉 remain approximately constant, we studied a random scale-free network model. We found that, if the network maintains the form of its degree distribution and the maximal degree k _c is N-dependent cutoff function k _c(N) < N, the degree distribution would be approximately power-law with an exponent between 2 and 3. The distribution exponent has little relationship with the average degree, denoted by 〈k〉. The diameter constraint can be interpreted as an environmental selection pressure, which could explain the scale-free nature of networks. The numerical results indicate that, under the diameter constraint, the preferential attachment can produce the cutoff function k _c(N) < N and power-law degree distribution.

Keywords

Scale-free networks / diameter / average connectivity

References

[1] Albert R., Barabasi A. L.. Statistical mechanics of complex networks. Reviews of Modern Physics, 2002, 74: 47-97.

[2] Faloutsos M., Faloutsos P., Faloutsos C.. On power-law relationships of the internet topology. ACM SIGCOMM Computer Communication Review, 1999, 29(4): 251-262.

[3] Jeong H., Albert R., Barabasi A.L.. Diameter of the world-wide web. Nature, 1999, 401: 130-131.

[4] Mendes J.F.F., Dorogovtsev S. N., Ioffe A.F.. Evolution of Networks: From Biological Nets to the Internet and the WWW, 2003, Oxford: Oxford University Press.

[5] Newman M.E.J.. The structure and function of complex networks. SIAM Review, 2003, 45: 167-256.

[6] Pastor-Satorras R., Vespignani A.. Evolution and Structure of the Internet: A Statistical Physics Approach, 2004, Cambridge: Cambridge University Press

[7] Wang X.F.. Complex networks: Topology, dynamics and synchronization. International Journal of Bifurcation and Chaos, 2002, 12: 885-916.