# A New Class of the Planar Networks with High Clustering and High Entropy

Authors: Guona Hu; Yuzhi Xiao; Huanshen Jia; Haixing Zhao
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

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.


---

## Body

## 1. Introduction

Over the past decade, a lot of authors in different scientific communities have made a concerted effort toward unveiling and understanding the generic properties of complex networked systems in nature and society [1–5]. One of the most important things is the network modeling. Its importance lies in the fact that it cannot only capture correctly the processes that assembled the networks that we see today, but also help to know how various microscopic processes influence the network topology [6]. At present, many papers related to complex network models are stochastic [7–9]. But the randomness, while in line with the major features of real-life networks, makes it harder to gain a visual understanding of how networks are shaped and how do different nodes relate to each other [10]. Therefore, it would be not only of major theoretical interest but also of great practical significance to construct models that lead to small-world networks in deterministic fashions.The first successful attempt to generate networks with high clustering coefficients and small average path length (APL) is the model introduced by Watts and Strogatz (WS model) [11]. This pioneering work of Watts and Strogatz started an avalanche of research on the properties of small-world networks and the Watts-Strogatz (WS) model [12]. A much-studied variant of the WS model was proposed by Newman and Watts [13, 14]. In 1999, Kasturirangan proposed an alternative model to WS small-world network [15]. Actually, small-world networks are characterized by three main properties. First, their APL does not increase linearly with the system size, but grows logarithmically with the number of nodes or slower. Second, average node degree of the network is small. Third, the network has a strong average clustering [11] compared to an Erdös-Rényi (ER) random network [16, 17] of equal size and average node degree.In this paper, we propose a generation algorithm of a deterministic planar network model. And we analyze its topological properties; the results show that our model has a discrete exponential degree distribution, high clustering, and small diameter, which appears small-world effect. In addition, it is known to us that the number of spanning trees is an important quantity characterizing the reliability of a network. Generally, the number of spanning trees in a network can be obtained by directly calculating a related determinant corresponding to the network. However, for a large network, evaluating the relevant determinant is intractable [18]. Therefore, we propose a generic linear algorithm to count the number of spanning trees of the general planar networks. Using the algorithm, we derive analytically the exact numbers of spanning trees in the planar networks. Based on the number of spanning trees, we determine the entropy of its spanning trees.


## 2. Network Construction

The studied network is constructed in an iterative way. We denote the network aftert steps by M(t). Then, the network at step t is built as follows. For t=1, M(1) is a complete graph with 4 nodes. For t≥2, M(t) is obtained from M(t-1) by replacing each existing iterative edge in M(t-1) with M(1). The process is repeated till the desired graph order is reached; see Figure 1.Figure 1
(Color online) construction of the deterministic planar networkM(t), showing three steps of the iterative progress. The solid links are iterated links; the dashed links are noniterated links.Now, we compute the order and size ofM(t). Let Lv(t), Le(t), and Li(t) denote, respectively, the set of vertices, edges, and iterative edges introduced at step t, while V(t) and E(t) are the set of vertices and edges of the graph M(t). Notice that, at each iteration, an iterative edge is replaced by two new iterative edges and three noniterative edges. Therefore, |Li(t)|=2|Li(t-1)|, and |Li(t)|=3·2t-1(t≥1). As each iterative edge introduces at the next iteration two new vertices and five new edges, we have |Lv(t)|=2|Li(t-1)|=3·2t-1(t≥2) and |Le(t)|=5|Li(t-1)|=15·2t-2(t≥2). As Li(1)=3, |Lv(t)|=4 and |Le(t)|=6. Thus,
(1)|V(t)|=∑i=0n‍|Lv(t)|=3·2t-2(t≥1)(2)|E(t)|=∑i=0n‍|Le(t)|=15·2t-1-9(t≥1).
The average degree is then
(3)〈k〉=2|E(t)||V(t)|=15·2t-1-93·2t-1-1.
Obviously, for large t, it is approximately equal to 5.


## 3. Relevant Characteristics of the Deterministic Small-World Network

In the following, we concentrate on the degree distribution, clustering coefficient, and diameter.


### 3.1. Degree Distribution

The degree is the simplest and the most intensively studied characteristic of an individual node. The degree of a nodei is the number of edges in the whole network connected to i. The degree distribution P(k) is defined as the probability that a randomly selected node has exactly k edges.Letki(t) be the degree of node i at step t. All nodes can be divided into two categories. (i) Interior nodes; for those nodes that only connect to noniterative edges, their degree is always equal to 3. (ii) Noninterior nodes; one can see that at any iteration, a iterative edge is replaced by two new iterative edges and three new noniterative edges, so the degree of noninterior nodes is added 4 at each iteration. Thus, the degree ki(t) of a node i satisfies the relation ki(t+1)=ki(t)+4. Then, ki(t)=4t-1. And we have
(4)ki(t)={3,ifthenodeiisinteriornode,4t-1ifthenodeiisnoninteriornode.
Let ti be the step at which a node i is created, then ki(ti)=3, and hence, for noninterior nodes, we have
(5)ki(t)=3+4(t-ti).
Therefore, the degree spectrum of the present network is a series of discrete values: at step t, the number of nodes of degree k=3,7,11,…,4t-9,4t-5,4t-1, equals 9·2t-2-2,|L(t-2)|,|L(t-3)|,…,|L(2)|,|L(1)|,|L(1)|, respectively. Other values of degree are absent in the spectrum. Due to the discreteness of this degree spectrum, it is convenient to obtain its cumulative degree distribution [18]; that is,
(6)Pcum(k)=∑k′=k∞‍P(k′).
Using (5), we have Pcum(k)=∑k′=k∞P(k′)=P(t′≤τ=(3+4t-k)/4). Hence,
(7)Pcum(k)=∑t′=0τ‍|n(t′)||V(t)|=3·2(3/4)+t-(k/4)3·2t-2.
Obviously, when the size of the network is large, the degree distribution Pcum(k)=2(3/4)-(k/4) is an exponential of a power of degree k.


### 3.2. Clustering Coefficient

Clustering coefficient is another significant property of a network, which provides a measure of the local structure within the network. The most immediate measure of clustering is the clustering coefficientCi for every node i. By definition, clustering coefficient Ci of a node i is the ratio of the total number Ei of edges that actually exist between all ki its nearest neighbors and the number ki(ki-1)/2 of all possible edges between them; that is, Ci=2Ei/[ki(ki-1)]. The clustering coefficient Ct of the whole network is the average of all individual Ci′s. For this network, we can obtain the exact expression of the clustering coefficient Ct. By construction, for any given node u having a degree k, there are Eu=3·(k-1)/2 links that actually exist among the neighbor nodes. So, one can see that there is a one-to-one corresponding relation between the coefficient C(k) of the node and its degree k: C(k)=3/k. This expression indicates that the local clustering scales as C(k)~k-1.Clearly, the number of nodes of degreek=3,7,11,…,4t-9,4t-5,4t-1, equals 9·2t-2-2,|L(t-2)|,|L(t-3)|,…,|L(2)|,|L(1)|,|L(1)|, respectively. The clustering coefficient Ct is given by the following:
(8)Ct=9·2t-2-2+9·∑i=2t-1((2t-1-i/(4i-1))+(9/(4t-1)))3·2t-2.
For infinite t, Ct approaches to a constant value of 0.8309, so the clustering is high.


### 3.3. Diameter

Besides degree distribution and clustering coefficient, average path length (APL) is another important parameter to characterize a network. APL is defined as the average number of edges along the shortest paths for all possible pairs of network nodes. People have found the small-world phenomenon in most real-life networks that behave with a short APL. For most network models, it is hard to obtain the analytic solution of APL. To demonstrate the short distance between any pair of nodes, we can adopt another parameter that is defined as the maximal communication delay in the network. If a network has a small diameter, then this network is undoubtedly with a short APL [19]. For the network proposed, we denote the diameter at iteration t as D(t). According to Figure 1, we can clearly know that D(1)=1 and D(2)=2. At each iteration, one can see that the diameter always lies between a pair of newly created nodes at this iteration because at each iterative edge we paste a complete graph M(1), so the diameter for the network proposed has the following simple formula, D(t)=t.Notice that the logarithm value of total number of nodes|V(t)| is approximately equal to tln2 for large t. Thus, the diameter grows logarithmically with the number of nodes and the average path length increases more slowly than ln|V(t)|.Based on the above discussions, our model is a deterministic small-world network because it is a sparse one with high clustering and short diameter, which satisfies the necessary property for small-world network.


## 3.1. Degree Distribution

The degree is the simplest and the most intensively studied characteristic of an individual node. The degree of a nodei is the number of edges in the whole network connected to i. The degree distribution P(k) is defined as the probability that a randomly selected node has exactly k edges.Letki(t) be the degree of node i at step t. All nodes can be divided into two categories. (i) Interior nodes; for those nodes that only connect to noniterative edges, their degree is always equal to 3. (ii) Noninterior nodes; one can see that at any iteration, a iterative edge is replaced by two new iterative edges and three new noniterative edges, so the degree of noninterior nodes is added 4 at each iteration. Thus, the degree ki(t) of a node i satisfies the relation ki(t+1)=ki(t)+4. Then, ki(t)=4t-1. And we have
(4)ki(t)={3,ifthenodeiisinteriornode,4t-1ifthenodeiisnoninteriornode.
Let ti be the step at which a node i is created, then ki(ti)=3, and hence, for noninterior nodes, we have
(5)ki(t)=3+4(t-ti).
Therefore, the degree spectrum of the present network is a series of discrete values: at step t, the number of nodes of degree k=3,7,11,…,4t-9,4t-5,4t-1, equals 9·2t-2-2,|L(t-2)|,|L(t-3)|,…,|L(2)|,|L(1)|,|L(1)|, respectively. Other values of degree are absent in the spectrum. Due to the discreteness of this degree spectrum, it is convenient to obtain its cumulative degree distribution [18]; that is,
(6)Pcum(k)=∑k′=k∞‍P(k′).
Using (5), we have Pcum(k)=∑k′=k∞P(k′)=P(t′≤τ=(3+4t-k)/4). Hence,
(7)Pcum(k)=∑t′=0τ‍|n(t′)||V(t)|=3·2(3/4)+t-(k/4)3·2t-2.
Obviously, when the size of the network is large, the degree distribution Pcum(k)=2(3/4)-(k/4) is an exponential of a power of degree k.


## 3.2. Clustering Coefficient

Clustering coefficient is another significant property of a network, which provides a measure of the local structure within the network. The most immediate measure of clustering is the clustering coefficientCi for every node i. By definition, clustering coefficient Ci of a node i is the ratio of the total number Ei of edges that actually exist between all ki its nearest neighbors and the number ki(ki-1)/2 of all possible edges between them; that is, Ci=2Ei/[ki(ki-1)]. The clustering coefficient Ct of the whole network is the average of all individual Ci′s. For this network, we can obtain the exact expression of the clustering coefficient Ct. By construction, for any given node u having a degree k, there are Eu=3·(k-1)/2 links that actually exist among the neighbor nodes. So, one can see that there is a one-to-one corresponding relation between the coefficient C(k) of the node and its degree k: C(k)=3/k. This expression indicates that the local clustering scales as C(k)~k-1.Clearly, the number of nodes of degreek=3,7,11,…,4t-9,4t-5,4t-1, equals 9·2t-2-2,|L(t-2)|,|L(t-3)|,…,|L(2)|,|L(1)|,|L(1)|, respectively. The clustering coefficient Ct is given by the following:
(8)Ct=9·2t-2-2+9·∑i=2t-1((2t-1-i/(4i-1))+(9/(4t-1)))3·2t-2.
For infinite t, Ct approaches to a constant value of 0.8309, so the clustering is high.


## 3.3. Diameter

Besides degree distribution and clustering coefficient, average path length (APL) is another important parameter to characterize a network. APL is defined as the average number of edges along the shortest paths for all possible pairs of network nodes. People have found the small-world phenomenon in most real-life networks that behave with a short APL. For most network models, it is hard to obtain the analytic solution of APL. To demonstrate the short distance between any pair of nodes, we can adopt another parameter that is defined as the maximal communication delay in the network. If a network has a small diameter, then this network is undoubtedly with a short APL [19]. For the network proposed, we denote the diameter at iteration t as D(t). According to Figure 1, we can clearly know that D(1)=1 and D(2)=2. At each iteration, one can see that the diameter always lies between a pair of newly created nodes at this iteration because at each iterative edge we paste a complete graph M(1), so the diameter for the network proposed has the following simple formula, D(t)=t.Notice that the logarithm value of total number of nodes|V(t)| is approximately equal to tln2 for large t. Thus, the diameter grows logarithmically with the number of nodes and the average path length increases more slowly than ln|V(t)|.Based on the above discussions, our model is a deterministic small-world network because it is a sparse one with high clustering and short diameter, which satisfies the necessary property for small-world network.


## 4. Spanning Trees in the Network

In this section, we investigate the number of spanning trees in this network. Our aim is to derive the exact formula for the number of spanning trees and determine its entropy.LetM(t) be a planar graph generated by t steps. Since M(t) is symmetry, suppose that the edges v1v2, v1v3, and v2v3 are weighted by (xt-1,yt-1), where xt-1 denote the number of spanning trees of the subgraph F1 and yt-1 denote the number of spanning forests of the subgraph F1 with two components such v1 and v2 belong to distinct components. Let NST(t) be the number of spanning trees of M(t). Figure 3 gives all spanning trees of M(1) and Figure 4 gives all spanning forests with two components. Then, by Figure 2, we have
(9)NST(t)=9xt-12yt-1+6xt-1yt-12+yt-13.Figure 2
(Color online) the networkM(t). The solid links are iterated links, the dashed links are noniterated links.Figure 3
The number of spanning trees ofM(1) is 16. The solid link indicates that one node is connected to another node; the dashed link indicates that one node is not connected to another node.Figure 4
The number of spanning forests with two components ofM(1) is 8. The solid link indicates that one node is connected to another node; the dashed link indicates that one node is not connected to another node.According to Figures2, 3, and 4, we obtain the recursion relations between xt-1 and xt-2 as follows:
(10)xt-1=3xt-22+3yt-22+10xt-2yt-2,yt-1=2yt-22+6xt-2yt-2.
Let at-1=xt-1/yt-1, by (10) it follows that
(11)at-1=3·2t-1-22t-1,
with the initial condition a0=1. So, we get
(12)yt=∏i=0t-2‍(20-32i-2)2t-i-2.
By (9),
(13)NST(t)=9xt-12yt-1+6xt-1yt-12+yt-13.
Substituting (11) and (12) with (13), we have
(14)NST(t)=(10-32t-2)2∏i=0t-2‍(20-32i-2)3·2t-i-2.
From (14), together with (1), we determine the entropy of the number of spanning trees—an important quantity characterizing network structure—for M(t) as the limiting value [20, 21]:
(15)EST(t)=lim|Vt|→∞lnNST(t)|Vt|≈1.2109.The obtained entropy of spanning trees inM(t) can be compared to those found in other networks. In the pseudofractal fractal web [22], the entropy is 0.8959, a value less than 1, for the square lattice [23] and the two-dimensional Sierpinski gasket [24], their entropy of spanning trees is 1.16624 and 1.0486, respectively, and for the fractal scale-free lattice [25], the entropy is 1.0397. And all of them have the same average degree of 4. While in Apollonian network [26] having the average degree of 6, the entropy is 1.3540, the entropy of our model with average degree of 5 is between them.


## 5. Conclusion

In conclusion, we have investigated a simple model, which is constructed in a deterministic way. Then, we have presented an exhaustive analysis of many properties of the considered model and obtained the analytic solutions for most of the topological features, including degree distributions, clustering coefficient, and diameter. Finally, according to the special structure, we give a general algorithm to count the number of spanning trees of this model. Using the algorithm, we obtained entropies of spanning trees.



---

*Source: 795682-2013-12-07.xml*