A geometric preferential attachment model with fitness H. van den Esker ∗ 3 January 2008 8 0 0 2 Abstract n a We study a random graph Gn, which combines aspects of geometric random graphs and preferential J attachment. Theresultingrandomgraphshavepower-lawdegreesequenceswithfinitemeanandpossibly 0 infinite variance. In particular, the power-law exponent can be any valuelarger than 2. 1 The vertices of Gn are n sequentially generated vertices chosen at random in the unit sphere in R3. A newly added vertex has m edges attached to it and the endpoints of these edges are connected to ] old vertices or to theadded vertex itself. The vertices are chosen with probability proportional to their O currentdegreeplussomeinitialattractivenessandmultipliedbyafunction,dependingonthegeometry. C . Keywords: Complex networks; Random geometric graphs; Scale free graphs; Preferential attachment; h t Power-lawdistributions; Ad hoc networks a m 2000 Mathematics Subject Classification: 05C80(Primary)05C07(Secondary) [ 1 1 Introduction v 2 1 Preferential attachment models are proposed by Baraba´si and Albert [1] as models for large-scale networks 6 like the Internet, electrical networks, telephone networks, and even complex biological networks. These 1 networks grow in time, because, for example, new routers, transform houses, switchboards or proteins are . 1 addedto the network. The behaviorcanbe modeledby means ofarandomgraphprocess. A randomgraph 0 process is a stochastic process that describes a random graph evolving with time. At each time step, the 8 random graph is updated using a given rule of growth, which will be specified later. 0 In literature a number of different rules of growth are explored. For example, each time step we add or : v remove edges/vertices [2], or, more advanced, copy parts of the graph [9]. Furthermore, there is freedom i X in the choice how to connect endpoints of newly added edges. Mostly, one randomly chooses the endpoint r over the vertices, or proportional to the degree. Another possibility is to assign to each vertex a fitness. In a [3, 4] additive fitness is explored where one chooses proportional to the degree plus some (random) value. In [5, 10] multiplicative fitness is explored where each vertex has a random fitness and one chooses a vertex proportional to the degree times the fitness. In this paper we use a constant additive fitness and a variant of multiplicative fitness, depending on the distance between vertices. Many large networks of interest have power-law degree sequences, by which we mean that the number of vertices with degree k falls off as k−τ for some exponent τ >1. The parameter τ is called the power-law exponent. Depending onthe value ofτ we classify the followingthree categories: the infinite mean case, the finitemean andinfinitevariance case,andthefinitevariance case,whichcorrespondstoτ (1,2),τ (2,3) ∈ ∈ and τ >3, respectively. These categoriesareofinterest,becausethe behaviorofthe typicaldistanceis determinedbythe power- law exponent τ. Results in the literature show that if τ (1,2) the typical distance is bounded by some ∈ constant, if τ (2,3) the typical distance is concentrated around loglogn and if τ > 3 it is concentrated ∈ around logn, where n is the number of vertices of the graph, see [13, 14, 15, 16, 10]. A large number of graph models have been introduced to describe complex networks, but often the underlying geometry is ignored. In generalit is difficult to get rigorousresults for properties like the degree distribution, typical distances or diameter, even if one disregardsthe geometry. However,in wireless ad-hoc ∗DelftUniversityofTechnology,ElectricalEngineering,MathematicsandComputerScience,P.O.Box5031,2600GADelft, TheNetherlands. E-mail: [email protected] 1 networks the geometry is of great importance, since in these networks nodes are spread over some surface and nodes can only communicate with neighbors within a certain range, depending on the geometry. In this paper we will rely on the geometric preferential attachment (GPA) model introduced in [6] and extended in [7] by the same authors. The GPA model is a variant of the well known Baraba´si-Albert (BA) model. IntheBAmodelnewverticesareaddedtothegraphoneatatime. Eachnewvertexisconnectedto moftheexistingvertices,wherewechoosetoconnecttoanoldvertexproportionaltoitsdegree. IntheGPA model eachvertex has a position ona surface,and we choose to connectto anold vertex proportionalto its degree times a non-constant multiplicative value. This multiplicative value depends on the distance of the old vertex and the newly added vertex. For instance, let the multiplicative constant be 1 if the vertices are atdistanceatmostr ,andotherwisezero. The latterattachmentruleessentiallydescribestheconstruction n of a simplified wireless ad-hoc network. 1.1 Definition of the model In this section we will introduce the Geometric Preferential Attachment model with fitness (GPAF). The GPAF model is described by a random graph process G n , which we will study for large values of n. For 0 σ n, each vertex of the graph G = (V ,E ){isσp}oσs=i0tioned on the sphere S R3. The radius of σ σ σ ≤ ≤ ⊂ the sphere S is taken equal to 1/(2√π), so that, conveniently, Area(S) = 1. The vertices of the graph G σ are given by V = 1,2,...,σ and E is the set of edges. The position of vertex v V in the graph G is σ σ σ σ { } ∈ given by x S and the degree at time σ is given by d (v). v σ ∈ In total we need 4 parameters to describe the GPAF model. The first parameter of the model is m = m(n) > 0, which is the number of edges added in every time step. The second parameter is α 0, which ≥ is a measure of the bias toward self-loops. The third one is δ > m, which is the initial attractiveness of a vertex. And,finally,thefourthparameterisafunctionF :[0,π]− R ,wherethevalueF (u)isaindicator n + n → of the attraction between two vertices at distance u. Before we give the model definition, we first will explain the use of the parameter α. Assume that the graph G is given, consisting of the vertices V . We construct the graph G by choosing vertex x σ σ σ+1 σ+1 uniformly atrandomin S andadditto G withm directededges emanatingfromthe vertexx . Let, for σ σ+1 σ =1,2,...,n 1, − σ T (u)= (d (v)+δ)F (x u), (1.1) σ,n σ n v | − | v=1 X where x u [0,π] is the angular distance from u to u along a circle with radius 1/(√2) over the v 0 | − | ∈ sphere S. Furthermore, let the endpoints of the m emanating edges be givenby the vertices v(1) ,...,v(m) . σ+1 σ+1 Intuitively, we would like to choose the endpoints at random (with replacement) from V , such that v V σ σ ∈ is chosen with probability (d (v)+δ)F (x x ) P v(i) =v = σ n | v − σ+1| , σ σ+1 T (x ) σ,n σ+1 (cid:0) (cid:1) where P ( ) = P( G ,x ). However, the above given rule of growth is not well-defined. To see this, σ σ σ+1 · ·| consider the simplified model for wireless ad-hoc networks, i.e., Fn(x) = 1{x≤rn}. Then, for any σ, there is a positive probability that there are no vertices within reach of the newly added vertex x and therefore σ+1 T (x )=0. σ,n σ+1 Introducing self-loops solvesthis problemandfor this the additionalparamaterα is introduced. We will follow the solution given by the authors of [7] for the GPA model: Rules of growth for α>0: Initial Rule (σ =0): To initialize the process, we start with G being the empty graph. 0 • Growth Rule (at time σ+1): We choose vertex x uniformly at random in S and add it to G σ+1 σ • with m directed edges emanating from the vertex x . Let the endpoints of the m emanating edges σ+1 givenby the verticesv(1) ,...,v(m) . We choosethe endpoints at random(with replacement)fromV , σ+1 σ+1 σ such that v V is chosen with probability σ ∈ (d (v)+δ)F (x x ) P v(i) =v = σ n | v − σ+1| , (1.2) σ σ+1 max T (x ),αE[T (x )]/2 σ,n σ+1 σ,n σ+1 { } (cid:0) (cid:1) 2 and T (x ) P v(i) =σ+1 =1 σ,n σ+1 , (1.3) σ σ+1 − max T (x ),αE[T (x )]/2 σ,n σ+1 σ,n σ+1 { } (cid:0) (cid:1) for i 1,2,...,m . ∈{ } The above given random graph model is well defined, since the denominator is always strictly positive. Indeed, the following lemma calculates the value of E[T (x )] which is strictly positive. σ,n σ+1 Lemma 1.1 For any fixed point v S, ∈ F (v u)du=I , (1.4) n n | − | ZS where 1 π I = F (x)sinxdx. n n 2 Zx=0 As a consequence, if U is a randomly chosen point from S, then E[T (U)]=I (2m+δ)σ. (1.5) σ,n n Proof. First note that I does not depend on v due to rotation invariance. Thus, without loss of n generality, we can assume that v is at the north pole of the sphere. Using spherical coordinates, we find du=r2sinθdθdϕ, where r =1/(2√π), and v u =θ, so that: 0 0 | − | 2π π π F (v u)du= r2F (θ)sinθdθdϕ=2πr2 F (θ)sinθdθ =I . n | − | 0 n 0 n n ZS Zϕ=0Zθ=0 Zθ=0 For the second claim we calculate the expected value of T (U), (1.1), conditional on the graph G : σ,n σ σ E[T (U) G ]= (d (v)+δ)E[F (x U ) G ] σ,n σ σ n v σ | | − | | v=1 X σ =I (d (v)+δ)=I (2m+δ)σ, n σ n v=1 X where we apply (1.4) on E[F (x U ) G ], since v σ and, therefore, n v σ | − | | ≤ E[F (x U ) G ]= F (x u)du=I . (1.6) n v σ n v n | − | | | − | ZS Hence, E[T (U)]=E[E[T (U) G ]]=I (2m+δ)σ. (cid:3) σ,n σ,n σ n | We use the abbreviations, for u S, ∈ M (u)=max T (u),αΘI σ and A (u)=F (u x ), (1.7) σ,n σ,n n σ,n n σ+1 { } | − | where Θ=Θ(δ,m)=(2m+δ)/2. (1.8) As a consequence, we can rewrite the attachment rules as (d (v)+δ)A (x ) T (x ) P v(i) =v = σ σ,n v and P v(i) =σ+1 =1 σ,n σ+1 , (1.9) σ σ+1 M (x ) σ σ+1 − M (x ) σ,n σ+1 σ,n σ+1 (cid:0) (cid:1) (cid:0) (cid:1) for i 1,2,...,m . ∈{ } Remark 1.2 In the above description we add directed edges to the graph and therefore we construct a directed graph. For questions about the connectedness and diameter of the graph we ignore the direction of the edges, but we need the direction of the edges in the proofs of the main results. 3 Remark 1.3 In this paper we will illustrate the theorems using the canonical functions 1 Fn(0)(u)≡1, Fn(1)(u)=1{|u|≤rn} and Fn(2)(u)= max n−ψ,u β, (1.10) { } where r nε−1/2, ε < 1/2, ψ < 1/2 and β (0,2) (2, ). The canonical function F(0) implies that the n ≥ ∈ ∪ ∞ n vertices are chosen proportional to the degree, and, furthermore, the geometry is ignored, the model is then equivalent to the PARID model, see [3] or section 1.2. The function F(1) implies that a new vertex can only § n connect to vertices at distance at most r . Finally, canonical function F(2) implies that vertices are chosen n n proportional to the degree, and, in contrast to F(0), will prefer vertices close to the new vertex, since F(2) is n n non-increasing as a function in u. 1.2 Heuristics and main results Using the results of [7], which is a special case of our model when δ = 0, together with the results of the PARID model, introduced in [3], we will predict how the power-law exponent of the degree sequence will behave. Consider the PARID randomgraphprocess G′ as introducedin [3] with constantweights equalto { σ}σ≥0 m. For this special case, we give a brief description of the model. The construction ofthe PARID graphG′ =(V′,E′) depends onthe graphG′ . The rule of growthis σ σ σ σ−1 asfollow: addavertextothegraphG′ andfromthisvertexemanatesmedges. Theendpointsofthesem σ−1 edges are chosen independently (with replacement) from the vertices of G′ . The probability that vertex σ−1 v V′ is chosen is proportional to the degree of vertex v plus δ, more specifically: ∈ σ−1 d (v)+δ P(choose vertex v G′ )= σ . (1.11) | σ (2m+δ)σ If α 2, δ > m and F = F(0), then the GPAF model coincides with the PARID model where the ≤ − n n weight of each vertex is set to m. Note that, for the chosen parameters, 1 π A (x )=F(0)(x x )=1, I(0) = sin(x)dx=1, σ,n v n | v − σ+1| n 2 Zx=0 and αΘI(0)σ 2Θσ=(2m+δ)σ = (d (v)+δ)=T(0)(x ), n ≤ σ σ,n σ+1 vX∈Vσ thus M(0)(x )=T(0)(x )=(2m+δ)σ. Therefore, the equations (1.9) turns into (1.11), since σ,n σ+1 σ,n σ+1 (d (v)+δ)A (x ) d (v)+δ P v(1) =v =P (choose vertex v)= σ σ,n v = σ . σ σ+1 σ M(0)(x ) (2m+δ)σ σ,n σ+1 (cid:0) (cid:1) Furthermore, note that for these parameters there are no self-loops, since T(0)(x ) M(0)(x ) P v(1) =σ+1 =1 σ,n σ+1 =1 σ,n σ+1 =0. σ σ+1 − M(0)(x ) − M(0)(x ) σ,n σ+1 σ,n σ+1 (cid:0) (cid:1) For the PARIDmodel,we knowthatthe power-lawexponentis3+δ/m,thus weexpectthatthe power- law exponent in ourmodel is 3+δ/m if α 2 and F =F(0). For α>2, δ =0 and F satisfying some mild ≤ n n n condition, see (1.12), we know from [7] that the power-law exponent is 1+α, which is independent of F . n We will show in this paper that the power-law exponent is given by 1+α(1+δ/2m), which generalizes the two mentioned papers [6, 7]. More precisely, let N (σ) denote the number of vertices of degree k in G k σ and let N¯ (σ) be its expectation. We will show that: k Theorem 1.4 (Behavior of the degree sequence) Supposethatα>2,δ > m=m(n)andinaddition − that for n , →∞ π F (x)2sinxdx= nθI2 , (1.12) n O n Zx=0 (cid:0) (cid:1) where θ <1 is a constant. Then there exists a constant γ >0 such that for all k=k(n) m, 1 ≥ m 1+α(1+δ/2m) N¯ (n)=neφk(m,α,δ) + (n1−γ1), (1.13) k k O (cid:16) (cid:17) 4 where φ (m,α,δ) tends to a constant φ (m,α,δ) as k . k ∞ →∞ Furthermore, for each ǫ > 0 and n sufficiently large, the random variables N (n) satisfy the following k concentration inequality P N (n) N¯ (n) I2nmax{1/2,2/α}+ǫ e−nǫ. (1.14) | k − k |≥ n ≤ (cid:16) (cid:17) Remark 1.5 Note that the power-law exponent in (1.13) does not depend on the choice of the function F . n We will see in the proof, that F manifests itself only in the error terms. n All the given canonical functions in Remark 1.3 do satisfy the condition given by (1.12): it should be evident that for F(0) the constants I and θ are given by I(0) = 1 and θ(0) = 0, respectively. Furthermore, n n n in [7] it is shown that one can take I(1) r2/4, I(2) = (1) if β (0,2), and I(2) nδ(β−2) if β > 2, and, n ∼ n n O ∈ n ∼ 2(β−2) hence we can take θ(1) =0, θ(2) =0 and θ(2) =2ψ, respectively. Before we consider the connectivity and diameter of G , we place some additional restrictions on the n functionF . Theserestrictionsarenecessarytoendupwithagraphwhichiswithhighprobabilityconnected. n Keep in mind the function Fn(1)(u)=1{|u|≤rn}, then it should be clear that rn should not decrease too fast, otherwise we end up with a disconnected graph. Let ρ =ρ(µ,n) be such that n 1 ρn µI = F (x)sinxdx, n n 2 Zx=0 for some µ (0,1]. ∈ We will call F smooth (for some value of µ) if n (S1) F is monotone non-increasing; n (S2) nρ2 Llogn, for some sufficiently large L; n ≥ (S3) ρ2F (2ρ ) c I , for some constant c which is bounded from below. n n n ≥ 3 n 3 Before stating the theorem, we will give an intuitive meaning of ρ . To that end, consider the function n Fn(1)(u) = 1{u<rn} and use the fact that if rn = O n−1/2−ε for some ε > 0, then the limiting graph is not connected, see [11]. It should be intuitively clear that in the limit, each newly added vertex x should n (cid:0) (cid:1) connect to at least one other vertex. Thus, there should be at least one vertex within distance r of x . At n n time n there are n 1 vertices and the probability that at least one of these vertices is at distance at most − r of vertex x , denoted by p (n,r ), is at most C(n 1)r2 for some constant C. On the other hand, we n n c n − n see that if r = n−1/2−ε then p (n,r )= n−2ε tends zero for large n, and, as a consequence, in the n c n O O limit the graph is not connected. If, as is our assumption, r >nε−1/2, then p (n,r ) . (cid:0) (cid:1) (cid:0) (cid:1) n c n →∞ Interpretρ forgeneralF astheradius. Theconditionthatp (n,r ) isreplacedbynρ2 >Llogn. n n c n →∞ n Then, intuitively, condition S2 implies that for general F the value p (n,ρ ), does not tend to zero and n c n implies that the limiting graph is connected. The conditions S1 and S3 are technicalities, combined they ensure that the ‘area’ due to the radius ρ is sufficiently large: condition S1 states that F is monotone n n non-increasingandcombinedwithS3onecanshowthatthe‘area’withinradius2ρ is(2ρ )2F (2ρ ),which n n n n is at least 4c I . 3 n Theorem 1.6 If α 2 and F is smooth, m Klogn, and K is sufficiently large constant, then with high n ≥ ≥ probability G is connected; n • G has diameter (logn/ρ ). n n • O Remark 1.7 Allthecanonicalfunctionsaresmooth. ItshouldbeevidentthatonecantakeforF(0): µ(0) =1, n ρ(0) =1 and c(0) =1 for F(0). For F(1)(u) one can take for example µ(1) 1/4 and ρ(1) =r /2 and c(1) 1. n 3 n n ∼ n n 3 ∼ Finally, F(2) is also smooth, we refer to [7] for the precise values of ρ(2),µ(2) and c(2). n n 3 Weendwithasharperresultonthediameter,howeverwe,also,needstrongerrestrictionsonthefunction F . We will call F tame if there exists strictly positive constants C and C such that n n 1 2 (T1) F (x) C for 0 x π; n 1 ≥ ≤ ≤ (T2) I C . n 2 ≤ 5 Theorem 1.8 If α 2, δ > m and F is tame and m Klogn, and K sufficiently large, then with high n ≥ − ≥ probability G is connected; n • G has diameter (log n). • n O m Remark 1.9 It should be evident that the function F(0) is tame, since one can take C = C = 1. If n 1 2 β (0,2) then we also have that F(2) is tame, since ∈ n 1 π π2−β F(2)(x) π−β, for 0 x π, and I(2) = x−βsinxdx . n ≥ ≤ ≤ n 2 ≤ 2(2 β) Zx=0 − Remark 1.10 If we consider the configuration model (CM), see 1.3, [15, 16] or the Poissonian random § graph (PRG), see [12, 10], then the typical distance depends on the power-law exponent. If the power-law exponent is larger than 3, then the typical distance is of (logn), where n is the number of vertices in the O graph, and if the power-law exponent is between 2 and 3 then the typical distance is of (loglogn). On O before hand, it is not clear if this holds for the GPAF model. Theorem 1.6, only states an upper bound on the diameter, independent of δ. If F = F(0) 1 and δ ( m,0) then the authors of [14] show that the diameter in the graph G n n ≡ ∈ − n fluctuates around loglogn. If Fn(u) = Fn(1)(u) = 1{|u|≤rn}, then, intuitively, the diameter depends only on r , since r determines the maximal length of an edge, and we conjecture that the diameter is at least of n n order logn. 1.3 Related work Inthissectionweconsiderrandomgraphmodels,whicharerelatedtotheGeometricPreferentialAttachment model with fitness (GPAF). As mentioned earlier the model is related to the Albert-Bara´basi (BA) model. In the BA-model the power-law exponent τ is limited to the value 3, which was proven by Bollob´as and Riordan. CooperandFriezeintroducedin[2]averygeneralmodelpreferentialattachmentmodel. Inthismodelit is both possible to introduce new vertices at each time step or to introduce new edges between old vertices. Due to the weightswithwhichedgesofthe new verticesareattachedtooldverticesandthe adding ofedges between old vertices, the power-law exponent τ can obtain any value τ >2. In [4] the authors overcome the restriction τ 3 in a different way, by choosing the endpoint of an edge ≥ proportional to the in-degree of a vertex plus some initial attraction A > 0. This is identical by choosing the endpoint of an edge proportionalto the degree of a vertexplus some amountδ =A m> m, as done − − in the PARID model (cf. [3]). The power-law exponent in [4] is given by τ =3+δ/m. Note that for δ =0 we obtain the BA model. The authors of [3] show more rigorously some of the results in [4]. Both in [2] and in [3] it is allowed to add a random number of edges W, with the introduction of a new vertex. In case the mean of W is finite the power-law exponent is given by τ = 3+δ/E[W]. Hence, if P(W = m) = 1 for some integer m 1 then we see that τ = 2+δ/m 2, since we can choose for δ any ≥ ≥ value in ( m,0). − In [6, 7] the authors add geometryto the BA model, which correspondsto the GPAF model, introduced above, with δ = 0. Due to a technical difficulty the model has an additional parameter, called α > 2. As a consequence of this restriction they only obtain power-law exponents greater than 3, since the power-law exponent is given by τ =α+2. By combining the GPA and PARID model, we obtain the GPAF model, introduced in this paper. Due tothe additionalparameterδ,itis inthis modelpossibletoobtainanypower-lawexponentτ biggerthan2. 1.4 Overview of the paper The remainder of this paper is divided into three sections. In 2 we will derive a recurrence relation for the § expected number of vertices of a given degree. In 3 we will present a coupling between the graph process § and an urn scheme, which will be used in 4 to show that the number of vertices with a given degree is § concentrated around its mean. 6 2 Recurrence relation for the expected degree sequence Inthis sectionwe will establisha recurrencerelationforN¯ (σ)=E[N (σ)], the expectednumber of vertices k k with degree k at time σ, which is claim (1.13) of Theorem 1.4. From this recurrence relation, we will show that N¯ (σ) σp , k k ∼ where p k−(1+α(1+δ/2m)), as k . The proof of claim (1.13) depends on a lemma, which is crucial k ∼ → ∞ for the proof. This lemma states that for sufficiently large n the value M (x ) is equal to αΘI σ, σ,n σ+1 n with high probability. This is a consequence of the fact that T (x ) is concentrated around its mean σ,n σ+1 E[T (x )]=2ΘI σ <αΘI σ, see (1.5) and (1.8), which is the content of the next lemma. σ,n σ+1 n n Lemma 2.1 If α>2, δ > m, σ =0,1,2,...,n, and U is chosen randomly from S then − P T (U) E[T (U)] >ΘI σ2/α+σ1/2logσ logn = n−2 . σ,n σ,n n | − | O (cid:16) (cid:16) (cid:17) (cid:17) (cid:0) (cid:1) The proof of this lemma is deferred to 4.1. § We will allow that m depends on n, thus m = m(n), as already pointed out previously. In establishing the recurrence relation for N¯ (σ), we will rely on the derivation for δ =0 in [7, Section 3.1]. k Ateachtime,weaddanewvertexfromwhichmedgesareemanating,andforeachofthesememanating edgesweneedtochooseavertex-endpoint. The firstpossibilityforavertextohavedegreek attime σ+1is thatthedegreeattimeσ wasequaltokandthatnoneofthemendpoints,emanatingfromx ,attachesto σ+1 the vertex. Furthermore, ignoring for the moment the effect of selecting the same vertex twice or more, the vertex could also havedegree k 1 at time σ andhaving one endpoint attached to it at time σ+1. Finally, − it is also possible that the newly added vertex x has degree k. The total number of vertex-endpoints σ+1 with degree k is distributed as Bin(m,p (σ)), where k (k+δ)A (x ) σ,n v p (σ)= , (2.1) k M (x ) σ,n σ+1 v∈XDk(σ) and D (σ) V is the set of vertices with degree k in the graph G . Similarly, the number of vertex- k σ σ ⊂ endpoints withdegreek 1is distributed asBin(m,p (σ)).If the newly addedvertexx ends upwith k−1 σ+1 − degree k, then this vertex has k m self-loops. The number of self-loops, d (σ+1) m, is distributed as σ+1 − − Bin(m,p), where p=1 T (x )/M (x ). (2.2) σ,n σ+1 σ,n σ+1 − For k m, this leads to, ≥ E[N (σ+1)G ,x ]=N (σ) mp (σ)+mp (σ) k σ σ+1 k k k−1 | − +E[1{dσ+1(σ+1)=k}|Gσ,xσ+1]+O(mηk(Gσ,xσ+1)), (2.3) where η (G ,x ) denotes the probability, conditionally on G , that the same vertex-endpoint is chosen k σ σ+1 σ at least twice and at most k times. Taking expectations on both sides of (2.3), we obtain (k+δ)A (x ) N¯ (σ+1)=N¯ (σ) mE σ,n v k k −  M (x )  σ,n σ+1 v∈XDk(σ)   (k 1+δ)A (x ) +mE − σ,n v  M (x )  σ,n σ+1 v∈DXk−1(σ) +P(d (σ+1) m=k m)+ (mE[η (G ,x )]). (2.4) σ+1 k σ σ+1 − − O Let = T (x ) 2ΘI σ <C ΘI σγlogn , (2.5) σ σ,n σ+1 n 1 n B {| − | } where max 2/α,θ <γ <1 and C is some sufficiently large constant. If 1 { } σ t =t (n)=(logn)2/(1−γ), 0 0 ≥ 7 then implies that for sufficiently large n, σ B T (x ) 2ΘI σ+C ΘI σγlogn=2ΘI σ 1+ log−1n αΘI σ, σ,n σ+1 n 1 n n n ≤ O ≤ since α>2, and, hence, with high probability (cid:0) (cid:0) (cid:1)(cid:1) M (x )=max T (x ),αΘI σ =αΘI σ. σ,n σ+1 σ,n σ+1 n n { } Next, we consider each term on the right hand side of (2.4) separately, for σ = 1,2,...,n. For the first two terms on the righthand side of (2.4) we will use that p (σ) is a probability and that P( c)= n−2 , k Bn O for σ >t , see Lemma 2.1, which yields 0 (cid:0) (cid:1) E[p (σ)]=E[p (σ) ]P( )+E[p (σ) c]P( c)=E[p (σ) ]+ n−2 . (2.6) k k |Bn Bn k |Bn Bn k |Bn O Also, using that N (σ) σ, (cid:0) (cid:1) k ≤ E[N (σ)] E[N (σ) c] E[N (σ) ]= k − k |Bn =N¯ (σ)+ σn−2 . (2.7) k |Bn P( ) k O n B (cid:0) (cid:1) For σ sufficiently large, using (1.4), (1.7), (2.1) and (2.7), k+δ E[p (σ) ]= E A (x ) k |Bn αΘI σ  σ,n v (cid:12) Bn n v∈XDk(σ) (cid:12)(cid:12)  (cid:12)  k+δ (cid:12) = E F (x(cid:12) u)du αΘI σ  n | v− | (cid:12) Bn n v∈XDk(σ)ZS (cid:12)(cid:12) = (k+δ)E[Nk(σ)|Bn] = (k+δ)N¯k(σ)(cid:12)(cid:12)(cid:12)+ kn−2 . (2.8) αΘσ αΘσ O (cid:0) (cid:1) Combining (2.6) and (2.8), we obtain (k+δ)A (x ) (k+δ)N¯ (σ) E[p (σ)]=E σ,n v = k + kn−2 , (2.9) k  M (x )  αΘσ O σ,n σ+1 v∈XDk(σ) (cid:0) (cid:1)   for σ t =t (n)=(logn)2/(1−γ). The above statement remains true when we replace k by k 1. 0 0 ≥ − For the third term on the right hand of (2.4), one can show that for σ t , using that d (x ) m 0 σ+1 σ+1 ≥ − has a binomial distribution, see (2.2), thus m P(d (x ) m=k m )= E pk−m(1 p)2m−k σ+1 σ+1 n n − − |B k m − B (cid:18) − (cid:19) (cid:2) (cid:12)k−m(cid:3) 2k−m m 2 (cid:12) 2 = 1 1+ σγ−1logn , k m − α α O (cid:18) − (cid:19)(cid:18) (cid:19) (cid:18) (cid:19) (cid:0) (cid:0) (cid:1)(cid:1) where we refer to [7, 3.1] for the derivation of the above result. It follows that § P(d (x )=k)=P(d (x ) m=k m )P( )+ (P( c)) σ+1 σ+1 σ+1 σ+1 − − |Bn Bn O Bn m 2 k−m 2 2k−m = 1 + σγ−1logn , (2.10) k m − α α O (cid:18) − (cid:19)(cid:18) (cid:19) (cid:18) (cid:19) (cid:0) (cid:1) where we refer to [7] for the derivation of the error term σγ−1logn . O For the fourth and final term on the right hand side of (2.4), we use (cid:0) (cid:1) k (i+ δ )2A (x )2 σ,n v η (G ,x )= min | | ,1 , k σ σ+1 O  M (x )2  σ,n σ+1 iX=mv∈XDi(σ)    which generalizes Equation (5) in [7]. Using similar arguments that led to (2.9),one can show for σ >t =t (n)=n(γ+θ)/2γ and k k =k (n)=n(γ−θ)/4, (2.11) 1 1 0 0 ≤ 8 that k2nθ E[mη (G ,x )]= = σγ−1 . (2.12) k σ σ+1 O mσ O (cid:18) (cid:19) (cid:0) (cid:1) Substituting (2.9), (2.10) and (2.12) in (2.4), we end up with the following recurrence relation: m m N¯ (σ+1)=N¯ (σ) (k+δ)N (σ)/σ+ (k 1+δ)N¯ (σ)/σ k k k k−1 − αΘ αΘ − +1{m≤k≤2m} m 1 2α−1 k−m 2α−1 2k−m+ σγ−1log(n) , (2.13) k m − O (cid:18) − (cid:19) (cid:0) (cid:1) (cid:0) (cid:1) (cid:0) (cid:1) for k m and N¯ (σ)=0 for all σ 0. The above recurrence relationdepends on σ and k. Consider the m−1 ≥ ≥ limiting case, i.e., σ , and assume that for each k the limit →∞ N¯ (σ)/σ p (2.14) k k → exists. If this is indeed the case, then in the limit the recurrence relation (2.13) yields: m m p = (k 1+δ)p (k+δ)p k k−1 k αΘ − − αΘ +1{m≤k≤2m} m 1 2α−1 k−m 2α−1 2k−m, k m − (cid:18) − (cid:19) (cid:0) (cid:1) (cid:0) (cid:1) where k m and p =0. By induction, we then obtain, for k>2m, m−1 ≥ m (k 1+δ) k 1+δ Γ(m+1+δ+ αΘ)Γ(k+δ) p = αΘ − p = − p = m p . k 1+ m (k+δ) k−1 k+δ+ αΘ k−1 Γ(m+δ)Γ(k+1+δ+ αΘ) 2m αΘ m m Using that Γ(t+a)/Γ(t) ta for a [0,1) and t large, we can rewrite the above equation as follow: ∼ ∈ m 1+ m m 1+α(1+δ/2m) p =φ (m,α,δ) αΘ =φ (m,α,δ) , k k k k k (cid:16) (cid:17) (cid:16) (cid:17) where φ (m,α,δ) = (1) and tends to the limit φ (m,α,δ) depending only on m,α and δ as k . k ∞ O → ∞ Finally, following the proof in [7, from equation (15) up to the end of the proof], which shows that there exists a constant M independent from n, such that N¯ (σ) p σ M(n1−(γ−θ)/4+σγlogn), (2.15) k k | − |≤ forall0 σ nandm k k (n). Thus,theassumption(2.14)issatisfied. Bypickingγ >0sufficiently 0 1 ≤ ≤ ≤ ≤ small, we can replace the right hand of (2.15) by n1−γ1, and one obtains the claim (1.13). 3 Coupling In this section we make preparations for the proofs of Lemma 2.1 and the concentration result in Theorem 1.4,see(1.14). Inthissectionwetakeτ 1,...,n fixedandweconsiderthegraphprocessuptotimeτ 1 ∈{ } − resultinginthe graphG . Attime τ weapplythe Growth Rule,see 1.1,twice onG ,independently τ−1 τ−1 of each other, which results in the graphs G and Gˆ . The idea is to co§mpare the graphs G and Gˆ over τ τ τ τ time by considering G and Gˆ for τ σ n. To this end, we will introduce two urn processes. The urns σ σ ≤ ≤ consistofweightedandnumberedballs. Insteadofchoosingavertex-endpointv V attimeσ+1by(1.2) σ+1 ∈ and (1.3), we will draw (with replacement) a ball proportionalto its weight and then the vertex-endpointis given by the number on the ball. The coupling between the urns will be introduced in four steps. The first step is to introduce for any σ τ twourns. Secondly,wewillintroduceaprobabilisticcouplingbetweenthetwournprocesses. Thirdly, we≥will describe the coupling between the graph processes G , Gˆ and the two urn processes. Finally, we σ σ consider the vertex-endpoints v(i) and vˆ(i), for i = 1,2,...,m, in the graphs G and Gˆ , respectively, and σ σ σ σ we will calculate the probability that v(i) =vˆ(i). σ 6 σ 9 3.1 The two urns In this section we describe the contents of the urns corresponding to the graphs G and Gˆ , for σ = σ σ τ,τ +1,...,n, and we give an alternative way of choosing the vertex-endpoints using the urns. Fixtwographprocesses G and Gˆ suchthatthegraphsuptotimeτ 1areidentical,i.e.,G =Gˆ s s s s { } { } − for s = 0,1,2...,τ 1, and that x = xˆ , for s = τ +1,τ +2,...,n. Thus, the points x and xˆ will s s τ τ differ from each othe−r, and, as a consequence, also, the edge sets E and Eˆ , for s= τ,τ +1,...,σ, will be s s different. Finally, we assume, without loss of generality, that T (x ) Tˆ (x ). σ,n σ+1 σ,n σ+1 ≤ Next, we will describe the contents of the urns U and Uˆ given the graphs G and Gˆ , and the newly σ σ σ σ added vertex x . We will use the following abbreviations: σ+1 T =T (x ) and M =M (x ). (3.1) σ,n σ,n σ+1 σ,n σ,n σ+1 Furthermore, if e is an edge, then we denote by to(e) the endpoint of the edge. Thus, if edge e is added at time t, emanating from the vertex t, points to a vertex s V then to(e)=s. t ∈ Contents of the urns: For each edge e E , such that to(e) = τ, there is a white ball in U of weight A (x ) and σ σ σ,n to(e) • ∈ 6 numberedto(e). Similarly,foreachedgeine Eˆ , suchthatto(e)=τ,there isawhite ballinUˆ of σ σ ∈ 6 weightA (xˆ )=A (x )andnumberedto(e). Observethatxˆ =x sinceto(e)=τ. σ,n to(e) σ,n to(e) to(e) to(e) 6 Foreachvertexv V τ thereisaredballineachofthe urnsU andUˆ ofweight(m+δ)A (x ) σ σ σ σ,n v • ∈ \{ } and numbered v. For the vertex τ there is in U a purple ball of weight (d (τ)+δ)A (x ) and number τ, and in Uˆ σ σ σ,n τ σ • there is an orange ball of weight (dˆ (τ)+δ)A (xˆ ) and numbered τ. σ σ,n τ For the vertex σ +1 each of the urns U and Uˆ contain a green ball of weight (αΘI σ Tˆ )+, σ σ n σ,n • − where ()+ = max 0, , and numbered σ+1. Furthermore, we add only to U a blue ball of weight σ ((αΘI σ· T )+{ (·α}ΘI σ Tˆ )+)+ and numbered σ+1. n σ,n n σ,n − − − Remark 3.1 The total weight of the white and red balls in U are given by σ Aσ,n(xto(e))1{to(e)6=τ} and (m+δ)Aσ,n(xv), eX∈Eσ v∈VXσ\{τ} respectively, and the weight of the purple ball in U can be rewritten as σ (dσ(τ)+δ)Aσ,n(xτ)= Aσ,n(xto(e))1{to(e)=τ}+(m+δ)Aσ,n(xτ). eX∈Eσ Therefore, the total weight of the white, red and purple balls in U is equal to: σ A (x )+ (m+δ)A (x )= (d (v)+δ)A (x )=T . σ,n to(e) σ,n v σ σ,n v σ,n eX∈Eσ vX∈Vσ vX∈Vσ Furthermore, from (1.7), and some easycalculation, thetotal weight of all theballs in U is M . Similarly, σ σ,n the total weight of the white, red and orange balls in the urn Uˆ is Tˆ and the total weight of all the balls σ σ,n in Uˆ is, precisely Mˆ . σ σ,n The weightofa balldepends onthe time σ, the colorofthe ballandthe number onthe ball. Letb be a ball in U or Uˆ , then we define the weight function w as σ σ σ A (x ) if b is white, σ,n ξ(b) (m+δ)A (x ) if b is red,  σ,n ξ(b) wσ(b)=((ddˆσσ((xxˆττ))++δδ))AAσσ,,nn((xxˆττ)) iiff bb iiss opruarnpglee,, (3.2) (αΘI σ Tˆ )+ if b is green, n σ,n − ((αΘInσ−Tσ,n)+−(αΘInσ−Tˆσ,n)+)+ if b is blue, 10