×

The evaluation of the number and the entropy of spanning trees on generalized small-world networks. (English) Zbl 1437.05048

Summary: Spanning trees have been widely investigated in many aspects of mathematics: theoretical computer science, combinatorics, so on. An important issue is to compute the number of these spanning trees. This number remains a challenge, particularly for large and complex networks. As a model of complex networks, we study two families of generalized small-world networks, namely, the Small-World Exponential and the Koch networks, by changing the size and the dimension of the cyclic subgraphs. We introduce their construction and their structural properties which are built in an iterative way. We propose a decomposition method for counting their number of spanning trees and we obtain the exact formulas, which are then verified by numerical simulations. From this number, we find their spanning tree entropy, which is lower than that of the other networks having the same average degree. This entropy allows quantifying the robustness of the networks and characterizing their structures.

MSC:

05C05 Trees
05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C30 Enumeration in graph theory
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Wang, X. F.; Chen, G., Complex networks: small-world, scale-free and beyond, IEEE Circuits and Systems Magazine, 3, 1, 6-20 (2003)
[2] Mowshowitz, A.; Dehmer, M., Entropy and the complexity of graphs revisited, Entropy. An International and Interdisciplinary Journal of Entropy and Information Studies, 14, 3, 559-570 (2012) · Zbl 1331.94041
[3] Colbourn, C. J., The combinatorics of network reliability (1987), Oxford University Press
[4] Chaiken, S.; Kleitman, D. J., Matrix tree theorems, Journal of Combinatorial Theory, Series A, 24, 3, 377-381 (1978) · Zbl 0376.05032
[5] Modabish, A.; Lotfi, D.; El Marraki, M., The number of spanning trees of planar maps: theory and applications, Proceedings of the 2011 International Conference on Multimedia Computing and Systems (ICMCS), IEEE · Zbl 1247.05059
[6] Dehmer, M.; Emmert-Streib, F.; Chen, Z.; Li, X.; Shi, Y., Mathematical foundations and applications of graph entropy, 6 (2017), John Wiley & Sons · Zbl 1406.92001
[7] Demetrius, L.; Manke, T., Robustness and network evolution - An entropic principle, Physica A: Statistical Mechanics and its Applications, 346, 3-4, 682-696 (2005)
[8] Zhang, Z.; Wu, B.; Lin, Y., Counting spanning trees in a small-world Farey graph, Physica A: Statistical Mechanics and its Applications, 391, 11, 3342-3349 (2012)
[9] Xiao, Y.; Zhao, H., New method for counting the number of spanning trees in a two-tree network, Physica A: Statistical Mechanics and its Applications, 392, 19, 4576-4583 (2013) · Zbl 1395.05174
[10] Xiao, Y.; Zhao, H.; Hu, G.; Ma, X., Enumeration of spanning trees in planar unclustered networks, Physica A: Statistical Mechanics and its Applications, 406, 236-243 (2014) · Zbl 1395.05164
[11] Sun, W.; Wang, S.; Zhang, J., Counting spanning trees in prism and anti-prism graphs, Journal of Applied Analysis and Computation, 6, 1, 65-75 (2016) · Zbl 1463.05287
[12] Felker, J. L.; Lyons, R., High-precision entropy values for spanning trees in lattices, Journal of Physics A: Mathematical and General, 36, 31, 8361-8365 (2003) · Zbl 1099.82503
[13] Mokhlissi, R.; Lotfi, D.; Debnath, J.; Marraki, M. E., Complexity Analysis of “Small-World Networks” and Spanning Tree Entropy, International Workshop on Complex Networks and their Applications, 197-208 (2016), Springer
[14] Liu, H.; Dolgushev, M.; Qi, Y.; Zhang, Z., Laplacian spectra of a class of small-world networks and their applications, Scientific Reports, 5, article 9024 (2015)
[15] Zhang, Z.; Zhou, S.; Xie, W.; Chen, L.; Lin, Y.; Guan, J., Standard random walks and trapping on the Koch network with scale-free behavior and small-world effect, Physical Review E: Statistical, Nonlinear, and Soft Matter Physics, 79, 6 (2009)
[16] Zhang, Z.; Gao, S.; Chen, L.; Zhou, S.; Zhang, H.; Guan, J., Mapping Koch curves into scale-free small-world networks, Journal of Physics A: Mathematical and General, 43, 39 (2010) · Zbl 1213.28004
[17] Von Koch, H., Une méthode géométrique élémentaire pour l’étude de certaines questions de la théorie des courbes planes, Acta Mathematica, 30, 1, 145-174 (1906) · JFM 37.0413.02
[18] Zhang, Z.; Wu, S.; Li, M.; Comellas, F., The number and degree distribution of spanning trees in the Tower of Hanoi graph, Theoretical Computer Science, 609, part 2, 443-455 (2016) · Zbl 1332.05036
[19] Mokhlissi, R.; Lotfi, D.; Debnath, J.; Marraki, M. E., An innovative combinatorial approach for the spanning tree entropy in Flower Network, International Conference on Networked Systems, 3-14 (2017), Springer
[20] Wu, F. Y., Number of spanning trees on a lattice, Journal of Physics A: Mathematical and General, 10, 6, L113-L115 (1977)
[21] Shrock, R.; Wu, F. Y., Spanning trees on graphs and lattices in \(d\) dimensions, Journal of Physics A: Mathematical and General, 33, 21, 3881-3902 (2000) · Zbl 0949.05041
[22] Moskowitz, M. A., A course in complex analysis in one variable (2002), World Scientific Publishing Company · Zbl 0994.30001
[23] Burton, R.; Pemantle, R., Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances, Annals of Probability, 21, 3, 1329-1371 (1993) · Zbl 0785.60007
[24] Barrière, L.; Comellas, F.; Dalfó, C.; Fiol, M. A., The hierarchical product of graphs, Discrete Applied Mathematics, 157, 1, 36-48 (2009) · Zbl 1200.05196
[25] Wu, S.; Zhang, Z.; Chen, G., Random walks on dual Sierpinski gaskets, The European Physical Journal B, 82, 1, 91-96 (2011) · Zbl 1515.82075
[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, article 113303 (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. 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.