VOLUME 84, NUMBER 14 PHYSICAL REVIEW LETTERS 3 APRIL 2000

Mean-Field Solution of the Small-World Network Model

M. E. J. Newman, C. Moore, and D. J. Watts
Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, New Mexico 87501
(Received 21 September 1999)
The small-world network model is a simple model of the structure of social networks, which possesses
characteristics of both regular lattices and random graphs. The model consists of a one-dimensional
lattice with a low density of shortcuts added between randomly selected pairs of points. These shortcuts
greatly reduce the typical path length between any two points on the lattice. We present a mean-field
solution for the average path length and for the distribution of path lengths in the model. This solution
is exact in the limit of large system size and either a large or small number of shortcuts.

PACS numbers: 87.23.Ge, 05.70.Jk, 64.60.Fr, 84.35. + i

Social networks, such as networks of friends, have two the distance between diametrically opposite points on the
characteristics which one might imagine were contradic- underlying lattice, and Dorogovtsev and Mendes [4] gave
tory. First, they show “clustering,” meaning that two of an exact solution for the distribution of path lengths on a
your friends are far more likely also to be friends of one different but related “hub” model in which all the shortcuts
another than two people chosen from the population at ran- are connected together at a central site.
dom. Second, they exhibit what has become known as the In this paper we derive an analytic solution for the
“small-world effect,” namely, that any two people can es- distribution of path lengths in the small-world model by
tablish contact by going through only a short chain of in- making use of a mean-field approximation in which the
termediate acquaintances. Following the work of Milgram distributions of quantities over realizations of the model
[1], it is widely touted that the average number of such are represented by their averages. As we will show, this
intermediates is about six—there are “six degrees of sepa- approximation is exact in the limit of large system size
ration” between two randomly chosen people in the world. [L ¿ 1兾共kf兲].
In fact, this number is probably not a very accurate esti- The approach we use is first to solve the continuum
mate, but the basic principle is sound. version of the Watts-Strogatz model shown in Fig. 1b for
These two properties appear contradictory because the general k. In this version of the model the underlying
first is a typical property of low-dimensional lattices but one-dimensional lattice is treated as a continuum rather
not of random graphs or other high-dimensional lattices, than a discrete lattice and shortcuts are assumed to have
while the second is typical of random graphs, but not of length zero. Once we have a solution for the continuum
low-dimensional lattices. Recently, Watts and Strogatz [2] model, we then note that if the density of shortcuts is
have proposed a simple model of social networks which low, the discrete and continuum models are equivalent,
interpolates between low-dimensional lattices and random and hence our solution is also a solution of the discrete
graphs and displays both the clustering and small-world small-world model for general k.
properties. In this model, L sites are placed on a regu- Consider then a “neighborhood” of radius r cen-
lar one-dimensional lattice with nearest- and next-nearest- tered around a randomly chosen point on a small-world
neighbor connections out to some constant range k and
periodic boundary conditions (the lattice is a ring). A num-
ber of shortcuts are then added between randomly chosen
pairs of sites with probability f per connection on the un- (a) (b) r
derlying lattice (of which there are Lk). Thus there are
on average Lkf shortcuts in the graph. An example of
a small-world graph with L 苷 24, k 苷 3, and four short-
cuts is shown in Fig. 1a. Watts and Strogatz examined
numerically the average distance between pairs of vertices
on small-world graphs and found that only a small density
of shortcuts is needed to produce distances comparable to
those seen in true random graphs.
The small-world model has received a great deal of at- FIG. 1. (a) A small-world graph of 24 sites with k 苷 3 and
tention from the statistical physics community in the last four shortcuts. ( b) The continuum version of the same graph.
year or so, but despite the large number of papers which The bold lines denote the portion of the graph which is within
distance r of the point at the top denoted by the arrow. In
have appeared, very few analytic results are known for the this case there are four filled segments, or “clusters,” around
model. Kulkarni et al. [3] derived an exact relationship be- the perimeter of the graph, or equivalently four gaps between
tween the average shortest path on a small-world graph and clusters.

0031-9007兾00兾84(14)兾3201(4)$15.00 © 2000 The American Physical Society 3201

VOLUME 84, NUMBER 14 PHYSICAL REVIEW LETTERS 3 APRIL 2000

network of L sites, where by neighborhood we mean dn 4kmn 2kn共n 2 1兲

the set of points which can be reached by following 苷 2 , (5)
dr jL m
paths of length r or less on the graph. Let m共r兲 be
the number of sites on the graph which do not belong or
to this neighborhood, averaged over many realizations
of the randomness in the graph, and let n共r兲 be the dn 4kmn 2kn共n 2 1兾L兲
苷 2 . (6)
average number of “gaps” around the lattice among dr j m
which those sites are divided—see Fig. 1b. Equiva-
This equation is only exact when the average values m共r兲
lently, n共r兲 can be viewed as the number of “clusters” of
and n共r兲 accurately represent the actual values of these
occupied sites. In the continuum model both m and n are
quantities in the particular realization of the model we are
real numbers. We will also find it convenient to use the
looking at, i.e., when the distribution of values is sharply
rescaled variables
peaked. This will be the case when the number of shortcuts
m共r兲 n共r兲 on the lattice is either much less than one—L ø j —or
m共r兲 苷 , n共r兲 苷 . (1)
L L much greater than one—L ¿ j —and therefore also in
In the continuum limit the quantities m共r兲 and n共r兲 the limit of large system size. We have confirmed this us-
satisfy differential equations as follows. The rate at which ing numerical simulations, which show the distributions of
m decreases with increasing r is equal to the number 2n m and n becoming more sharply peaked as we go to either
of growing edges of clusters on the lattice times the range small or large values of L兾j. The convergence is slow
k of connections on the lattice. Thus for the large system size case, so the distribution is still
moderately broad for the largest system sizes examined
dm
苷 22kn , (2) here but, as we will see, the mean-field theory nonethe-
dr less gives good agreement with numerical results for
or L兾j * 100.
dm Between them, Eqs. (3) and (6) are the fundamental
苷 22kn . (3) equations which lead to our solution for the small-world
dr
model. These equations can also be derived by writing
This equation is exact for all values of L and f. down difference equations for the variables m and n in the
The rate at which the number of gaps n changes has discrete small-world model and then expanding in powers
two contributions. First, the number of gaps increases of 1兾j and keeping only the leading-order terms [7].
as a result of the shortcuts on the graph. Let us define We solve Eqs. (3) and (6) as follows. First, we take their
a characteristic length j 苷 1兾共kf兲 such that L兾j is the ratio, which eliminates the variable r and gives us a single
average number of shortcuts in the graph and the density
differential equation directly relating m and n thus:
of the ends of shortcuts is 2兾j [5,6]. This means that as r
increases, new shortcuts are encountered at a rate 4kn兾j. dn 2m n 2 1兾L
For each shortcut encountered, a new cluster will be started 苷2 1 . (7)
dm j m
at a random position on the lattice, provided that the other
end of the shortcut in question falls in one of the gaps The general solution of this equation is
around the ring. The probability of this happening is m兾L. 2m2 1
Thus the rate at which clusters (or gaps) are created is n苷2 1 1 Cm , (8)
4kmn兾jL. j L
The number of gaps decreases when the edges of a gap where C is an integration constant. The constant can be
meet one another. This will happen in the interval from r fixed using the boundary conditions m共0兲 苷 1, n共0兲 苷
to r 1 dr if the size of one of the gaps is less than 2k dr. 1兾L, which imply that C 苷 2兾j and hence
If we consider all possible ways of distributing m sites
over n gaps, we can see that the probability distribution of 2 1
n苷 共m 2 m2 兲 1 . (9)
the sizes of the gaps is the same as the distribution of the j L
smallest of n 2 1 uniformly distributed random numbers
Substituting this solution back into Eq. (3), we get
x between 0 and m, which is
∑ ∏ dm 4k 2 2k
n21 x n22 苷 共m 2 m兲 2 . (10)
p共x兲 苷 12 . (4) dr j L
m m
Thus the probability of one particular gap being smaller If we neglect the constant term in this equation, we arrive
than 2k dr is 1 2 共1 2 2k dr兾m兲n21 , which tends to at the normal logistic growth equation [8], which will give
2k共n 2 1兲 dr兾m in the limit of small dr. The probability an accurate solution for m in the regime where the lattice is
that any one of them is smaller than 2k dr is n times this. neither very full nor very empty. If we keep all the terms,
Thus our final equation for the rate of change of n is the general solution given the boundary conditions is

3202
VOLUME 84, NUMBER 14 PHYSICAL REVIEW LETTERS 3 APRIL 2000

j Z m dz j 1 Z ` Z 1
r 苷 2
苷 p ᐉ苷 rA共r兲 dr 苷 r dm , (15)
4k 1 z 2 z 2 j兾2L 2k 1 1 2j兾L L 0 0
" #
21 p 1 21 p 2m 2 1 where we have made use of Eq. (14). Even before per-
3 tanh 2 tanh .
1 1 2j兾L 1 1 2j兾L forming the integral, we can see that this implies a certain
behavior on the part of ᐉ. Equation (11) shows that kr兾j
(11)
is a function only of m and of the ratio of L and j. In
Rearranging for m this gives other words r has the form
" q √ j
1 1 r 苷 h共m, L兾j兲 , (16)
m苷 1 1 1 1 2j兾L tanh tanh21 p k
2 1 1 2j兾L
q !# where h共x, y兲 is a universal scaling function with no depen-
kr dence on the parameters of the model other than through
2 2 1 1 2j兾L .
j its arguments. Substituting this form into Eq. (15) and per-
forming the integral over m, we get
(12)
j
ᐉ 苷 g共L兾j兲 , (17)
This equation gives us m in terms of r, j, and L for k
the continuum version of the small-world model. In the where g共x兲 is another universal scaling function. Except
case where the typical lattice distance between the ends for the leading factor of 1兾k, this scaling form is identical
of shortcuts is much larger than one—j ¿ 1—the con- to the one suggested previously by Barthélémy and Amaral
tinuum version becomes equivalent to the normal discrete [6]. Making the substitution g共x兲 苷 xf共x兲, we can also
version of the model and so in this limit our solution is also write it in the form
a solution of the discrete small-world model. Combining L L
this condition with the conditions specified earlier, we see ᐉ 苷 f共L兾j兲 苷 f共Lkf兲 , (18)
that our solution will be exact when either 1 ø L ø j, k k
or when 1 ø j ø L. This latter regime is precisely the a form which was proposed by Newman and Watts on the
regime in which the small-world model is physically inter- basis of renormalization group arguments, and which has
esting: the regime of large system size and a large num- been confirmed by extensive numerical simulation [10,11].
ber of sparsely distributed shortcuts. In the intermediate The complete solution for ᐉ is obtained by substituting
regime between the two conditions given, the solution is (11) into (15) and performing the integral, which gives
still quite accurate, and gives a good guide to the general j 1
behavior of the model, as we will shortly show. ᐉ苷 p tanh21 p . (19)
2k 1 1 2j兾L 1 1 2j兾L
We now derive some of the more important conse-
quences of Eq. (12). First, we check that it reduces to The scaling function f共x兲 is then given by
the correct expression in the case L ! `. Making use 1 x
of the identity tanh共x1 1 x2 兲 苷 共tanhx1 1 tanhx2 兲兾共1 1 f共x兲 苷 p tanh21 p . (20)
2
2 x 1 2x 2
x 1 2x
tanhx1 tanhx2 兲, we find that to first order in j兾L
j In Fig. 2 we show this form for the scaling function along
m苷11 关1 2 e4kr兾j 兴 , (13) with numerical data from direct measurements of the av-
2L
erage path length on k 苷 1 discrete small-world graphs of
which agrees with the direct derivation for the L 苷 ` case size up to L 苷 107 sites. As the figure shows, the two
in Ref. [5]. are in good agreement for large and small values of the
Next, we note that once we have the fraction m of sites independent variable x but, as expected, there is some dis-
not belonging to a neighborhood of radius r, we can also agreement in the region around x 苷 1 where j and L are
calculate the number A共r兲 dr in an interval from r to r 1 of the same order of magnitude. In the lower inset of the
dr —the “surface area” of the neighborhood—from figure we have replotted the same data on log-log scales,
dm 4Lk to show how the analytic and numerical results converge
A 苷 2L 苷 2k 1 共m 2 m2 兲 苷 2Lkn . for large values of x.
dr j
(14) The asymptotic forms of Eq. (20) are
8
>
< 14 for x ø 1 ,
Thus, once we have either m or n we can easily calcu- f共x兲 ⬃ (21)
late A. >
: 共log2x兲兾4x for x ¿ 1 ,
We can also derive an expression for the average vertex-
vertex separation ᐉ on the graph, a quantity which has been where we have made use of the identity tanh21 x 苷
1
studied by many authors [2–6,9–12]. We write 2 log关共1 1 x兲兾共1 2 x兲兴. These forms are in agreement

3203
VOLUME 84, NUMBER 14 PHYSICAL REVIEW LETTERS 3 APRIL 2000

0.3 figure shows numerical results for ᐉ for a variety of values

2
of the shortcut density f 苷 1兾j from 0.01 up to 1, for
10
systems of one million sites (circles). The dotted line is
Eq. (19). As the figure shows, the analytic solution is a

l
0.2 1
10 reasonable guide to the behavior of ᐉ up to quite large
values of f but, as expected, fails when f gets close to 1.
To conclude, we have given a mean-field-like analytic
l/L

10 100 1000 0.01 0.1

0
10 φ solution for the distribution of path lengths in the con-
0.1 10
−1 tinuum version of the Watts-Strogatz small-world model.
−2
This solution is exact in the limit of large system sizes for
10
a given density of shortcuts, or in the limit of low shortcut
−3
10 density for a given system size. In the case where the short-
cut density is low but the total number of shortcuts on the
0.0
0.001 0.01 0.1 1 10 100 1000 10000 lattice is large (because the lattice itself is also large) our
solution is also an exact solution of the normal discrete
L/ξ
small-world model. We have also derived an expression
FIG. 2. The average path length as a fraction of system size on for the average path length in the model and from this ex-
a k 苷 1 small-world graph, plotted against the average number tracted the scaling forms which this path length obeys. We
L兾j of shortcuts. The circles are numerical measurements for have checked our results against numerical simulation of
the discrete model and the solid line is the analytic solution for
the continuum model, Eq. (20). The error bars on the numerical the discrete small-world model and find good agreement
measurements are smaller than the points. Lower inset: the in the regions where our solution is expected to be exact.
same data replotted on log-log scales, showing the convergence In other regions the solution is a good guide to the general
of the numerical and analytic results in the limit of large L兾j. behavior of the model but shows some deviation from the
Upper inset: the average path length on small-world graphs with numerical results.
L 苷 106 , for values of f from 0.01 up to 1 (circles) and the
analytic solution, Eq. (19) (dotted line).

with previous conjectures [6,10], which suggested that [1] S. Milgram, Psychol. Today 2, 60 (1967).
1 [2] D. J. Watts and S. H. Strogatz, Nature (London) 393, 440
f共x兲 should have the value 4 for small x and should go
as 共logx兲兾x for large x. As we see, the leading numerical (1998).
1 [3] R. V. Kulkarni, E. Almaas, and D. Stroud, Phys. Rev. E (to
factor in the latter case is also 4 ; this figure is exact, since be published).
Eq. (20) is exact for large x. [4] S. N. Dorogovtsev and J. F. F. Mendes, cond-mat /9907445.
In passing, we note that there is a simple physical in- [5] M. E. J. Newman and D. J. Watts, Phys. Rev. E 60, 7332
terpretation of the scaling function f共x兲: apart from the (1999).
1
leading factor of 4 , it is the fraction by which the aver- [6] M. Barthélémy and L. A. N. Amaral, Phys. Rev. Lett. 82,
age path length on a small-world graph is reduced if the 3180 (1999).
graph has x shortcuts. For example, Eq. (20) indicates [7] M. E. J. Newman, C. Moore, and D. J. Watts, cond-mat /
that it takes x 苷 3.5 shortcuts on average to reduce the 9909165.
[8] S. H. Strogatz, Nonlinear Dynamics and Chaos (Addison-
mean path length by a half, and 44 shortcuts to reduce it
Wesley, Reading, MA, 1994).
by a factor of 10. Thus only a small number of shortcuts [9] C. F. Moukarzel, Phys. Rev. E 60, 6263 (1999).
are needed to reduce path lengths quite considerably. The [10] M. E. J. Newman and D. J. Watts, Phys. Lett. A 263, 341
same conclusion has been reached by Watts and Strogatz (1999).
[2] on the basis of numerical data. [11] M. Argollo de Menezes, C. F. Moukarzel, and T. J. P. Penna,
In the upper inset of Fig. 2 we show how our solution cond-mat /9903426.
fails when the shortcut density becomes too high. The [12] A. Barrat and M. Weigt, Euro. Phys. J. B 13, 547 (2000).

3204