A phase transition for the diameter of the configuration model
Remco van der Hofstad∗
Gerard Hooghiemstra†and Dmitri Znamenski‡
August31,2007
Abstract
In this paper,we study the configuration model(CM)with i.i.d.degrees.We establish
a phase transition for the diameter when the power-law exponentτof the degrees satisfies
τ∈(2,3).Indeed,we show that forτ>2and when vertices with degree2are present with
positive probability,the diameter of the random graph is,with high probability,bounded from
below by a constant times the logarithm of the size of the graph.On the other hand,assuming
that all degrees are at least3or more,we show that,forτ∈(2,3),the diameter of the graph
is,with high probability,bounded from above by a constant times the log log of the size of the
1Introduction
Random graph models for complex networks have received a tremendous amount of attention in the past decade.See[1,22,26]for reviews on complex networks and[2]for a more expository account.Measurements have shown that many real networks share two fundamental properties. Thefirst is the fact that typical distances between vertices are small,which is called the‘small world’phenomenon(see[27]).For example,in the Internet,IP-packets cannot use more than a threshold of physical links,and if the distances in terms of the physical links would be large,e-mail service would simply break down.Thus,the graph of the Internet has evolved in such a way that typical distances are relatively small,even though the Internet is rather large.The second and maybe more surprising property of many networks is that the number of vertices with degree k falls offas an inverse power of k.This is called a‘power law degree sequence’,and resulting graphs often go under the name‘scale-free graphs’(see[15]for a discussion where power laws occur in the Internet).
The observation that many real networks have the above two properties has incited a burst of activit
y in network modelling using random graphs.These models can,roughly speaking,be divided into two distinct classes of models:‘static’models and’dynamic’models.In static models, we model with a graph of a given size a snap-shot of a real network.A typical example of this kind of model is the configuration model(CM)which we describe below.A related static model, which can be seen as an inhomogeneous version of the Erd˝o s-R´e nyi random graph,is treated in great generality in[4].Typical examples of the‘dynamical’models,are the so-called preferential attachment models(PAM’s),where added vertices and edges are more likely to be attached to vertices that already have large degrees.PAM’s often focus on the growth of the network as a way to explain the power law degree sequences.
∗Department of Mathematics and Computer Science,Eindhoven University of Technology,P.O.Box513,5600 MB Eindhoven,The Netherlands.E-mail:rhofstad@win.tue.nl
†Delft University of Technology,Electrical Engineering,Mathematics and Computer Science,P.O.Box5031,2600 GA Delft,The Netherlands.E-mail:G.Hooghiemstra@ewi.tudelft.nl
‡EURANDOM,P.O.Box513,5600MB Eindhoven,The Netherlands.E-mail:znamenski@eurandom.nl
Physicists have predicted that distances in PAM’s behave similarly to distances in the CM with simila
r degrees.Distances in the CM have attracted considerable attention(,[14,16,17,18]), but distances in PAM’s far less(see[5,19]),which makes it hard to verify this prediction.Together with[19],the current paper takes afirst step towards a rigorous verification of this conjecture.At the end of this introduction we will return to this observation,but let usfirst introduce the CM and present our diameter results.
1.1The configuration model
The CM is defined as follows.Fix an integer N.Consider an i.i.d.sequence of random variables D1,D2,...,D
N
.We will construct an undirected graph with N vertices where vertex j has degree
D j.We will assume that L
N =
N
j=1
D j is even.If L
N
is odd,then we will increase D
N
by1.This
single change will make hardly any difference in what follows,and we will ignore this effect.We will later specify the distribution of D1.
To construct the graph,we have N separate vertices and incident to vertex j,we have D j stubs or half-edges.The stubs need to be paired to construct the graph.We number the stubs in a given
order from1to L
N .We start by pairing at random thefirst stub with one of the L
N
−1remaining
英语画刊stubs.Once paired,two stubs form a single edge of the graph.Hence,a stub can be seen as the left-or the right-half of an edge.We continue the procedure of randomly choosing and pairing the stubs until all stubs are connected.Unfortunately,vertices having self-loops,as well as multiple edges between vertices,may occur,so that the CM is a multigraph.However,self-loops are scarce when N→∞,as in[7].
The above model is a variant of the configuration model[3],which,given a degree sequence,is the random graph with that given degree sequence.The degree sequence of a graph is the vector of which the k th coordinate equals the fraction of vertices with degree k.In our model,by the law of large numbers,the degree sequence is close to the distribution of the nodal degree D of which D1,...,D
N
are i.pies.
The probability mass function and the distribution function of the nodal degree law are denoted by
P(D=k)=f k,k=1,2,...,and F(x)= x
k=1
f k,(1.1)
where x is the largest integer smaller than or equal to x.We pay special attention to distributions of the form
1−F(x)=x1−τL(x),(1.2) whereτ>2and L is slowly varying at infinity.This means that the random variables D j obey a power law,and the factor L is meant to generalize the model.We denote the expectation of D by
µ,i.e.,
µ=
∞
k=1
kf k.(1.3)
1.2The diameter in the configuration model
In this section we present the results on the bounds on the diameter.We use the abbreviation whp for a statement that occurs with probability tending to1if the number of vertices of the graph N tends to∞.
Theorem1.1(Lower bound on diameter)Forτ>2,assuming that f1+f2>0and f1<1, there exists a positive constantαsuch that whp the diameter of the configuration model is bounded below byαlog N.
A more precise result on the diameter in the CM is presented in[16],where it is proved that under rather general assumptions on the degree sequence of the CM,the diameter of the CM divided by log N converges to a constant.This result is also valid for related models,such as the Erd˝o s-R´e nyi random graph,but the proof is quite difficult.While Theorem1.1is substantially weaker,the fact that a positive constant times log N appears is most interesting,as we will discuss now in more detail.
Indeed,the result in Theorem1.1is most interesting in the case whenτ∈(2,3).By[18, Theorem1.2],the t
ypical distance forτ∈(2,3)is proportional to log log N,whereas we show here that the diameter is bounded below by a positive constant times log N when f1+f2>0and f1<1. Therefore,we see that the average distance and the diameter are of a different order of magnitude. The pairs of vertices where the distance is of the order log N are thus scarce.The proof of Theorem 1.1reveals that these pairs are along long lines of vertices with degree2that are connected to each other.Also in the proof of[16],one of the main difficulties is the identification of the precise length of these long thin lines.
Our second main result states that whenτ∈(2,3),the above assumption that f1+f2>0is necessary and sufficient for log N lower bounds on the diameter.In Theorem1.2below,we assume that there exists aτ∈(2,3)such that,for some c>0and all x≥1,
1−F(x)≥cx1−τ,(1.4) which is slightly weaker than the assumption in(1.2).We further define for integer m≥2and a real numberσ>1,
C
F =C
F
(σ,m)=
2
|log(τ−2)|
+
2σ
log m
.(1.5)
Then our main upper bound on the diameter when(1.4)holds is as follows:
Theorem1.2(A log log upper bound on the diameter)Fix m≥2,and assume that P(D≥m+1)=1,and that(1.4)holds.Then,for everyσ>(3−τ)−1,the diameter of the configuration model is,whp,bounded above by C
F
log log N.
1.3Discussion and related work
Theorem1.2has a counterpart for preferential attachment models(PAM)proved in[19].In these PAM’s,at each integer time t,a new vertex with m≥1edges attached to it,is added to the graph. The new edges added at time t are then preferentially connected to older ,conditionally on the graph at time t−1,which is denoted by G(t−1),the probability that a given edge is connected to vertex i is proportional to d i(t−1)+δ,whereδ>−m is afixed parameter and d i(t−1)is the degree of vertex i at time t−1.A substantial literature exists,[10],proving that the degree sequence of PAM’s in rather great generality satisfy a power law(he references in [11]).In the above setting of linear preferential attachment,the exponentτis equal to[21,11]
τ=3+δ
m
.(1.6)
A log log t upper bound on the diameter holds for PAM’s with m≥2and−m<δ<0,which, by(1.6),corresp
onds toτ∈(2,3)[19]:
Theorem1.3(A log log upper bound on the diameter of the PAM)Fix m≥2andδ∈(−m,0).Then,for everyσ>1
3−τ
,and with
C
G (σ)=
4
|log(τ−2)|
+
4σ
log m
the diameter of the preferential attachment model is,with high probability,bounded above by C
G
log log t,as t→∞.
Observe that the condition m≥2in the PAM corresponds to the condition P(D≥m+1)=1 in the CM,where one half-edge is used to attach the vertex,while in PAM’s,vertices along a path
have degree at least three when m≥2.Also note from the definition of C
G and C
F
that distances
in PAM’s tend to be twice as big compared to distances in the CM.This is related to the structure of the graphs.Indeed,in both graphs,vertices of high degree play a crucial role in shortest paths. In the CM vertices of high degree are often directly connected to each other,while in the PAM, they tend to be connected through a later vertex which links to both vertices of high degree.
Unfortunately,there is no log t lower bound in the PAM forδ>0and m≥2,or equivalently τ>3.However,[19]does contain a(1−ε)log t/log log t lower bound for the diameter when m≥1 andδ≥0.When m=1,results exists on log t asymptotics of the diameter,[6,24].
The results in Theorems1.1–1.3are consistent with the non-rigorous physics predictions that distances in the PAM and in the CM,for similar degree sequences,behave similarly.It is an interesting problem,for both the CM and PAM,to determine the exact constant C≥0such that the diameter of the graph of N vertices divided by log N converges in probability to C.For the CM,the results in[16]imply that C>0,for the PAM,this is not known.
We now turn to related work.Many distance results for the CM are known.Forτ∈(1,2) distances are bounded[14],forτ∈(2,3),they behave as log log N[25,18,9],whereas forτ>3 the correct scaling is log N[17].Observe that these results induce lower bounds for the diameter of the CM,since the diameter is the supremum of the distance,where the supremum is taken over all pairs of vertices.Similar results for models with conditionally independent edges exist, [4,8,13,23].Thus,for these classes of models,distances are quite well understood.The authors in [16]prove that the diameter of a sparse random graph,with specified degree sequence,has,whp, diameter equal to c log N(1+o(1)),for some constant c.Note that our Theorems1.1–1.2imply that c>0when f1+f2>0,while c=0
when f1+f2=0and(1.4)holds for someτ∈(2,3).
There are few results on distances or diameter in PAM’s.In[5],it was proved that in the PAM
and forδ=0,for whichτ=3,the diameter of the resulting graph is equal to log t
log log t (1+o(1)).
Unfortunately,the matching result for the CM has not been proved,so that this does not allow us to verify whether the models have similar distances.
This paper is organized as follows.In Section2,we prove the lower bound on the diameter formulated in Theorem1.1and in Section3we prove the upper bound in Theorem1.2.
2A lower bound on the diameter:Proof of Theorem1.1
We start by proving the claim when f2>0.The idea behind the proof is simple.Under the conditions of the theorem,one can,whp,find a pathΓ(N)in the random graph such that this path consists exclusively of vertices with degree2and has length at least2αlog N.This implies that the diameter is at leastαlog N,since the above path could be a cycle.
Below we define a procedure which proves the existence of such a path.Consider the process of pairing stubs in the graph.We are free to choose the order in which we pair the free stubs,since this order is irrelevant for the distribution of the random graph.Hence,we are allowed to start with pairing the stubs of the vertices of degree2.
Let N(2)be the number of vertices of degree2and S
N
(2)=(i1,...,i N(2))∈N N(2)the collection of these vertices.We will pair the stubs and at the same time define a permutationΠ(N)=
(i∗1, (i)
N(2))of S
N
(2),and a characteristicχ(N)=(χ1,...,χN(2))onΠ(N),whereχj is either
0or1.Π(N)andχ(N)will be defined inductively in such a way that for any vertex i∗
k ∈Π(N),
χk=1,if and only if vertex i∗
k is connected to vertex i∗
k+1
.Hence,χ(N)contains a substring of
at least2αlog N ones precisely when the random graph contains a pathΓ(N)of length at least 2αlog N.
We initialize our inductive definition by i∗1=i1.The vertex i∗1has two stubs,we consider the second one and pair it to an arbitrary free stub.If this free stub belongs to another vertex j=i∗1 in S
N
(2)then we choose i∗2=j andχ1=1,otherwise we choose i∗2=i2,andχ1=0.Suppose for
some1<k≤N(2),the sequences(i∗1, (i)
k )and(χ1,...,χk−1)are defined.Ifχk−1=1,then one
stub of i∗
k is paired to a stub of i∗
k−1
,and another stub of i∗
k
is free,else,ifχk−1=0,vertex i∗
k
has
two free stubs.Thus,for every k≥1,the vertex i∗
k has at least one free stub.We pair this stub
to an arbitrary remaining free stub.If this second stub belongs to vertex j∈S
N (2)\{i∗1, (i)
k
},
then we choose i∗
k+1=j andχk=1,else we choose i∗
k+1
as thefirst stub in S
N
(2)\{i∗1, (i)
k
},
andχk=0.Hence,we have defined thatχk=1precisely when vertex i∗
k is connected to vertex
i∗k+1.
We show that whp there exists a substring of ones of length at least2αlog N in thefirst
half ofχ
N ,i.e.,inχ1
2
(N)=(χi∗
1
,...,χi∗
N(2)/2
).For this purpose,we couple the sequenceχ1
2
(N)
with a sequence B1
2(N)={ξk},whereξk are i.i.d.Bernoulli random variables taking value1with
probability f2/(4µ),and such that,whp,χi∗
k ≥ξk for all k∈{1,..., N(2)/2 }.We write P
N
for
the law of the CM conditionally on the degrees D1,...,D
N
.Then,for any1≤k≤ N(2)/2 ,the
P
N
-probability thatχk=1is at least
2N(2)−C
N
(k)
L
N −C
(k)
,(2.1)
where,as before,N(2)is the total number of vertices with degree2,and C
N
(k)is one plus the
total number of paired stubs after k−1pairings.By definition of C
N
(k),for any k≤N(2)/2,we have
C
N
(k)=2(k−1)+1≤N(2).(2.2) Due to the law of large numbers we also have that whp
N(2)≥f2N/2,L
N
≤2µN.(2.3) Substitution of(2.2)and(2.3)into(2.1)then yields that the right side of(2.1)is at least
N(2) L
N ≥
f2
4µ
.
Thus,whp,we can stochastically dominate all coordinates of the random sequenceχ1
2(N)with an
i.i.d.Bernoulli sequence B1
2(N)of Nf2/2independent trials with success probability f2/(4µ)>0.
It is well known([12])that the probability of existence of a run of2αlog N ones converges
to one whenever
2αlog N≤
log(Nf2/2) |log(f2/(4µ))|
,
We conclude that whp the sequence B1(N)contains a substring of2αlog N ones.Since whp
χ
N ≥B1
2
(N),where the ordering is componentwise,whp the sequenceχ
N
also contains the same
substring of2αlog N ones,and hence there exists a required path consisting of at least2αlog N vertices with degree2.Thus,whp the diameter is at leastαlog N,and we have proved Theorem 1.1in the case that f2>0.
We now complete the proof of Theorem1.1when f2=0by adapting the above argument. When f2=0,and since f1+f2>0,we must have that f1>0.Let k∗>2be the smallest integer such that f k∗>0.This k∗must exist,since f1<1.Denote by N∗(2)the total number of vertices of degree k∗of which itsfirst k∗−2stubs are connected to a vertex with degree1.Thus,effectively, after thefirst k∗−2stubs have been connected to vertices with degree1,we are left with a structure which has2free stubs.These vertices will replace the N(2)vertices used in the above proof.It is not hard to see that whp N∗(2)≥f∗2N/2for some f∗2>0.Then,the argument for f2>0can be repeated,replacing N(2)by N∗(2)and f2by f∗2.In more detail,for any1≤k≤ N∗(2)/(2k∗) , the P
N
-probability thatχk=1is at least
2N∗(2)−C∗
N
(k)
L
N −C
N
(k)
,(2.4)
where C∗
N
(k)is the total number of paired stubs after k−1pairings of the free stubs incident to the N∗(2)vertices.By definition of C∗
N
(k),for any k≤N∗(2)/(2k∗),we have
C
N
(k)=2k∗(k−1)+1≤N∗(2).(2.5)
晋江实验小学Substitution of(2.5),N∗(2)≥f∗2N/2and the bound on L N
in(2.3)into(2.4)gives us that the right side of(2.4)is at least
N∗(2) L
N ≥
f∗2
4µ
.
Now the proof of Theorem1.1in the case where f2=0and f1∈(0,1)can be completed as above.
We omit further details. 3A log log upper bound on the diameter forτ∈(2,3)
In this section,we investigate the diameter of the CM when P(D≥m+1)=1,for some integer m≥2.We assume(1.4)for someτ∈(2,3).We will show that under these assumptions C
F
log log N is
an upper bound on the diameter of the CM,where C
F
is defined in(1.5).
The proof is divided into two key steps.In thefirst,in Proposition3.1,we give a bound on the diameter of the core of the CM consisting of all vertices with degree at least a certain power of log N.This argument is very close in spirit to the one in[25],the only difference being that we have simplified the argument slightly.After this,in Proposition3.4,we derive a bound on the distance between vertices with small degree and the core.We note that Proposition3.1only relies on the assumption in(1.4),while Proposition3.4only relies on the fact that P(D≥m+1)=1,for some m≥2.The proof of Proposition3.1can easily be adapted to a setting where the degrees arefixed, by formulating the appropriate assumptions on the number of vertices with degree at least x for a sufficient range of x.This assumption would replace(1.5).Proposition3.4can easily be adapted to a setting where there are no vertices of degree smaller than or equal to m.This assumption would replace the assumption P(D≥m+1)=1,for some m≥2.We refrain from stating these extensions of our results,and start by investigating the core of the CM.
We takeσ>1
3−τand define the core Core
N
of the CM to be
Core
N
={i:D i≥(log N)σ},(3.1)
<,the set of vertices with degree at least(log N)σ.Also,for a subset A⊆{1,...,N},we define the diameter of A to be equal to the maximal shortest path distance between any pair of vertices of A.Note,in particular,that if there are pairs of vertices in A that are not connected,then the diameter of A is infinite.Then,the diameter of the core is bounded in the following proposition:
Proposition3.1(Diameter of the core)For everyσ>1
3−τ,the diameter of Core
N
is,whp,
bounded above by
2log log N
|log(τ−2)|
(1+o(1)).(3.2)
Proof.We note that(1.4)implies that whp the largest degree D
(N)
=max1≤i≤N D i satisfies
D
(N)
≥u1,where u1=N1τ−1(log N)−1,(3.3) because,when N→∞,
P(D
(N)>u1)=1−P(D
(N)
≤u1)=1−(F(u1))N≥1−(1−cu1−τ
1
)N
=1−
1−c
(log N)τ−1
N
N
∼1−exp(−c(log N)τ−1)→1.(3.4)
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议