# Structure Properties of Koch Networks Based on Networks Dynamical Systems

Authors: Yinhu Zhai; Jia-Bao Liu; Shaohui Wang
Journal: Complexity
 (2017)

---

## Abstract

We introduce an informative labeling algorithm for the vertices of a family of Koch networks. Each label consists of two parts: the precise position and the time adding to Koch networks. The shortest path routing between any two vertices is determined only on the basis of their labels, and the routing is calculated only by few computations. The rigorous solutions of betweenness centrality for every node and edge are also derived by the help of their labels. Furthermore, the community structure in Koch networks is studied by the current and voltage characterizations of its resistor networks.


---

## Body

## 1. Introduction

The WS small-world models [1] and BA scale-free networks [2] are two famous random networks which stimulated an in-depth understanding of various physical mechanisms in empirical complex networks. The two main shortcomings are the uncertain creating mechanism and the huge computation in analysis. Deterministic models always have important properties similar to random models, such as being scale-free, having small-world behavior, and being highly clustered, and thus they could be used to imitate empirical networks appropriately. Hence, the study of the deterministic models of a complex network is increasing recently.Inspired by the simple recursive operation and techniques of plane filling and generating processes of fractals, several deterministic models [3–18] have been created imaginatively and studied carefully. The lines in the famous Koch fractals [19] are mapped into vertices, and there is an edge between two vertices if two lines are connected; the generated novel networks were named Koch networks [20]. This novel class of networks incorporates some key properties which characterize the majority of real-life networked systems: a power-law distribution with exponent in the range between 2 and 3, a high clustering coefficient, a small diameter, and average path length and degree correlations. Besides, the exact numbers of spanning trees, spanning forests, and connected spanning subgraphs in the networks are enumerated by Zhang et al. in [20]. All these features are obtained exactly according to the proposed generation algorithm of the networks considered [21–29]. The deterministic models of the complex network have a fixed shortest path, but how to mark it only by their labels is rarely researched [30–34].However, some important properties in Koch networks, such as vertex labeling, the shortest path routing algorithm, the length of the shortest path between arbitrary two vertices, the betweenness centrality, and the current and voltage properties of Koch resistor networks have not yet been researched. In this paper, we introduce an informative labeling and routing algorithm for Koch networks. By the intrinsic advantages of the labels, we calculate the shortest path distances between two arbitrary vertices in a couple of computations. We derive the rigorous solutions of betweenness centrality of every node and edge, and we also research the current and voltage characteristics of Koch resistor networks.


## 2. Koch Networks

The Koch networks are constructed in an iterative way. LetKm,t be the Koch networks after t∈N iterations, where m is a structural parameter.Definition 1.
The Koch networksKm,t are generated as follows: initially (t=0), Km,0 is a triangle. For t≥1, Km,t is obtained from Km,t-1 by adding m groups of vertices to each of the three vertices of every existing triangle in Km,t-1.Remark 2.
Each group consists of two new vertices, called son vertices. Both sons are connected to one another and to their father vertices; thus, the three vertices shape a new triangle.That is to say, we can getKm,t from Km,t-1 just by replacing each existing triangle in Km,t-1 with the connected clusters on the right-hand side of Figure 1.Figure 1
Iterative construction method for the Koch networks whenm=1,2,…,k.For the integrity of the article, we firstly introduce some important properties of Koch networks from [20]. The numbers of vertices and edges in networks Km,t are(1)Nt=23m+1t+1,(2)Et=33m+1t.By denotingΔv(t) as the numbers of nodes created at step t, we obtain Δv(t)=6m(3m+1)t-1; then, we also get that the degree distribution is P(k=2(m+1)t-i)=6m(3m+1)i-1/(2(3m+1)t+1); by substituting i=t-ln(k/2)/ln(m+1), for a-lnb/lnc=b-lna/lnc, and then (3m+1)-ln(k/2)/ln(m+1)=2ln(3m+1)/ln(m+1)k-ln(3m+1)/ln(m+1) and Pk=[6m(3m+1)t-1/2(3m+1)t+1]2ln(3m+1)/ln(m+1)k-ln(3m+1)/ln(m+1), in the infinite t limit, one can get(3)Pk=3m3m+12ln3m+1/lnm+1k-ln3m+1/lnm+1.Then, the exponent of degree distribution isγ=ln(3m+1)/ln(m+1), which belongs to the interval (1,2]. The average clustering coefficient C of the whole network is given by C=(1/Nt)∑r=0t‍(1/(ki(r)-1))Lu(r). When m increases from 1 to infinity, C increases from 0.82008 to 1. So, the Koch networks are highly clustered. The average path length (APL) approximates 4mt/(3m+1) in the infinite t, for APL is(4)dt=3m+5+24mt+24m+43m+1t33m+123m+1t+1~4mt3m+1.This formula shows that Koch networks exhibit small-world behavior. These properties indicate that Koch networks incorporate some key properties characterizing a majority of empirical networks: simultaneously scale-free, small-world, and highly clustered [20].


## 3. Vertex Labeling and Routing Algorithm by the Shortest Path

Definition 3.
All the vertices are located in three different subnetworks of the Koch network; the labeln(n=1,2, or 3) is used to denote the subnetworks.Remark 4.
Denote the three symmetrical subnetworks in Koch networksKm,t as Km,t1, Km,t2, and Km,t3. Then, Km,t is obtained just by linking the hub of three subnetworks directly. Therefore, the label n(n=1,2, or 3) is used to differentiate the vertices in the three different subnetworks Km,tn.A binary digits code is used to identify the precise position of a vertex inKm,tn and the exact time which is linked to Km,tn. The method is shown as follows.Definition 5.
Any vertex inKm,tn is marked with binary digits b1b2b3⋯bj, where b1=0 when j=1.  bj=0 or 1 when j=2,3,…,t. The 0 (or 1) in binary digits represents the notion that the new m vertices are grown from a son vertex (or father vertex) in a triangle. The length of the binary digit is the time at which the vertex is linked to Koch networks.Remark 6.
Because the initial networkKm,0 is a triangle, all the three initial vertices in it have no father vertices, so that the new vertices adding to the initial vertices should be marked with 0 at time j=1; that is, b1 must be 0.Then, we obtain the setS, by processing the binary digit codes of each vertex in Km,t.(5)S=Φ,b1,b1b2,b1b2b3,…,b1b2b3⋯bt.Remark 7.
The elementΦ in S implies that when t=0, the length of Φ is zero in Km,0.Definition5 implies that all the vertices, added to an existing vertex at step j, have the same binary codes b1b2b3⋯bj. Consequently, the number of vertices which are added to an existing father vertex at step j is given by(6)lmaxj=2mj-∑i=1jbim+1∑i=1jbi.So we need to mark the vertices of this group with an extra integerl(j)∈[1,lmax(j)] for they all have the same binary codes b1b2b3⋯bj and the same group indicator n.Definition 8.
An integerl(j) is used to identify the precise position, increasing by clockwise direction, of a vertex in the group which is added to a father vertex at the iteration j.Remark 9.
Becausel(j) increases from 1 and is positioned after the binary blue code, a dot is needed between l(j) and the binary code to avoid confusion.In sum, the arbitrary vertex which is added toKm,t at step j is labeled with nb1b2b3⋯bj·l(j). The code n denotes which subnetwork of Km,tn the vertex belongs to; the binary digit b1b2b3⋯bj indicates the father vertex which is linked to this new vertex; the positive integer l, which increases in a clockwise manner, is used to mark the precise position around a father vertex.Define the setM(j) as the label set of the vertices added to networks Km,t at step j. It is apparent that M(0)={1,2,3} and M(j)={nb1b2b3⋯bj·l(j)}. Let the set Lm,t represent the labels of all the vertices in Km,t; we obtain(7)Lm,t=⋃j=1tMj.For example, Figure2 demonstrates the vertex labeling of all the vertices in Koch network K2,2. In the following sections, we deduced some important properties of Koch networks just on the basis of the labels of their vertices.Figure 2
The labeling of Koch networkK2,2 when m=2 and t=0,1,2. The blue dots are initial vertices; the green squares are vertices adding at t=1; the red dots denote vertices adding to the network at t=2.Property 1.
Each vertex has a unique label.Suppose an arbitrary vertex is labeled withnb1b2b3⋯bj·l(j). Firstly, from the labeling algorithm, the labels of any pair of vertices are different from each other. Secondly, the size of Lm,t equals the size of Koch networks. So, we deduced that any vertex has a unique label.Assume thatnb1b2b3⋯bi·lv(i) is the label of arbitrary vertex v which is added to Km,t at step i, and let the set A(v) denote the labels of all neighbor vertices of v. By comparing the vertex’s degree between v and its neighbors, A(v) can be divided into three subsets: Ae(v), Al(v), and Ah(v), the vertices in which sets have a degree equal to, lower than, and higher than the degree of v, respectively. That is to say, A(v)=Ae(v)∪Al(v)∪Ah(v).Property 2.
A
e
(
v
)
=
{
n
b
1
b
2
b
3
⋯
b
i
·
l
e
(
i
)
}, where vertex degree le(i)=lv(i)+1 if mod(lv(i),2)=1, or le(i)=lv(i)-1 if mod(lv(i),2)=0.According to the proposed algorithm, at each step, any father vertex addsm groups of vertices, with each group consisting of two vertices. Thus, these latter, together with the father, are linked to each other and form a new triangle. Therefore, the two vertices in the same group are neighbors which are linking directly and have the same degrees. By the labeling method, the m group vertices are labeled with the integers l(i) which increase from 1 to lmax(i) in a clockwise manner. So, nb1b2b3⋯bi·(lv(i)+1) is the neighbor of nb1b2b3⋯bi·lv(i) with the same degrees if mod(lv(i),2)=1, or nb1b2b3⋯bi·(lv(i)-1) is the neighbor if mod(lv(i),2)=0.Property 3.
A
l
(
v
)
=
{
n
b
1
b
2
b
3
⋯
b
i
0
·
l
v
(
i
+
1
)
,
n
b
1
b
2
b
3
⋯
b
i
0
·
l
v
(
i
+
2
)
,
…
,
n
b
1
b
2
b
3
⋯
b
i
0
·
l
v
(
t
)
}
.From the labeling algorithm, the vertices with longer binary codes have lower degrees than the vertices with shorter binary codes. In addition, the0 or 1 in binary codes indicates that the new vertex is growing from the two son vertices or father vertex in each triangle. Hence, we can understand that the vertices, adding to v at steps i+1,i+2,…,t, are labeled with nb1b2b3⋯bi0·lv(i+1),nb1b2b3⋯bi0·lv(i+2),…,nb1b2b3⋯bi0·lv(t).Let⌈x⌉ be the function returning the biggest integer just smaller than real number x.Property 4.
A
h
(
v
)
=
{
n
b
1
b
2
b
3
⋯
b
j
-
1
·
⌈
l
v
(
i
)
/
2
m
(
m
+
1
)
∑
k
=
j
+
1
i
‍
b
k
⌉
}.We remark thatnb1b2b3⋯bi·lv(i) is the label of an arbitrary vertex v. From construction, we obtain that the label of the only father vertex of v depends on the composition in binary codes b1b2b3⋯bi of vertex v. Suppose the first 0 in b1b2b3⋯bi, from the right to the left side, is bj. By the construction method, it is clear that v is linked to a vertex with higher degree which is labeled with nb1b2b3⋯bj-1·⌈lv(i)/2m(m+1)∑k=j+1i‍bk⌉. In particular, if the first 0 of b1b2b3⋯bi is b1, the vertex with a higher degree is exactly a hub of Koch networks which is labeled with n=1,2 or 3.The deterministic models of the complex network have a fixed shortest path, but how to mark it only by their labels is rarely researched [15]. The following rules are used to determine the shortest path routing between any two vertices by the help of their labels. Let nb1b2b3⋯bi·l and n′b1′b2′b3′⋯bj′·l′ be the labels of arbitrary pair of vertices in Km,t.Algorithm 10.
The shortest path routing algorithm in Koch networks is discussed.
Ifn≠n′, find out, by Property 4, all the higher degree neighbors of the two vertices, until the hubs n and n′. Thus, by linking all vertices of them, we obtained the shortest path.
Ifn=n′, the first step is to mark higher degree neighbors until the common highest degree vertex by Property 4 and then judge whether the two second highest degree vertices are neighbors or not by Property 3; if not, the shortest path is connected to all higher degree neighbors until the highest degree vertex; if so, the shortest path is just the same as above, only eliminating the highest degree vertex.Ifn≠n′, the two vertices are located in different subnetworks Km,nn and Km,nn′. The routing by the shortest path between two vertices in different subsets is ascertained as follows. First, we obtain the neighbors which have higher degrees recursively by Property 4, until the hubs n and n′. Then, we connect all of them in turn; this is the only shortest path between two vertices.Ifn=n′, it is clear that the shortest path is located in the same subnetworks Km,tn. We find out the neighbors with higher degree by using Property 4 repeatedly, until the common highest degree vertex. Then, we judge whether the two second highest degree vertices are neighbors or not by Property 3. If they are not neighbors, we determine the shortest path as above by linking all the higher degree vertices until the highest vertex, by the help of the construction method of Koch networks. Else, if they are neighbors, the shortest path is the same as above by excluding the highest degree vertex.The shortest path between any pair of vertices inKm,t is obtained after no more than 2t times of integral computations and modulo operations by the help of the labeling method and routing algorithm proposed in this research. That is to say, the shortest path routing and the shortest distance between an arbitrary pair of vertices in Koch networks can be dealt with in few computations.


## 4. Betweenness Centrality

Betweenness centrality is originated from the analysis of the importance of the individual in social networks, including the betweenness of any vertex and edge in networks. If the betweenness of a node/edge is bigger, then the node/edge in the social network is more important [2]. The betweenness of a vertex for undirected networks is given by the expression(8)gv=∑s≠v≠tσstvNt-1Nt-2/2, where σst(v) is the number of the shortest paths passing through v. The computation of betweenness is very difficult in most networks. Fortunately, the betweenness of Koch networks can be derived qualitatively and quantitatively by the help of their labels in Koch networks, which is shown as follows.Suppose that an arbitrary vertexv, which is adding to Km,t at time i, is labeled with nb1b2b3⋯bi·lv(i). The vertices in Km,t can be divided into three parts: the vertex v, the offspring vertices which are connected to v directly and indirectly after step i (they all have lower degrees than v), and the other vertices in Km,t. Assume that the number of the second part vertices is Nl, and it can be worked out that Nl=(2(3m+1)t-i-2)/3 by (1). Apparently, the number of the third parts is Nt-Nl-1. For the shortest path routing between any two vertices is unique, we get that ∑s≠v≠l‍σst(v)=Nl(Nt-Nl-1)/2. Substitute this equation and (1) into (8); the betweenness of a vertex which is labeled with nb1b2b3⋯bi·lv(i) is given by(9)gv=23m+1t-i-133m+1t-3m+1t-i-133m+1t23m+1t-1.Fori=t-ln(k/2)/ln(m+1) and a-ln(b)/ln(c)=b-ln(a)/ln(c), we obtain the formula g(v)~c1kln(3m+1)/ln(m+1) which holds with c1>0. Therefore, the vertex betweenness in Koch networks is exponentially proportional to the vertex’s degree with an exponent γ=ln(3m+1)/ln(m+1) belonging to the interval (1,2].The betweenness of edges can also be deduced in a similar way. Notee as the edge between any two neighbor vertices v and u which are labeled with nb1b2b3⋯bi·lv(i) and n′b1′b2′⋯bj′·lu′(j). Without loss of generality, assume that vertex u has higher degree than v. So the label of u belongs to the set Ah(v) by Property 4. Suppose a triangle is shaped by three vertices: v, u, and w. Therefore, w has the same degree as v. Then, Koch network Km,t can be divided into three parts: the lower degree vertices linking to v directly or indirectly, the vertices connected to u directly or indirectly, and the lower degree vertices adding directly or indirectly, respectively. Correspondingly, the label set Lm,t falls into three subsets: Ael(v), Aother(u), and Ael(w). The relationship of these four label sets is shown as follows:(10)Lm,t=Aelv∪Aotheru∪Aelw.The size ofAel(v) is derived as Nel(v)=(2(3m+1)t-i+1)/3. From the symmetry of vertices v and w, we obtain Nel(v)=Nel(w). Then, we get that (11)Notheru=Nt-Nelv-Nelw=23m+1t-i+1-23m+1t-i+13 from the construction of Koch networks. For the shortest path between any two vertices is unique, then the betweenness of the edge e is defined as follows:(12)ge=NelvNotheru/2Nt-1Nt-2/2.Therefore, the betweenness centrality of the edgee is given by(13)ge=23m+1t-i+163m+1t-43m+1t-i+1183m+1t23m+1t-1. Therefore, the edge betweenness holds g(e)~c2kln(3m+1)/ln(m+1), where c2>0. The edge betweenness is also exponentially proportional to the degree of the lower degree vertex v, and the exponent is γ=ln(3m+1)/ln(m+1) belonging to the interval (1,2]. In a word, the betweenness of an edge is exponentially proportional to the time of adding to Koch networks.


## 5. Resistor Networks

The communities in networks are the groups of vertices within which the connections are dense but between which the connections are sparser. A community detection algorithm which is based on voltage differences in resistor networks is described in [35, 36]. The electrical circuit is formed by placing a unit resistor on each edge of the network and then applying a unit potential difference (voltage) between two vertices chosen arbitrarily. If the network is divided strongly into two communities and the vertices in question happen to fall in different communities, then the spectrum of voltages on the rest of the vertices should show a large gap corresponding to the border between the communities. For more work on resistance distance and resistor networks, the readers are referred to the recent papers [37, 38].Moreover, the information in complex networks not always flows in the shortest path, so that the evaluation of the betweenness of nodes can also have other principles, such as the current-flow betweenness. Consider an electrical circuit created by placing a unit resistor on every edge of the network. One unit of current is injected into the network at a source vertex and one unit is extracted at a target vertex, so that the current in the network as a whole is conserved. Then, the current-flow betweenness of a vertex is defined as the amount of current that flows through in this setup; the average of the current flow over all source-target pairs is shown as follows:(14)gv=∑s<tIstvNtNt-1/2, where Ist(v) is the current over vertex v.After placing a unit resistor on every edge inKm,t, insert one unit of current or voltage at source vertex v0 labeled with nb1b2b3⋯bi·l, and further choose the target vertex vm+1 with labels n′b1′b2′⋯bj′·l′. Assume the shortest path is from v0 to vertices v1,…,vm until vm+1. Therefore, the shortest distance is m+1. The property of Koch resister networks is described as follows.Property 5.
The voltages of vertices{vi} shape an arithmetic progression from 1 to 0, and the step length is 1/(m+1). The voltage of vertices {vk¯} decreases from 1-1/(2m+2) to 1/(2m+2), but the step length is also 1/(m+1).Ifn≠n′, from Algorithm 10, there are two hubs vj=n and vj+1=n′ with the highest degree in the shortest path. Hence, the vertices which are affected by unit voltage are {vi}∪{vk¯}, where i=0,1,2,…,m+1,  k=0,1,2,…,j-1,j+1,…,m+1, vi¯ is the neighbor of vi with the same degree, and apparently vj+1¯ is the other hub. The edges between vertices {vi}∪{vk¯} formed m+1 triangles which are in series and the common vertices are {vi}, so that the unit current only passes through these edges in whole Koch networks Km,t.Ifn=n′ and there are two highest degree vertices, noting vj and vj+1, in the shortest path, hence the unit voltage can only affect vertices {vi}∪{vk¯} in Km,t, where i=0,1,2,…,m+1, k=0,1,2,…,j-1,j+1,…,m+1, and vi¯ is the neighbor of vi with the same degree too, but vj+1¯ is a higher degree neighbor which is linked with vj and vj+1 directly; the unit current also flows through the edges in m+1 triangles which are in series.Ifn=n′ but there are the only highest degree vertices, denoting vj, in the shortest path, the unit voltage impacts vertices {vi}∪{vk¯}, where i=0,1,2,…,m+1, k=0,1,2,…,j-1,j+1,…,m+1, and vi¯ is the neighbor of vi with the same degree; the behavior of unit current is the same as the two conditions above.Property 6.
The current stream from the edges which are linked to the vertices{vi} is 2/3, while the current passing though the edges linking to {vk¯} is the remaining 1/3.The property can be proved similarly as the proof of Property5 by the help of the forming mechanism of Koch resistor networks.In brief, the spectrum of voltages on the vertices shows that Koch networks have no significant community structure in spite of having massive triangles between nodes. Also, the current flow can gauge well the importance of edges betweenness in Koch networks in information flowing which is not flowing only by the shortest path.


## 6. Conclusions

The family of Koch networks, with high clustering coefficient, scale-free, small diameter and average path length, and small-world properties, successfully reproduces some remarkable characteristics in many nature and man-made networks and has special advantages in the research of some physical mechanisms such as random walk in complex networks.We provided an informative vertex labeling method and produced a routing algorithm for Koch networks. The labels include full information about any vertices precise position and the time adding to the networks. By the help of labels, we marked the shortest path routing and the shortest distance between any pair of vertices in Koch networks. The needed computation is just no more than2t times of integral computations and modulo operations. Moreover, we derived the rigorous solution of betweenness centrality of every vertex and edge in Koch networks, and we also researched the current and voltage characteristics in Koch networks on the basis of their labels.By the help of our results, in contrast with more usually probabilistic approaches, the deterministic Koch models will have unique virtues in understanding the underlying mechanisms between dynamical processes (random walk, consensus, stabilization, synchronization, etc.) to the structure of complex networks by the new method of rigorous derivation.



---

*Source: 6210878-2017-03-06.xml*