a r X i v :c o n d -m a t /9903357v 1 [c o n d -m a t .s t a t -m e c h ] 24 M a r 1999
Renormalization group analysis of the small-world network model
M.E.J.Newman and D.J.Watts
Santa Fe Institute,1399Hyde Park Road,Santa Fe,NM 87501
We study the small-world network model,which mimics the transition between regular-lattice and random-lattice behavior in social networks of increasing size.We contend that the model displays a normal continuous phase transition with a divergent correlation length as the degree of randomness tends to zero.We propose a real-space renormalization group transformation for the model and demonstrate that the transformation is exact in the limit of large system size.We use this result to calculate the exact value of the single critical exponent for the system,and to derive the scaling form for the average number of “degrees of separation”between two nodes on the network as a function of the three independent variables.We confirm our results by extensive numerical simulation.
Folk wisdom holds that there are “six degrees of sepa-ration”between any two human beings on the planet—i.e.,a path of no more than six acquaintances linking any person to any other.While the exact n
umber six may not be a very reliable estimate,it does appear that for most social networks quite a short chain is needed to connect even the most distant of the network’s members [1],an observation which has important consequences for issues such as the spread of disease [2],oscillator syn-chrony [3],and genetic regulatory networks [4].At first sight this does not seem too surprising a result;random networks have average vertex–vertex distances which in-crease as the logarithm of the number of vertices and which can therefore be small even in very large networks [5].However,real social networks are far from random,possessing well-defined locales in which the probability of connection is high and very low probability of con-nection between two vertices chosen at random.Watts and Strogatz [6]have recently proposed a model of the “small world”which reconciles these observations.Their model does indeed possess well-defined locales,with ver-tices falling on a regular lattice,but in addition there is a fixed density of random “shortcuts”on the lattice which can link distant vertices.Their principal finding is that only a very small density of such shortcuts is necessary to produce vertex–vertex distances comparable to those found on a random lattice.
In this paper we study the model of Watts and Stro-gatz using the techniques of statistical physics,and show that it possesses a continuous phase transition in the limit where the density of sh
ortcuts tends to zero.We investi-gate this transition using a renormalization group (RG)method and calculate the scaling forms and the single critical exponent describing the behavior of the model in the critical region.
Previous studies have concentrated on the one-dimensional version of the small-world model,and we will start with this version too,although we will later generalize our results to higher dimensions.In one di-mension the model is defined on a lattice with L sites and periodic boundary conditions (the lattice is a ring).Initially each site is connected to all of its neighbors up to some fixed range k to make a network with average coordination number z =2k [7].Randomness is then in-troduced by independently rewiring each of the kL con-nections with probability p .“Rewiring”in this context means moving one end of the connection to a new,ran-domly chosen site.The behavior of the network thus depends on three independent parameters:L ,k and p .In this paper we will study a slight variation on the model in which shortcuts are added between randomly chosen pairs of sites,but no connections are removed from the regular lattice.For sufficiently small p and large L this makes no difference to the mean separation between ver-tices of the network for k ≥2.For k =1it does make a difference,since the original small-world model is poorly defined in this case—there is a finite probability of a part of the lattice becoming disconnected from the rest and therefore making
an infinite contribution to the average distance between vertices,and this makes the distance averaged over all networks for a given value of p also infi-nite.Our variation does not suffer from this problem and this makes the analysis significantly simpler.In Fig.1we show some examples of small-world networks.
We consider the behavior of the model for low density p of shortcuts.The fundamental observable quantity that we measure is the shortest distance between a pair of ver-tices on the network,averaged both over all pairs on the network and over all possible realizations of the random-ness.This quantity,which we denote ℓ,has two regimes of behavior.For systems small enough that there is much less than one shortcut on the lattice on average,ℓis dom-inated by the connections of the regular lattice and can be expected to increase linearly with system size L .As the lattice becomes larger with p held fixed,the aver-age number of shortcuts will eventually become greater than one and ℓwill start to scale as log L .The transition between these two regimes takes place at some interme-diate system size L =ξ,and from the arguments above we would expect ξto take a value such that the number of shortcuts pkξ≃1.In other words we expect ξto di-verge in the limit of small p as ξ∼p −1.The quantity ξplays a role similar to the correlation length in an inter-acting system in conventional statistical physics,and its divergence leaves the small-world model with no charac-ter
istic length scale other than the fundamental lattice spacing.Thus the model possesses a continuous phase transition at p =0,and,as we will see,this gives rise
1
FIG.1.The RG transformations used in the calculations described in the text:(a)the transformation used for the k=1system;(b)the transformation used for k>1,illus-trated in this case for k=3.The coloring of the sites indicates how they are grouped under the transformations.
to specificfinite-size scaling behavior in the region close to the transition.Note that the transition is a one-sided one,since p can never take a value less than zero.In this respect the transition is similar to transitions seen in other one-dimensional systems such as1D bond or site percolation,or the1D Ising model.
Barth´e l´e my and Amaral[8]have suggested that the arguments above,although correct in outline,are not correct in detail.They contend that the length-scaleξdiverges as
ξ∼p−τ(1) withτdifferent from the value of1given by the scal-ing argument.On the basis of numerical results,they conjecture thatτ=2
4
.A scaling law similar to this has been proposed previously by Barth´e l´e my and Amaral[8]for the small-world model,although curiously they suggested that scaling of this type was evidence for the absence of a phase transition in the model,whereas we regard it as the appropriate form forℓin the presence of one[10]. We now assume that,in the critical region,ξtakes the form(1),and that we do not know the value of the exponentτ.Then we can rewrite Eq.(3)in the form
ℓ=Lf(pτL),(4) where we have absorbed a multiplicative constant into the argument of f(x),but otherwise it is the same scaling function as before,with the same limits,Eq.(3).
Now consider the real-space RG transformation on the k=1small-world model in which we block sites in adja-cent pairs to create a one-dimensional lattice of a half as many sites.(We assume that the lattice size L is even.In fact the transformation worksfine if we block in groups of any size which divides L.)Two vertices are connected on the renormalized lattice if either of the original vertices in one was connected to either of the original vertices in the other.This includes shortcut connections.The transformation is illustrated in Fig.1a for a lattice of size L=24.
The number of shortcuts on the lattice is conserved under the transformation,so the fundamental par
ameters L and p renormalize according to
L′=1
2
ℓ(6) in this limit.
Eqs.(5)and(6)constitute the RG equations for this system and are exact for n≫1and p≪1.Substituting into Eq.(4)we thenfind that
τ=
log(L/L′)
Now we turn to the case of k>1.To treat this case we define a slightly different RG transformation:we group adjacent sites in groups of k,with connections assigned using the same rule as before.The transformation is illustrated in Fig.1b for a lattice of size L=24with k=3.Again the number of shortcuts in the network is preserved under the transformation,which gives the following renormalization equations for the parameters: L′=L/k,p′=k2p,k′=1,ℓ′=ℓ.(8) Note that,in the limit of large L and small p,t
he mean distanceℓis not affected at all;the number of vertices along the path joining two distant sites is reduced by a factor k,but the number of vertices that can be traversed in one step is reduced by the same factor,and the two cancel out.For the same reasons as before,this transfor-mation is exact in the limit of large L and small p.
We can use this second transformation to turn any network with k>1into a corresponding network with k=1,which we can then treat using the arguments given before.Thus,we conclude,the exponentτ=1for all values of k and,substituting from Eq.(8)into Eq.(4), the general small-world network must satisfy the scaling form
ℓ=L
3
.
way,the results should collapse onto a single curve and,
as thefigure shows,they do indeed do this to a reasonable
approximation.
As mentioned above,Barth´e l´e my and Amaral[8]
also performed numerical simulations of the small-world
lpk
model and extracted a value ofτ=2
0.1
1
10
p 1/2
L
0.0
0.2力月西
0.40.6
l /L
L = 64L = 128L = 256L = 512
FIG.3.Collapse of numerical data for networks based on the square lattice in two dimensions,as described in the text.Error bars are in all cases smaller than the data points.
for small L ,logarithmically for large L ,and the length-scale ξ
of the
transition diverges according to Eq.(1)for small p .Thus the scaling form (4)applies for general d also.The appropriate generalization of our RG transfor-mation involves grouping sites in square or cubic blocks of side 2,and the quantities L ,p and ℓthen renormalize according to
主治医师
L ′=
1
2ℓ.
(10)
Thus
log(L/L ′)
d .
(11)
As an example,we show in Fig.3numerical results for the d =2case,for L equal to a power of two from 64up to ,a little over a quarter of a million vertices for the largest networks simulated)and six different values of p for each system size from p =3×10−6up to 1×10−3.The results are plotted according to Eq.(4)with τ=1
k
f (pk )1/d L .
(13)
Alternatively,we could redefine our scaling function f (x )so that ℓk/L is given as a function of pkL d .Writing it in this form makes it clear that the number of vertices in the network at the transition from large-to small-world behavior diverges as (pk )−1in any number of dimensions.Another possible generalization to k >1is to add con-nections between all sites within square or cubic regions of side 2k .This gives a different dependence on k in the scaling relation,but τstill equal to 1/d .
To conclude,we have studied the small-world network model of Watts and Strogatz using an asymptotically ex-act real-space renormalization group method.We find that in all dimensions d the model undergoes a continu-ous phase transition as the density p of shortcuts tends to zero and that the characteristic length ξdiverges ac-cording to ξ∼p −τwith τ=1/d for all values of the connection range k .We have also deduced the general finite-size scaling law which describes the variation of the mean vertex–vertex separation as a function of p ,k and the system size L .We have performed extensive numer-ical calculations which confirm our analytic results.
2
factors of 2in our equations.[8]M.Barth´e l´e my and L. A.N.Amaral,“Small-world networks:Evidence for a crossover picture”,
cond-mat/9903108.
[9]A.Barrat,“Comment on ‘Small-world networks:Evi-dence for a crossover picture’,”cond-mat/9903323.
gongqijun[10]Ref.[8]is a little confusing in this respect.It appears
the authors may have been referring to the possibility that the system shows a phase transition as the size L of the system is varied.This however would not be a sensible suggestion,since it is well-known that systems of finite size do not show sharp phase transitions.The only sensible scenario is a phase transition with varying shortcut probability p ,which the model does indeed seem to show.
4
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议