# Topological Properties of a 3-Regular Small World Network

Authors: Huanshen Jia; Guona Hu; Haixing Zhao
Journal: Discrete Dynamics in Nature and Society
 (2014)

---

## Abstract

Complex networks have seen much interest from all research fields and have found many potential applications in a variety of areas including natural, social, biological, and engineering technology. The deterministic models for complex networks play an indispensable role in the field of network model. The construction of a network model in a deterministic way not only has important theoretical significance, but also has potential application value. In this paper, we present a class of 3-regular network model with small world phenomenon. We determine its relevant topological characteristics, such as diameter and clustering coefficient. We also give a calculation method of number of spanning trees in the 3-regular network and derive the number and entropy of spanning trees, respectively.


---

## Body

## 1. Introduction

In recent years, research on complex networks is in the ascendant. Complex networks by using graph theory and some methods of statistical physics can be used to capture and describe the evolution of the system mechanism, evolution pattern, and the overall behavior, which is one of the main causes of vigorous development on complex networks research [1].Construction of small-world networks that conform to the real system features not only has important theoretical significance but also has potential application value in deterministic way [2]. In this paper, we present 3-regular small-world network. We determine the relevant topological characteristics of the regular network, such as diameter and clustering coefficient. The results show that our model has a discrete exponential degree distribution, high clustering, and small diameter, which appears in a small-world effect. It is known that the number of spanning trees is an important quantity characterizing the reliability of a network. Because of the diverse applications in a number of fields, a lot of efforts have been devoted to the study of spanning trees. For example, in [3, 4] the author gave the accurate number of spanning trees in regular lattices. The number of spanning trees in a network can be obtained by directly calculating a related determinant corresponding to the network. We also give a method to calculate the number of spanning trees of the 3-regular network and derive the formulas. Based on the number of spanning trees we determine the entropy of its spanning trees.


## 2. Network Construction

The degreed(v) of a vertex v in G is the number of edges of G incident with v, each loop counting as two edges [5]. A graph G is k-regular if d(v)=k for all v∈V. In this section we describe a model of growing network, which is constructed in an iterative manner. We denote our network after t steps by Ut(t≥1). Then the network is constructed in the following way. For t=1, U1 is a graph that two nodes connect three edges. For t≥2, Ut is obtained from Ut-1 by adding two new nodes at step t=1; then two edges are increased; replicate it and connect four new nodes. The process is repeated till the desired graph order is reached; see Figure 1.Figure 1
Construction of the deterministic 3-regular networkUt, showing three steps of the iterative progress.Now we compute the size and order ofUt. Denote by nv(t) the total number of nodes in the network and by ne(v) the total number of edges in the network. It is easy to get that
(1)Δnv(t)=nv(t)-nv(t-1)=2Δnv(t-1),t>1.
Since nv(1)=2 and Δnv(2)=6, it follows that
(2)Δnv(t)=3×2t-1,nv(t)=3×2t-4.
Note that the addition of four new nodes leads to two new edges. Then
(3)Δne(t)=ne(t)-ne(t-1)=3Δnv(t-1)=9×2t-2.
As ne(1)=3, we have
(4)ne(t)=9×2t-1-6.


## 3. Relevant Characteristics

Due to the determinacy, the relevant characteristics of our model described above can be solved exactly. In the following we concentrate on the diameter and clustering coefficient.


### 3.1. Diameter

Small-world networks describe many real-life networks; that is, there is a relatively short distance between most pairs of nodes in most real-life networks and their average path length (APL) does not increase linearly with the system size but grows logarithmically with the number of nodes or slower. The average path length is the smallest number of links connecting a pair of nodes, averaged over all pairs of nodes [2]. The longest shortest path between all pairs of nodes is called diameter, which is one of the most important evaluation index because it characterizes the maximum communication delay in the network [6]. For most network models, it is hard to obtain the analytic solution of the average path length. So we will study the diameter instead of average path length. We denote the diameter at iteration t as D(t); then according to Figure 1, we can clearly know that D(1)=1 and D(2)=3. At each iteration for t>2, one can see that the diameter always lies between a pair of newly created nodes at this iteration. Thus the diameter for the network proposed has the following formula:
(5)D(t)=2t-1=ln⁡Ntln⁡2.So, the diameterD(t) grows logarithmically with the number of nodes. Because the average path length is smaller than diameter, the APL should increase more slowly. So our model satisfies the property for small-world networks.


### 3.2. Clustering Coefficient

Clustering is another important property of a complex network, which provides a measure of the local structure within the network [2]. The clustering coefficient indicates the connection relationship between a node and its neighborhood nodes. By definition, clustering coefficient Ci of a node i with degree ki is the ratio of the total number ei of existing edges between all its ki 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 C of the whole network is the average of all individual Ci′s; that is, C=(1/N)∑i=1NCi, where N is the number of nodes of the network. So the clustering coefficient for our network has the following simple formula. We know C=1 at step t=1. At each iteration t≥2, we have
(6)C=2t3·2t-4.
Obviously, C≈1/3 when t→∞; thus the clustering is high and also satisfies the properties for small-world networks.Based on the above discussion, we can conclude that our model is a deterministic small-world network, because it is sparse with small diameter and average path length and high clustering coefficient.


## 3.1. Diameter

Small-world networks describe many real-life networks; that is, there is a relatively short distance between most pairs of nodes in most real-life networks and their average path length (APL) does not increase linearly with the system size but grows logarithmically with the number of nodes or slower. The average path length is the smallest number of links connecting a pair of nodes, averaged over all pairs of nodes [2]. The longest shortest path between all pairs of nodes is called diameter, which is one of the most important evaluation index because it characterizes the maximum communication delay in the network [6]. For most network models, it is hard to obtain the analytic solution of the average path length. So we will study the diameter instead of average path length. We denote the diameter at iteration t as D(t); then according to Figure 1, we can clearly know that D(1)=1 and D(2)=3. At each iteration for t>2, one can see that the diameter always lies between a pair of newly created nodes at this iteration. Thus the diameter for the network proposed has the following formula:
(5)D(t)=2t-1=ln⁡Ntln⁡2.So, the diameterD(t) grows logarithmically with the number of nodes. Because the average path length is smaller than diameter, the APL should increase more slowly. So our model satisfies the property for small-world networks.


## 3.2. Clustering Coefficient

Clustering is another important property of a complex network, which provides a measure of the local structure within the network [2]. The clustering coefficient indicates the connection relationship between a node and its neighborhood nodes. By definition, clustering coefficient Ci of a node i with degree ki is the ratio of the total number ei of existing edges between all its ki 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 C of the whole network is the average of all individual Ci′s; that is, C=(1/N)∑i=1NCi, where N is the number of nodes of the network. So the clustering coefficient for our network has the following simple formula. We know C=1 at step t=1. At each iteration t≥2, we have
(6)C=2t3·2t-4.
Obviously, C≈1/3 when t→∞; thus the clustering is high and also satisfies the properties for small-world networks.Based on the above discussion, we can conclude that our model is a deterministic small-world network, because it is sparse with small diameter and average path length and high clustering coefficient.


## 4. Enumeration of Spanning Trees

A spanning tree of any connected network is defined as a minimal set of edges that connect every node. The enumeration of spanning trees in networks is a fundamental issue in mathematics [7–9], physics [3, 10], and other disciplines [11]. The problem of spanning trees is relevant to various aspects of networks, such as reliability [12, 13], optimal synchronization [14], and random walks [15]. In what follows we will examine the number of spanning trees in the 3-regular network.In order to calculate the number of spanning trees accurately, at first we build a new modelFt shown in Figure 2. We list the relationship between Ut and Ft in Figure 3. The number of the spanning trees and the spanning forests with two components such as u and v belongs to distinct components of Ft that are denoted by ST(Ft) and SF(Ft), respectively. Then the number of spanning trees of the original model U(t) can be obtained from the number of the spanning trees of Ft. Then we have the following relationship:
(7)ST(Ut)=2ST2(Ft-1)+2ST(Ft-1)·SF(Ft-1).Figure 2
Construction of the deterministic 3-regular networkFt, showing three steps of the iterative progress.Figure 3
The network modelsUt and Ft at step t.We calculate the number of spanning trees ofFt in the following. It is easy to obtain the relationship of ST(Ft) and ST(Ft-1) from (7). From Figure 4, one can see that the shape of the spanning trees of Ft includes two cases.Figure 4
The number of spanning trees ofFt.And the shape of the spanning forests with two components such asu and v belongs to distinct components of Ft that have five cases; see Figure 5.Figure 5
The number of spanning forests with two components ofFt.By considering the symmetric, it is not hard to get the recurrence relation of the number of spanning trees and spanning forests ofFt and Ft-1 in Figures 4 and 5:
(8)ST(Ft)=4ST2(Ft-1)+2ST(Ft-1)·SF(Ft-1),SF(Ft)=4ST2(Ft-1)+SF2(Ft-1)+4ST(Ft-1)·SF(Ft-1),
with the initial conditions ST(F1)=8 and SF(F1)=8. By computation, it follows that
(9)ST(Ft)SF(Ft)=4·(ST2(Ft-1)/SF2(Ft-1))+2·(ST(Ft-1)/SF(Ft-1))4·(ST2(Ft-1)/SF2(Ft-1))+4·(ST(Ft-1)/SF(Ft-1))+1.
Let at=ST(Ft)/SF(Ft); then at=2at-1/(2at-1+1) with a1=1. So at=2t-1/(2t-1).Noticing thatSF(Ft)=((2t-1)/2t-1)·ST(Ft), by (8), we know that
(10)ST(Ft)=23·2t-3·∏i=0t-2(1-12t-i)2i,(11)SF(Ft)=23·2t-2·(1-12t)·∏i=0t-2(1-12t-i)2i.Note thatNt′=3·2t-2 is the number of nodes of Ft. From (10) we determine the entropy of the spanning trees of Ft [7, 16] as follows:
(12)EST(Ft)=lim⁡t→∞ln⁡⁡ST(Ft)Nt′=ln⁡2≈0.6931.
From (10) and (11), together with (7), the number of spanning trees of Ut is given by
(13)ST(Ut)=2ST(Ft-1)(ST(Ft-1)+SF(Ft-1))=26·2t-1-5·[1+2(1-12t-1)]×[∏i=0t-3(1-12t-i-1)2i]2,
with the initial condition ST(U1)=1.So, the entropy of the spanning trees ofUt is given by
(14)EST(Ut)=lim⁡t→∞ln⁡⁡ST(Ut)Nt=ln⁡2≈0.6931.We can compare the entropy of the spanning trees ofUt with other networks [17, 18]. The entropy of the spanning trees in Koch networks with an average degree of 3 is 0.5493 [17], while the entropy of the spanning trees of our model is 0.6931.


## 5. Conclusions

In this paper, we proposed a class of deterministic regular small-world model which is constructed in an iterative manner and presented an exhaustive analysis of many properties of considered model. Then we obtained the analytic solutions for most of the topological features, including diameter and clustering coefficient. We also determined the number of spanning trees in the 3-regular small-world network. In addition, using the algorithm, we obtained the entropies of spanning trees.



---

*Source: 160740-2014-04-29.xml*