A new class of the planar networks with high clustering and high entropy. (English) Zbl 1470.05152

Summary: Small-world networks are ubiquitous in real-life systems, such as the World Wide Web, communication networks, and electric power grids, and most of them are stochastic. In this paper, we present a model that generates a small-world network in a simple deterministic way and analyze the relevant topological properties of the model, such as the degree distribution, clustering coefficient, and diameter. Meanwhile, according to the special structure of the model, we derive analytically the exact numbers of spanning trees in the planar networks. The results show that the model has a discrete exponential degree distribution, high clustering coefficient, short diameter, and high entropy.


05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C80 Random graphs (graph-theoretic aspects)
Full Text: DOI


[1] Albert, R.; Barabási, A. L., Statistical mechanics of complex networks, Reviews of Modern Physics, 74, 1, 47-97 (2002) · Zbl 1205.82086
[2] Dorogovtsev, S. N.; Mendes, J. F. F., Evolution of networks, Advances in Physics, 51, 4, 1079-1187 (2002)
[3] Newman, M. E. J., The structure and function of complex networks, SIAM Review, 45, 2, 167-256 (2003) · Zbl 1029.68010
[4] Boccaletti, S.; Latora, V.; Moreno, Y.; Chavez, M.; Hwang, D.-U., Complex networks: structure and dynamics, Physics Reports, 424, 4-5, 175-308 (2006) · Zbl 1371.82002
[5] Zhang, Z.; Lin, Y.; Gao, S.; Zhou, S.; Guan, J., Average distance in a hierarchical scale-free network: an exact solution, Journal of Statistical Mechanics, 2009, 10 (2009)
[6] Zhang, Z. Z.; Zhou, S. G.; Fang, J. Q., Recent progess of deterministic models of complex networks, Complex Systems and Complexity Science (2008)
[7] Dorogovtsev, S. N.; Mendes, J. F. F., Scalling behavior of developing and decaying networks, Europhysics Letters, 52, 1 (2000)
[8] Kleinberg, J. M., Navigation in a small world, Nature, 406, 6798, 845 (2000)
[9] Ozik, J.; Hunt, B. R.; Ott, E., Growing networks with geographical attachment preference: emergence of small worlds, Physical Review E, 69, 2, 026108-5 (2004)
[10] Barabási, A.-L.; Ravasz, E.; Vicsek, T., Deterministic scale-free networks, Physica A, 299, 3-4, 559-564 (2001) · Zbl 0972.57003
[11] Watts, D. J.; Strogatz, S. H., Collective dynamics of small world network, Nature, 393, 6684, 440-442 (1998) · Zbl 1368.05139
[12] Zhang, Z.; Rong, L.; Guo, C., A deterministic small-world network created by edge iterations, Physica A, 363, 2, 567-572 (2006)
[13] Newman, M. E. J.; Watts, D. J., Renormalization group analysis of the small-world network model, Physics Letters A, 263, 4-6, 341-346 (1999) · Zbl 0940.82029
[14] Newman, M. E. J.; Watts, D. J., Scaling and percolation in the small-world network model, Physical Review E, 60, 6, 7332-7342 (1999)
[15] Kasturirangan, R., Multiple Scales in Small-World Graphs, AI Lab Memo. 1663 (1999), Massachusetts Institute of Technology
[16] Erdös, P.; Rényi, A. R., On random graphs I, Publicationes Mathematicae, 6, 290-297 (1959) · Zbl 0092.15705
[17] Erdös, P.; Rényi, A. R., On the evolution of random graphs, Publication of the Mathematical Institute of the Hungarian Academy of Sciences, 5, 17-61 (1960) · Zbl 0103.16301
[18] Xiao, Y. Z.; Zhao, H. X., New method for counting the numberof spanning trees in a two-tree network, Physica A, 392, 4576-4583 (2013) · Zbl 1395.05174
[19] Lu, Z.-M.; Guo, S.-Z., A small-world network derived from the deterministic uniform recursive tree, Physica A, 391, 1-2, 87-92 (2012)
[20] Burton, R.; Pemantle, R., Local characteristics, entropyand limit theorems for spanning trees and domino tilingsvia transfer-impedances, Annals of Probability, 21, 1329 (1993) · Zbl 0785.60007
[21] Lyons, R., Asymptotic enumeration of spanning trees, Combinatorics Probability and Computing, 14, 4, 491-522 (2005) · Zbl 1076.05007
[22] Zhang, Z. Z.; Liu, H. X.; Wu, B.; Zhou, S. G., Enumeration of spanning trees in a pseudofractal scale-free web, Europhysics Letters, 90, 6 (2010)
[23] Wu, F. Y., Number of spanning trees on a lattice, Journal of Physics A, 10, 6, article 4, L113-L115 (1977)
[24] Chang, S.-C.; Chen, L.-C.; Yang, W.-S., Spanning trees on the Sierpinski gasket, Journal of Statistical Physics, 126, 3, 649-667 (2007) · Zbl 1110.82007
[25] Zhang, Z.; Liu, H.; Wu, B.; Zou, T., Spanning trees in a fractal scale-free lattice, Physical Review E, 83, 1 (2011)
[26] Lin, Y.; Wu, B.; Zhang, Z.; Chen, G., Counting spanning trees in self-similar networks by evaluating determinants, Journal of Mathematical Physics, 52, 11 (2011) · Zbl 1272.05187
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.