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 0k>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 1998
Nature © 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 introduce 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 consider 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
letters to nature removed from a clustered neighbourhood to make a short cut has, at model-it is probably generic for many large, sparse networks most, a linear effect on C, hence C(p)remains practically unchanged found in nature. for small p even though L(p)drops rapidly. The important implica- We now investigate the functional significance of small-world tion here is that at the local level (as reflected by C(p)), the transition connectivity for dynamical systems. Our test case is a deliberately to a small world is almost undetectable. To check the robustness of simplified model for the spread of an infectious disease. The these results, we have tested many different types of initial regular population structure is modelled by the family of graphs described graphs, as well as different algorithms for random rewiring, and all in Fig. 1. At time t= 0, a single infective individual is introduced give qualitatively similar results. The only requirement is that the into an otherwise healthy ly population. Infective individuals are rewired edges must typically connect vertices that would otherwise removed permanently(by immunity or death) after a period of The idealized construction above reveals the key role of short each infective individual can infect each of its healthy neighs ime, be much farther apart than Random. cuts. It suggests that the small-world phenomenon might be with probability r On subsequent time steps, the disease spreads common in sparse networks with many vertices, as even a tiny along the edges of the graph until it either infects the entire fraction of short cuts would suffice. To test this idea, we have population, or it dies out, having infected some fraction of the computed L and C for the collaboration graph of actors in feature population in the process films(generatedfromdataavailableathttp://us.imdbcom),the cientific interest. The graph of film actors is a surrogate for a social Table 1 Empirical examples of small-world networks network, with the advantage of being much more easily specified. 3.65 traditionallyonP.Erdospartialdataavailableathttp:// www.acs.oakland.edu/-grossman/erdoshp.htmi).ThegraphofElegans 65 power networks". And C. elegans is the sole example of a completely vertex().Actors: n=225 226, k=61. Power grid: n =4.941,k=2.67..elegans: n=282 pped neural network. Theseexampleswerenothand-picked;theywerechosenbecauseofhttp://usimdb.com),asofApril1997.ForthepowergridvemIvieDataba Table 1 shows that all three graphs are small-world works. grap their inherent interest and because complete wiring diagrams were between them. For Celegans,ane available. Thus the small-world phenomenon is not merely a scag ss f a tica recoin ng hret t ase are s as ndprectem ation s aw grete n e ana ks uriosity of social networks. nor an artefact of an idealized show the small-world phenomenon:L>Lanton butC>Crandem Regular C(p)/c(0)口 00001 001 Figure 1 Random rewiring procedure for interpolating between a regular ring Figure 2 Characteristic path length L(p) and clustering coefficient Clp) for the the graph. We start with a ring of n vertices, each connected to its k nearest number of edges in the shortest path between two vertices, averaged over all ighbours by undirected edges. For clarity, n= 20 and k= 4 in the schematic pairs of vertices. The clustering coefficient Clp)is defined as follows. Suppose ples shown here but much larger n and k are used in the rest of this Letter. that a vertex v has ky neighbours: then at most k,(, -1y2 edges can exist Ve choose a vertex and the edge that connects it to its nearest neighbour in a between them this occurs when every neighbour of v is connected to every other clockwise sense With probability p, we reconnect this edge to a vertex chosen neighbour of v) Let C denote the fraction of these allowable edges that actually uniformly at random over the entire ring, with duplicate edges forbidden; other- exist. Define C as the average of Cy over all v For friendship networks, these vise we leave the edge in place. We repeat this process by moving clockwise statistics have intuitive meanings: L is the average number of friendships in the ound the ring, considering each vertex in tum until one lap is completed. Next, shortest chain connecting two people; Cy reflects the extent to which friends of consider the edges that connect vertices to their second-nearest neighbours are also friends of each other; and thus c measures the cliquishness of a typical clockwise. As before we randomly rewire each of these edges with probability p, friendship circle. The data shown in the figure are averages over 20 random the rewiring process described in Fig. 1, and have been normalize been considered once (As there are nk/2 edges in the entire graph, the rewiring and an average degree of k= 10 edges per vertex. We note that a logarithmic process stops after k/2 laps. )Three realizations of this process are shown, for horizontal scale has been used to resolve the rapid drop in l(p), corresponding to ifferent values ofp. Forp =0, the original ring is unchanged; asp increases, the the onset of the small-world phenomenon. During this drop, clp)remains almos raph becomes increasingly disordered until for p= all edges are rewired constant at its value for the regular lattice, indicating that the transition to a small randomly. One of our main results is that for intermediate values of p, the graph is world is almost undetectable at the local level small-world network: highly clustered like a regular graph, yet with small characteristic path length, like a random graph. (See Fig. 2-) NATURE VOL 393 4 JUNE 1998 Nature Macmillan publishers Ltd 1998
Nature © Macmillan Publishers Ltd 1998 8 letters to nature NATURE | VOL 393 | 4 JUNE 1998 441 removed from a clustered neighbourhood to make a short cut has, at most, a linear effect on C; henceC(p)remains practically unchanged for small p even though L(p) drops rapidly. The important implication here is that at the local level(as reflected by C(p)), the transition to a small world is almost undetectable. To check the robustness of these results, we have tested many different types of initial regular graphs, as well as different algorithms for random rewiring, and all give qualitatively similar results. The only requirement is that the rewired edges must typically connect vertices that would otherwise be much farther apart than Lrandom. The idealized construction above reveals the key role of short cuts. It suggests that the small-world phenomenon might be common in sparse networks with many vertices, as even a tiny fraction of short cuts would suffice. To test this idea, we have computed L and C for the collaboration graph of actors in feature films (generated from data available at http://us.imdb.com), the electrical power grid of the western United States, and the neural network of the nematode worm C. elegans17. All three graphs are of scientific interest. The graph of film actors is a surrogate for a social network18, with the advantage of being much more easily specified. It is also akin to the graph of mathematical collaborations centred, traditionally, on P. Erdo¨s (partial data available at http:// www.acs.oakland.edu/,grossman/erdoshp.html). The graph of the power grid is relevant to the efficiency and robustness of power networks19. And C.elegans is the sole example of a completely mapped neural network. Table 1 shows that all three graphs are small-world networks. These examples were not hand-picked; they were chosen because of their inherent interest and because complete wiring diagrams were available. Thus the small-world phenomenon is not merely a curiosity of social networks13,14 nor an artefact of an idealized model—it is probably generic for many large, sparse networks found in nature. We now investigate the functional significance of small-world connectivity for dynamical systems. Our test case is a deliberately simplified model for the spread of an infectious disease. The population structure is modelled by the family of graphs described in Fig. 1. At time t ¼ 0, a single infective individual is introduced into an otherwise healthy population. Infective individuals are removed permanently (by immunity or death) after a period of sickness that lasts one unit of dimensionless time. During this time, each infective individual can infect each of its healthy neighbours with probability r. On subsequent time steps, the disease spreads along the edges of the graph until it either infects the entire population, or it dies out, having infected some fraction of the population in the process. p = 0 p = 1 Increasing randomness Regular Small-world Random Figure 1 Random rewiring procedure for interpolating between a regular ring lattice and a random network, without altering the number of vertices or edges in the graph. We start with a ring of n vertices, each connected to its k nearest neighbours by undirected edges. (For clarity, n ¼ 20 and k ¼ 4 in the schematic examples shown here, but much larger n and k are used in the rest of this Letter.) We choose a vertex and the edge that connects it to its nearest neighbour in a clockwise sense. With probability p, we reconnect this edge to a vertex chosen uniformly at random over the entire ring, with duplicate edges forbidden; otherwise we leave the edge in place. We repeat this process by moving clockwise around the ring, considering each vertex in turn until one lap is completed. Next, we consider the edges that connect vertices to their second-nearest neighbours clockwise. As before, we randomly rewire each of these edges with probability p, and continue this process, circulating around the ring and proceeding outward to more distant neighbours after each lap, until each edge in the original lattice has been considered once. (As there are nk/2 edges in the entire graph, the rewiring process stops after k/2 laps.) Three realizations of this process are shown, for different values of p. For p ¼ 0, the original ring is unchanged; as p increases, the graph becomes increasingly disordered until for p ¼ 1, all edges are rewired randomly. One of our main results is that for intermediate values of p, the graph is a small-world network: highly clustered like a regular graph, yet with small characteristic path length, like a random graph. (See Fig. 2.) Table 1 Empirical examples of small-world networks Lactual Lrandom Cactual Crandom ............................................................................................................................................................................. Film actors 3.65 2.99 0.79 0.00027 Power grid 18.7 12.4 0.080 0.005 C. elegans 2.65 2.25 0.28 0.05 ............................................................................................................................................................................. Characteristic path length L and clustering coefficient C for three real networks, compared to random graphs with the same number of vertices (n) and average number of edges per vertex (k). (Actors: n ¼ 225;226, k ¼ 61. Power grid: n ¼ 4;941, k ¼ 2:67. C. elegans: n ¼ 282, k ¼ 14.) The graphs are defined as follows. Two actors are joined by an edge if they have acted in a film together. We restrict attention to the giant connected component16 of this graph, which includes ,90% of all actors listed in the Internet Movie Database (available at http://us.imdb.com), as of April 1997. For the power grid, vertices represent generators, transformers and substations, and edges represent high-voltage transmission lines between them. For C. elegans, an edge joins two neurons if they are connected by either a synapse or a gap junction. We treat all edges as undirected and unweighted, and all vertices as identical, recognizing that these are crude approximations. All three networks show the small-world phenomenon: L ) Lrandom but C q Crandom. 0 0.2 0.4 0.6 0.8 1 0.0001 0.001 0.01 0.1 1 p L(p) / L(0) C(p) / C(0) Figure 2 Characteristic path length L(p) and clustering coefficient C(p) for the family of randomly rewired graphs described in Fig. 1. Here L is defined as the number of edges in the shortest path between two vertices, averaged over all pairs of vertices. The clustering coefficient C(p) is defined as follows. Suppose that a vertex v has kv neighbours; then at most kvðkv 2 1Þ=2 edges can exist between them (this occurs when every neighbour of v is connected to every other neighbour of v). Let Cv denote the fraction of these allowable edges that actually exist. Define C as the average of Cv over all v. For friendship networks, these statistics have intuitive meanings: L is the average number of friendships in the shortest chain connecting two people; Cv reflects the extent to which friends of v are also friends of each other; and thus C measures the cliquishness of a typical friendship circle. The data shown in the figure are averages over 20 random realizations of the rewiring process described in Fig.1, and have been normalized by the values L(0), C(0) for a regular lattice. All the graphs have n ¼ 1;000 vertices and an average degree of k ¼ 10 edges per vertex. We note that a logarithmic horizontal scale has been used to resolve the rapid drop in L(p), corresponding to the onset of the small-world phenomenon. During this drop, C(p) remains almost constant at its value for the regular lattice, indicating that the transition to a small world is almost undetectable at the local level
letters to nature c Two results emerge. First, the critical infectiousness half, at which changes in the number of concurrent partners are obvious to an disease infects half the population, decreases rapidly for small p individual, whereas transitions leading to a smaller world are not (Fig 3a). Second, for a disease that is sufficiently infectious to infect We have also examined the effect of small-world connectivity on the entire population regardless of its structure, the time T(p) three other dynamical systems. In each case, the elements were required for global infection resembles the L(p)curve(Fig. 3b) coupled acco rding to the family of graphs described in Fig. 1. (1)For Thus, infectious diseases are predicted to spread much more easily cellular automata charged with the computational task of density and quickly in a small world; the alarming and less obvious point is classification, we find that a simple majority-rule running on a how few short cuts are needed to make the world small small-world graph can outperform all known human and genetic Our model differs in some significant ways from other network algorithm-generated rules running on a ring lattice.(2)For the models of disease spreading20-. All the models indicate that net- iterated, multi-player 'Prisoner's dilemma played on a graph, we work structure influences the speed and extent of disease transmis- find that as the fraction of short cuts increases, cooperation is less but our model illuminates the dynamics as an explicit function likely to emerge in a population of players using a generalized'tit of structure(Fig 3), rather than for a few particular topologies, such for-tat"strategy. The likelihood of cooperative strategies evolving random graphs, stars and chains -. In the work closest to ours, out of an initial cooperative/non-cooperative mix also decreases Kretschmar and Morris have shown that increases in the number with increasing P.(3)Small-world networks of coupled phase of concurrent partnerships can significantly accelerate the propaga- oscillators synchronize almost as readily as in the mean-field tion of a sexually-transmitted disease that spreads along the edges of model, despite having orders of magnitude fewer edges. This a graph. All their graphs are disconnected because they fix the result may be relevant to the observed synchronization of widely average number of partners per person at k= 1. An increase in the separated neurons in the visual cortex"if, as seems plausible, the number of concurrent partnerships causes faster spreading by brain has a small-world architectu creasing the number of vertices in the graph's largest connected We hope that our work will stimulate further studies of small- component. In contrast, all our graphs are connected; hence the world networks. Their distinctive combination of high clustering predicted changes in the spreading dynamics are due to more with short characteristic path length cannot be captured by structural features than changes in connectedness. Mor traditional app s such as those based on regular lattices or random graphs. Although small-world architecture has not received much attention, we suggest that it will probably turn out to be widespread in biological, social and man-made systems, often with important dynami Waves, and Turbulence(Springer, Berlin, 1984). 3. Strogatz, S.H. Stewart, I Coupled oscillators and biological synchronization Sa. Am. 269(6),102- 4 Coombes,S.&Dsmn图Dm of a ring of pulse-coupled oscillators a group theoretic approach. Phys. Rev. Lett. 79, 2791-2794(1997). 5. Braiman, Y, Lindner, L. E. Ditto, w. L Taming spatiotemporal chaos with disorder. Nature 378, 6. wiesenfeld, K New results on frequency-locking dymamics of disordered Josephson arrays. Phy iat B 02 7. Gerhardt, M, Schuster, H.& Tyson, J. L. A cellular automaton model of excitable media induding 0.0001 with coupled integrate-and-fire neurons. Proc. Natl Acad. Sci. USA 92. 6655-6662(1 Pulse-cou I1. Nowak, M.A.& May. R. M. Evolutionary games and spatial chaos. Nature 359, 826-829( 1992). 12. Kauffman, S A Metabolic stability and epigenesis in randomly constructed genetic nets. J. Theor. BioL. 口Tp)/T(0) 13. Magram, S. The small world problem. Psychol. Today 2, 60-67( 1967) 14.Ko 0.8 ·L()∥L(0) Guare. L Six Degrees of Separation: A Play (Vintage Books, New York, 1990). 17. Achacoso, T B& Yamamoto, w.S.AY's Neuroamatormryof C elegans for Computation(CRC Press,Boca 18. Wasserman,S& Faust, K Social Network Amalysis Methods and Applications(Cambridge Univ Press, 19 Phadke, A G.& ThorP, J.S. Commputer Relaying for Power Systems(Wiley. New York, 1988). 0.2 2kRM如mx图1mp 00001 23. Blythe, S. P, Castillo-Chavez, C& Palmer, J S. Toward a unified theory of sexual mixing and pair formation. Math. Biosci. 107, 379-405(1991) 24. Kretschmar, M. Morris, M. Measures of concurrency in networks and the spread of infectious 25. Das, R, Mitchell, M. Crutchfield, I. P. in Parallel Problenm Solving from Nature (eds Davido, Y, Figure 3 Simulation results for a simple model of disease spreading. The chwefel, H-P.& Manner, R )344-353 ( Lecture Notes in Computer Science 866, Springer, Berlin, community structure is given by one realization of the family of randomly rewired 26. Axelrod, R. The Evolation of Cooperation(Basic Books, New York, 1984) graphs used in Fig. 1. a, Critical infectiousness halt, at which the disease infec 27. Gray, C M, Konig. P, Engel, A K.& Singer, w Oscillatory half the population, decreases with p b, The time Tp)required for a maximally columnar synchronization which refle stimulus properties. Nature 338, 334-337(1989). infectious disease (= 1)to spread throughout the entire population has essen- actor data, and Thorp and K Bae for the ially the same functional form as the characteristic path length L(p) Even if only a by the US National Science Foundation few per cent of the edges in the original lattice are randomly rewired, the time to Division of Mathematical Sciences global infection is nearly as short Correspondence and requests for materials should be addressed to D ] w(e-mail: d@columbia. edu) Nature Macmillan publishers Ltd 1998 NATURE VOL 393 4JUNE 1998
Nature © Macmillan Publishers Ltd 1998 8 letters to nature 442 NATURE | VOL 393 | 4 JUNE 1998 Two results emerge. First, the critical infectiousness rhalf, at which the disease infects half the population, decreases rapidly for small p (Fig. 3a). Second, for a disease that is sufficiently infectious to infect the entire population regardless of its structure, the time T(p) required for global infection resembles the L(p) curve (Fig. 3b). Thus, infectious diseases are predicted to spread much more easily and quickly in a small world; the alarming and less obvious point is how few short cuts are needed to make the world small. Our model differs in some significant ways from other network models of disease spreading20–24. All the models indicate that network structure influences the speed and extent of disease transmission, but our model illuminates the dynamics as an explicit function of structure (Fig. 3),ratherthan for a few particular topologies, such as random graphs, stars and chains20–23. In the work closest to ours, Kretschmar and Morris24 have shown that increases in the number of concurrent partnerships can significantly accelerate the propagation of a sexually-transmitted disease that spreads along the edges of a graph. All their graphs are disconnected because they fix the average number of partners per person at k ¼ 1. An increase in the number of concurrent partnerships causes faster spreading by increasing the number of vertices in the graph’s largest connected component. In contrast, all our graphs are connected; hence the predicted changes in the spreading dynamics are due to more subtle structural features than changes in connectedness. Moreover, changes in the number of concurrent partners are obvious to an individual, whereas transitions leading to a smaller world are not. We have also examined the effect of small-world connectivity on three other dynamical systems. In each case, the elements were coupled according to the family of graphs described in Fig. 1.(1) For cellular automata charged with the computational task of density classification25, we find that a simple ‘majority-rule’ running on a small-world graph can outperform all known human and genetic algorithm-generated rules running on a ring lattice. (2) For the iterated, multi-player ‘Prisoner’s dilemma’ 11 played on a graph, we find that as the fraction of short cuts increases, cooperation is less likely to emerge in a population of players using a generalized ‘titfor-tat’26 strategy. The likelihood of cooperative strategies evolving out of an initial cooperative/non-cooperative mix also decreases with increasing p. (3) Small-world networks of coupled phase oscillators synchronize almost as readily as in the mean-field model2 , despite having orders of magnitude fewer edges. This result may be relevant to the observed synchronization of widely separated neurons in the visual cortex27 if, as seems plausible, the brain has a small-world architecture. We hope that our work will stimulate further studies of smallworld networks. Their distinctive combination of high clustering with short characteristic path length cannot be captured by traditional approximations such as those based on regular lattices or random graphs. Although small-world architecture has not received much attention, we suggest that it will probably turn out to be widespread in biological, social and man-made systems, often with important dynamical consequences. M Received 27 November 1997; accepted 6 April 1998. 1. Winfree, A. T. The Geometry of Biological Time (Springer, New York, 1980). 2. Kuramoto, Y. Chemical Oscillations, Waves, and Turbulence (Springer, Berlin, 1984). 3. Strogatz, S. H. & Stewart, I. Coupled oscillators and biological synchronization. Sci. Am. 269(6), 102– 109 (1993). 4. Bressloff, P. C., Coombes, S. & De Souza, B. Dynamics of a ring of pulse-coupled oscillators: a group theoretic approach. Phys. Rev. Lett. 79, 2791–2794 (1997). 5. Braiman, Y., Lindner, J. F. & Ditto, W. L. Taming spatiotemporal chaos with disorder. Nature 378, 465–467 (1995). 6. Wiesenfeld, K. New results on frequency-locking dynamics of disordered Josephson arrays. Physica B 222, 315–319 (1996). 7. Gerhardt, M., Schuster, H. & Tyson, J. J. A cellular automaton model of excitable media including curvature and dispersion. Science 247, 1563–1566 (1990). 8. Collins, J. J., Chow, C. C. & Imhoff, T. T. Stochastic resonance without tuning. Nature 376, 236–238 (1995). 9. Hopfield, J. J. & Herz, A. V. M. Rapid local synchronization of action potentials: Toward computation with coupled integrate-and-fire neurons. Proc. Natl Acad. Sci. USA 92, 6655–6662 (1995). 10. Abbott, L. F. & van Vreeswijk, C. Asynchronous states in neural networks of pulse-coupled oscillators. Phys. Rev. E 48(2), 1483–1490 (1993). 11. Nowak, M. A. & May, R. M. Evolutionary games and spatial chaos. Nature 359, 826–829 (1992). 12. Kauffman, S. A. Metabolic stability and epigenesisin randomly constructed genetic nets. J. Theor. Biol. 22, 437–467 (1969). 13. Milgram, S. The small world problem. Psychol. Today 2, 60–67 (1967). 14. Kochen, M. (ed.) The Small World (Ablex, Norwood, NJ, 1989). 15. Guare, J. Six Degrees of Separation: A Play (Vintage Books, New York, 1990). 16. Bollaba´s, B. Random Graphs (Academic, London, 1985). 17. Achacoso, T. B. & Yamamoto, W. S. AY’s Neuroanatomy of C.elegans for Computation (CRC Press, Boca Raton, FL, 1992). 18. Wasserman, S. & Faust, K. Social Network Analysis: Methods and Applications (Cambridge Univ. Press, 1994). 19. Phadke, A. G. & Thorp, J. S. Computer Relaying for Power Systems (Wiley, New York, 1988). 20. Sattenspiel, L. & Simon, C. P. The spread and persistence of infectious diseases in structured populations. Math. Biosci. 90, 341–366 (1988). 21. Longini, I. M. Jr A mathematical model for predicting the geographic spread of new infectious agents. Math. Biosci. 90, 367–383 (1988). 22. Hess, G. Disease in metapopulation models: implications for conservation. Ecology 77, 1617–1632 (1996). 23. Blythe, S. P., Castillo-Chavez, C. & Palmer, J. S. Toward a unified theory of sexual mixing and pair formation. Math. Biosci. 107, 379–405 (1991). 24. Kretschmar, M. & Morris, M. Measures of concurrency in networks and the spread of infectious disease. Math. Biosci. 133, 165–195 (1996). 25. Das, R., Mitchell, M. & Crutchfield, J. P. in Parallel Problem Solving from Nature (eds Davido, Y., Schwefel, H.-P. & Ma¨nner, R.) 344–353 (Lecture Notes in Computer Science 866, Springer, Berlin, 1994). 26. Axelrod, R. The Evolution of Cooperation (Basic Books, New York, 1984). 27. Gray, C. M., Ko¨nig, P., Engel, A. K. & Singer, W. Oscillatory responsesin cat visual cortex exhibit intercolumnar synchronization which reflects global stimulus properties. Nature 338, 334–337 (1989). Acknowledgements. We thank B. Tjaden for providing the film actor data, and J. Thorp and K. Bae forthe Western States Power Grid data. This work was supported by the US National Science Foundation (Division of Mathematical Sciences). Correspondence and requestsfor materialsshould be addressed to D.J.W.(e-mail: djw24@columbia.edu). 0.15 0.2 0.25 0.3 0.35 0.0001 0.001 0.01 0.1 1 r half p a Figure 3 Simulation results for a simple model of disease spreading. The community structure is given by one realization of the family of randomly rewired graphs used in Fig. 1. a, Critical infectiousness rhalf, at which the disease infects half the population, decreases with p. b, The time T(p) required for a maximally infectious disease (r ¼ 1) to spread throughout the entire population has essentially the same functional form as the characteristic path length L(p). Even if only a few per cent of the edges in the original lattice are randomly rewired, the time to global infection is nearly as short as for a random graph. 0 0.2 0.4 0.6 0.8 1 0.0001 0.001 0.01 0.1 1 T(p) /T(0) L(p) /L(0) p b
