# Exact Solutions of a Generalized Weighted Scale Free Network

Authors: Li Tan; Dingyou Lei
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

We investigate a class of generalized weighted scale-free networks, where the new vertex connects tom pairs of vertices selected preferentially. The key contribution of this paper is that, from the standpoint of random processes, we provide rigorous analytic solutions for the steady state distributions, including the vertex degree distribution, the vertex strength distribution and the edge weight distribution. Numerical simulations indicate that this network model yields three power law distributions for the vertex degrees, vertex strengths and edge weights, respectively.


---

## Body

## 1. Introduction

Recently, complex networks have become a hot topic due to the two most important discoveries of real networks, that is, the small world phenomenon raised by Watts and Strogatz [1], and the scale-free property presented by Barabási and Albert [2]. For most real-world complex systems, the proportion of vertices with degree  k obeys a power-law form, that is, P(k)∝k-γ, where γ is a constant (see Albert et al. [3] for detail). To describe such a property, Barabási et al. [4] proposed a model (BA model for short) with growth and preferential attachment. The mean field method was used in [4] to get approximate expressions of the degree distribution.Since then, Krapivsky et al. [5] expanded the preferential attachment of the BA model to be nonlinear. With the rate equation method, it is found that power-law degree distribution can only be obtained in the case of linear preferential attachment. Meanwhile, Dorogovtsev et al. [6] generalized the BA model to include initial attractiveness. Except for preferential selection of vertices, Dorogovtsev et al. [7] introduced a simple model based on selection of edges. This model starts with three vertices connected to each other; at each time step, an edge is randomly selected, and both its ends are connected to the new vertex. With the master equation method, the degree distribution of this model was shown to behave as a power-law form [7].All the models of [4–7] share a common property that all links are equivalent. However, it is widely known that interaction strengths can vary widely, and such variations are essential to the network’s ability to carry on its basic functions [8]. Barrat et al. [9] proposed a model for the growth of weighted networks that couples the establishment of new edges and vertices, and the weights’ dynamical evolution. Tanaka and Aoyagi [10] generalized the model of [9] through the weight-driven preferential attachment of new vertices to existing vertices and the growth of the weights of existing links, generating scale-free networks with variable power-law exponents.As one of the most important characteristics of networks, the degree distribution is always a big consideration. However, there is no systematic and rigorous method for solving degree distribution, the methods in [4–7] have to assume the existence of P(k) or assume the vertex number Nk(t) with degree k be continuous. But Bollobás et al. [11] gave a rigorous method, but this only applies to networks with multiple edges and loops. Stem from this consideration, in this paper, we try to provide a systematic and rigorous method to solve the steady state distribution from a new perspective.Firstly, we shall give a new weighted network model. The model starts with a complete graph, at each step, the new vertex is connected tom(m≥1) pairs of vertices which are selected preferentially; and meantime, the weights between the selected pairs of vertices are strengthened. Based on the Stolz theorem, rigorous analytic derivations to the steady state degree distribution of the model is provided. What’s more, the method of solving the degree distribution can be applied to study the steady state of both the vertex strength distribution and the edge weight distribution. Both theoretical derivations and numerical simulations show that the model displays power-law behavior for the degree, the strength and the weight distribution. Lastly, we show that the clustering coefficient is larger than that of the BA model.The rest of the paper is organized as follows. Section2 is the description of the model, and Section 3 is devoted to discuss some properties of the network. The analytical results are demonstrated by numerical simulations in the last section.


## 2. The Model

The detailed model construction algorithm is described as follows:(i)
Initialization. The initial network, denoted as G0, is a complete graph with n vertices, which are denoted by v01,v02,…,v0n. The weight of each link is assigned w0(w0≥v01).(ii)
Growth. To construct Gt+1 from Gt, we add a new vertex vt+1 and then add 2m(2m≤n-1) edges between vt+1 and vertices of Gt. We choose m pairs of vertices Wt1,Wt1′,Wt2,Wt2′,…,Wtm,Wtm′ according to a preferential attachment rule. If wii′(t) is the weight between vertices vi and vi′ in Gt, then the vertices vi and vi′ are selected with probability
(1)wii′(t)∑q,l∈V(Gt)wql(t)independently for each vertex pair i,i′∈1,2,…,m.Note that this allows the possibility that we choose the same vertex more than once, and hence the graphs may have multiple edges.The weight of each new edge isw0. Meanwhile, the weight between each selected pair of vertices is strengthened by adding w0 to it. If there are multiple edges added between two vertices, then the weight between them will increase multiple times. For example, if there are a new edges added between vertices vt and vi, then the weight between them will increase aw0.In this case, the strength of vertexvi can be expressed as si(t)=∑j∈V(i)wij(t), where V(i) is the neighbor set of vertex vi.The number of vertices inGt is obviously Nt=n+t. Because 2m edges are added at each stage, the total number of edges in Gt is Lt=n(n-1)/2+2mt. Moreover, the total strength of vertices in Gt is St=n(n-1)w0+6mtw0.Before analyzing the steady state distribution of the network, let us firstly introduce some concepts and symbols. Let the random variableNk(t) be the number of vertices with degree k in Gt, and moreover let the network degree distribution be the average over all its vertices at time t, namely E(Nk(t))/Nt. If  limt→∞(E(Nk(t))/Nt) exists, we say that the steady state degree distribution of the network exists and it can be quantified by PD(k)=limt→∞(E(Nk(t))/Nt).LetMs(t) represent the number of vertices with strength s in Gt Similarly, the steady state distribution of vertex strength is denoted as PS(s)=limt→∞(E(Ms(t))/Nt).


### 2.1. Network Analysis

To analytically obtain the statistical properties of the network generated by the above algorithm, we give strict proofs from the perspective of random process.Lemma 1.
Letpt>0,qt≥0,t≥1, then the difference equation xt+1=ptxt+qt has the solution
(2)xt=∏i-1t-1pi(x1+∑i=1t-1ql∏j=1lpj).Lemma 2 (Stolz Theorem, [12]).
In sequence{xt/yt}, assume that {yt} is a monotone increasing sequence with yt→∞, if limt→∞((xt+1-xt)/(yt+1-yt))=l exists, where -∞≤l≤∞, then limt→∞(xt/yt)=l.Theorem 3 (Degree Distribution).
For any positive integerk≥2m, the steady state degree distribution of the model exists and is given by
(3)PD(k)=limt→∞E(Nk(t))Nt=Γ(k-m-1)Γ(k-m+(3/2))Γ(m+(3/2))Γ(m-1)32m+3,
where Γ(x)=(x-1)!.Proof.
For use in this proof, as well as later proofs, we define the σ-algebra ℱt=σ(Gi;0≤i≤t).
For0≤d≤m, the probability that an old vertex vi, with degree k and strength s, to get d edges from the new vertex vt+1 is
(4)(md)(∑jwij(t)∑q,lwql(t))d(1-∑jwij(t)∑q,lwq,l(t))m-d.
Clearly, the above equation can also be rewritten as(5)(md)(2si(t)St)d(1-2si(t)St)m-d.
Note that for verticesv01,v02,…,v0n, the initial strength is (n-1)w0. If the degree of  v0r(r=1,2,…,n) at time t is k0r(t), then it means that there are k0r(t)-(n-1) new edges linked to vertex v0r in the process of network growth, thus the strength of v0r at time t is
(6)s0r(t)=(n-1)w0+2w0(k0r(t)-(n-1))=(2k0r(t)-(n-1))w0,r=1,2,…,n.
Similarly, for verticesv1 to vt, we have
(7)si(t)=2mw0+2w0(ki(t)-2m)=(2ki(t)-2m)w0,
where ki(t) is the degree of vertex vi in Gt.
The above two cases can be rewritten together as(8)si(t)=K0w0+2w0(ki(t)-K0)=(2ki(t)-K0)w0,i=01,…,0n,1,…,n,
where
(9)K0={n-1,i=01,…,0n,2m,i=1,…,n.
For variablet,Nk(t) is a random process. Thus, given ℱt, the expected number of vertices with degree k in Gt+1 is
(10)E(Nk(t+1)∣ℱt)=∑d=0mNk-d(t)(md)[[4(k-d)-2K0]w0St]d×[1-[4(k-d)-2K0]w0St]m-d+I{k=2m}.
In particular, fork=2m, we have
(11)E(N2m(t+1)∣ℱt)=(1-4mw0St)mN2m(t)+1.
Taking expectations on both sides and combing the property of conditional probability,(12)E(N2m(t+1))=(1-4mw0St)mE(N2m(t))+1.
Computing by Lemma1 iteratively, we get
(13)E(N2m(t))=∏i=1t-1(1-4mw0Si)m×[E(N2m(1))+∑l=1t-11∏j=1l(1-(4mw0/Sj))m].
Divide byNt on both sides, let
(14)xt=E(N2m(1))+∑l=1t-11∏j=1l(1-(4mw0/Sj))m,yt=Nt∏i=1t-1(1-4mw0Si)-m,
then xt,yt>0,yt+1-yt>0 and {yt} is a monotone increasing sequence with yt→∞, limt→∞((xt+1-xt)/(yt+1-yt))=3/(2m+3), by Lemma 2, we have limt→∞(xt/yt)=3/(2m+3).
Thus,limt→∞(E(N2m(t))/Nt) exists and
(15)PD(2m)=limt⟶∞E(N2m(t))Nt=32m+3.
Fork>2m,
(16)E(Nk(t+1)∣ℱt)=∑d=0mNk-d(t)(md)[[4(k-d)-2K0]w0St]d×[1-[4(k-d)-2K0]w0St]m-d.
Taking expectation on both sides and using the properties of conditional expectations,(17)E(Nk(t+1))=[1-(4k-2K0)w0St]mE(Nk(t))+∑d=1m(md)[[4(k-d)-2K0]w0St]d·[1-[4(k-d)-2K0]w0St]m-dE(Nk-d(t)).
Supposelimt→∞(E(Nk-1(t))/Nt) exists and equals PD(k-1), use the same procedure of the case for k=2m, by Lemmas 1 and 2, then limt→∞(E(Nk(t))/Nt) also exists and
(18)PD(k)=limt→∞E(Nk(t))Nt=2k-2m-22k-2m+3PD(k-1).
Combine (15) and (18), resulting in
(19)PD(k)=Γ(k-m-1)Γ(k-m+(3/2))Γ(m+(3/2))Γ(m-1)32m+3.
This completes the proof.Remark 4.
For largek, the degree distribution is proportional to k-5/2, that is, PD(k)∝k-5/2. This implies that the degree distribution of our model obeys a power-law form like the BA model but the degree exponent is no longer 3.In order to obtain the vertex strength distribution analytically, we derive it in the same way as the degree distributionTheorem 5 (Strength Distribution).
For vertex strengths≥2mw0, the steady state of vertex strength distribution exists and satisfies that
(20)PS(s)=limt→∞E(Ms(t))Nt∝s-5/2.Proof.
Following the arguments of Theorem3, given ℱt, the expected number of vertices with strength s in Gt+1 is
(21)E(Ms(t+1)∣ℱt)=∑d=0mMs-2dw0(t)(md)×[2(s-2dw0)St]d[1-2(s-2dw0)St]m-d+I{s=2mw0}.
Use the same procedure of Theorem 3, we know that limt→∞(E(M2mw0(t))/Nt) exists and
(22)PS(2mw0)=limt→∞E(M2mw0(t))Nt=32m+3.
Fors>2mw0, suppose limt→∞(E(Ms-2w0(t))/Nt) exists and equals PS(s-2w0), then limt→∞(E(Ms(t))/Nt) also exists and
(23)PS(s)=limt→∞E(Ms(t))Nt=s-2w0s+3w0PS(s-2w0).
This, together with (22), leads to
(24)PS(s)=limt→∞E(Ms(t))Nt∝s-5/2.
Setw0=1, the exact expression of vertex strength distribution has the form of
(25)PS(s)=limt→∞E(Ms(t))Nt=(s-2)!!(2m+3)!!(s+3)!!(2m-2)!!PS(2m)∝s-5/2,
as required. This completes the proof.In what follows, we shall discuss the edge weight distribution.Theorem 6 (Weight Distribution).
The steady state edge weight distribution of the model exists and is given by(26)PW(w)∝w-(3m+1).Proof.
Since the proof is similar to that of Theorems3 and 5, here we omit it.Remark 7.
By Theorem6, we can conclude that the edge weight distribution follows power-law behavior with degree exponent γ=3m+1, which is related to m.


## 2.1. Network Analysis

To analytically obtain the statistical properties of the network generated by the above algorithm, we give strict proofs from the perspective of random process.Lemma 1.
Letpt>0,qt≥0,t≥1, then the difference equation xt+1=ptxt+qt has the solution
(2)xt=∏i-1t-1pi(x1+∑i=1t-1ql∏j=1lpj).Lemma 2 (Stolz Theorem, [12]).
In sequence{xt/yt}, assume that {yt} is a monotone increasing sequence with yt→∞, if limt→∞((xt+1-xt)/(yt+1-yt))=l exists, where -∞≤l≤∞, then limt→∞(xt/yt)=l.Theorem 3 (Degree Distribution).
For any positive integerk≥2m, the steady state degree distribution of the model exists and is given by
(3)PD(k)=limt→∞E(Nk(t))Nt=Γ(k-m-1)Γ(k-m+(3/2))Γ(m+(3/2))Γ(m-1)32m+3,
where Γ(x)=(x-1)!.Proof.
For use in this proof, as well as later proofs, we define the σ-algebra ℱt=σ(Gi;0≤i≤t).
For0≤d≤m, the probability that an old vertex vi, with degree k and strength s, to get d edges from the new vertex vt+1 is
(4)(md)(∑jwij(t)∑q,lwql(t))d(1-∑jwij(t)∑q,lwq,l(t))m-d.
Clearly, the above equation can also be rewritten as(5)(md)(2si(t)St)d(1-2si(t)St)m-d.
Note that for verticesv01,v02,…,v0n, the initial strength is (n-1)w0. If the degree of  v0r(r=1,2,…,n) at time t is k0r(t), then it means that there are k0r(t)-(n-1) new edges linked to vertex v0r in the process of network growth, thus the strength of v0r at time t is
(6)s0r(t)=(n-1)w0+2w0(k0r(t)-(n-1))=(2k0r(t)-(n-1))w0,r=1,2,…,n.
Similarly, for verticesv1 to vt, we have
(7)si(t)=2mw0+2w0(ki(t)-2m)=(2ki(t)-2m)w0,
where ki(t) is the degree of vertex vi in Gt.
The above two cases can be rewritten together as(8)si(t)=K0w0+2w0(ki(t)-K0)=(2ki(t)-K0)w0,i=01,…,0n,1,…,n,
where
(9)K0={n-1,i=01,…,0n,2m,i=1,…,n.
For variablet,Nk(t) is a random process. Thus, given ℱt, the expected number of vertices with degree k in Gt+1 is
(10)E(Nk(t+1)∣ℱt)=∑d=0mNk-d(t)(md)[[4(k-d)-2K0]w0St]d×[1-[4(k-d)-2K0]w0St]m-d+I{k=2m}.
In particular, fork=2m, we have
(11)E(N2m(t+1)∣ℱt)=(1-4mw0St)mN2m(t)+1.
Taking expectations on both sides and combing the property of conditional probability,(12)E(N2m(t+1))=(1-4mw0St)mE(N2m(t))+1.
Computing by Lemma1 iteratively, we get
(13)E(N2m(t))=∏i=1t-1(1-4mw0Si)m×[E(N2m(1))+∑l=1t-11∏j=1l(1-(4mw0/Sj))m].
Divide byNt on both sides, let
(14)xt=E(N2m(1))+∑l=1t-11∏j=1l(1-(4mw0/Sj))m,yt=Nt∏i=1t-1(1-4mw0Si)-m,
then xt,yt>0,yt+1-yt>0 and {yt} is a monotone increasing sequence with yt→∞, limt→∞((xt+1-xt)/(yt+1-yt))=3/(2m+3), by Lemma 2, we have limt→∞(xt/yt)=3/(2m+3).
Thus,limt→∞(E(N2m(t))/Nt) exists and
(15)PD(2m)=limt⟶∞E(N2m(t))Nt=32m+3.
Fork>2m,
(16)E(Nk(t+1)∣ℱt)=∑d=0mNk-d(t)(md)[[4(k-d)-2K0]w0St]d×[1-[4(k-d)-2K0]w0St]m-d.
Taking expectation on both sides and using the properties of conditional expectations,(17)E(Nk(t+1))=[1-(4k-2K0)w0St]mE(Nk(t))+∑d=1m(md)[[4(k-d)-2K0]w0St]d·[1-[4(k-d)-2K0]w0St]m-dE(Nk-d(t)).
Supposelimt→∞(E(Nk-1(t))/Nt) exists and equals PD(k-1), use the same procedure of the case for k=2m, by Lemmas 1 and 2, then limt→∞(E(Nk(t))/Nt) also exists and
(18)PD(k)=limt→∞E(Nk(t))Nt=2k-2m-22k-2m+3PD(k-1).
Combine (15) and (18), resulting in
(19)PD(k)=Γ(k-m-1)Γ(k-m+(3/2))Γ(m+(3/2))Γ(m-1)32m+3.
This completes the proof.Remark 4.
For largek, the degree distribution is proportional to k-5/2, that is, PD(k)∝k-5/2. This implies that the degree distribution of our model obeys a power-law form like the BA model but the degree exponent is no longer 3.In order to obtain the vertex strength distribution analytically, we derive it in the same way as the degree distributionTheorem 5 (Strength Distribution).
For vertex strengths≥2mw0, the steady state of vertex strength distribution exists and satisfies that
(20)PS(s)=limt→∞E(Ms(t))Nt∝s-5/2.Proof.
Following the arguments of Theorem3, given ℱt, the expected number of vertices with strength s in Gt+1 is
(21)E(Ms(t+1)∣ℱt)=∑d=0mMs-2dw0(t)(md)×[2(s-2dw0)St]d[1-2(s-2dw0)St]m-d+I{s=2mw0}.
Use the same procedure of Theorem 3, we know that limt→∞(E(M2mw0(t))/Nt) exists and
(22)PS(2mw0)=limt→∞E(M2mw0(t))Nt=32m+3.
Fors>2mw0, suppose limt→∞(E(Ms-2w0(t))/Nt) exists and equals PS(s-2w0), then limt→∞(E(Ms(t))/Nt) also exists and
(23)PS(s)=limt→∞E(Ms(t))Nt=s-2w0s+3w0PS(s-2w0).
This, together with (22), leads to
(24)PS(s)=limt→∞E(Ms(t))Nt∝s-5/2.
Setw0=1, the exact expression of vertex strength distribution has the form of
(25)PS(s)=limt→∞E(Ms(t))Nt=(s-2)!!(2m+3)!!(s+3)!!(2m-2)!!PS(2m)∝s-5/2,
as required. This completes the proof.In what follows, we shall discuss the edge weight distribution.Theorem 6 (Weight Distribution).
The steady state edge weight distribution of the model exists and is given by(26)PW(w)∝w-(3m+1).Proof.
Since the proof is similar to that of Theorems3 and 5, here we omit it.Remark 7.
By Theorem6, we can conclude that the edge weight distribution follows power-law behavior with degree exponent γ=3m+1, which is related to m.


## 3. Numerical Simulations

In this section, we perform several numerical simulations in regard to the vertex degree distribution, the vertex strength distribution and the edge weight distribution. The initial network is a complete graph with 10 vertices. All the simulations are conducted 200,000 steps. It is obvious that all the results shown in Figures1–3 are consistently conformed to the analytical analysis obtained in the previous sections.Figure 1
The degree distribution.Figure 2
The strength distribution.Figure 3
The weight distribution.Figure1 is the simulation of degree distribution PD(k) in log-log scale. The circles (◯), the upper triangles (△) and the lower triangles (▽) represent the simulation values of m=1,2,3, respectively. The dotted lines are theoretical results predicted by (3). Moreover, the legends here are the same as those in Figures 2 and 3.Figure2 shows the results of the simulations and the analysis of the vertex strength distribution PS(s) in log-log scale. Because of the linear relation between the degree and the strength of the vertex, their distributions are in the same form, that is, both obey a power-law form with degree exponent γ=5/2.Figure3 clearly verifies the theoretical results obtained by (26) with m=1. However, when it comes to m=2 and m=3, there are too few simulation data to explain the theoretical formula. All of these are resulted from the attribute of the negative exponential form of (26). With this form, the percentage of the edges dramatically decreases with the increase of w and/or m, and the number of steps required for more accurate simulation results increases exponentially. In fact, the number is at least w(3m+1)/2m without considering the random error. For example, the minimum number of required step for simulation is 174,763, when w=4 and m=3; however, we can obtain w=24 by the same number of simulation step if m=1. Despite the fact that the data of m=2 and m=3 are so few, the simulations can explain the edge weight distribution in some degree; they can at least illustrate the trend of the distribution. It is also easy to see that m has great influence on the weight distribution.In Figure4, we make a comparison of the simulation time under different values of m. It is obvious that the time required increases dramatically with the increase of the network size.Figure 4
Time required for simulation.


## 4. Conclusions

A weighted network model based on preferential selection of weights between vertices is studied in this paper. Based on the Stolz theorem, rigorous and analytic proofs for the steady state distributions of the model are provided. The approach developed here is quite general, applicable to many other scale free types of complex networks. Moreover, the theoretical derivations are verified by computer simulations (see Figures1–3 for details). Both theoretical derivations and numerical simulations show that the model displays power-law behavior for the degree, the strength and the edge weight distribution. In addition, to illustrate the complexity of generating complex networks, we compare the number of steps and the simulation time under different values of m.



---

*Source: 902519-2013-03-28.xml*