Small-world networks are regular structures with a fraction p of regular co
nnections per site replaced by totally random ones ("shortcuts"). This kind
of structure seems to be present on networks arising in nature and technol
ogy. in this work we show that the small-world transition is a first-order
transition at zero density p of shortcuts, whereby the normalized shortest-
path distance L = (l) over bar /L undergoes a discontinuity in the thermody
namic limit. On finite systems the apparent transition is shifted by Deltap
similar to L-=d. Equivalently a "persistence size" L* similar to p(-l/d) c
an be defined in connection with finite-size effects. Assuming L* similar t
o p(-tau), simple rescaling arguments imply that tau = l/d. We confirm this
result by extensive numerical simulation in one to four dimensions, and ar
gue that tau = l/d implies that this transition is first-order. (C) 2001 El
sevier Science B.V. All rights reserved.