Deterministic scale-free small-world networks of arbitrary order. (English) Zbl 1395.05161
Summary: In many real-life networks, both the scale-free distribution of degree and small-world behavior are important features. There are many random or deterministic models of networks to simulate these features separately. However, there are few models that combine the scale-free effect and small-world behavior, especially in terms of deterministic versions. What is more, all the existing deterministic algorithms running in the iterative mode generate networks with only several discrete numbers of nodes. This contradicts the purpose of creating a deterministic network model on which we can simulate some dynamical processes as widely as possible. According to these facts, this paper proposes a deterministic network generation algorithm, which can not only generate deterministic networks following a scale-free distribution of degree and small-world behavior, but also produce networks with arbitrary number of nodes. Our scheme is based on a complete binary tree, and each newly generated leaf node is further linked to its full brother and one of its direct ancestors. Analytical computation and simulation results show that the average degree of such a proposed network is less than 5, the average clustering coefficient is high (larger than 0.5, even for a network of size 2 million) and the average shortest path length increases much more slowly than logarithmic growth for the majority of small-world network models.
MSC:
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 90B10 | Deterministic network models in operations research |
References:
| [1] | Watts, D. J.; Strogatz, S. H., Collective dynamics of ‘small-world’ networks, Nature, 393, 440, (1998) · Zbl 1368.05139 |
| [2] | Newman, M. E.J.; Watts, D. J., Renormalization group analysis of the small-world network model, Phys. Lett. A, 263, 341-346, (1999) · Zbl 0940.82029 |
| [3] | Barabási, A. L.; Albert, R., Emergence of scaling in random networks, Science, 286, 509, (1999) · Zbl 1226.05223 |
| [4] | Barabási, A. L.; Ravasz, E.; Vicsek, T., Deterministic scale-free networks, Physica A, 299, 559-564, (2001) · Zbl 0972.57003 |
| [5] | Zhang, Z. Z.; Rong, L. L.; Guo, C. H., A deterministic small-world network created by edge iterations, Physica A, 363, 567-572, (2006) |
| [6] | Xiao, W. J.; Parhami, B., Cayley graphs as models of deterministic small-world networks, Inform. Process. Lett., 97, 115-117, (2006) · Zbl 1184.68060 |
| [7] | Klemm, K.; Eguíluz, V. M., Growing scale-free networks with small-world behavior, Phys. Rev. E, 65, 057102, (2002) |
| [8] | F. Comellas, G. Fertin, A. Raspaud, Recursive graphs with small-world scale-free properties, 2004. arXiv:cond-mat/0402033v2. |
| [9] | Guan, J. H.; Wu, Y. W.; Zhang, Z. Z.; Zhou, S. G.; Wu, Y. H., A unified model for sierpinski networks with scale-free scaling and small-world effect, Physica A, 388, 2571-2578, (2009) |
| [10] | Lu, Z. M.; Guo, S. Z., A small-world network derived from the deterministic uniform recursive tree, Physica A, 391, 87-92, (2012) |
| [11] | Zhang, Z. Z.; Zhou, S. G.; Xie, W. L.; Chen, L. C.; Lin, Y.; Guan, J. H., Standard random walks and trapping on the Koch network with scale-free behavior and small-world effect, Phys. Rev. E, 79, 061113, (2009) |
| [12] | Newman, M. E.J., The structure and function of complex networks, SIAM Rev., 45, 2, 167-256, (2003) · Zbl 1029.68010 |
| [13] | Noh, J. D.; Rieger, H., Random walks on complex networks, Phys. Rev. Lett., 92, 11, (2004) |
| [14] | Baronchelli, A.; Catanzaro, M.; Satorras, R. P., Random walks on complex trees, Phys. Rev. E, 78, 011114, (2008) |
| [15] | Zhang, Z. G.; Xu, X. J.; Wu, Z. X.; Wang, Y. H., Walks on Apollonian networks, Eur. Phys. J. B, 51, 549-553, (2006) |
| [16] | Jespersen, S.; Sokolov, I. M.; Blumen, A., Relaxation properties of small-world networks, Phys. Rev. E, 62, 3, (2000) |
| [17] | Bollt, E. M.; Avraham, D. B., What is special about diffusion on scale-free nets, New J. Phys., 7, 26, (2005) |
| [18] | Zhang, Z. Z.; Julaiti, A.; Hou, B. Y.; Zhang, H. J.; Chen, G. R., Mean first-passage time for random walks on undirected networks, Eur. Phys. J. B, 84, 691-697, (2011) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
