# Graph Concatenations to Derive Weighted Fractal Networks

Authors: Zhanqi Zhang; Yingqing Xiao
Journal: Complexity
 (2020)

---

## Abstract

Given an initial weighted graphG0, an integer m>1, and m scaling factors f1,…,fm∈0,1, we define a sequence of weighted graphs Gkk=0∞ iteratively. Provided that Gk−1 is given for k≥1, we let Gk−11,…,Gk−1m be m copies of Gk−1, whose weighted edges have been scaled by f1,…,fm, respectively. Then, Gk is constructed by concatenating G0 with all the m copies. The proposed framework shares several properties with fractal sets, and the similarity dimension dfract has a great impact on the topology of the graphs Gk (e.g., node strength distribution). Moreover, the average geodesic distance of Gk increases logarithmically with the system size; thus, this framework also generates the small-world property.


---

## Body

## 1. Introduction

For the past two decades, various networked systems and their models have been studied intensively by researchers from many different scientific fields. Examples include neural networks, protein networks, metabolic networks, phone call networks, the Internet and the World Wide Web, social networks of acquaintance, and many others. The graph models of networked systems such as these often consist of millions or even billions of nodes and have large-scale statistical properties. Due to the abundance of systems of this sort and the increased computing powers, complex networks are currently very hot and attractive research objects, and they define a powerful framework for describing and analyzing the real-world networks. In comparison with regular networks and random networks, the structure of complex networks is irregular, complex, and usually dynamically evolving in time. Complex networks possess all or part of the remarkable properties including small-world effect, scale-free property, correlations in the node degrees, and community structure, which reproduce topological properties of most of the real-world networks considered. One can refer to [1–5] for a detailed exposition of the theory of complex networks.In the study of complex networks, one of the topics is to construct models mimicking real-world networks. Some construction algorithms are based on the fixed fractal sets or merely the ideas taken from the fractal construction. In [6], Barabási et al. presented a model that constructs a sequence of networks in a deterministic fashion and proved the model generates the scale-free property. In [7], Zhang et al. constructed a class of networks named incompatibility networks based on the structure of the Sierpiński gasket and showed that the networks are scale-free and small-world. In [8], the authors proposed a method converting the Koch curve into a family of deterministic networks called Koch networks, which also possess general properties observed in real-world networks. Inspired by the works of mapping fractal sets into complex networks and in order to generalize the former constructions, Carletti and Righi defined a class of weighted complex networks via an explicit algorithm in [9]. Their framework shares several properties with fractal sets, and the procedure of constructing the networks is similar to constructing a sequence of sets by the iterated function system [10]. They hereby called this framework weighted fractal networks, WFNs for short. Recently, in [11], Li et al. introduced a method of generating a family of growing symmetrical tree networks Tkk=0∞ from a symmetrical tree T0, where Tk is constructed by replacing each edge of Tk−1 with a reduced scale of T0. They studied the asymptotic behavior of the average geodesic distance of Tk. In [12], Xi and Ye did a similar work, whereas the initial graph turns into a directed tree.In this paper, we introduce a method which generates a class of weighted graphs based on a weighted graph and some parameters. Our framework is different from the construction in [9]; it, however, also shares some properties with fractal sets, hereby named weighted fractal networks. As for the model introduced in [9], the topological properties of the networks are mainly determined by the scaling factor, the number of copies, and the order and size of the initial network, whereas other topologies of the initial network have only a small impact on the properties of their framework. In our case, the initial graph plays a dominant role in the construction and topologies of the weighted graphs. In Section 2, we will introduce the model and show some applications of it. In Section 3, we study several topological properties of the graphs, including the average weighted geodesic distance and the node strength distribution. We found that the average geodesic distance increases logarithmically with the system size; thus, the weighted fractal networks generate the small-world property. Besides, the similarity dimension plays a relevant role in the topologies of the weighted fractal networks.


## 2. Weighted Fractal Networks

### 2.1. The Model

Let us fix a positive integerm>1 and m positive real numbers f1,…,fm∈0,1. Let G0=VG0,EG0 be an initial weighted graph satisfying three conditions: G0 has no loops or parallel edges; G0 is connected; and the cardinality of nodes in G0, denoted by n, satisfies n=#VG0>m. One of the nodes has been labeled as the beginning node and is denoted by s0. m other nodes have been labeled as end nodes and are denoted by v1,v2,…,vm, respectively.We construct a sequence of weighted graphsGkk=0∞ iteratively. G0 is given. We let G01,…,G0m be m copies of G0. For each i∈1,…,m, weighted edges of G0i have been scaled by fi, and the node in the G0i image of the beginning node s0 is denoted by s0i. Concatenate G0 with G0i by merging node vi and node s0i into a single new node, denoted by vi1, for i=1,…,m. Then, we obtain the new graph G1, of which G0 is a subgraph. s0 in the new graph is also labeled as a beginning node, and we denote it by s1 when talking about G1.SupposeGk−1 is given, we define Gk similarly. Let Gk−11,…,Gk−1m be m copies of Gk−1. For each i∈1,…,m, weighted edges of Gk−1i have been scaled by fi, and the node in the Gk−1i image of the beginning node sk−1 is denoted by sk−1i. Concatenate G0 with Gk−1i by merging node vi and node sk−1i into a single new node, denoted by vik, for i=1,…,m. We obtain graph Gk. s0 in the new graph Gk is labeled as a beginning node and is also denoted by sk. Two examples are stated for illustration (see Figures 1 and 2).Figure 1
From the left to the right,G0, G1, and G2. G0 is a 5-cycle, whose edges have weight 5. For each i∈0,1,2, the red point of Gi denotes the beginning node, and the blue points of Gi denote the end nodes. Set f1=f2=f3=0.6. Thickness of the lines reproduces edge weights: the thicker the line, the larger the weight.
(a)(b)(c)Figure 2
The graphical representations of (a)G0 and (b) G3. G0 has 2 end nodes and 4 edges of weight 5. We set f1=0.9 and f2=0.7. Thickness of the lines reproduces edge weights: the thicker the line, the larger the weight.
(a)(b)The similarity dimensiondfract of the WFN is the real number satisfying(1)∑i=1mfidfract=1.Iff1=⋯=fm=f∈0,1, then dfract=−logm/logf.Our framework supplies a general way of constructing complex networks with respect to plenty of fractal sets, e.g., Sierpinski gasket, uniform Cantor set [13], generalized Koch curves [14], and Cantor dust [15]. Roughly speaking, using this framework, we could construct complex networks with remarkable properties (e.g., small-world effect and scale-free property) from a lot of self-similar sets, for which the iterated function systems satisfy the open set condition. The approach provides an alternative way to study fractals via the theory of complex networks, and vice versa.


### 2.2. Generalized Koch Curve

Let us fix a positive integerp∈ℕ. We define an operation as follows: partition each existing line segment into 2p+1 segments, which are consecutively numbered 1,…,2p+1 from one endpoint to the other; replace each even-numbered segment by the other two sides of the equilateral triangle based on the removed segment. Let Hp,0 be a line segment of unitary length. For t>0, we obtain Hp,t by performing the operation on Hp,t−1. The sequence of curves Hp,t approaches a limit curve, called the generalized Koch curve. With respect to this fractal set, we set m=3p+1 and f1=⋯=f3p+1=1/2p+1. Obviously, the similarity dimension dfract=log3p+1/log2p+1 is equal to the Hausdorff dimension of the generalized Koch curve. The initial weighted graph G0 is as follows: G0 consists of 3p+2 nodes, one of which has been labeled the beginning node, and the others have been labeled end nodes. Each end node and the beginning node are adjacent with an edge of unitary weight. There is a one-to-one mapping from the segments of Hp,1 to the end nodes of G0. Two end nodes are adjacent if and only if their inverse images in Hp,1 are connected. The edges that join two end nodes have a weight 1/2p+1. Figure 3 shows the structure of H2,2 and the corresponding initial graph G0.Figure 3
(a) The first two generations of the construction for the generalized Koch curve withp=2. (b) The initial weighted graph G0.
(a)(b)


### 2.3. Cantor Dust

Define an operation as follows: divide each existing square into 16 identical squares, which are consecutively numbered1,…,16 from left to right and from top to bottom. Set A=2,3,5,8,9,12,14,15. Remove the squares whose numbers belong to A, and we obtain 5 squares. Let S0 be a unit square. For t>0, we obtain St by performing the operation on St−1. The limit set of the sequence Stt=0∞ is Cantor dust. With respect to this fractal set, we set m=5, f1=⋯=f4=1/4, and f5=1/2. Once again, the similarity dimension and the Hausdorff dimension of the Cantor dust coincide. The initial weighted graph G0 is as follows: G0 consists of 14 nodes, one of which has been labeled the beginning node, and 5 others have been labeled end nodes. Assume VG0=s0,v1,…,v5,u1,…,u8. The beginning node s0 and other nodes are adjacent with an edge of unitary weight. For each node x∈VG0\s0,v5, x is connected to v5 with an edge of weight 1/4+1/8. There is a one-to-one mapping ψ from VG0\s0,v5 to the squares in S1 whose numbers belong to A∪1,4,13,16 satisfying ψu1,…,u8=A. The nodes in VG0\s0,v5 are connected to one another with edges of weight 1/8+1/8 if their images in S1 are connected (see Figure 4 for illustration).Figure 4
InG0, black lines denote edges of weight 1, blue lines denote edges of weight 0.375, and orange lines denote edges of weight 0.25. (a) S1. (b) S2. (c) G0.
(a)(b)(c)Due to the self-similarity of the weighted fractal networks and the scaling factorsf1,…,fm∈0,1, our approach may have some applications in the spread of some infections, connection of the social communication, airflows in mammalian lungs, phone call networks, and so on. The framework also provides an alternative to explain the frequent appearance of fractal phenomena in nature and society.


## 2.1. The Model

Let us fix a positive integerm>1 and m positive real numbers f1,…,fm∈0,1. Let G0=VG0,EG0 be an initial weighted graph satisfying three conditions: G0 has no loops or parallel edges; G0 is connected; and the cardinality of nodes in G0, denoted by n, satisfies n=#VG0>m. One of the nodes has been labeled as the beginning node and is denoted by s0. m other nodes have been labeled as end nodes and are denoted by v1,v2,…,vm, respectively.We construct a sequence of weighted graphsGkk=0∞ iteratively. G0 is given. We let G01,…,G0m be m copies of G0. For each i∈1,…,m, weighted edges of G0i have been scaled by fi, and the node in the G0i image of the beginning node s0 is denoted by s0i. Concatenate G0 with G0i by merging node vi and node s0i into a single new node, denoted by vi1, for i=1,…,m. Then, we obtain the new graph G1, of which G0 is a subgraph. s0 in the new graph is also labeled as a beginning node, and we denote it by s1 when talking about G1.SupposeGk−1 is given, we define Gk similarly. Let Gk−11,…,Gk−1m be m copies of Gk−1. For each i∈1,…,m, weighted edges of Gk−1i have been scaled by fi, and the node in the Gk−1i image of the beginning node sk−1 is denoted by sk−1i. Concatenate G0 with Gk−1i by merging node vi and node sk−1i into a single new node, denoted by vik, for i=1,…,m. We obtain graph Gk. s0 in the new graph Gk is labeled as a beginning node and is also denoted by sk. Two examples are stated for illustration (see Figures 1 and 2).Figure 1
From the left to the right,G0, G1, and G2. G0 is a 5-cycle, whose edges have weight 5. For each i∈0,1,2, the red point of Gi denotes the beginning node, and the blue points of Gi denote the end nodes. Set f1=f2=f3=0.6. Thickness of the lines reproduces edge weights: the thicker the line, the larger the weight.
(a)(b)(c)Figure 2
The graphical representations of (a)G0 and (b) G3. G0 has 2 end nodes and 4 edges of weight 5. We set f1=0.9 and f2=0.7. Thickness of the lines reproduces edge weights: the thicker the line, the larger the weight.
(a)(b)The similarity dimensiondfract of the WFN is the real number satisfying(1)∑i=1mfidfract=1.Iff1=⋯=fm=f∈0,1, then dfract=−logm/logf.Our framework supplies a general way of constructing complex networks with respect to plenty of fractal sets, e.g., Sierpinski gasket, uniform Cantor set [13], generalized Koch curves [14], and Cantor dust [15]. Roughly speaking, using this framework, we could construct complex networks with remarkable properties (e.g., small-world effect and scale-free property) from a lot of self-similar sets, for which the iterated function systems satisfy the open set condition. The approach provides an alternative way to study fractals via the theory of complex networks, and vice versa.


## 2.2. Generalized Koch Curve

Let us fix a positive integerp∈ℕ. We define an operation as follows: partition each existing line segment into 2p+1 segments, which are consecutively numbered 1,…,2p+1 from one endpoint to the other; replace each even-numbered segment by the other two sides of the equilateral triangle based on the removed segment. Let Hp,0 be a line segment of unitary length. For t>0, we obtain Hp,t by performing the operation on Hp,t−1. The sequence of curves Hp,t approaches a limit curve, called the generalized Koch curve. With respect to this fractal set, we set m=3p+1 and f1=⋯=f3p+1=1/2p+1. Obviously, the similarity dimension dfract=log3p+1/log2p+1 is equal to the Hausdorff dimension of the generalized Koch curve. The initial weighted graph G0 is as follows: G0 consists of 3p+2 nodes, one of which has been labeled the beginning node, and the others have been labeled end nodes. Each end node and the beginning node are adjacent with an edge of unitary weight. There is a one-to-one mapping from the segments of Hp,1 to the end nodes of G0. Two end nodes are adjacent if and only if their inverse images in Hp,1 are connected. The edges that join two end nodes have a weight 1/2p+1. Figure 3 shows the structure of H2,2 and the corresponding initial graph G0.Figure 3
(a) The first two generations of the construction for the generalized Koch curve withp=2. (b) The initial weighted graph G0.
(a)(b)


## 2.3. Cantor Dust

Define an operation as follows: divide each existing square into 16 identical squares, which are consecutively numbered1,…,16 from left to right and from top to bottom. Set A=2,3,5,8,9,12,14,15. Remove the squares whose numbers belong to A, and we obtain 5 squares. Let S0 be a unit square. For t>0, we obtain St by performing the operation on St−1. The limit set of the sequence Stt=0∞ is Cantor dust. With respect to this fractal set, we set m=5, f1=⋯=f4=1/4, and f5=1/2. Once again, the similarity dimension and the Hausdorff dimension of the Cantor dust coincide. The initial weighted graph G0 is as follows: G0 consists of 14 nodes, one of which has been labeled the beginning node, and 5 others have been labeled end nodes. Assume VG0=s0,v1,…,v5,u1,…,u8. The beginning node s0 and other nodes are adjacent with an edge of unitary weight. For each node x∈VG0\s0,v5, x is connected to v5 with an edge of weight 1/4+1/8. There is a one-to-one mapping ψ from VG0\s0,v5 to the squares in S1 whose numbers belong to A∪1,4,13,16 satisfying ψu1,…,u8=A. The nodes in VG0\s0,v5 are connected to one another with edges of weight 1/8+1/8 if their images in S1 are connected (see Figure 4 for illustration).Figure 4
InG0, black lines denote edges of weight 1, blue lines denote edges of weight 0.375, and orange lines denote edges of weight 0.25. (a) S1. (b) S2. (c) G0.
(a)(b)(c)Due to the self-similarity of the weighted fractal networks and the scaling factorsf1,…,fm∈0,1, our approach may have some applications in the spread of some infections, connection of the social communication, airflows in mammalian lungs, phone call networks, and so on. The framework also provides an alternative to explain the frequent appearance of fractal phenomena in nature and society.


## 3. Topological Properties

In this section, we characterize the topology of the weighted graphsGk for all k≥0. Let Nk be the cardinality of nodes in Gk and Ek be the cardinality of edges in Gk. One can easily verify that(2)Nk=mk+1−1m−1n−mk−1m−1m,Ek=mk+1−1m−1E0.The degree of nodev in graph G is the cardinality of edges of G incident with v. The sum of degrees of all nodes in G equals to 2#EG ([16], Theorem 1.1). Note that, for any graph G, we denote the class of all nodes in G by VG and denote by EG the class of all edges in G. The cardinal numbers of VG and EG are called the order and size of G, respectively. Thus, the asymptotic behavior of the average degree of Gk satisfies(3)2EkNk=2mk+1−1E0mk+1n−1−n−m⟶k⟶∞2E0n−1.


### 3.1. Average Weighted Geodesic Distance

Letdkx,y denote the weighted geodesic distance between nodes x and y in Gk. Set d⋅,⋅=d0⋅,⋅ for convention. Define(4)Λk=∑x,y∈Gkdkx,y,fork≥0.Thus, the average weighted geodesic distance ofGk is given by(5)δk=ΛkNkNk−1.Fork≥0, we define(6)λk=∑x∈Gkdkx,sk,i.e., the sum of all weighted geodesic distances of the nodes in Gk from the beginning node sk. Define F=∑i=1mfi. Set(7)λ0′=∑i=1mdvi,s0,λ0″=λ0−λ0′.Lemma 1.
Fork≥1, we have(8)λk=Fkλ0+∑t=0k−1Fk−1−tNtλ0′+∑t=0k−1Ftλ0″.
The asymptotic behavior ofλk satisfies(9)limk⟶∞λkmk=mn−1m−1m−Fλ0′.Proof.
By the construction ofGk, we obtain that(10)λk=∑i=1mfiλk−1+Nk−1dvi,s0+λ0″=Fλk−1+Nk−1λ0′+λ0″.
By direct calculation, we obtain equation (8).
SinceF<m, we have(11)limk⟶∞Fkλ0+∑t=0k−1Ftλ0″mk=0.
Thus, in order to prove equation (9), it suffices to prove(12)limk⟶∞∑t=0k−1Fk−1−tNtmk=mn−1m−1m−F.
However,(13)limk⟶∞∑t=0k−1Fk−1−tNtmk=1Flimk⟶∞∑t=0k−1Nt/Ftm/Fk=1Flimk⟶∞Nk−1/Fk−1m/Fk−m/Fk−1=1m−Flimk⟶∞Nk−1mk−1=mn−1m−1m−F.
The second equality uses O. Stolz’s formula. The proof is complete.
Recall the construction algorithm. In order to obtainGk with k≥1, we concatenate G0 with Gk−1i for all i∈1,…,m; thus, it is proper to regard Gk−1i as a subgraph of Gk. Set V∗=VG0\v1,…,vm.
Fori=1,…,m, we can decompose the sum ∑x∈Gk−1i∑y∈Gkdkx,y into three terms:(14)∑x,y∈Gk−1idkx,y+∑j=1j≠im∑x∈Gk−1i,y∈Gk−1jdkx,y+∑x∈Gk−1i,y∈V∗dkx,y,and use the scaling mechanism for the edges and with the construction of Gk(15)=fiΛk−1+F+m−2fiNk−1λk−1+Nk−12αi+n−mfiλk−1+Nk−1βi,where(16)αi=∑j=1mdvi,vj,βi=∑y∈V∗dvi,y.
Similarly, we decompose the sum∑x∈V∗∑y∈Gkdkx,y into two terms:(17)∑x,y∈V∗dkx,y+∑j=1m∑x∈V∗∑y∈Gk−1jdkx,y,and use the scaling mechanism for the edges(18)=∑x,y∈V∗dx,y+Nk−1∑x∈V∗∑j=1mdx,vj+n−mFλk−1.
In conclusion, we obtain(19)Λk=∑x,y∈Gkdkx,y=∑x∈V∗∑y∈Gkdkx,y+∑i=1m∑x∈Gk−1i∑y∈Gkdkx,y=FΛk−1+2m−1Nk−1+n−mFλk−1+Nk−12α+2Nk−1β+η,where(20)α=∑i,j=1mdvi,vj,β=∑i=1m∑y∈V∗dvi,y,η=∑x,y∈V∗dx,y.
Now, we define(21)Γk=2m−1Nk+n−mFλk+Nk2α+2Nkβ+η,for k≥0. Hence, we obtain the following key equation:(22)Λk=FΛk−1+Γk−1.
After all the preparations are complete, we are finally ready to study the asymptotic behavior of the average weighted geodesic distance ofGk. The result is stated in the following theorem.Theorem 1.
The asymptotic behavior of the average weighted geodesic distance ofGk satisfies(23)limk⟶∞δk=2m−1Fm2−Fm−F∑i=1mdvi,s0+1m2−F∑i,j=1mdvi,vj.Proof.
First, we prove(24)limk⟶∞δk=m−12m2n−12m2−Flimk⟶∞Γkm2k.
By equation (22), for all k≥1, we have(25)Λk=∑t=0k−1Fk−1−tΓt+FkΛ0.
Then,(26)limk⟶∞δk=limk⟶∞Λkm2k⋅m2kNkNk−1=m−12m2n−12limk⟶∞∑t=0k−1Fk−1−tΓtm2k=m−12m2n−12Flimk⟶∞∑t=0k−1Γt/Ftm2/Fk=m−12m2n−12Flimk⟶∞Γk/Fkm2/Fk+1−m2/Fk=m−12m2n−12m2−Flimk⟶∞Γkm2k.
The last but one equality uses O. Stolz’s formula. So, equation (24) is valid.
By the definition ofΓk, one can verify that(27)limk⟶∞Γkm2k=2n−1mFlimk⟶∞λkmk+m2n−12m−12α.
By equation (9) in Lemma 1, we have(28)limk⟶∞Γkm2k=2m2n−12Fλ0′m−Fm−1+m2n−12m−12α.
Combining equations (24) and (28), we have the desired result.
In networksGk, let pkx,y denote the geodesic distance between nodes x and y in Gk. Set p⋅,⋅=p0⋅,⋅ for convention. Define(29)Θk=∑x,y∈Gkpkx,y,for k≥0. Thus, the average geodesic distance of Gk is given by(30)θk=ΘkNkNk−1.
We can also computeθk, formally obtained by setting f1=⋯=fm=1 and replacing weighted geodesic distance dk⋅,⋅ by geodesic distance pk⋅,⋅ in the previous argument. The asymptotic behavior of the average geodesic distance of Gk is given in the following theorem, and the theorem shows the average geodesic distance increases logarithmically with the network size.Theorem 2.
The asymptotic behavior of the average geodesic distance ofGk satisfies(31)limk⟶∞θk−2km∑i=1mpvi,s0=∑i,j=1mpvi,vjmm−1+2m−1mn−1∑x∈G0px,s0+∑x∈V∗px,s0m−1−2n−mmm−1n−1+1m−1∑i=1mpvi,s0.Proof.
Define(32)ιk=∑x∈Gkpkx,sk,fork≥0,ι0′=∑i=1mpvi,s0,ι0″=ι0−ι0′.
By equation (8), we obtain(33)ιk=mkι0+∑t=0k−1mk−1−tNtι0′+∑t=0k−1mtι0″=mkι0−mkn−mι0′mm−1∑t=0k−11mt+∑t=0k−1mtι0″+mkn−1ι0′m−1k=ι˜k+mkn−1ι0′m−1k,for k>0. Take ι0=ι˜0. One can verify that(34)limk⟶∞ι˜kmk=ι0−n−mm−12ι0′+1m−1ι0″.
Now, we define(35)ϒk=2m−1Nk+n−mmιk+Nk2α∗+2Nkβ∗+η∗,ϒ˜k=2m−1Nk+n−mmι˜k+Nk2α∗+2Nkβ∗+η∗,for k≥0. The definitions of α∗, β∗, and η∗ are similar to α, β, and η, respectively; we just replace d⋅,⋅ by geodesic distance p⋅,⋅ in the new definitions. Thus,(36)ϒk=ϒ˜k+Ukιk−ι˜k=Υ˜k+Ukmkn−1ι0′m−1k,where Uk=2m−1Nk+n−mm for k≥0.
By equations (22) and (25), we obtain(37)Θk=∑t=0k−1mk−1−tΥt+mkΘ0.
Sincelimk⟶∞mkΘ0/NkNk−1=0, we have(38)limk⟶∞θk−2ι0′mk−1+2ι0′mm−1=limk⟶∞∑t=0k−1mk−1−tϒtNkNk−1−2ι0′mk−1+2ι0′mm−1=limk⟶∞∑t=0k−1mk−1−tϒ˜t+Utιt−ι˜tNkNk−1−2ι0′mk−1+2ι0′mm−1=limk⟶∞∑t=0k−1mk−1−tϒ˜tNkNk−1+limk⟶∞∑t=0k−1mk−1−tUtιt−ι˜tNkNk−1−2ι0′mk−1+2ι0′mm−1.
By direct calculation, we have(39)limk⟶∞∑t=0k−1mk−1−tUtιt−ι˜tNkNk−1−2ι0′mk−1+2ι0′mm−1=0.
Thus,(40)limk⟶∞θk−2ι0′mk−1+2ι0′mm−1=limk⟶∞∑t=0k−1mk−1−tϒ˜tNkNk−1=m−12m3n−12limk⟶∞∑t=0k−1ϒ˜t/mtmk=m−1m3n−12limk⟶∞ϒ˜km2k.
By equation (34), we obtain(41)limk⟶∞ϒ˜km2k=2m2n−1ι0−n−mm−12ι0′+1m−1ι0″+m2n−12m−12α∗.
Combining equations (40) and (41), we have the desired result. The proof is complete.


### 3.2. Node Strength Distribution

Given nodex in Gk, we denote by Nkx the set of nodes adjacent to x. If y∈Nkx, the weight of edge xy in Gk is wxyk. The node strength of x is defined by(42)wxk=∑y∈Nkxwxyk.Node strength is a generalization of the degree to weighted graphs. We are in the place to study the node strength distribution of the weighted graphsGk. Let gkh denote the cardinality of nodes in Gk that have strength h. Without loss of generality, we assume that n−m−1=l>0 and VG0\s0,v1,…,vm=u1,…,ul.We first present some notations and definitions that will be used throughout this section. Set(43)x0=ws00,zj=wuj0,forj=1,…,l,yi=wvi0,xi=yi+fix0,fori=1,…,m.Recall thatℕ=0,1,2,…. Define(44)Πk=r1,…,rm∈ℕm:r1+⋯+rm=k,Π=∪k=0∞Πk.ForΔ⊂Π, we define(45)Δk=r1,…,rm∈Δ:r1+⋯+rm=k,fork≥0.ForΔ⊂Πk, we can also define(46)Δt=r1,…,rm∈Πt: there existsr1′,…,rm′∈Δs.t.r1,…,rm≺r1′,…,rm′,for 0≤t≤k. Here, r1,…,rm≺r1′,…,rm′ means ri≤ri′ for all i∈1,…,m.Lemma 3.
IfΔ⊂Πk for k>0, then for any 0≤t<k, we have(47)∑r1,…,rm∈Δtt!r1!⋯rm!f1r1⋯fmrmdfract≥∑r1,…,rm∈Δk!r1!⋯rm!f1r1⋯fmrmdfract.Proof.
For anyΩ⊂Π, we define(48)SΩ=∑r1,…,rm∈Ωr1+⋯+rm!r1!⋯rm!f1r1⋯fmrmdfract,for brevity. Note that(49)1=f1dfract+⋯+fmdfractk=SΔtf1dfract+⋯+fmdfractk−t+SΠt\Δtf1dfract+⋯+fmdfractk−t=SΔ+SΠk\Δ.
By the definition ofΔt, we have the desired result.Lemma 4.
For anyα1,…,αm∈Π, we define(50)Δα1,…,αm=r1,…,rm∈Π:f1r1⋯fmrm=f1α1⋯fmαm.Then, we have(51)SΔα1,…,αm≤1.Proof.
For fixedα1,…,αm, we let Δ=Δα1,…,αm for brevity. There exist integers t0,…,tl such that(52)0≤t0<t1<⋯<tl,Δ=∪i=0lΔti.
Define a sequence of setsΩ0,…,Ωl satisfying Ωl=Δtl and(53)Ωi=Ωi+1ti∪Δti,fori=0,…,l−1.
Firstly, we prove(54)Ωi+1ti∩Δti=∅,for i=0,…,l−1. If r1,…,rm∈Ωi+1, then f1r1⋯fmrm≥f1α1⋯fmαm. Since ti<ti+1, any r1,…,rm∈Ωi+1ti satisfies that f1r1⋯fmrm>f1α1⋯fmαm. Hence, Ωi+1ti and Δti have no common member.
By Lemma3, we obtain(55)SΔ=∑i=0lSΔti≤∑i=0l−2SΔti+SΔtl−1+SΔtltl−1=∑i=0l−2SΔti+SΩl−1⋯⋯≤SΩ0≤1.
The proof is complete.Theorem 3.
There existsC1>0 such that, for all k>0, we have(56)gkh≤C1hdfract.
Iff1=⋯=fm=f, then there exists C2>0 such that, for all k>0, if gkh≠0, then(57)gkh≥C2hdfract.Proof.
For anyh>0, we set(58)ϕj=r1,…,rm∈∪t=0kΠt:h=zjf1r1⋯fmrm,forj=1,…,l,φi=r1,…,rm∈∪t=0k−1Πt:h=xif1r1⋯fmrm,fori=1,…,m,ηi=r1,…,rm∈Πk:h=yif1r1⋯fmrm,fori=1,…,m.
One can easily verify that(59)gkh≤x0dfracthdfract+∑j=1lSϕjh/zjdfract+∑i=1mSφih/xidfract+∑i=1mSηih/yidfract.
By equation (51), we have(60)gkh≤∑i=0mxidfract+∑i=1myidfract+∑j=1lzjdfracthdfract≕C1hdfract.
Now, we assumef1=⋯=fm=f. There are at least mt nodes that have strength ftzj for 0≤t≤k. There are at least mt nodes that have strength ftxi for 0≤t<k. There are at least mk nodes that have strength fkyi. Set(61)C2=minx0,yi,zj:i=1,…,m,j=1,…,ldfract.
Ifh=zjft, then(62)gkh≥mt=1h/zjdfract≥C2hdfract.
Ifh=yifk, then(63)gkh≥mk=1h/yidfract≥C2hdfract.
Ifh=xift, for i>0, then(64)gkh≥mt=1h/xidfract=yi+fx0dfracthdfract≥C2hdfract.
The proof is complete.


## 3.1. Average Weighted Geodesic Distance

Letdkx,y denote the weighted geodesic distance between nodes x and y in Gk. Set d⋅,⋅=d0⋅,⋅ for convention. Define(4)Λk=∑x,y∈Gkdkx,y,fork≥0.Thus, the average weighted geodesic distance ofGk is given by(5)δk=ΛkNkNk−1.Fork≥0, we define(6)λk=∑x∈Gkdkx,sk,i.e., the sum of all weighted geodesic distances of the nodes in Gk from the beginning node sk. Define F=∑i=1mfi. Set(7)λ0′=∑i=1mdvi,s0,λ0″=λ0−λ0′.Lemma 1.
Fork≥1, we have(8)λk=Fkλ0+∑t=0k−1Fk−1−tNtλ0′+∑t=0k−1Ftλ0″.
The asymptotic behavior ofλk satisfies(9)limk⟶∞λkmk=mn−1m−1m−Fλ0′.Proof.
By the construction ofGk, we obtain that(10)λk=∑i=1mfiλk−1+Nk−1dvi,s0+λ0″=Fλk−1+Nk−1λ0′+λ0″.
By direct calculation, we obtain equation (8).
SinceF<m, we have(11)limk⟶∞Fkλ0+∑t=0k−1Ftλ0″mk=0.
Thus, in order to prove equation (9), it suffices to prove(12)limk⟶∞∑t=0k−1Fk−1−tNtmk=mn−1m−1m−F.
However,(13)limk⟶∞∑t=0k−1Fk−1−tNtmk=1Flimk⟶∞∑t=0k−1Nt/Ftm/Fk=1Flimk⟶∞Nk−1/Fk−1m/Fk−m/Fk−1=1m−Flimk⟶∞Nk−1mk−1=mn−1m−1m−F.
The second equality uses O. Stolz’s formula. The proof is complete.
Recall the construction algorithm. In order to obtainGk with k≥1, we concatenate G0 with Gk−1i for all i∈1,…,m; thus, it is proper to regard Gk−1i as a subgraph of Gk. Set V∗=VG0\v1,…,vm.
Fori=1,…,m, we can decompose the sum ∑x∈Gk−1i∑y∈Gkdkx,y into three terms:(14)∑x,y∈Gk−1idkx,y+∑j=1j≠im∑x∈Gk−1i,y∈Gk−1jdkx,y+∑x∈Gk−1i,y∈V∗dkx,y,and use the scaling mechanism for the edges and with the construction of Gk(15)=fiΛk−1+F+m−2fiNk−1λk−1+Nk−12αi+n−mfiλk−1+Nk−1βi,where(16)αi=∑j=1mdvi,vj,βi=∑y∈V∗dvi,y.
Similarly, we decompose the sum∑x∈V∗∑y∈Gkdkx,y into two terms:(17)∑x,y∈V∗dkx,y+∑j=1m∑x∈V∗∑y∈Gk−1jdkx,y,and use the scaling mechanism for the edges(18)=∑x,y∈V∗dx,y+Nk−1∑x∈V∗∑j=1mdx,vj+n−mFλk−1.
In conclusion, we obtain(19)Λk=∑x,y∈Gkdkx,y=∑x∈V∗∑y∈Gkdkx,y+∑i=1m∑x∈Gk−1i∑y∈Gkdkx,y=FΛk−1+2m−1Nk−1+n−mFλk−1+Nk−12α+2Nk−1β+η,where(20)α=∑i,j=1mdvi,vj,β=∑i=1m∑y∈V∗dvi,y,η=∑x,y∈V∗dx,y.
Now, we define(21)Γk=2m−1Nk+n−mFλk+Nk2α+2Nkβ+η,for k≥0. Hence, we obtain the following key equation:(22)Λk=FΛk−1+Γk−1.
After all the preparations are complete, we are finally ready to study the asymptotic behavior of the average weighted geodesic distance ofGk. The result is stated in the following theorem.Theorem 1.
The asymptotic behavior of the average weighted geodesic distance ofGk satisfies(23)limk⟶∞δk=2m−1Fm2−Fm−F∑i=1mdvi,s0+1m2−F∑i,j=1mdvi,vj.Proof.
First, we prove(24)limk⟶∞δk=m−12m2n−12m2−Flimk⟶∞Γkm2k.
By equation (22), for all k≥1, we have(25)Λk=∑t=0k−1Fk−1−tΓt+FkΛ0.
Then,(26)limk⟶∞δk=limk⟶∞Λkm2k⋅m2kNkNk−1=m−12m2n−12limk⟶∞∑t=0k−1Fk−1−tΓtm2k=m−12m2n−12Flimk⟶∞∑t=0k−1Γt/Ftm2/Fk=m−12m2n−12Flimk⟶∞Γk/Fkm2/Fk+1−m2/Fk=m−12m2n−12m2−Flimk⟶∞Γkm2k.
The last but one equality uses O. Stolz’s formula. So, equation (24) is valid.
By the definition ofΓk, one can verify that(27)limk⟶∞Γkm2k=2n−1mFlimk⟶∞λkmk+m2n−12m−12α.
By equation (9) in Lemma 1, we have(28)limk⟶∞Γkm2k=2m2n−12Fλ0′m−Fm−1+m2n−12m−12α.
Combining equations (24) and (28), we have the desired result.
In networksGk, let pkx,y denote the geodesic distance between nodes x and y in Gk. Set p⋅,⋅=p0⋅,⋅ for convention. Define(29)Θk=∑x,y∈Gkpkx,y,for k≥0. Thus, the average geodesic distance of Gk is given by(30)θk=ΘkNkNk−1.
We can also computeθk, formally obtained by setting f1=⋯=fm=1 and replacing weighted geodesic distance dk⋅,⋅ by geodesic distance pk⋅,⋅ in the previous argument. The asymptotic behavior of the average geodesic distance of Gk is given in the following theorem, and the theorem shows the average geodesic distance increases logarithmically with the network size.Theorem 2.
The asymptotic behavior of the average geodesic distance ofGk satisfies(31)limk⟶∞θk−2km∑i=1mpvi,s0=∑i,j=1mpvi,vjmm−1+2m−1mn−1∑x∈G0px,s0+∑x∈V∗px,s0m−1−2n−mmm−1n−1+1m−1∑i=1mpvi,s0.Proof.
Define(32)ιk=∑x∈Gkpkx,sk,fork≥0,ι0′=∑i=1mpvi,s0,ι0″=ι0−ι0′.
By equation (8), we obtain(33)ιk=mkι0+∑t=0k−1mk−1−tNtι0′+∑t=0k−1mtι0″=mkι0−mkn−mι0′mm−1∑t=0k−11mt+∑t=0k−1mtι0″+mkn−1ι0′m−1k=ι˜k+mkn−1ι0′m−1k,for k>0. Take ι0=ι˜0. One can verify that(34)limk⟶∞ι˜kmk=ι0−n−mm−12ι0′+1m−1ι0″.
Now, we define(35)ϒk=2m−1Nk+n−mmιk+Nk2α∗+2Nkβ∗+η∗,ϒ˜k=2m−1Nk+n−mmι˜k+Nk2α∗+2Nkβ∗+η∗,for k≥0. The definitions of α∗, β∗, and η∗ are similar to α, β, and η, respectively; we just replace d⋅,⋅ by geodesic distance p⋅,⋅ in the new definitions. Thus,(36)ϒk=ϒ˜k+Ukιk−ι˜k=Υ˜k+Ukmkn−1ι0′m−1k,where Uk=2m−1Nk+n−mm for k≥0.
By equations (22) and (25), we obtain(37)Θk=∑t=0k−1mk−1−tΥt+mkΘ0.
Sincelimk⟶∞mkΘ0/NkNk−1=0, we have(38)limk⟶∞θk−2ι0′mk−1+2ι0′mm−1=limk⟶∞∑t=0k−1mk−1−tϒtNkNk−1−2ι0′mk−1+2ι0′mm−1=limk⟶∞∑t=0k−1mk−1−tϒ˜t+Utιt−ι˜tNkNk−1−2ι0′mk−1+2ι0′mm−1=limk⟶∞∑t=0k−1mk−1−tϒ˜tNkNk−1+limk⟶∞∑t=0k−1mk−1−tUtιt−ι˜tNkNk−1−2ι0′mk−1+2ι0′mm−1.
By direct calculation, we have(39)limk⟶∞∑t=0k−1mk−1−tUtιt−ι˜tNkNk−1−2ι0′mk−1+2ι0′mm−1=0.
Thus,(40)limk⟶∞θk−2ι0′mk−1+2ι0′mm−1=limk⟶∞∑t=0k−1mk−1−tϒ˜tNkNk−1=m−12m3n−12limk⟶∞∑t=0k−1ϒ˜t/mtmk=m−1m3n−12limk⟶∞ϒ˜km2k.
By equation (34), we obtain(41)limk⟶∞ϒ˜km2k=2m2n−1ι0−n−mm−12ι0′+1m−1ι0″+m2n−12m−12α∗.
Combining equations (40) and (41), we have the desired result. The proof is complete.


## 3.2. Node Strength Distribution

Given nodex in Gk, we denote by Nkx the set of nodes adjacent to x. If y∈Nkx, the weight of edge xy in Gk is wxyk. The node strength of x is defined by(42)wxk=∑y∈Nkxwxyk.Node strength is a generalization of the degree to weighted graphs. We are in the place to study the node strength distribution of the weighted graphsGk. Let gkh denote the cardinality of nodes in Gk that have strength h. Without loss of generality, we assume that n−m−1=l>0 and VG0\s0,v1,…,vm=u1,…,ul.We first present some notations and definitions that will be used throughout this section. Set(43)x0=ws00,zj=wuj0,forj=1,…,l,yi=wvi0,xi=yi+fix0,fori=1,…,m.Recall thatℕ=0,1,2,…. Define(44)Πk=r1,…,rm∈ℕm:r1+⋯+rm=k,Π=∪k=0∞Πk.ForΔ⊂Π, we define(45)Δk=r1,…,rm∈Δ:r1+⋯+rm=k,fork≥0.ForΔ⊂Πk, we can also define(46)Δt=r1,…,rm∈Πt: there existsr1′,…,rm′∈Δs.t.r1,…,rm≺r1′,…,rm′,for 0≤t≤k. Here, r1,…,rm≺r1′,…,rm′ means ri≤ri′ for all i∈1,…,m.Lemma 3.
IfΔ⊂Πk for k>0, then for any 0≤t<k, we have(47)∑r1,…,rm∈Δtt!r1!⋯rm!f1r1⋯fmrmdfract≥∑r1,…,rm∈Δk!r1!⋯rm!f1r1⋯fmrmdfract.Proof.
For anyΩ⊂Π, we define(48)SΩ=∑r1,…,rm∈Ωr1+⋯+rm!r1!⋯rm!f1r1⋯fmrmdfract,for brevity. Note that(49)1=f1dfract+⋯+fmdfractk=SΔtf1dfract+⋯+fmdfractk−t+SΠt\Δtf1dfract+⋯+fmdfractk−t=SΔ+SΠk\Δ.
By the definition ofΔt, we have the desired result.Lemma 4.
For anyα1,…,αm∈Π, we define(50)Δα1,…,αm=r1,…,rm∈Π:f1r1⋯fmrm=f1α1⋯fmαm.Then, we have(51)SΔα1,…,αm≤1.Proof.
For fixedα1,…,αm, we let Δ=Δα1,…,αm for brevity. There exist integers t0,…,tl such that(52)0≤t0<t1<⋯<tl,Δ=∪i=0lΔti.
Define a sequence of setsΩ0,…,Ωl satisfying Ωl=Δtl and(53)Ωi=Ωi+1ti∪Δti,fori=0,…,l−1.
Firstly, we prove(54)Ωi+1ti∩Δti=∅,for i=0,…,l−1. If r1,…,rm∈Ωi+1, then f1r1⋯fmrm≥f1α1⋯fmαm. Since ti<ti+1, any r1,…,rm∈Ωi+1ti satisfies that f1r1⋯fmrm>f1α1⋯fmαm. Hence, Ωi+1ti and Δti have no common member.
By Lemma3, we obtain(55)SΔ=∑i=0lSΔti≤∑i=0l−2SΔti+SΔtl−1+SΔtltl−1=∑i=0l−2SΔti+SΩl−1⋯⋯≤SΩ0≤1.
The proof is complete.Theorem 3.
There existsC1>0 such that, for all k>0, we have(56)gkh≤C1hdfract.
Iff1=⋯=fm=f, then there exists C2>0 such that, for all k>0, if gkh≠0, then(57)gkh≥C2hdfract.Proof.
For anyh>0, we set(58)ϕj=r1,…,rm∈∪t=0kΠt:h=zjf1r1⋯fmrm,forj=1,…,l,φi=r1,…,rm∈∪t=0k−1Πt:h=xif1r1⋯fmrm,fori=1,…,m,ηi=r1,…,rm∈Πk:h=yif1r1⋯fmrm,fori=1,…,m.
One can easily verify that(59)gkh≤x0dfracthdfract+∑j=1lSϕjh/zjdfract+∑i=1mSφih/xidfract+∑i=1mSηih/yidfract.
By equation (51), we have(60)gkh≤∑i=0mxidfract+∑i=1myidfract+∑j=1lzjdfracthdfract≕C1hdfract.
Now, we assumef1=⋯=fm=f. There are at least mt nodes that have strength ftzj for 0≤t≤k. There are at least mt nodes that have strength ftxi for 0≤t<k. There are at least mk nodes that have strength fkyi. Set(61)C2=minx0,yi,zj:i=1,…,m,j=1,…,ldfract.
Ifh=zjft, then(62)gkh≥mt=1h/zjdfract≥C2hdfract.
Ifh=yifk, then(63)gkh≥mk=1h/yidfract≥C2hdfract.
Ifh=xift, for i>0, then(64)gkh≥mt=1h/xidfract=yi+fx0dfracthdfract≥C2hdfract.
The proof is complete.



---

*Source: 4906878-2020-07-18.xml*