Geometric phase-transition on systems with sparse long-range connections

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.