Complexity Analysis of “Small-World Networks” and Spanning Tree Entropy

The number of spanning trees of a network is an important measure related to topological and dynamic properties of the network, such as its reliability, communication aspects, and so on. However, obtaining the number of spanning trees of networks and the study of their properties are computationally demanding, in particular for complex networks. In this paper, we introduce a family of small-world networks denoted G k,n , characterized by dimension k, we present its topological construction and we examine its structural properties. Then, we propose the decomposition method to find the exact formula for the number of spanning trees of our small world network. This result allows the calculation of the spanning tree entropy which depends on the network structure, indicating that the entropy of low dimensional network is higher than that of high dimensional network.