# Scale-Free Property for Degrees and Weights in a Preferential Attachment Random Graph Model

Authors: István Fazekas; Bettina Porvázsnyik
Journal: Journal of Probability and Statistics
 (2013)

---

## Abstract

A random graph evolution mechanism is defined. The evolution studied is a combination of the preferential attachment model and the interaction of four vertices. The asymptotic behaviour of the graph is described. It is proved that the graph exhibits
a power law degree distribution; in other words, it is scale-free. It turns out that any exponent in(2,∞) can be achieved. The proofs are based on martingale methods.


---

## Body

## 1. Introduction

During the last15 years the behaviour of many types of real-world networks was investigated. Such networks are the WWW, the Internet, and social and biological networks (see [1] for an overview). The main common characteristic of such networks is their scale-free nature, in other words the power law degree distribution, that is, pk~Ck-γ, as k→∞. Using real-life data, the exponents were determined for several cases. For the WWW the in-degree and the out-degree of web pages follow power law with γin=2.1 and γout=2.7, for the Internet γ=2.3, for the movie actor network γ=2.3, and for the collaboration graph of mathematicians γ=2.4 (see [1] for details). To describe the phenomenon, in [2] the preferential attachment model was introduced. In that model the growing procedure of the random graph is the following. At every time t=2,3,… a new vertex with m edges is added so that the edges link the new vertex to m existing vertices. The probability πi that the new vertex will be connected to the old vertex i depends on the degree ki of vertex i, so that πi=ki/∑j‍kj. Then several papers were devoted to the proof of the power law in the preferential attachment model (see, e.g., [3]).There are versions of the preferential attachment model (see [4, 5]). It turned out that besides the degrees of the vertices other characteristics of the graph can be important (see [5]). In [6] a model based on the interaction of three vertices was introduced. Then the power law degree distribution in that model was obtained in [7].In this paper, we extend the model and the results of [6, 7] to interactions of four vertices. Our model is the following. For short, a complete graph with four vertices we will call tetragon. The starting point at time n=0 is one tetragon. The initial weight of this graph is one. This graph contains 4 vertices, 6 edges, and 4 triangles. Each of these objects has initial weight 1. After the initial step we start to increase the size of the graph. The main feature of the procedure is that at each step n=1,2,… we consider four vertices and draw all nonexisting edges between these vertices. So we obtain a tetragon. The weight of this tetragon and the weights of all the objects in the tetragon are increased by 1. (That is, we increase the weights of 4 vertices, 6 edges, 4 triangles, and 1 tetragon.) The choice of the four vertices is the following.There are two possibilities at each step. With probabilityp we add a new vertex that interacts with three old vertices, on the other hand, with probability (1-p) four old vertices interact. Here 0<p≤1 is fixed.When we add a new vertex, then we choose3 old vertices and they together will form a tetragon. However, to choose the three old vertices we have two possibilities. With probability r we choose a triangle from the existing triangles according to the weights of the triangles. It means that a triangle of weight wt is chosen with probability wt/∑h‍wh (preferential attachment rule). On the other hand, with probability 1-r, we choose among the existing vertices uniformly; that is, all three vertices have the same chance.When four old vertices interact, we have again two possibilities. With probabilityq, we choose among the existing tetragons according to their weights. It means that a tetragon of weight w~t is chosen with probability w~t/∑h‍w~h (preferential attachment rule). On the other hand, with probability 1-q, we choose among the existing vertices uniformly; that is, all four vertices have the same chance.Our aim is to prove that the above mechanism produces a scale-free graph. We follow the lines of [6, 7]. Let X(n,d,w) denote the number of vertices of weight w and degree d after the nth step. Let Vn denote the number of vertices after the nth step. Let ℱn-1 denote the σ-algebra of observable events after the (n-1)th step. First we calculate the conditional expectation 𝔼{X(n,d,w)∣ℱn-1}, see Lemma 2. Then we prove (Theorem 3) that X(n,d,w)/Vn→xd,w almost surely (a.s.) as n→∞, where xd,w are fixed nonnegative numbers. The main tool of the proof is the Doob-Meyer decomposition of submartingales. We remark that in the 3-interaction model of [6] the limit xd,w is always positive (see [7]). As in our case the limit can be zero, we should modify the proof presented in [7].We show thatxd,w, d=3,4,…,3w, w=1,2,…, is a proper two-dimensional discrete probability distribution (Lemma 4). Then we turn to the scale-free property for the weights. Let X(n,w) denote the number of vertices of weight w after the nth step. Then for all w=1,2,… we have
(1)X(n,w)Vn⟶xw=x3,w+x4,w+⋯+x3w,w
almost surely and xw~Cw-(1+1/α), as w→∞ (Theorem 5). To derive the above results from Theorem 3, we need only some known facts about the Γ-function, see Lemma 4 and Theorem 5. Finally, we obtain the scale-free property for the degrees. Let us denote by U(n,d) the number of vertices of degree d after the nth step. For any d≥3 we have
(2)U(n,d)Vn⟶ud
almost surely as n→∞, where ud are positive numbers. Furthermore,
(3)ud~Γ(1+(β+1)/α)α2Γ(1+β/α)(αdα2)-(1+1/α),
as d→∞, where α, β, and α2 are appropriate constants (see Theorem 8). In both cases the exponent is 1+1/α. We can see that its value can be any number in (2,∞).If we compare the results and methods of the present paper with the ones in [6, 7], we can see that the calculations for the 4-vertice model are much longer than those of the 3-vertice model (see the proofs of Lemma 2 and Theorem 3). One can think that when we want to extend our model to the interaction of N vertices, then formulae will be burdening. But it is not the case. Analysing the proof of Theorem 3, it turns out that several terms are asymptotically negligible and this phenomenon remains true for the N-vertices model, too. Therefore the asymptotic results of the 3- and 4-vertice models can be extended to the N-vertices model. Moreover, several versions of the N-vertices model can be constructed and their fit to real-life data can be studied.


## 2. The Evolution of the Graph

Throughout the paper0<p≤1, 0≤r≤1, 0≤q≤1 are fixed numbers. Let X(n,d,w) denote the number of vertices of weight w and degree d after the nth step. Let Vn denote the number of vertices after the nth step.Remark 1.
Each vertex has initial weight1 and initial degree 3. When a vertex takes part in an interaction, then its weight is increased by 1 and its degree may be increased by 0, 1, 2, or 3. Therefore X(n,d,w) can be positive only for 1≤w and 3≤d≤3w.
Letℱn-1 denote the σ-algebra of observable events after the (n-1)th step. We compute the conditional expectation of X(n,d,w) with respect to ℱn-1 for w≥1.
Let(4)α1=(1-p)q,α2=34pr,α=α1+α2,β=3(1-r)+4(1-p)(1-q)p.
The following lemma contains the basic equation of the paper.Lemma 2.
We have(5)𝔼{X(n,d,w)∣ℱn-1}=X(n-1,d,w)[1-(wnα+pVn-1β)]+X(n-1,d,w-1)×[(1-p)(qw-1n+(1-q)(d3)(Vn-14))]+X(n-1,d-1,w-1)×[p(r3(w-1)4n+(1-r)(d-12)(Vn-13))+(1-p)(1-q)(d-12)(Vn-1-d)(Vn-14)]+X(n-1,d-2,w-1)×[(d-2)(Vn-1-d+12)(Vn-14)p(1-r)(d-2)(Vn-1-d+1)(Vn-13)+(1-p)(1-q)(d-2)(Vn-1-d+12)(Vn-14)(d-2)(Vn-1-d+1)(Vn-13)]+X(n-1,d-3,w-1)×[p(1-r)(Vn-1-d+22)(Vn-13)+(1-p)(1-q)(Vn-1-d+23)(Vn-14)]+pδd,3δw,1
for w≥1 and 3≤d≤3w. Here δk,l denotes the Dirac-delta.Proof.
The total weight of tetragons after(n-1) steps is n. The total weight of triangles after (n-1) steps is 4n. The total weight of the triangles having a fixed common vertex of weight w is 3w. Moreover, after (n-1) steps, we have the following. When we choose three vertices randomly, then the probability that a given vertex is chosen is
(6)(Vn-1-12)(Vn-13)=3Vn-1.
When we choose four vertices randomly, then the probability that a given vertex is chosen is
(7)(Vn-1-13)(Vn-14)=4Vn-1.
Therefore the probability that an old vertex of weight w takes part in the interaction at step n is
(8)p(r3w4n+(1-r)3Vn-1)+(1-p)(qwn+(1-q)4Vn-1)=wnα+pVn-1β,
where α and β are defined by (4). A new vertex always takes part in the interaction. At each step with probability p a new vertex with weight 1 and with degree 3 is born. This explains term pδd,3δw,1 in (5).
Consider a fixed vertex with weightw and degree d. The probability of the event that in the nth step (i)
neither its degreed nor its weight w change is
(9)1-(wnα+pVn-1β);(ii)
its degree does not change but its weight is increased by 1 is(10)(1-p)(qw-1n+(1-q)(d3)(Vn-14));(iii)
both its degree and its weight are increased by 1 is(11)p(r3(w-1)4n+(1-r)(d-12)(Vn-13))+(1-p)(1-q)(d-12)(Vn-1-d)(Vn-14);(iv)
its degree is increased by 2 and its weight is increased by 1 is(12)p(1-r)(d-2)(Vn-1-d+1)(Vn-13)+(1-p)(1-q)(d-2)(Vn-1-d+12)(Vn-14);(v)
its degree is increased by 3 and its weight is increased by 1 is(13)p(1-r)(Vn-1-d+22)(Vn-13)+(1-p)(1-q)(Vn-1-d+23)(Vn-14).Using the above formulae, we obtain (5).The following theorem is an extension of Theorem  3.1 in [7].Theorem 3.
Let0<p<1, q>0, r>0 and (1-r)(1-q)>0. For any fixed w and d with 1≤w and 3≤d≤3w one has
(14)X(n,d,w)Vn⟶xd,w
almost surely as n→∞, where xd,w are fixed nonnegative numbers. Furthermore, the numbers xd,w satisfy the following recurrence:
(15)x3,1=1α+β+1,xd,1=0,ford≠3,xd,w=1αw+β+1[α1(w-1)xd,w-1+α2(w-1)xd-1,w-1+βxd-3,w-1],
for w≥2, 3≤d≤3w, where α1, α2, α, and β are given by (4). One has xd,w>0 if w≥1, 3≤d≤3w unless d=3w-1. If d=3w-1, then one has xd,w=0; moreover, in this case
(16)X(n,d,w)Vn=o(n-a),
where a is a positive number which may depend on w and d. If 3≤d≤3w does not satisfied, then xd,w=0.Proof.
During the proof we take care of the casexd,w=0 which does not appear in [7]. Introduce notation
(17)c(n,w)=∏i=w-1n‍(1-αwi-βpVi-1)-1,n≥w-1,w≥1.c(n,w) is an ℱn-1-measurable random variable. Applying the Marcinkiewicz strong law of large numbers to the number of vertices, we have
(18)Vn=pn+o(n1/2+ε)
almost surely, for any ε>0.
Using (18) and the Taylor expansion for log(1+x), we obtain
(19)logc(n,w)=-∑i=w-1n‍log(1-αwi-βi+o(i1/2+ε))=(αw+β)∑i=w-1n‍1i+O(1),
where the error term is convergent as n→∞. Therefore
(20)c(n,w)~awnαw+β
almost surely, as n→∞, where aw is a positive random variable.
Let(21)Z(n,d,w)=c(n,w)X(n,d,w)for1≤w,3≤d≤3w.
Using (5), we can see that {Z(n,d,w),ℱn,n=w-1,w,w+1,…} is a nonnegative submartingale for any fixed 1≤w, 3≤d≤3w. Define Z(n,d,w)=0 for n=1,2,…,w-2. Applying the Doob-Meyer decomposition to Z(n,d,w), we can write
(22)Z(n,d,w)=M(n,d,w)+A(n,d,w),
where M(n,d,w) is a martingale and A(n,d,w) is a predictable increasing process. The general form of M(n,d,w) and A(n,d,w) is the following:
(23)M(n,d,w)=∑i=1n‍[Z(i,d,w)-𝔼(Z(i,d,w)∣ℱi-1)],(24)A(n,d,w)=𝔼Z(1,d,w)+∑i=2n‍[𝔼(Z(i,d,w)∣ℱi-1)-Z(i-1,d,w)],
where ℱ0 is the trivial σ-algebra. Using (5) and (24), we obtain
(25)A(n,d,w)=𝔼Z(1,d,w)+∑i=2n‍[(p(r3(w-1)4i+(1-r)(d-12)(Vi-13))c(i,w)X(i-1,d,w-1)(1-p)×(qw-1i+(1-q)(d3)(Vi-14))+c(i,w)X(i-1,d-1,w-1)×(p(r3(w-1)4i+(1-r)(d-12)(Vi-13))+(1-p)(1-q)(d-12)(Vi-1-d)(Vi-14)(r3(w-1)4i+(1-r)(d-12)(Vi-13)))+c(i,w)X(i-1,d-2,w-1)×((d-2)(Vi-1-d+12)(Vi-14)p(1-r)(d-2)(Vi-1-d+1)(Vi-13)+(1-p)(1-q)(d-2)(Vi-1-d+12)(Vi-14))+c(i,w)X(i-1,d-3,w-1)×(p(1-r)(Vi-1-d+22)(Vi-13)+(1-p)(1-q)(Vi-1-d+23)(Vi-14))+c(i,w)pδd,3δw,1(p(r3(w-1)4i+(1-r)(d-12)(Vi-13))].
Let B(n,d,w) denote the sum of the conditional variances of the process Z(n,d,w). Now we will give an upper bound of B(n,d,w) as follows:
(26)B(n,d,w)=∑i=2n‍𝔻2(Z(i,d,w)∣ℱi-1)=∑i=2n‍𝔼{(Z(i,d,w)-𝔼(Z(i,d,w)∣ℱi-1))2∣ℱi-1}=∑i=2n‍c(i,w)2×𝔼{(X(i,d,w)-𝔼(X(i,d,w)∣ℱi-1))2∣ℱi-1}≤∑i=2n‍c(i,w)2×𝔼{(X(i,d,w)-X(i-1,d,w))2∣ℱi-1}≤16∑i=2n‍c(i,w)2=O(n2(αw+β)+1).
Above we used that c(i,w) is ℱi-1-measurable and at each step four vertices can interact. Jensen’s inequality implies that M2(n,d,w) is a (nonnegative) submartingale if M(n,d,w) is a martingale. Now we can apply the Doob-Meyer decomposition to M2(n,d,w). It is known that B(n,d,w), that is the sum of the conditional variances of terms Z(n,d,w) from formula (26), is the same (up to an additive constant) as the increasing predictable process in the Doob-Meyer decomposition of the nonnegative submartingale M2(n,d,w). Therefore the Doob-Meyer decomposition is
(27)M2(n,d,w)=Y(n,d,w)+B(n,d,w),
where Y(n,d,w) is a martingale and the predictable increasing process B(n,d,w) is given by (26).
We use induction onw. Let w=1. We can see that a vertex of weight 1 could take part in an interaction when it was born. Therefore its degree must be equal to 3. By (25) and (20),
(28)A(n,3,1)~p∑i=2n‍c(i,1)~p∑i=2n‍a1iα+β~pa1nα+β+1α+β+1
almost surely as n→∞. By (26), B(n,3,1)=O(n2(α+β)+1) and therefore (B(n,3,1))1/2logB(n,3,1)=O(A(n,3,1)). It follows from Proposition VII-2-4 of [8] (see Proposition 10 in the Appendix) that
(29)Z(n,3,1)~A(n,3,1)a.s.ontheevent{A(n,3,1)⟶∞}asn⟶∞.
As, by (28), A(n,3,1)→∞ almost surely, therefore using (18) and (20), relation (29) implies
(30)X(n,3,1)Vn=Z(n,3,1)c(n,1)Vn~A(n,3,1)c(n,1)Vn~pa1(nα+β+1/(α+β+1))a1nα+βpn=1α+β+1=x3,1>0
almost surely. So (14) is valid for w=1.
Now letw=2. In this case the degree of the vertex must be 3≤d≤6. If w=2 and d=3,4,or6, then we will show xd,w>0. By (18), (20), and (25), we can find the asymptotic behaviour of A(n,d,2) as
(31)A(n,3,2)~pa2n2α+β+12α+β+1(1-p)qx3,1⟶∞,A(n,4,2)~pa2n2α+β+12α+β+134prx3,1⟶∞,A(n,6,2)~pa2n2α+β+12α+β+1×[3(1-r)+4(1-p)(1-q)p]x3,1⟶∞.
Moreover, by (26), B(n,d,2)=O(n2(2α+β)+1); thus, (B(n,d,2))1/2logB(n,d,2)=O(A(n,d,2)) for d=3, 4, and 6. Therefore in these cases Z(n,d,2)~A(n,d,2) almost surely on {A(n,d,2)→∞} as n→∞. It implies that
(32)X(n,d,2)Vn=Z(n,d,2)c(n,2)Vn~A(n,d,2)c(n,2)Vn~pa2(n2α+β+1/(2α+β+1))a2n2α+βpnTd,2=Td,22α+β+1
with appropriate Td,2. In particular, we have
(33)X(n,3,2)Vn⟶(1-p)qx3,12α+β+1=x3,2>0,X(n,4,2)Vn⟶(3/4)prx3,12α+β+1=x4,2>0,X(n,6,2)Vn⟶[3(1-r)+4(1-p)(1-q)p]x3,12α+β+1=x6,2>0,
as n→∞. So (14) is valid for w=2 and d=3,4,6.
However, the cased=5, w=2 is different from the previous cases. As x5,2=0, the relation X(n,5,2)/Vn→x5,2 would not be enough to proceed the induction. By (25) and using Remark 1, we have
(34)A(n,5,2)=𝔼Z(1,5,2)+∑i=2n‍[3(Vi-1-42)(Vi-14))c(i,2)X(i-1,3,1)×(3(Vi-1-42)(Vi-14)p(1-r)3(Vi-1-4)(Vi-13)+(1-p)(1-q)3(Vi-1-42)(Vi-14)3(Vi-1-4)(Vi-13))].
Using (18), (34), and the limit of X(i-1,3,1)/Vi-1, we obtain
(35)A(n,5,2)~∑i=2n‍a2i2α+βx3,1ip×[18p(1-r)(pi)2+36(1-p)(1-q)(pi)2]~a2x3,118p∑i=2n‍i2α+β-1(p(1-r)+2(1-p)(1-q))~a2x3,118p(p(1-r)+2(1-p)(1-q))×n2α+β2α+β⟶∞,asn⟶∞.
Now we have
(36)X(n,5,2)Vn=Z(n,5,2)c(n,2)Vn=M(n,5,2)+A(n,5,2)c(n,2)Vn.
We denoted by B(n,d,w) the increasing predictable process in the Doob-Meyer decomposition of M2(n,d,w). We know, by (26), that B(n,5,2)=O(n4α+2β+1) and so (B(n,5,2))1/2logB(n,5,2)=O(n2α+β+1/2+ε) with arbitrary small positive ε.
Applying Propositions VII-2-3 and VII-2-4 of [8] (see Proposition 9 in the Appendix), we have
(37)M(n,5,2)=o((B(n,5,2))1/2logB(n,5,2))=o(n2α+β+1/2+ε)a.e.on{B(n,5,2)⟶∞}.
Moreover, on the set {B(∞,5,2)<∞}, the sequence M(n,5,2) is almost surely. convergent. So M(n,5,2)=o(n2α+β+1/2+ε) almost surely. Therefore, using (18), (20), and (35), we obtain
(38)X(n,5,2)Vn=M(n,5,2)+A(n,5,2)c(n,2)Vn≤Cn2α+β+1/2+εn2α+βn=C1na⟶0,
if n→∞ where 1/4<a<1/2. So the proposition is valid for w=1 and w=2.
Now, suppose that the statement is true for all weights less thanw and for all possible degrees. First we study the positive limits. Consider A(n,d,w) in (25) and assume that at least one of the coefficients xd,w-1, xd-1,w-1, xd-3,w-1 is positive. Then by (18), (20), and using the induction hypothesis, we see that
(39)A(n,d,w)~∑i=2n‍[4(1-p)(1-q)pi)c(i,w)xd,w-1pi(1-p)qw-1i+c(i,w)xd-1,w-1pipr3(w-1)4i+c(i,w)xd-3,w-1pi×(3p(1-r)pi+4(1-p)(1-q)pi)]~∑i=2n‍awiαw+β×[xd,w-1p(1-p)q(w-1)+xd-1,w-134p2r(w-1)+xd-3,w-1(3p(1-r)+4(1-p)(1-q))]~pawnαw+β+1αw+β+1×[4(1-p)(1-q)p)(1-p)q(w-1)xd,w-1+34pr(w-1)xd-1,w-1+(3(1-r)+4(1-p)(1-q)p)xd-3,w-1].
In the above computation we deleted all terms having asymptotically smaller degree than the largest one.
Consider the case when3≤d≤3w and d≠3w-1. In this case, by the induction hypothesis, there is at least one positive term in (39). Therefore (39) implies A(n,d,w)~pawnαw+β+1xd,w→∞ (because xd,w>0). In this case (B(n,d,w))1/2logB(n,d,w)=O(A(n,d,w)). So, using Proposition VII-2-4 of [8] (see Proposition 10 in the Appendix), we have Z(n,d,w)~A(n,d,w). Therefore
(40)X(n,d,w)Vn=Z(n,d,w)c(n,w)Vn~A(n,d,w)c(n,w)Vn~pawnαw+β+1xd,wawnαw+βpn=xd,wa.s.asn⟶∞,
where, by (39),
(41)xd,w=1αw+β+1×[α1(w-1)xd,w-1+α2(w-1)xd-1,w-1+βxd-3,w-1],
with α1, α2, α, and β defined by (4).
To handle the case when the limit is0, we argue as follows. Consider the case when d=3w-1. By (25) and using the induction hypothesis, we have
(42)A(n,3w-1,w)=𝔼Z(1,3w-1,w)+∑i=2n‍[(Vi-1-3w+33)(Vi-14))c(i,w)X(i-1,3w-3,w-1)×((3w-3)(Vi-1-3w+22)(Vi-14)p(1-r)(3w-3)(Vi-1-3w+2)(Vi-13)+(1-p)(1-q)(3w-3)(Vi-1-3w+22)(Vi-14)(3w-3)(Vi-1-3w+2)(Vi-13))+c(i,w)X(i-1,3w-4,w-1)×(p(1-r)(Vi-1-3w+32)(Vi-13)+(1-p)(1-q)(Vi-1-3w+33)(Vi-14))]~∑i=2n‍awiαw+β[x3w-3,w-1C11pi+O(1ia)]≤C1nαw+βαw+β+C2nαw+β+1-aαw+β+1-a=O(nαw+β+1-a).
On the other hand,B(n,d,w)=O(n2(αw+β)+1). Therefore, using (18), (20), and (42), by Propositions VII-2-3 and VII-2-4 of [8] (see Proposition 9 in the Appendix), we obtain
(43)X(n,d,w)Vn=Z(n,d,w)c(n,w)Vn=M(n,d,w)+A(n,d,w)c(n,w)Vn=O(nαw+β+1-a)nαw+βpn=O(n-a)⟶0=x3w-1,w,a.s.
So we have obtained the desired result for the case of 0 limit as well.


## 3. The Scale-Free Property for the Weights and Degrees

Lemma 4.
Letp>0 and define
(44)xw=x3,w+x4,w+⋯+x3w,w
for w=1,2,…. Then xw, w=1,2,…, are positive numbers satisfying the following recurrence:
(45)x1=1α+β+1,xw=α(w-1)+βαw+β+1xw-1,ifw>1,
where α and β are defined by (4). xw, w=1,2,…, is a discrete probability distribution. Moreover, xd,w, d=3,4,…,3w, w=1,2,…, is a two-dimensional discrete probability distribution.Proof.
Ifα=0, then the statement is obvious. Now assume α≠0. As xd,w is defined as xd,w=0 for d∉{3,4,…,3w}, therefore xw=∑d‍xd,w. From the recurrence (15) forxd,w, we obtain
(46)xw=∑d=33w‍xd,w=∑d‍xd,w=1αw+β+1[α1(w-1)∑d‍xd,w-1+α2(w-1)∑d‍xd-1,w-1+β∑d‍xd-3,w-1]=α(w-1)+βαw+β+1xw-1.
Using this recursive formula for xw, we obtain
(47)xw=x1∏j=2w‍α(j-1)+βαj+β+1=1α+β+1α+β2α+β+12α+β3α+β+1⋯(w-1)α+βwα+β+1=1αw+β+1∏j=1w-1‍β/α+j(β+1)/α+j=1αw+β+1Γ(w+β/α)Γ(1+β/α)Γ(1+(β+1)/α)Γ(w+(β+1)/α)=Γ(1+(β+1)/α)αΓ(1+β/α)Γ(w+β/α)Γ(w+(β+1)/α+1).
Moreover, by [9], we have the following formula:
(48)∑k=0n‍Γ(k+a)Γ(k+b)=1a-b+1[Γ(n+a+1)Γ(n+b)-Γ(a)Γ(b-1)].
Therefore, by some calculation, we obtain ∑w=1n‍xw→1, as n→∞. So ∑w=1∞‍xw=1. As ∑d‍xd,w=xw, so ∑w=1∞‍∑d=33w‍xd,w=1 and therefore xd,w, d=3,4,…,3w, w=1,2,…, is a (proper) two-dimensional discrete probability distribution.LetX(n,w) denote the number of vertices of weight w after n steps. Next theorem is the scale-free property for the weights. It is an extension of Theorem  3.1 in [6].Theorem 5.
Let0<p<1, q>0, r>0 and (1-r)(1-q)>0. Then for all w=1,2,… one has
(49)X(n,w)Vn⟶xw=x3,w+x4,w+⋯+x3w,w
almost surely, as n→∞, where xw, w=1,2,…, are positive numbers satisfying the recurrence (45). Moreover,
(50)xw~Cw-(1+1/α),
as w→∞, with C=Γ(1+(β+1)/α)/(αΓ(1+β/α)).Proof.
We have(51)X(n,w)=X(n,3,w)+X(n,4,w)+⋯+X(n,3w,w).
Therefore, by Theorem 3,
(52)X(n,w)Vn⟶x3,w+⋯+x3w,w=xw
almost surely, as n→∞. Here each xw is positive.
Using formula (47) and the Stirling-formula for the Gamma function, we obtain
(53)xw=Γ(1+(β+1)/α)αΓ(1+β/α)Γ(w+β/α)Γ(w+(β+1)/α+1)~C0(w+β/α)(w+β/α)(w+β/α+1/α+1)(w+β/α+1/α+1)=C0((w+β/α)(w+β/α+1/α+1))(w+β/α)×1(w+β/α+1/α+1)1/α+1~Cw-(1+1/α),
where C0=Γ(1+(β+1)/α)/(αΓ(1+β/α))(1/(1/e)1+1/α) and C=Γ(1+(β+1)/α)(αΓ(1+β/α)).Now, following [7], we construct a representation of the limiting joint distribution of degrees and weights.LetW be a random variable with distribution ℙ(W=w)=xw,w=1,2,…. Let ξ1≡3 and ξ2,ξ3,… be independent random variables being independent of W, too. For w≥2 let ξw have the following distribution:
(54)ℙ(ξw=0)=α1(w-1)α(w-1)+β,ℙ(ξw=1)=α2(w-1)α(w-1)+β,ℙ(ξw=3)=βα(w-1)+β.
Introduce notation Sw=ξ1+ξ2+⋯+ξw.The following representation of the joint distribution of degrees and weights is useful to obtain scale-free property for degrees.Theorem 6.
ℙ
(
S
W
=
d
,
W
=
w
)
=
x
d
,
w for all w=1,2,…, d=3,4,…,3w.Proof.
It is easy to see that ifw=1 and d=3, then we have
(55)ℙ(SW=3,W=1)=ℙ(S1=3,W=1)=ℙ(ξ1=3,W=1)=ℙ(W=1)=x1=x3,1.
If w=2 and d=5 we have
(56)ℙ(SW=5,W=2)=ℙ(S2=5,W=2)=ℙ(ξ1=3,ξ2=2,W=2)=0=x5,2.
Generally, for all w=1,2,… and d=3w-1 we have
(57)ℙ(SW=3w-1,W=w)=ℙ(ξ1=3,ξ2=k2,…,ξw=kw,W=w)=0=x3w-1,w,
because one of k2,…,kw should be equal to 2, which is of zero probability. Furthermore, using the recursion (45) and the assumption that ξi are independent random variables which are independent of W, we have
(58)ℙ(SW=d,W=w)=ℙ(Sw=d,W=w)=ℙ(Sw=d)ℙ(W=w)=[ℙ(Sw-1=d)ℙ(ξw=0)+ℙ(Sw-1=d-1)ℙ(ξw=1)+ℙ(Sw-1=d-3)ℙ(ξw=3)]×ℙ(W=w-1)xwxw-1=[ℙ(Sw-1=d)ℙ(W=w-1)α1(w-1)+ℙ(Sw-1=d-1)ℙ(W=w-1)α2(w-1)+ℙ(Sw-1=d-3)ℙ(W=w-1)β]×1αw+β+1=1αw+β+1×[α1(w-1)ℙ(SW=d,W=w-1)+α2(w-1)(SW=d-1,W=w-1)+βℙ(SW=d-3,W=w-1)].
Therefore, the sequence ℙ(SW=d,W=w) satisfies the same recursion (15) as xd,w.Theorem 7.
Suppose thatα1>0 and α2>0. Then
(59)xd,w=xwα2πα1α2w×[exp(-(d-𝔼Sw)22𝔻2Sw)+O(w-1/2)],asw⟶∞,
where the error term O(w-1/2) does not depend on d.Proof.
We can follow the ideas of Theorem  4.2 in [7]. For w≥1 we have
(60)𝔼ξw=α2(w-1)α(w-1)+β+3βα(w-1)+β=α2α+(3α-α2)βα(α(w-1)+β);
hence,
(61)𝔼Sw=𝔼ξ1+⋯+𝔼ξw=wα2α+O(logw),
as w→∞. Similarly, by simple computation, we have
(62)𝔻2ξw=α1α2α2+O(1w),𝔻2Sw=α1α2α2w+O(logw),
as w→∞.
Now, we can apply Theorem VII.2.5 in [10] (see Proposition 11 in the Appendix) for Sw. The conditions of that theorem are satisfied; therefore, we have
(63)supd∈ℤ|𝔻Swℙ(Sw=d)-12πexp(-(d-𝔼Sw)22𝔻2Sw)|=O(1w).
Using (62) and (63), we obtain |𝔻Sw-α1α2w/α|ℙ(Sw=d)=O(w-1/2). Therefore, it follows from (63) that
(64)supd∈ℤ|α1α2wαℙ(Sw=d)-12πexp(-(d-𝔼Sw)22𝔻2Sw)|=O(1w).
The independence of W and ξi implies that xd,w=ℙ(SW=d,W=w)=ℙ(Sw=d)xw. Using this in (64), we can obtain the desired result.Our last theorem is an extension of Theorem  4.3 in [7] to the case of 4 interactions. The theorem shows the scale-free property for the degrees.Theorem 8.
Let0<p<1, q>0, r>0 and (1-r)(1-q)>0. Let us denote by U(n,d) the number of vertices of degree d after n steps; that is, U(n,d)=∑w:d/3≤w≤n+1‍X(n,d,w). Then, for any d≥3 one has
(65)U(n,d)Vn⟶ud=∑w‍xd,w
almost surely as n→∞, where ud are positive numbers. Furthermore,
(66)ud~Γ(1+(β+1)/α)α2Γ(1+β/α)(αdα2)-(1+1/α),
as d→∞.Proof.
By Theorems3 and 6, X(n,d,w)/Vn converges almost surely to the distribution xd,w=ℙ(SW=d,W=w). But the cardinalities of terms in ∑w:d/3≤w≤n+1‍X(n,d,w) are not bounded when n→∞. However, using that xd,w, d=3,4,…,3w, w=1,2,… is a proper two-dimensional discrete distribution, the convergence of the marginal distributions is a consequence of the convergence of the two-dimensional distributions. So we obtain (65).
To obtain (66), we can apply the method of Theorem  4.3 in [7]. Let
(67)f=αα2d,H=Hd={w:f-f1/2+ε≤w≤f+f1/2+ε},H-=Hd-={w:w<f-f1/2+ε},H+=Hd+={w:w>f+f1/2+ε}
with some fixed 0<ε<1/6.
Using (61) and Hoeffding’s exponential inequality (Theorem  2 in [11], see Proposition 12 in the Appendix) we obtain for w∈H-(68)ℙ(Sw=d)≤ℙ(Sw≥d)≤ℙ(Sw-𝔼Sw≥d-α2αw-O(logw))≤exp{-29w(d-α2αw-O(logw))2}=exp{-29(α2α)2(f-w-O(logw))2w}.
Here w∈H- implies that
(69)(f-w-O(logw))2=(f-w)2-2(f-w)O(logw)+(O(logw))2≥f1+2ε-O(flogf).
Therefore in the case when w∈H- we have
(70)ℙ(Sw=d)≤exp{-29(α2α)2f1+2ε-O(flogf)f}=exp{-29(α2α)2f2ε+O(logf)}.
Using this, we can obtain that
(71)ℙ(SW=d,W∈H-)=∑w∈H-‍ℙ(Sw=d,W=w)≤∑w∈H-‍ℙ(Sw=d)≤fexp{-29(α2α)2f2ε+O(logf)}=o(f-(1+1/α)).
Similarly, if w∈H+, again by Hoeffding’s inequality, we have
(72)ℙ(Sw=d)≤ℙ(Sw≤d)≤ℙ(Sw-𝔼Sw≤d-α2αw)≤exp{-29w(d-α2αw)2}=exp{-29(α2α)2(f-w)2w}.
Using that w∈H+ and 1/2+ε<1, we obtain 2(w-f)≥f1/2+ε+w-f≥f1/2+ε+(w-f)1/2+ε≥w1/2+ε. Therefore
(73)ℙ(Sw=d)≤exp{-29(α2α)2w1+2ε4w}=exp{-118(α2α)2w2ε}.
Hence
(74)ℙ(SW=d,W∈H+)≤∑{w:f<w}‍exp{-118(α2α)2w2ε}=o(f-(1+1/α)).
Now consider the case whenw∈H=Hd. First we need some general facts. Consider the set
(75)B={(d,w):w≥1,d≥3,w∈Hd}.
It is easy to see that when (d,w)∈B then d→∞ if and only if w→∞. More precisely,
(76)wd⟶1,ifd⟶∞,(d,w)∈B.
As w∈H, so we have w=f+O(f1/2+ε). Then (with ε1>0 arbitrarily small)
(77)-(d-𝔼Sw)22𝔻2Sw=-(d-w(α2/α)-O(logw))22(α1α2/α2)w+O(logw)=-α2α1(f-w-O(logw))22w+O(logw)=-α2α1(f-w)2+O(f1/2+ε+ε1)2w+O(logw)=-α2α1(f-w)2+O(f1/2+ε+ε1)2f×2f2f+O(f1/2+ε)=-α2α1(f-w)2+O(f1/2+ε+ε1)2f×[1-O(f1/2+ε)2f+O(f1/2+ε)]=-α2α1(f-w)22f+O(f-1/2+3ε),
as d→∞. Here the error term does not depend on w. We will apply Theorem 7, that is, formula (59). The asymptotic behaviour of xw is known from (50). Using these facts and (77), we obtain
(78)xd,w~Cw-(1+1/α)α2πα1α2w×[exp{-α2α1(f-w)22f+O(f-1/2+3ε)}+O(w-1/2)]~Cf-(1+1/α)αα212π(α1/α2)fexp{-(f-w)22(α1/α2)f}
as d→∞ and w∈H, where C=Γ(1+(β+1)/α)/(αΓ(1+β/α)). Therefore
(79)∑w∈H‍xd,w~∑f-f1/2+ε<w<f+f1/2+ε‍Cf-(1+1/α)αα212π(α1/α2)f×exp{-(f-w)22(α1/α2)f}=Cf-(1+1/α)αα2∑-f1/2+ε<k<f1/2+ε‍12π(α1/α2)f×exp{-k22(α1/α2)f}=A∑-fε<k/f<fε‍1f12π(α1/α2)×exp{-(k/f)22(α1/α2)}⟶A∫-∞+∞‍12π(α1/α2)exp{-x22(α1/α2)}dx=A.
Thus we have
(80)ℙ(SW=d,W∈H)~A=Γ(1+(β+1)/α)α2Γ(1+β/α)(αdα2)-(1+1/α),
as d→∞. Finally, (71), (74), and (80) imply
(81)ud=∑w‍xd,w=∑w∈H-‍xd,w+∑w∈H‍xd,w+∑w∈H+‍xd,w~o(f-(1+1/α))+Cαα2f-(1+1/α)+o(f-(1+1/α))~Γ(1+(β+1)/α)α2Γ(1+β/α)((α/α2)d)-(1+1/α),
as d→∞. The proof is complete.



---

*Source: 707960-2013-09-22.xml*