# The Evaluation of the Number and the Entropy of Spanning Trees on Generalized Small-World Networks

Authors: Raihana Mokhlissi; Dounia Lotfi; Joyati Debnath; Mohamed El Marraki; Noussaima EL Khattabi
Journal: Journal of Applied Mathematics
 (2018)

---

## Abstract

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.


---

## Body

## 1. Introduction

Recently, the analysis of complex networks has received a major boost caused by the huge network data resources and many systems in the real world can be described and characterized by complex networks [1]. Some scientific studies have inspired researchers to construct network models to explain the existing common characteristics in real-life systems. Among the well-known models of the complex networks, there is a small-world network. It displays rich behavior as observed in a large variety of real systems including Internet (websites with navigation menus), electric power grids, networks of brain neurons, telephone call graphs, and social networks. It is characterized by specific structural features: large clustering coefficient and small average distance. To analyze this class of complex networks, theories are needed to explain their inherent and emergent properties. New formal models of these networks are needed to predict accurately their performance, assert the guarantees of their reliability, and quantify their robustness. The graph theory has a powerful tool to simplify this theoretical study by enumeratingthe spanning trees of a network G [2]. The latter are defined as a connected and acyclic subgraph of G having all vertices (nodes) of G and some or all its edges. The goal of this paper is to know how many spanning trees can have a network. The enumeration of these spanning trees tends to be one of the most important parameters that characterizes the network reliability [3]. We denote the number of spanning trees by τ(G), also known as the complexity of a network. In general, it can be obtained by calculating the determinant or the eigenvalues of the Laplacian matrix corresponding to the network [4]. However, this general method is not acceptable for large and complex networks due to its high computing time complexity. Therefore, it is interesting to develop techniques and methods to facilitate the calculation of the number of spanning trees and find its exact formula for special classes of networks. In this context, our work proposes a combinatorial method for determining the spanning trees number for some complex networks, which is the decomposition method [5]. It relies on the principle of a process of “Divide and Conquer" by dividing a problem in subproblems, solving each of these subproblems and then incorporating the partial results for a general solution.As an application of the number of spanning trees of a network, we usethe entropy of spanning trees or what is called the asymptotic complexity (see, e.g., Dehmer, Emmert-Streib, Chen, Li, and Shi [2, 6]). By calculating this entropy, we can estimate how the network will evolve to infinity. This parameter permits us to quantify the robustness of complex networks and to characterize their structures [7]. It is related to the ability of the network to resist random changes in its structures. Many researchers have used this measure to estimate the robustness of some complex networks and the heterogeneity of their structures such as the small-world Farey graph [8], the two-tree network [9], the planar unclustered networks [10], the prism and antiprism graphs [11], and the lattices [12].The novelty of our work is to analytically investigate two generalized families of small-world networks, called the Small-World Exponential network. See, e.g., Mokhlissi, Lotfi, Debnath and El Marraki [13] and Liu, Dolgushev, Qi and Zhang [14], and the Koch network. See, e.g., Zhang, Zhou, Xie, Chen, Lin and Guan [15] and Zhang, Gao, Chen, Zhou, Zhang, and Guan [16]. The first network is based on complete graphs and the second network is based on the classical fractal Koch curve [17], which has many important properties observed in real networks. To generalize these two networks, we add two important parameters related to the size of the cyclic subgraphs and the dimension of the cyclic subgraphs (the number of the cyclic subgraphs added). We suggest two iterative algorithms generating their structures, we determine their topological properties, and we calculate their complexities. In the end, we evaluate and compare their spanning trees entropy with other networks having the same average degree as the Hanoi network, the Flower network, the Honeycomb lattice. As a result, we conclude that the generalized Small-World Exponential network and the generalized Koch network have the same spanning tree entropy, so the same robustness although their structures and properties are totally different, and this entropy depends just on the size of the cyclic subgraphs, which means the articulation nodes degree of the first iteration increases according to the dimension of the cyclic subgraphs; it does not influence the spanning tee entropy. The scope of this study is that the generalization of these two small-world networks does not affect the concept of the small-world networks (large clustering coefficient and small average distance). The work of this paper presents an alternative perspective in the analysis of small-world networks that exhibit typical features of real-world systems.The outline of this paper is organized as follows. In Section2, we present the preliminaries and the used methodology. The construction, the properties, and the complexity of the generalized Small-World Exponential network and the generalized Koch network are provided in Sections 3 and 4. Then, the spanning trees entropy of these small-world networks are presented in Section 5. Finally, the conclusion is included in Section 6.


## 2. Preliminaries

In this section, we introduce some notations and the method used to facilitate the calculation of the complexity of a complex network. LetG=(V(G),E(G),F(G)) be a connected planar graph with V(G) being its number of vertices, E(G) being its number of edges, and F(G) being its number of faces; it has no loops and no parallel edges. The number of vertices of a graph refers to its order and its number of edges refers to its size. The terms graph and network are used indistinctly. A network is said to be a small-world network if the distance L between two random nodes grows proportionally to the logarithm of the number of nodes in the network, that is, L∝log⁡N, while the clustering coefficient (measure of the degree to which nodes in a network tend to cluster together) is not small.Euler’s formula [22]: Euler’s formula is a topological invariant that characterized the topological properties related to the number of vertices, edges, and faces.Theorem 1.
LetG be a connected planar graph with n vertices, m edges, and f faces. These numbers are connected by the well-known Euler’s relation; then(1)n-m+f=2The selection of the appropriate method for calculating the spanning trees number is a key factor in a given network. For this work, we put forward a decomposition method to make the number of spanning trees easy for computation. This method relies on the principle of Divide and Conquer; we decompose the graph into different subgraphs according certain constraints: by following one node, two nodes, an edge, and a path. In this work, we study the case where subgraphs are connected by one vertex (see Figure1). To apply this method, we follow this algorithm:(1)
We decompose the original graph into different subgraphs that are connected to one vertex.(2)
We calculate the number of spanning trees for each of subgraph.(3)
We collect the results to obtain the complexity of the original graph.Figure 1
Star network and chain network.LetG be a chain of planar graphs defined by G=C1•C2•…•Cn (see Figure 1). The number of spanning trees in G is given by the following formula:(2)τG=∏i=1nτCi.If the complexity of a networkτ(G) grows exponentially with the number of vertices VG, then there exists a constant ρG, called the entropy of spanning trees or the asymptotic complexity [23], described by this relation:(3)ρG=limVG⟶∞ln⁡τGVGThe entropy of spanning trees of a networkG is a quantitative measure of the number of spanning trees to evaluate the robustness of a network and to characterize its structure. The most robust network with the stronger heterogeneous topology is the network that has the highest spanning tree entropy. According to the definition of the entropy of spanning trees of a network, the bigger the entropy value, the more the number of spanning trees, so there are more possibilities of connections between two nodes related to defective links that ensures a good reliability and robustness.


## 3. A Generalized Small-World Exponential NetworkGk,l,n

In this section, we introduce a well-known family of small-world network: the Small-World Exponential network [24]. It has an exponential form of degree distribution and the same number of nodes and edges as the dual Sierpinski gaskets [25]. It has been observed from some real-life systems as tensor networks, social networks, quantum walks. We propose a generalized Small-World Exponential network, where the difference relies on the size of the cyclic subgraph and the dimension of the cyclic subgraph (the number of the cyclic subgraphs added). We also investigate its construction and structural properties and calculate its complexity.


### 3.1. The Construction and the Properties of the Generalized Small-World Exponential NetworkGk,l,n

The generalized Small-World Exponential network is denoted byGk,l,n with two controllable parameters: l is the size of the cyclic subgraph and k is the dimension of the cyclic subgraph, i.e., the number of the cyclic subgraphs added. The construction of Gk,l,n follows this algorithm: at n=0, we have a simple node. At first generation, Gk,l,1 is a cyclic graph with the size l. For n>1, each node in the network of the previous iteration is replaced by k new cyclic subgraphs having the size l. Thus, each of the newly appeared cyclic subgraphs contains exactly one node of the network of the previous iteration and the articulation nodes degree of the first iteration is dGk,l,n=2(kn-1)/(k-1) (in Figure 2, the articulation nodes are colored by the red). The same process is used for the other iterations. In Figure 2, the first four iterations of the generalized Small-World Exponential network Gk,l,n are illustrated.Figure 2
The first four generations of the generalized Small-World Exponential networkG2,4,n.Let us compute the order, the size, the number of faces, the average degree, and the diameter of the generalized Small-World Exponential networkGk,l,n. Let VGk,l,n be the numbers of nodes created at n. From Figure 2, we notice for i from 1 to n: VGk,l,i=lk×VGk,l,i-1-(k-1)l. Then, we multiply the equation of VGk,l,n-1 by (lk), the equation of VGk,l,n-2 by (lk)2, and so on until the last equation VGk,l,1 which will be multiplied by (lk)(n-1). Summing all the obtained equations: ∑i=0n-1(lk)iVGk,l,n-i=∑i=0n-1(lk)i+1VGk,l,n-i-1-(k-1)l∑i=0n-1(lk)i. We find the following results: VGk,l,n=(lk)nVGk,l,0-(k-1)l∑i=0n-1(lk)i with VGk,l,0=1. Thus,the number of nodes ofGk,l,nis(4)VGk,l,n=lknl-1+k-1llk-1,n≥0.LetEGk,l,n be the numbers of links created at iteration n. By construction, for i from 1 to n, we have EGk,l,i=lk×EGk,l,i-1+l. Then, we multiply the equation of EGk,l,n-1 by (lk), the equation of EGk,l,n-2 by (lk)2, and so on until the last equation EGk,l,1 which will be multiplied by (lk)(n-1). Summing all the obtained equations: ∑i=0n-1(lk)iEGk,l,n-i=∑i=0n-1(lk)i+1EGk,l,n-i-1+l∑i=0n-1(lk)i. We find EGk,l,n=(lk)nEGk,l,0+l∑i=0n-1(lk)i with EGk,l,0=0. Thus,the number of links ofGk,l,nis(5)EGk,l,n=l×lkn-1lk-1,n≥0.LetFGk,l,n be the numbers of faces created at generation n. We apply Theorem 1; we obtain thatthe number of faces ofGk,l,nis(6)FGk,l,n=lkn+lk-2lk-1,n≥0.The average degree of G k , l , n is (which is approximately 3 for large n)(7)zGk,l,n=2EGk,l,nVGk,l,n=2l×lkn-1lknl-1+k-1l,n≥0.The diameterD is the maximum of the shortest distance between any two nodes (u,v) of a network: D=maxu,vd(u,v). Let DGk,l,n be the diameter of Gk,l,n created at generation n. This diameter can be calculated in two cases:(i)
If the size of cyclic subgraphsl is pair, we can calculate the diameter as follows: at iteration n=1, the diameter DGk,l,1=l/2. For n>1, the diameter of Gk,l,n increases by l at most.(ii)
If the size of cyclic subgraphsl is odd, we can calculate the diameter as follows: at iteration n=1, the diameter DGk,l,1=⌊l/2⌋. For n>1, the diameter of Gk,l,n increases by (l-1) at most.Sothe diameter ofGk,l,nis(8)DGk,l,n=l-ϵ2+l-ϵn-1withϵ=0,ifliseven,ϵ=1,iflisoddThis diameter can be presented by another formula which grows logarithmically with the number of vertices of the network indicating thatGk,l,n is a small-world network.(9)DGk,l,n=l-ϵ2+l-ϵloglk⁡VGk,l,nlk-1-k-1ll-1-1withϵ=0,ifliseven,ϵ=1,iflisodd


### 3.2. The Number of Spanning Trees of the Generalized Small-World Exponential NetworkGk,l,n

The enumeration of spanning trees is a fundamental issue in many problems encountered in network analysis. However, explicitly determining this interesting quantity in networks is a theoretical challenge specially for the complex networks. Fortunately, the construction of the generalized Small-World Exponential networkGk,l,n makes it possible to derive the exact formula of this number using the decomposition method.Theorem 2.
LetGk,l,n denote the generalized Small-World Exponential networks. The complexity of Gk,l,n is given by the following formula:(10)τGk,l,n=llkn-1/lk-1,n≥1.Proof.
From Figure2, we see that Gk,l,n contains several cyclic subgraphs Yk,l,n. Using (2) we obtain τ(Gk,l,n)=∏δYk,l,nτ(Yk,l,n)=τ(Yk,l,n)δYk,l,n, where δYk,l,n is the number of cyclic subgraphs in Gk,l,n. In order to calculate the number of spanning trees of Gk,l,n, we need to find firstly the number of cyclic subgraphs in Gk,l,n. From our network, for i from 1 to n, we see δYk,l,i=lk×δYk,l,i-1+1. Then, we multiply the equation of δYk,l,n-1 by (lk), the equation of δYk,l,n-2 by (lk)2, and so on until the last equation δYk,l,1 which will be multiplied by (lk)n-1. Summing all the obtained equations: ∑i=0n-1(lk)iδYk,l,n-i=∑i=0n-1(lk)i+1δYk,l,n-i-1+∑i=0n-1(lk)i. We find the number of cycles in Gk,l,n: δYk,l,n=((lk)n-1)/((lk)-1). We replace it in the equation of τ(Gk,l,n); hence, we obtain τ(Gk,l,n)=l((lk)n-1)/(lk-1).
Fork=1 and l=3, the network G1,3,n is the Small-World Exponential network. Its number of spanning trees is given by the following formula [26]:(11)τG1,3,n=33n-1/2,n≥1.


## 3.1. The Construction and the Properties of the Generalized Small-World Exponential NetworkGk,l,n

The generalized Small-World Exponential network is denoted byGk,l,n with two controllable parameters: l is the size of the cyclic subgraph and k is the dimension of the cyclic subgraph, i.e., the number of the cyclic subgraphs added. The construction of Gk,l,n follows this algorithm: at n=0, we have a simple node. At first generation, Gk,l,1 is a cyclic graph with the size l. For n>1, each node in the network of the previous iteration is replaced by k new cyclic subgraphs having the size l. Thus, each of the newly appeared cyclic subgraphs contains exactly one node of the network of the previous iteration and the articulation nodes degree of the first iteration is dGk,l,n=2(kn-1)/(k-1) (in Figure 2, the articulation nodes are colored by the red). The same process is used for the other iterations. In Figure 2, the first four iterations of the generalized Small-World Exponential network Gk,l,n are illustrated.Figure 2
The first four generations of the generalized Small-World Exponential networkG2,4,n.Let us compute the order, the size, the number of faces, the average degree, and the diameter of the generalized Small-World Exponential networkGk,l,n. Let VGk,l,n be the numbers of nodes created at n. From Figure 2, we notice for i from 1 to n: VGk,l,i=lk×VGk,l,i-1-(k-1)l. Then, we multiply the equation of VGk,l,n-1 by (lk), the equation of VGk,l,n-2 by (lk)2, and so on until the last equation VGk,l,1 which will be multiplied by (lk)(n-1). Summing all the obtained equations: ∑i=0n-1(lk)iVGk,l,n-i=∑i=0n-1(lk)i+1VGk,l,n-i-1-(k-1)l∑i=0n-1(lk)i. We find the following results: VGk,l,n=(lk)nVGk,l,0-(k-1)l∑i=0n-1(lk)i with VGk,l,0=1. Thus,the number of nodes ofGk,l,nis(4)VGk,l,n=lknl-1+k-1llk-1,n≥0.LetEGk,l,n be the numbers of links created at iteration n. By construction, for i from 1 to n, we have EGk,l,i=lk×EGk,l,i-1+l. Then, we multiply the equation of EGk,l,n-1 by (lk), the equation of EGk,l,n-2 by (lk)2, and so on until the last equation EGk,l,1 which will be multiplied by (lk)(n-1). Summing all the obtained equations: ∑i=0n-1(lk)iEGk,l,n-i=∑i=0n-1(lk)i+1EGk,l,n-i-1+l∑i=0n-1(lk)i. We find EGk,l,n=(lk)nEGk,l,0+l∑i=0n-1(lk)i with EGk,l,0=0. Thus,the number of links ofGk,l,nis(5)EGk,l,n=l×lkn-1lk-1,n≥0.LetFGk,l,n be the numbers of faces created at generation n. We apply Theorem 1; we obtain thatthe number of faces ofGk,l,nis(6)FGk,l,n=lkn+lk-2lk-1,n≥0.The average degree of G k , l , n is (which is approximately 3 for large n)(7)zGk,l,n=2EGk,l,nVGk,l,n=2l×lkn-1lknl-1+k-1l,n≥0.The diameterD is the maximum of the shortest distance between any two nodes (u,v) of a network: D=maxu,vd(u,v). Let DGk,l,n be the diameter of Gk,l,n created at generation n. This diameter can be calculated in two cases:(i)
If the size of cyclic subgraphsl is pair, we can calculate the diameter as follows: at iteration n=1, the diameter DGk,l,1=l/2. For n>1, the diameter of Gk,l,n increases by l at most.(ii)
If the size of cyclic subgraphsl is odd, we can calculate the diameter as follows: at iteration n=1, the diameter DGk,l,1=⌊l/2⌋. For n>1, the diameter of Gk,l,n increases by (l-1) at most.Sothe diameter ofGk,l,nis(8)DGk,l,n=l-ϵ2+l-ϵn-1withϵ=0,ifliseven,ϵ=1,iflisoddThis diameter can be presented by another formula which grows logarithmically with the number of vertices of the network indicating thatGk,l,n is a small-world network.(9)DGk,l,n=l-ϵ2+l-ϵloglk⁡VGk,l,nlk-1-k-1ll-1-1withϵ=0,ifliseven,ϵ=1,iflisodd


## 3.2. The Number of Spanning Trees of the Generalized Small-World Exponential NetworkGk,l,n

The enumeration of spanning trees is a fundamental issue in many problems encountered in network analysis. However, explicitly determining this interesting quantity in networks is a theoretical challenge specially for the complex networks. Fortunately, the construction of the generalized Small-World Exponential networkGk,l,n makes it possible to derive the exact formula of this number using the decomposition method.Theorem 2.
LetGk,l,n denote the generalized Small-World Exponential networks. The complexity of Gk,l,n is given by the following formula:(10)τGk,l,n=llkn-1/lk-1,n≥1.Proof.
From Figure2, we see that Gk,l,n contains several cyclic subgraphs Yk,l,n. Using (2) we obtain τ(Gk,l,n)=∏δYk,l,nτ(Yk,l,n)=τ(Yk,l,n)δYk,l,n, where δYk,l,n is the number of cyclic subgraphs in Gk,l,n. In order to calculate the number of spanning trees of Gk,l,n, we need to find firstly the number of cyclic subgraphs in Gk,l,n. From our network, for i from 1 to n, we see δYk,l,i=lk×δYk,l,i-1+1. Then, we multiply the equation of δYk,l,n-1 by (lk), the equation of δYk,l,n-2 by (lk)2, and so on until the last equation δYk,l,1 which will be multiplied by (lk)n-1. Summing all the obtained equations: ∑i=0n-1(lk)iδYk,l,n-i=∑i=0n-1(lk)i+1δYk,l,n-i-1+∑i=0n-1(lk)i. We find the number of cycles in Gk,l,n: δYk,l,n=((lk)n-1)/((lk)-1). We replace it in the equation of τ(Gk,l,n); hence, we obtain τ(Gk,l,n)=l((lk)n-1)/(lk-1).
Fork=1 and l=3, the network G1,3,n is the Small-World Exponential network. Its number of spanning trees is given by the following formula [26]:(11)τG1,3,n=33n-1/2,n≥1.


## 4. A Generalized Koch NetworkCk,l,n

In this section, another class of small-world networks called theKoch networkCn is studied analytically. This network is derived from the class of Koch curves. They are one of the interesting families of fractals. We use them to understand the geometric fractals in real systems. This Koch network incorporates some properties characterizing a majority of real-life network systems: a high clustering coefficient and a small diameter, indicating that the Koch network is a small-world network. We put forward a family of generalized Koch network Ck,l,n, where the difference relies on the size of the cyclic subgraphs and the number of the cyclic subgraphs added in each node change according to two parameters k and l. We propose analytically an algorithm of the construction of the generalized Koch network, we determine its properties and we calculate its complexity.


### 4.1. The Construction and the Properties of the Generalized Koch NetworkCk,l,n

Inspired by the algorithm of the Koch network, we propose a family of generalized Koch network asCk,l,n with two integer parameters l (the size of the cyclic subgraph) and k (the dimension of the cyclic subgraph). The algorithm of its construction is as follows: initially (n=0), Ck,l,0 is a cyclic graph with the size l. For n≥1, Ck,l,n is obtained from Ck,l,n-1 by adding k new cyclic subgraphs having the size l for each of the nodes of every existing cyclic subgraph in Ck,l,n-1. The growth process of the generalized Koch network to the next generation keeps on in a similar way. The articulation nodes degree of the first iteration is dCk,l,n=2(k+1)n (in Figure 3, the articulation nodes are colored by the green). Figure 3 illustrates the growing process of the networks for the first three generations of Ck,l,n.Figure 3
The first three generations of the generalized Koch networkC2,4,n.In this section, exact expressions for the properties of the generalized Koch NetworkCk,l,n are given. Then the explicit results for its number of nodes, number of edges, number of faces, average degree, and diameter are stated.The structural properties of the generalized Koch NetworkCk,l,n are presented as follows: the number of nodes of Ck,l,n is calculated as follows. From Figure 3, we notice for i from 1 to n: VCk,l,i=(lk+1)×VCk,l,i-1-lk. Then, we multiply the equation of VCk,l,n-1 by (lk+1), the equation of VCk,l,n-2 by (lk+1)2, and so on until the last equation VCk,l,1 which will be multiplied by (lk+1)(n-1). Summing all the obtained equations: ∑i=0n-1(lk+1)iVCk,l,n-i=∑i=0n-1(lk+1)i+1VCk,l,n-i-1-lk∑i=0n-1(lk+1)i. We find VCk,l,n=(lk+1)nVCk,l,0-lk∑i=0n-1(lk+1)i with VCk,l,0=l. Sothe number of nodes ofCk,l,nis(12)VCk,l,n=l-1lk+1n+1,n≥0.The number of edges ofCk,l,n is calculated as follows: from Figure 3, we notice for i from 1 to n: ECk,l,i=(lk+1)ECk,l,i-1 (a geometric suite). Sothe number of edges ofCk,l,nis(13)ECk,l,n=llk+1n,n≥0.The number of faces ofCk,l,n is calculated as follows: from Figure 3, we notice for i from 1 to n: FCk,l,i=(lk+1)×FCk,l,i-1-lk. Then, the equation of FCk,l,n-1 is multiplied by (lk+1), the equation of FCk,l,n-2 by (lk+1)2, and so on until the last equation FCk,l,1 which is multiplied by (lk+1)n-1. Summing all the obtained equations: ∑i=0n-1(lk+1)iFCk,l,n-i=∑i=0n-1(lk+1)i+1FCk,l,n-i-1-lk∑i=0n-1(lk+1)i. We find FCk,l,n=(lk+1)nFCk,l,0-lk∑i=0n-1(lk+1)i with FCk,l,0=2. Sothe number of faces ofCk,l,nis(14)FCk,l,n=lk+1n+1,n≥0.We can obtain the number of faces ofCk,l,n also by using Theorem 1.The average degree of C k , l , n is (which is approximately 3 for large n)(15)zCk,l,n=2ECk,l,nVCk,l,n=2llk+1nl-1lk+1n+1,n≥0LetDCk,l,n be the diameter of Ck,l,n created at generation n.This diameter can be presented by the following formula for n≥0:(16)DCk,l,n=l-ϵ2+nl-ϵwithϵ=0,ifliseven,ϵ=1,iflisoddWe can present it by another formula which grows logarithmically with the number of vertices of the network indicating thatCk,l,n is a small-world network.(17)DCk,l,n=l-ϵ2+l-ϵloglk+1VCk,l,n-1l-1withϵ=0,ifliseven,ϵ=1,iflisodd


### 4.2. The Number of Spanning Trees of the Generalized Koch NetworkCk,l,n

In order to calculate the number of spanning trees of the generalized Koch NetworkCk,l,n, we use the same method as the other networks studied before: the decomposition method.Theorem 3.
LetCk,l,n denote the generalized Koch network. The complexity of Ck,l,n is given by the following formula:(18)τCk,l,n=llk+1n,n≥0Proof.
From Figure3, we see that Ck,l,n contains several cyclic subgraphs Xk,l,n. Using (2) τ(Ck,l,n)=∏δXk,l,nτ(Xk,l,n)=τ(Xk,l,n)δXk,l,n with δXk,l,n as the number of the cyclic subgraphs in Ck,l,n. From Figure 3, we see for i from 1 to n: δXk,l,i=(lk+1)δXk,l,i-1(a geometric suite). So the number of cyclic subgraphs in Ck,l,n is δXk,l,n=(lk+1)n. Replacing this result in the equation of τ(Ck,l,n) with τ(Xk,l,n)=l, hence we obtain τ(Ck,l,n)=l(lk+1)n,n≥0. For k=1 and l=3, the network C1,3,n is the Koch network. Its number of spanning trees is given by the following formula [16]:(19)τC1,3,n=34n,n≥0.


## 4.1. The Construction and the Properties of the Generalized Koch NetworkCk,l,n

Inspired by the algorithm of the Koch network, we propose a family of generalized Koch network asCk,l,n with two integer parameters l (the size of the cyclic subgraph) and k (the dimension of the cyclic subgraph). The algorithm of its construction is as follows: initially (n=0), Ck,l,0 is a cyclic graph with the size l. For n≥1, Ck,l,n is obtained from Ck,l,n-1 by adding k new cyclic subgraphs having the size l for each of the nodes of every existing cyclic subgraph in Ck,l,n-1. The growth process of the generalized Koch network to the next generation keeps on in a similar way. The articulation nodes degree of the first iteration is dCk,l,n=2(k+1)n (in Figure 3, the articulation nodes are colored by the green). Figure 3 illustrates the growing process of the networks for the first three generations of Ck,l,n.Figure 3
The first three generations of the generalized Koch networkC2,4,n.In this section, exact expressions for the properties of the generalized Koch NetworkCk,l,n are given. Then the explicit results for its number of nodes, number of edges, number of faces, average degree, and diameter are stated.The structural properties of the generalized Koch NetworkCk,l,n are presented as follows: the number of nodes of Ck,l,n is calculated as follows. From Figure 3, we notice for i from 1 to n: VCk,l,i=(lk+1)×VCk,l,i-1-lk. Then, we multiply the equation of VCk,l,n-1 by (lk+1), the equation of VCk,l,n-2 by (lk+1)2, and so on until the last equation VCk,l,1 which will be multiplied by (lk+1)(n-1). Summing all the obtained equations: ∑i=0n-1(lk+1)iVCk,l,n-i=∑i=0n-1(lk+1)i+1VCk,l,n-i-1-lk∑i=0n-1(lk+1)i. We find VCk,l,n=(lk+1)nVCk,l,0-lk∑i=0n-1(lk+1)i with VCk,l,0=l. Sothe number of nodes ofCk,l,nis(12)VCk,l,n=l-1lk+1n+1,n≥0.The number of edges ofCk,l,n is calculated as follows: from Figure 3, we notice for i from 1 to n: ECk,l,i=(lk+1)ECk,l,i-1 (a geometric suite). Sothe number of edges ofCk,l,nis(13)ECk,l,n=llk+1n,n≥0.The number of faces ofCk,l,n is calculated as follows: from Figure 3, we notice for i from 1 to n: FCk,l,i=(lk+1)×FCk,l,i-1-lk. Then, the equation of FCk,l,n-1 is multiplied by (lk+1), the equation of FCk,l,n-2 by (lk+1)2, and so on until the last equation FCk,l,1 which is multiplied by (lk+1)n-1. Summing all the obtained equations: ∑i=0n-1(lk+1)iFCk,l,n-i=∑i=0n-1(lk+1)i+1FCk,l,n-i-1-lk∑i=0n-1(lk+1)i. We find FCk,l,n=(lk+1)nFCk,l,0-lk∑i=0n-1(lk+1)i with FCk,l,0=2. Sothe number of faces ofCk,l,nis(14)FCk,l,n=lk+1n+1,n≥0.We can obtain the number of faces ofCk,l,n also by using Theorem 1.The average degree of C k , l , n is (which is approximately 3 for large n)(15)zCk,l,n=2ECk,l,nVCk,l,n=2llk+1nl-1lk+1n+1,n≥0LetDCk,l,n be the diameter of Ck,l,n created at generation n.This diameter can be presented by the following formula for n≥0:(16)DCk,l,n=l-ϵ2+nl-ϵwithϵ=0,ifliseven,ϵ=1,iflisoddWe can present it by another formula which grows logarithmically with the number of vertices of the network indicating thatCk,l,n is a small-world network.(17)DCk,l,n=l-ϵ2+l-ϵloglk+1VCk,l,n-1l-1withϵ=0,ifliseven,ϵ=1,iflisodd


## 4.2. The Number of Spanning Trees of the Generalized Koch NetworkCk,l,n

In order to calculate the number of spanning trees of the generalized Koch NetworkCk,l,n, we use the same method as the other networks studied before: the decomposition method.Theorem 3.
LetCk,l,n denote the generalized Koch network. The complexity of Ck,l,n is given by the following formula:(18)τCk,l,n=llk+1n,n≥0Proof.
From Figure3, we see that Ck,l,n contains several cyclic subgraphs Xk,l,n. Using (2) τ(Ck,l,n)=∏δXk,l,nτ(Xk,l,n)=τ(Xk,l,n)δXk,l,n with δXk,l,n as the number of the cyclic subgraphs in Ck,l,n. From Figure 3, we see for i from 1 to n: δXk,l,i=(lk+1)δXk,l,i-1(a geometric suite). So the number of cyclic subgraphs in Ck,l,n is δXk,l,n=(lk+1)n. Replacing this result in the equation of τ(Ck,l,n) with τ(Xk,l,n)=l, hence we obtain τ(Ck,l,n)=l(lk+1)n,n≥0. For k=1 and l=3, the network C1,3,n is the Koch network. Its number of spanning trees is given by the following formula [16]:(19)τC1,3,n=34n,n≥0.


## 5. The Spanning Tree Entropy of the Generalized Small-World Exponential Network and the Generalized Koch Network

The spanning tree number of the generalized small-world networks grows exponentially, so we can calculate their spanning trees entropy according to the definition of the entropy in Section2. Let ρGk,l,n be the entropy of spanning trees for the generalized Small-World Exponential network and ρCk,l,n be the entropy of spanning trees for the generalized Koch network.Corollary 4.
The entropy of spanning trees of the generalized Small-World Exponential networkGk,l,n is(20)ρGk,l,n=ln⁡ll-1
The entropy of spanning trees of the generalized Koch networkCk,l,n is(21)ρCk,l,n=ln⁡ll-1From the results, we find that the generalized Small-World Exponential network and the generalized Koch network have the same entropy even if their complexities are different. The entropy depends just on the size of the cyclic subgraphsl and not on the dimension of the cyclic subgraphs k. It means that generalized Small-World Exponential network and the generalized Koch network have the same robustness despite the fact that their structures and properties are different. Notice that the degree of the articulation nodes of the first iteration increases according to the value of k, and it does not influence the spanning tree entropy and, therefore, does not influence the robustness of these two small-world networks.Figure4 shows that increasing the size of the cyclic subgraphs l leads to the decreasing of the entropy of spanning trees of Gk,l,n and Ck,l,n. This result proves that these networks having low value of l are more robust than those having high value of l.Figure 4
The spanning tree entropy of the generalized Small-World Exponential network and the generalized Koch network.From Table1, we compare the spanning trees entropy of the Small-World Exponential network G1,3,n and the Koch network C1,3,n (0.549) with those of other networks having the same average degree 3. We notice that the value of their spanning trees entropy is the smallest known for networks with average degree 3. This reflects the fact that the Koch network and the Small-World Exponential network are less robust and their topology is less heterogeneous than other networks having the same average degree.Table 1
T: The spanning trees entropy of several networks having the same average degree.
Type of network z ρ Koch network  C1,3,n 3 0.549 Small-World Exponential network  G1,3,n 3 0.549 The Hanoi network [18] 3 0.677 The 2-Flower network [19] 3 0.6931 The 3-2-12 lattices [20] 3 0.721 The 4-8-8 bathroom tile [20] 3 0.787 Honeycomb lattice [21] 3 0.807


## 6. Conclusion

In this paper, we have studied the problem of efficiently computing the number of spanning trees in two well-known small-world networks: Generalized Small-World Exponential network and the generalized Koch network. We have examined their construction and determined a detailed analysis of their topological properties. We have obtained the exact solutions for their number of spanning trees using the decomposition method. We have further calculated and compared their entropy of spanning trees. The result shows that these two generalized small-world networks have the same entropy of the spanning trees although they do not have the same complexity. As a future work, we intend to analyse another type of complex networks and to use a new combinatorial method that facilitates the calculation of its number of spanning trees.



---

*Source: 1017308-2018-09-03.xml*