letters to nature 如B二eol lective dynamics of adapted our code for massively parallel architectures (K M. Olson small-worldnetworks and E A, manuscript in preparation), we are now ready to perform a more co ve analvsis Duncan J. Watts *& Steven H. Strogatz The exploratory simulations presented here suggest that when a Department of Theoretical and Applied Mechanics, Kimball Hall, young, non-porous asteroid (if such exist) suffers extensive impact Cornell University, Ithaca, New York 14853, USA damage, the resulting fracture pattern largely defines the asteroid response to future impacts. The stochastic nature of collisions Networks of coupled dynamical systems have been used to model plies that small asteroid interiors may be as diverse as their biological oscillators, Josephson junction arrays excitable shapes and spin states. Detailed numerical simulations of impacts, media, neural networks-o, spatial games", genetic control ing accurate shape models and rheologies, could shed light on networks and many other self-organizing systems. Ordinarily ow asteroid collisional response depends on internal configuration the connection topology is assumed to be either completely nd shape, and hence on how planetesimals evolve. Detailed regular or completely random. But many biological, technological simulations are also required before one can predict the quantitative and social networks lie somewhere between these two extremes. ffects of nuclear explosions on Earth-crossing comets and Here we explore simple models of networks that can be tuned asteroids, either for hazard mitigation through disruption and through this middle ground: regular networks rewired'to intro- deflection, or for resource exploitation. Such predictions would duce increasing amounts of disorder. We find that these systems equire detailed reconnaissance concerning the composition and can be highly clustered, like regular lattices, yet have small nternal structure of the targeted object D characteristic path lengths, like random graphs. We call them Received 4 February, accepted 18 March 1998. small-world networks, by analogy with the small-world phenomenon(popularly known as six degrees of separation) Asphaug. E& Melosh, H J. The Stickney impact of Phobos: A dynamical The neural network of the worm Caenorhabditis elegans, the 120, 158-184 power grid of the western United States, and the collaboration graph of film actors are shown to be small-world networks. 3. Nolan M, C sphia ge Melos h, 4. 8- ize m berg R. impact craters on asteroids. Does strength or Models of dynamical systems with small-world coupling display 4.Love,SL&Ahrens,TL Catastrophic impacts on gravity dominated asteroids. Icarus 124, 141-155 enhanced signal-propagation speed, computational power, and ynchronizability. In particular, infectie more aoa dimensional analyis. L Geophys i 24 arcsec lig laws Fu merflfrmsbased easily in small-world networks than in regular lattices. To interpolate between regular and random networks, we con- 7. Holsapple, KA&Schmidt, R. M. Point source solutions and coupling parameters in cratering sider the following random rewiring rocedure(Fig. 1). Starting 8. Housen, KR&Holsapple, K.A. On the fragmentation of asteroids and planetary satellites. Icars 84. from a ring lattice with n vertices and k edges per vertex, we rewire ations of brittle solids using smooth partide hydrodynamics. Comput. each edge at random with probability p. This construction allows us to tune the graph between regularity(p= 0)and disorder(p= 1), Asphaug, E et al. Mechanical and geological effects of impact cratering on Ida. Icarus 120, 158-184 and thereby to probe the intermediate region 0<P<l, about Hudson,RS&Ostro,S].Shape of asteroid 4769 Castalia(1989 PB)from inversion of radar images. which little is known Ostro, S.I et aL Asteroid radar astrometry. Astron. /. 102, 1490-1502(199 m New work. 97 m Cratering (eds Rody, D.L. Pepin, &. 0. defined in Fig. 2 legend. Here L(p) measures the typical separation Tillotson, L H Metallic equations of state for hypervelocity impact( GeneralAtomic Report GA-3216, between two vertices in the graph(a global property), whereas C(p) San Diego, 1962 15.Nakamura,A&Fujiwara, A. Velocty distribution of fragments formed in a simulated collisional measures the cliquishness of a typical neighbourhood(a local property). The networks of interest to us have many vertices Pem Comman 82.,253-25 (195). t britle solids using smooth partide hydrodynamic Comput. with sparse connections, but not so sparse that the graph is in Betron, M,. S 1 a aie 8n ogwnterwith SI Gaspra-First picture of an asteroid Siene 257, m>k>In(m) >1, where k> In(m) guarantees that a random s's encounter with 243 ldr An overview of the imaging experiment. lars L-n/2k> 1 and C-3/4 as p-0, while L lrandom-In(n/n(k) lost, H. The Stickney impact of Phobos: A dynamical model. (arns 101, 144-164 and C= Random/n I asp-1. Thus the regular lattice atp =0 21 Asphaug, E et al. Mechanical and geological effects of impact cratering on Ida. Icarus 120, 158-184 whereas the random network at p= l is a poorly clustered, small Housen, K, R,Schmid, R.M. Holsapple, K A Crater ejecta scaling laws: Fundamental forms based world where L grows only logarithmically with n. These limiting cases might lead one to suspect that large Cis always associated with 24. Asphaug E. et al Impact evolution of icy regoliths. Lunar Planet. Sci Canf. (Abstr. )xxVIlL, 2112(1997. large L, and small C with small L 25. Love, S.G, Hir, E.& Brownlee, D. E Target porosity effects in impact cratering and collisional 0 On the contrary, Fig. 2 reveals that there is a broad interval of p 26. Fuiwpra. l, Cer on. 2. Davis, D. R, yan, E V& DiMartino. M in Asteroids t feds Binal R. P. These small-world networks result from the immediate drop in L(p) 27. Davis, D.R.& Farinella, P Collisional evolution of Edgeworth-Kuiper Belt objects. Icarus 125, 50-60 cuts' connect vertices that would otherwise be much farther apart *arens, T 1.& Harris, A wDeflection and fragmentation of near-Earth asteroids. Nature 360, 429- than Random. For small p, each short cut has a highly nonlinear effect on L, contracting the distance not just between the pair of vertice 29. Resources of Near-Earth Space (eds Lewis, L S, Matthews, M.s. Guerrieri, M L-)(Univ. Arizona that it connects, but between their immediate neighbourhoods, ess, Tucson, 1993) neighbourhoods of neighbourhoods and so on. By contrast, an edge materials should be addressed to EA(e-mail: asphaugeearthsci ucsc. Present address: Paul I Sciences, Columbia University, 812 SIPA St, New York, New York 10027, US 44o Nature Macmillan publishers Ltd 1998 NATURE VOL 393 4JUNE 1998Nature © Macmillan Publishers Ltd 1998 8 typically slower than ,1 km s−1 ) might differ significantly from what is assumed by current modelling efforts27. The expected equation-of-state differences among small bodies (ice versus rock, for instance) presents another dimension of study; having recently adapted our code for massively parallel architectures (K. M. Olson and E.A, manuscript in preparation), we are now ready to perform a more comprehensive analysis. The exploratory simulations presented here suggest that when a young, non-porous asteroid (if such exist) suffers extensive impact damage, the resulting fracture pattern largely defines the asteroid’s response to future impacts. The stochastic nature of collisions implies that small asteroid interiors may be as diverse as their shapes and spin states. Detailed numerical simulations of impacts, using accurate shape models and rheologies, could shed light on how asteroid collisional response depends on internal configuration and shape, and hence on how planetesimals evolve. Detailed simulations are also required before one can predict the quantitative effects of nuclear explosions on Earth-crossing comets and asteroids, either for hazard mitigation28 through disruption and deflection, or for resource exploitation29. Such predictions would require detailed reconnaissance concerning the composition and internal structure of the targeted object. M Received 4 February; accepted 18 March 1998. 1. Asphaug, E. & Melosh, H. J. The Stickney impact of Phobos: A dynamical model. Icarus 101, 144–164 (1993). 2. Asphaug, E. et al. Mechanical and geological effects of impact cratering on Ida. Icarus 120, 158–184 (1996). 3. Nolan, M. C., Asphaug, E., Melosh, H. J. & Greenberg, R. Impact craters on asteroids: Does strength or gravity control their size? Icarus 124, 359–371 (1996). 4. Love, S. J. & Ahrens, T. J. Catastrophic impacts on gravity dominated asteroids. Icarus 124, 141–155 (1996). 5. Melosh, H. J. & Ryan, E. V. Asteroids: Shattered but not dispersed. Icarus 129, 562–564 (1997). 6. Housen, K. R., Schmidt, R. M. & Holsapple, K. A. Crater ejecta scaling laws: Fundamental forms based on dimensional analysis. J. Geophys. Res. 88, 2485–2499 (1983). 7. Holsapple, K. A. & Schmidt, R. M. Point source solutions and coupling parameters in cratering mechanics. J. Geophys. Res. 92, 6350–6376 (1987). 8. Housen, K. R. & Holsapple, K. A. On the fragmentation of asteroids and planetary satellites. Icarus 84, 226–253 (1990). 9. Benz, W. & Asphaug, E. Simulations of brittle solids using smooth particle hydrodynamics. Comput. Phys. Commun. 87, 253–265 (1995). 10. Asphaug, E. et al. Mechanical and geological effects of impact cratering on Ida. Icarus 120, 158–184 (1996). 11. Hudson, R. S. & Ostro, S. J. Shape of asteroid 4769 Castalia (1989 PB) from inversion of radar images. Science 263, 940–943 (1994). 12. Ostro, S. J. et al. Asteroid radar astrometry. Astron. J. 102, 1490–1502 (1991). 13. Ahrens, T. J. & O’Keefe, J. D. in Impact and Explosion Cratering (eds Roddy, D. J., Pepin, R. O. & Merrill, R. B.) 639–656 (Pergamon, New York, 1977). 14. Tillotson, J. H. Metallic equations of state for hypervelocity impact. (General Atomic Report GA-3216, San Diego, 1962). 15. Nakamura, A. & Fujiwara, A. Velocity distribution of fragments formed in a simulated collisional disruption. Icarus 92, 132–146 (1991). 16. Benz, W. & Asphaug, E. Simulations of brittle solids using smooth particle hydrodynamics. Comput. Phys. Commun. 87, 253–265 (1995). 17. Bottke, W. F., Nolan, M. C., Greenberg, R. & Kolvoord, R. A. Velocity distributions among colliding asteroids. Icarus 107, 255–268 (1994). 18. Belton, M. J. S. et al. Galileo encounter with 951 Gaspra—First pictures of an asteroid. Science 257, 1647–1652 (1992). 19. Belton, M. J. S. et al. Galileo’s encounter with 243 Ida: An overview of the imaging experiment. Icarus 120, 1–19 (1996). 20. Asphaug, E. & Melosh, H. J. The Stickney impact of Phobos: A dynamical model. Icarus 101, 144–164 (1993). 21. Asphaug, E. et al. Mechanical and geological effects of impact cratering on Ida. Icarus 120, 158–184 (1996). 22. Housen, K. R., Schmidt, R. M. & Holsapple, K. A. Crater ejecta scaling laws: Fundamental forms based on dimensional analysis. J. Geophys. Res. 88, 2485–2499 (1983). 23. Veverka, J. et al. NEAR’s flyby of 253 Mathilde: Images of a C asteroid. Science 278, 2109–2112 (1997). 24. Asphaug, E. et al. Impact evolution of icy regoliths. Lunar Planet. Sci. Conf. (Abstr.) XXVIII, 63–64 (1997). 25. Love, S. G., Ho¨rz, F. & Brownlee, D. E. Target porosity effects in impact cratering and collisional disruption. Icarus 105, 216–224 (1993). 26. Fujiwara, A., Cerroni, P., Davis, D. R., Ryan, E. V. & DiMartino, M. in Asteroids II (eds Binzel, R. P., Gehrels, T. & Matthews, A. S.) 240–265 (Univ. Arizona Press, Tucson, 1989). 27. Davis, D. R. & Farinella, P. Collisional evolution of Edgeworth-Kuiper Belt objects. Icarus 125, 50–60 (1997). 28. Ahrens, T. J. & Harris, A. W. Deflection and fragmentation of near-Earth asteroids. Nature 360, 429– 433 (1992). 29. Resources of Near-Earth Space (eds Lewis, J. S., Matthews, M. S. & Guerrieri, M. L.) (Univ. Arizona Press, Tucson, 1993). Acknowledgements. This work was supported by NASA’s Planetary Geology and Geophysics Program. Correspondence and requests for materials should be addressed to E.A. (e-mail: asphaug@earthsci.ucsc. edu). letters to nature 440 NATURE | VOL 393 | 4 JUNE 1998 Collective dynamics of ‘small-world’ networks Duncan J. Watts* & Steven H. Strogatz Department of Theoretical and Applied Mechanics, Kimball Hall, Cornell University, Ithaca, New York 14853, USA ......................................................................................................................... Networks of coupled dynamical systems have been used to model biological oscillators1–4, Josephson junction arrays5,6, excitable media7 , neural networks8–10, spatial games11, genetic control networks12 and many other self-organizing systems. Ordinarily, the connection topology is assumed to be either completely regular or completely random. But many biological, technological and social networks lie somewhere between these two extremes. Here we explore simple models of networks that can be tuned through this middle ground: regular networks ‘rewired’ to intro￾duce increasing amounts of disorder. We find that these systems can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs. We call them ‘small-world’ networks, by analogy with the small-world phenomenon13,14 (popularly known as six degrees of separation15). The neural network of the worm Caenorhabditis elegans, the power grid of the western United States, and the collaboration graph of film actors are shown to be small-world networks. Models of dynamical systems with small-world coupling display enhanced signal-propagation speed, computational power, and synchronizability. In particular, infectious diseases spread more easily in small-world networks than in regular lattices. To interpolate between regular and random networks, we con￾sider the following random rewiring procedure (Fig. 1). Starting from a ring lattice with n vertices and k edges per vertex, we rewire each edge at random with probability p. This construction allows us to ‘tune’ the graph between regularity (p ¼ 0) and disorder (p ¼ 1), and thereby to probe the intermediate region 0 , p , 1, about which little is known. We quantify the structural properties of these graphs by their characteristic path length L(p) and clustering coefficient C(p), as defined in Fig. 2 legend. Here L(p) measures the typical separation between two vertices in the graph (a global property), whereas C(p) measures the cliquishness of a typical neighbourhood (a local property). The networks of interest to us have many vertices with sparse connections, but not so sparse that the graph is in danger of becoming disconnected. Specifically, we require n q k q lnðnÞ q 1, where k q lnðnÞ guarantees that a random graph will be connected16. In this regime, we find that L,n=2k q 1 and C,3=4 as p → 0, while L < Lrandom,lnðnÞ=lnðkÞ and C < Crandom,k=n p 1 as p → 1. Thus the regular lattice at p ¼ 0 is a highly clustered, large world where L grows linearly with n, whereas the random network at p ¼ 1 is a poorly clustered, small world where L grows only logarithmically with n. These limiting cases might lead one to suspect that large C is always associated with large L, and small C with small L. On the contrary, Fig. 2 reveals that there is a broad interval of p over which L(p) is almost as small as Lrandom yet CðpÞ q Crandom. These small-world networks result from the immediate drop in L(p) caused by the introduction of a few long-range edges. Such ‘short cuts’ connect vertices that would otherwise be much farther apart than Lrandom. For small p, each short cut has a highly nonlinear effect on L, contracting the distance not just between the pair of vertices that it connects, but between their immediate neighbourhoods, neighbourhoods of neighbourhoods and so on. By contrast, an edge * Present address: Paul F. Lazarsfeld Center for the Social Sciences, Columbia University, 812 SIPA Building, 420 W118 St, New York, New York 10027, USA