Collective dynamics of 'small

letterstonature

typicallyslowerthanϳ1kms)mightdiffersignificantlyfrom

−1

whatisassumedbycurrentmodellingefforts.Theexpected

27

equation-of-statedifferencesamongsmallbodies(iceversusrock,

forinstance)prentsanotherdimensionofstudy;havingrecently

adaptedourcodeformassivelyparallelarchitectures(K.M.Olson

andE.A,manuscriptinpreparation),wearenowreadytoperforma

morecomprehensiveanalysis.

Theexploratorysimulationsprentedheresuggestthatwhena

young,non-porousasteroid(ifsuchexist)suffersextensiveimpact

damage,theresultingfracturepatternlargelydefinestheasteroid’s

respontofutureimpacts.Thestochasticnatureofcollisions

impliesthatsmallasteroidinteriorsmaybeasdiverastheir

shapesandspinstates.Detailednumericalsimulationsofimpacts,

usingaccurateshapemodelsandrheologies,couldshedlighton

howasteroidcollisionalrespondependsoninternalconfiguration

andshape,andhenceonhowplanetesimalsevolve.Detailed

simulationsarealsorequiredbeforeonecanpredictthequantitative

effectsofnuclearexplosionsonEarth-crossingcometsand

asteroids,eitherforhazardmitigation

28

throughdisruptionand

deflection,orforresourceexploitation.Suchpredictionswould

29

requiredetailedreconnaissanceconcerningthecompositionand

Ⅺ

internalstructureofthetargetedobject.

Received4February;accepted18March1998.

1.Asphaug,E.&Melosh,H.J.TheStickneyimpactofPhobos:Adynamicalmodel.Icarus101,144–164

(1993).

2.Asphaug,E.etal.MechanicalandgeologicaleffectsofimpactcrateringonIda.Icarus120,158–184

(1996).

3.Nolan,M.C.,Asphaug,E.,Melosh,H.J.&Greenberg,R.Impactcratersonasteroids:Doesstrengthor

gravitycontroltheirsize?Icarus124,359–371(1996).

4.Love,S.J.&Ahrens,T.J.Catastrophicimpactsongravitydominatedasteroids.Icarus124,141–155

(1996).

5.Melosh,H.J.&Ryan,E.V.Asteroids:Shatteredbutnotdisperd.Icarus129,562–564(1997).

6.Houn,K.R.,Schmidt,R.M.&Holsapple,K.A.Craterejectascalinglaws:Fundamentalformsbad

ondimensionalanalysis.J.Geophys.Res.88,2485–2499(1983).

7.Holsapple,K.A.&Schmidt,R.M.Pointsourcesolutionsandcouplingparametersincratering

mechanics.J.Geophys.Res.92,6350–6376(1987).

8.Houn,K.R.&Holsapple,K.A.Onthefragmentationofasteroidsandplanetarysatellites.Icarus84,

226–253(1990).

9.Benz,W.&Asphaug,E.Simulationsofbrittlesolidsusingsmoothparticlehydrodynamics.Comput.

Phys.Commun.87,253–265(1995).

10.Asphaug,E.etal.MechanicalandgeologicaleffectsofimpactcrateringonIda.Icarus120,158–184

(1996).

11.Hudson,R.S.&Ostro,S.J.Shapeofasteroid4769Castalia(1989PB)frominversionofradarimages.

Science263,940–943(1994).

12.Ostro,S.J.etal.Asteroidradarastrometry.Astron.J.102,1490–1502(1991).

13.Ahrens,T.J.&O’Keefe,J.D.inImpactandExplosionCratering(edsRoddy,D.J.,Pepin,R.O.&

Merrill,R.B.)639–656(Pergamon,NewYork,1977).

14.Tillotson,J.H.Metallicequationsofstateforhypervelocityimpact.(GeneralAtomicReportGA-3216,

SanDiego,1962).

15.Nakamura,A.&Fujiwara,A.Velocitydistributionoffragmentsformedinasimulatedcollisional

disruption.Icarus92,132–146(1991).

16.Benz,W.&Asphaug,E.Simulationsofbrittlesolidsusingsmoothparticlehydrodynamics.Comput.

Phys.Commun.87,253–265(1995).

17.Bottke,W.F.,Nolan,M.C.,Greenberg,R.&Kolvoord,R.A.Velocitydistributionsamongcolliding

asteroids.Icarus107,255–268(1994).

18.Belton,M.J.S.etal.Galileoencounterwith951Gaspra—Firstpicturesofanasteroid.Science257,

1647–1652(1992).

19.Belton,M.J.S.etal.Galileo’sencounterwith243Ida:Anoverviewoftheimagingexperiment.Icarus

120,1–19(1996).

20.Asphaug,E.&Melosh,H.J.TheStickneyimpactofPhobos:Adynamicalmodel.Icarus101,144–164

(1993).

21.Asphaug,E.etal.MechanicalandgeologicaleffectsofimpactcrateringonIda.Icarus120,158–184

(1996).

22.Houn,K.R.,Schmidt,R.M.&Holsapple,K.A.Craterejectascalinglaws:Fundamentalformsbad

ondimensionalanalysis.J.Geophys.Res.88,2485–2499(1983).

23.Veverka,J.etal.NEAR’sflybyof253Mathilde:ImagesofaCasteroid.Science278,2109–2112(1997).

24.Asphaug,E.etal.Impactevolutionoficyregoliths.LunarPlanet.Sci.Conf.(Abstr.)XXVIII,63–64

(1997).

¨

rz,F.&Brownlee,D.E.Targetporosityeffectsinimpactcrateringandcollisional25.Love,S.G.,Ho

disruption.Icarus105,216–224(1993).

26.Fujiwara,A.,Cerroni,P.,Davis,D.R.,Ryan,E.V.&DiMartino,M.inAsteroidsII(edsBinzel,R.P.,

Gehrels,T.&Matthews,A.S.)240–265(Univ.ArizonaPress,Tucson,1989).

27.Davis,D.R.&Farinella,P.CollisionalevolutionofEdgeworth-KuiperBeltobjects.Icarus125,50–60

(1997).

28.Ahrens,T.J.&Harris,A.W.Deflectionandfragmentationofnear-Earthasteroids.Nature360,429–

433(1992).

29.ResourcesofNear-EarthSpace(edsLewis,J.S.,Matthews,M.S.&Guerrieri,M.L.)(Univ.Arizona

Press,Tucson,1993).

Acknowledgements.ThisworkwassupportedbyNASA’sPlanetaryGeologyandGeophysicsProgram.

CorrespondenceandrequestsformaterialsshouldbeaddresdtoE.A.(e-mail:asphaug@.

edu).

*Prentaddress:PaulF.LazarsfeldCenterfortheSocialSciences,ColumbiaUniversity,812SIPA

Building,420W118St,NewYork,NewYork10027,USA.

Collectivedynamicsof

‘small-world’networks

DuncanJ.Watts*&StevenH.Strogatz

DepartmentofTheoreticalandAppliedMechanics,KimballHall,

CornellUniversity,Ithaca,NewYork14853,USA

.........................................................................................................................

8

Networksofcoupleddynamicalsystemshavebeenudtomodel

biologicaloscillators

1–45,6

,Jophsonjunctionarrays,excitable

media,neuralnetworks,spatialgames,geneticcontrol

78–1011

networks

12

andmanyotherlf-organizingsystems.Ordinarily,

theconnectiontopologyisassumedtobeeithercompletely

regularorcompletelyrandom.Butmanybiological,technological

andsocialnetworksliesomewherebetweenthetwoextremes.

Hereweexploresimplemodelsofnetworksthatcanbetuned

throughthismiddleground:regularnetworks‘rewired’tointro-

duceincreasingamountsofdisorder.Wefindthatthesystems

canbehighlyclustered,likeregularlattices,yethavesmall

characteristicpathlengths,likerandomgraphs.Wecallthem

‘small-world’networks,byanalogywiththesmall-world

phenomenon

13,1415

(popularlyknownassixdegreesofparation).

TheneuralnetworkofthewormCaenorhabditiselegans,the

powergridofthewesternUnitedStates,andthecollaboration

graphoffilmactorsareshowntobesmall-worldnetworks.

Modelsofdynamicalsystemswithsmall-worldcouplingdisplay

enhancedsignal-propagationspeed,computationalpower,and

synchronizability.Inparticular,infectiousdiasspreadmore

easilyinsmall-worldnetworksthaninregularlattices.

Tointerpolatebetweenregularandrandomnetworks,wecon-

siderthefollowingrandomrewiringprocedure(Fig.1).Starting

fromaringlatticewithnverticesandkedgespervertex,werewire

eachedgeatrandomwithprobabilityp.Thisconstructionallowsus

to‘tune’thegraphbetweenregularity(p¼0)anddisorder(p¼1),

andtherebytoprobetheintermediateregion0ϽpϽ1,about

whichlittleisknown.

Wequantifythestructuralpropertiesofthegraphsbytheir

characteristicpathlengthL(p)andclusteringcoefficientC(p),as

definedinFig.2legend.HereL(p)measuresthetypicalparation

betweentwoverticesinthegraph(aglobalproperty),whereasC(p)

measuresthecliquishnessofatypicalneighbourhood(alocal

property).Thenetworksofinteresttoushavemanyvertices

withsparconnections,butnotsosparthatthegraphisin

dangerofbecomingdisconnected.Specifically,werequire

nqkqlnðnÞq1,wherekqlnðnÞguaranteesthatarandom

graphwillbeconnected

16

.Inthisregime,wefindthat

Lϳn=2kq1andCϳ3=4asp→0,whileLϷL

random

ϳlnðnÞ=lnðkÞ

andCϷC

random

ϳk=np1asp→1.Thustheregularlatticeatp¼0

isahighlyclustered,largeworldwhereLgrowslinearlywithn,

whereastherandomnetworkatp¼1isapoorlyclustered,small

worldwhereLgrowsonlylogarithmicallywithn.Thelimiting

casmightleadonetosuspectthatlargeCisalwaysassociatedwith

largeL,andsmallCwithsmallL.

Onthecontrary,Fig.2revealsthatthereisabroadintervalofp

overwhichL(p)isalmostassmallasL

random

yetCðpÞqC.

random

Thesmall-worldnetworksresultfromtheimmediatedropinL(p)

caudbytheintroductionofafewlong-rangeedges.Such‘short

cuts’connectverticesthatwouldotherwibemuchfartherapart

thanL

random

.Forsmallp,eachshortcuthasahighlynonlineareffect

onL,contractingthedistancenotjustbetweenthepairofvertices

thatitconnects,butbetweentheirimmediateneighbourhoods,

neighbourhoodsofneighbourhoodsandsoon.Bycontrast,anedge

440

Nature © Macmillan Publishers Ltd 1998

NATUREVOL3934JUNE1998

||

letterstonature

removedfromaclusteredneighbourhoodtomakeashortcuthas,at

most,alineareffectonC;henceC(p)remainspracticallyunchanged

forsmallpeventhoughL(p)dropsrapidly.Theimportantimplica-

tionhereisthatatthelocallevel(asreflectedbyC(p)),thetransition

toasmallworldisalmostundetectable.Tochecktherobustnessof

theresults,wehavetestedmanydifferenttypesofinitialregular

graphs,aswellasdifferentalgorithmsforrandomrewiring,andall

givequalitativelysimilarresults.Theonlyrequirementisthatthe

rewirededgesmusttypicallyconnectverticesthatwouldotherwi

bemuchfartherapartthanL

random

.

Theidealizedconstructionaboverevealsthekeyroleofshort

cuts.Itsuggeststhatthesmall-worldphenomenonmightbe

commoninsparnetworkswithmanyvertices,asevenatiny

fractionofshortcutswouldsuffice.Totestthisidea,wehave

computedLandCforthecollaborationgraphofactorsinfeature

films(generatedfromdataavailableat),the

electricalpowergridofthewesternUnitedStates,andtheneural

networkofthenematodewormC.elegans

17

.Allthreegraphsareof

scientificinterest.Thegraphoffilmactorsisasurrogateforasocial

network,withtheadvantageofbeingmuchmoreeasilyspecified.

18

Itisalsoakintothegraphofmathematicalcollaborationscentred,

¨

s(partialdataavailableattraditionally,onP.Erdo

/ϳgrossman/).Thegraphof

thepowergridisrelevanttotheefficiencyandrobustnessof

powernetworks

19

.AndC.elegansisthesoleexampleofacompletely

mappedneuralnetwork.

Table1showsthatallthreegraphsaresmall-worldnetworks.

Theexampleswerenothand-picked;theywerechonbecauof

theirinherentinterestandbecaucompletewiringdiagramswere

available.Thusthesmall-worldphenomenonisnotmerelya

curiosityofsocialnetworks

13,14

noranartefactofanidealized

model—itisprobablygenericformanylarge,sparnetworks

foundinnature.

Wenowinvestigatethefunctionalsignificanceofsmall-world

connectivityfordynamicalsystems.Ourtestcaisadeliberately

simplifiedmodelforthespreadofaninfectiousdia.The

populationstructureismodelledbythefamilyofgraphsdescribed

inFig.1.Attimet¼0,asingleinfectiveindividualisintroduced

intoanotherwihealthypopulation.Infectiveindividualsare

removedpermanently(byimmunityordeath)afteraperiodof

sicknessthatlastsoneunitofdimensionlesstime.Duringthistime,

eachinfectiveindividualcaninfecteachofitshealthyneighbours

withprobabilityr.Onsubquenttimesteps,thediaspreads

alongtheedgesofthegraphuntiliteitherinfectstheentire

population,oritdiesout,havinginfectedsomefractionofthe

populationintheprocess.

8

Table1Empiricalexamplesofsmall-worldnetworks

.............................................................................................................................................................................

LLCC

actualrandomactualrandom

2.99Filmactors3.650.790.00027

12.4Powergrid18.70.0800.005

2.25C.elegans2.650.280.05

.............................................................................................................................................................................

CharacteristicpathlengthLandclusteringcoefficientCforthreerealnetworks,compared

torandomgraphswiththesamenumberofvertices(n)andaveragenumberofedgesper

vertex(k).(Actors:n¼225;226,k¼61.Powergrid:n¼4;941,k¼2:67.C.elegans:n¼282,

k¼14.)Thegraphsaredefinedasfollows.Twoactorsarejoinedbyanedgeiftheyhave

actedinafilmtogether.Werestrictattentiontothegiantconnectedcomponent

16

ofthis

graph,whichincludesϳ90%ofallactorslistedintheInternetMovieDataba(availableat

),asofApril1997.Forthepowergrid,verticesreprentgenerators,

transformersandsubstations,andedgesreprenthigh-voltagetransmissionlines

betweenthem.ForC.elegans,anedgejoinstwoneuronsiftheyareconnectedbyeither

asynaporagapjunction.Wetreatalledgesasundirectedandunweighted,andall

verticesasidentical,recognizingthatthearecrudeapproximations.Allthreenetworks

showthesmall-worldphenomenon:LՌL

randomrandom

butCqC.

1

RegularSmall-worldRandom

0.8

CpC

() / (0)

0.6

0.4

0.2

L

() / (0)

pL

pp

= 0 = 1

Increasing randomness

0

0.00010.0010.010.11

p

Figure2CharacteristicpathlengthL(p)andclusteringcoefficientC(p)fortheFigure1Randomrewiringprocedureforinterpolatingbetweenaregularring

familyofrandomlyrewiredgraphsdescribedinFig.1.HereLisdefinedasthelatticeandarandomnetwork,withoutalteringthenumberofverticesoredgesin

numberofedgesintheshortestpathbetweentwovertices,averagedoverallthegraph.Westartwitharingofnvertices,eachconnectedtoitsknearest

pairsofvertices.TheclusteringcoefficientC(p)isdefinedasfollows.Supponeighboursbyundirectededges.(Forclarity,n¼20andk¼4intheschematic

thatavertexvhaskexamplesshownhere,butmuchlargernandkareudintherestofthisLetter.)

v

neighbours;thenatmostkðk

vv

Ϫ1Þ=2edgescanexist

betweenthem(thisoccurswheneveryneighbourofvisconnectedtoeveryother

neighbourofv).LetC

v

denotethefractionoftheallowableedgesthatactually

exist.DefineCastheaverageofC

v

overallv.Forfriendshipnetworks,the

statisticshaveintuitivemeanings:Listheaveragenumberoffriendshipsinthe

shortestchainconnectingtwopeople;C

v

reflectstheextenttowhichfriendsofv

arealsofriendsofeachother;andthusCmeasuresthecliquishnessofatypical

friendshipcircle.Thedatashowninthefigureareaveragesover20random

realizationsoftherewiringprocessdescribedinFig.1,andhavebeennormalized

bythevaluesL(0),C(0)foraregularlattice.Allthegraphshaven¼1;000vertices

andanaveragedegreeofk¼10edgespervertex.Wenotethatalogarithmic

horizontalscalehasbeenudtoresolvetherapiddropinL(p),correspondingto

theontofthesmall-worldphenomenon.Duringthisdrop,C(p)remainsalmost

constantatitsvaluefortheregularlattice,indicatingthatthetransitiontoasmall

worldisalmostundetectableatthelocallevel.

Wechooavertexandtheedgethatconnectsittoitsnearestneighbourina

clockwin.Withprobabilityp,wereconnectthisedgetoavertexchon

uniformlyatrandomovertheentirering,withduplicateedgesforbidden;other-

wiweleavetheedgeinplace.Werepeatthisprocessbymovingclockwi

aroundthering,consideringeachvertexinturnuntilonelapiscompleted.Next,

weconsidertheedgesthatconnectverticestotheircond-nearestneighbours

clockwi.Asbefore,werandomlyrewireeachoftheedgeswithprobabilityp,

andcontinuethisprocess,circulatingaroundtheringandproceedingoutwardto

moredistantneighboursaftereachlap,untileachedgeintheoriginallatticehas

beenconsideredonce.(Astherearenk/2edgesintheentiregraph,therewiring

processstopsafterk/2laps.)Threerealizationsofthisprocessareshown,for

differentvaluesofp.Forp¼0,theoriginalringisunchanged;aspincreas,the

graphbecomesincreasinglydisordereduntilforp¼1,alledgesarerewired

randomly.Oneofourmainresultsisthatforintermediatevaluesofp,thegraphis

asmall-worldnetwork:highlyclusteredlikearegulargraph,yetwithsmall

characteristicpathlength,likearandomgraph.(SeeFig.2.)

NATUREVOL3934JUNE1998

||

Nature © Macmillan Publishers Ltd 1998

441

letterstonature

Tworesultsemerge.First,thecriticalinfectiousnessr,atwhich

half

thediainfectshalfthepopulation,decreasrapidlyforsmallp

(Fig.3a).Second,foradiathatissufficientlyinfectioustoinfect

theentirepopulationregardlessofitsstructure,thetimeT(p)

requiredforglobalinfectionremblestheL(p)curve(Fig.3b).

Thus,infectiousdiasarepredictedtospreadmuchmoreeasily

andquicklyinasmallworld;thealarmingandlessobviouspointis

howfewshortcutsareneededtomaketheworldsmall.

Ourmodeldiffersinsomesignificantwaysfromothernetwork

modelsofdiaspreading

20–2411

.Allthemodelsindicatethatnet-playedonagraph,we

workstructureinfluencesthespeedandextentofdiatransmis-findthatasthefractionofshortcutsincreas,cooperationisless

sion,butourmodelilluminatesthedynamicsasanexplicitfunctionlikelytoemergeinapopulationofplayersusingageneralized‘tit-

ofstructure(Fig.3),ratherthanforafewparticulartopologies,suchfor-tat’

asrandomgraphs,starsandchainsoutofaninitialcooperative/non-cooperativemixalsodecreas

20–23

.Intheworkclosttoours,

KretschmarandMorrishaveshownthatincreasinthenumber

24

ofconcurrentpartnershipscansignificantlyacceleratethepropaga-oscillatorssynchronizealmostasreadilyasinthemean-field

tionofaxually-transmitteddiathatspreadsalongtheedgesofmodel

agraph.Alltheirgraphsaredisconnectedbecautheyfixthe

averagenumberofpartnersperpersonatk¼1.Anincreainthe

numberofconcurrentpartnershipscausfasterspreadingby

increasingthenumberofverticesinthegraph’slargestconnected

component.Incontrast,allourgraphsareconnected;hencethe

predictedchangesinthespreadingdynamicsareduetomoresubtle

structuralfeaturesthanchangesinconnectedness.Moreover,

changesinthenumberofconcurrentpartnersareobvioustoan

individual,whereastransitionsleadingtoasmallerworldarenot.

Wehavealsoexaminedtheeffectofsmall-worldconnectivityon

threeotherdynamicalsystems.Ineachca,theelementswere

coupledaccordingtothefamilyofgraphsdescribedinFig.1.(1)For

cellularautomatachargedwiththecomputationaltaskofdensity

classification

25

,wefindthatasimple‘majority-rule’runningona

small-worldgraphcanoutperformallknownhumanandgenetic

algorithm-generatedrulesrunningonaringlattice.(2)Forthe

iterated,multi-player‘Prisoner’sdilemma’

26

strategy.Thelikelihoodofcooperativestrategiesevolving

withincreasingp.(3)Small-worldnetworksofcoupledpha

2

,despitehavingordersofmagnitudefeweredges.This

resultmayberelevanttotheobrvedsynchronizationofwidely

paratedneuronsinthevisualcortexif,asemsplausible,the

27

brainhasasmall-worldarchitecture.

Wehopethatourworkwillstimulatefurtherstudiesofsmall-

worldnetworks.Theirdistinctivecombinationofhighclustering

withshortcharacteristicpathlengthcannotbecapturedby

traditionalapproximationssuchasthobadonregularlattices

orrandomgraphs.Althoughsmall-worldarchitecturehasnot

receivedmuchattention,wesuggestthatitwillprobablyturnout

tobewidespreadinbiological,socialandman-madesystems,often

Ⅺ

withimportantdynamicalconquences.

Received27November1997;accepted6April1998.

1.Winfree,A.T.TheGeometryofBiologicalTime(Springer,NewYork,1980).

2.Kuramoto,Y.ChemicalOscillations,Waves,andTurbulence(Springer,Berlin,1984).

3.Strogatz,S.H.&Stewart,I.Coupledoscillatorsandbiologicalsynchronization.Sci.Am.269(6),102–

109(1993).

4.Bressloff,P.C.,Coombes,S.&DeSouza,B.Dynamicsofaringofpul-coupledoscillators:agroup

theoreticapproach.Phys.Rev.Lett.79,2791–2794(1997).

5.Braiman,Y.,Lindner,J.F.&Ditto,W.L.Tamingspatiotemporalchaoswithdisorder.Nature378,

465–467(1995).

6.Wienfeld,K.Newresultsonfrequency-lockingdynamicsofdisorderedJophsonarrays.PhysicaB

222,315–319(1996).

7.Gerhardt,M.,Schuster,H.&Tyson,J.J.Acellularautomatonmodelofexcitablemediaincluding

curvatureanddispersion.Science247,1563–1566(1990).

8.Collins,J.J.,Chow,C.C.&Imhoff,T.T.Stochasticresonancewithouttuning.Nature376,236–238

(1995).

9.Hopfield,J.J.&Herz,A.V.M.Rapidlocalsynchronizationofactionpotentials:Towardcomputation

withcoupledintegrate-and-fireneurons.Proc.NatlAcad.Sci.USA92,6655–6662(1995).

10.Abbott,L.F.&vanVreeswijk,C.Asynchronousstatesinneuralnetworksofpul-coupledoscillators.

Phys.Rev.E48(2),1483–1490(1993).

11.Nowak,M.A.&May,R.M.Evolutionarygamesandspatialchaos.Nature359,826–829(1992).

12.Kauffman,S.A.Metabolicstabilityandepigenesisinrandomlyconstructedgeneticnets.J.Theor.Biol.

22,437–467(1969).

13.Milgram,S.Thesmallworldproblem.Psychol.Today2,60–67(1967).

14.Kochen,M.(ed.)TheSmallWorld(Ablex,Norwood,NJ,1989).

15.Guare,J.SixDegreesofSeparation:APlay(VintageBooks,NewYork,1990).

´

s,B.RandomGraphs(Academic,London,1985).16.Bollaba

17.Achacoso,T.B.&Yamamoto,W.S.AY’sNeuroanatomyofC.elegansforComputation(CRCPress,Boca

Raton,FL,1992).

18.Wasrman,S.&Faust,K.SocialNetworkAnalysis:MethodsandApplications(CambridgeUniv.Press,

1994).

19.Phadke,A.G.&Thorp,J.S.ComputerRelayingforPowerSystems(Wiley,NewYork,1988).

20.Sattenspiel,L.&Simon,C.P.Thespreadandpersistenceofinfectiousdiasinstructured

populations.Math.Biosci.90,341–366(1988).

21.Longini,I.M.JrAmathematicalmodelforpredictingthegeographicspreadofnewinfectiousagents.

Math.Biosci.90,367–383(1988).

22.Hess,G.Diainmetapopulationmodels:implicationsforconrvation.Ecology77,1617–1632

(1996).

23.Blythe,S.P.,Castillo-Chavez,C.&Palmer,J.S.Towardaunifiedtheoryofxualmixingandpair

formation.Math.Biosci.107,379–405(1991).

24.Kretschmar,M.&Morris,M.Measuresofconcurrencyinnetworksandthespreadofinfectious

dia.Math.Biosci.133,165–195(1996).

25.Das,R.,Mitchell,M.&Crutchfield,J.P.inParallelProblemSolvingfromNature(edsDavido,Y.,

¨

nner,R.)344–353(LectureNotesinComputerScience866,Springer,Berlin,Schwefel,H.-P.&Ma

1994).

26.Axelrod,R.TheEvolutionofCooperation(BasicBooks,NewYork,1984).

¨

nig,P.,Engel,A.K.&Singer,W.Oscillatoryresponsincatvisualcortexexhibitinter-27.Gray,C.M.,Ko

columnarsynchronizationwhichreflectsglobalstimulusproperties.Nature338,334–337(1989).

Acknowledgements.WethankB.Tjadenforprovidingthefilmactordata,andJ.ThorpandK.Baeforthe

WesternStatesPowerGriddata.ThisworkwassupportedbytheUSNationalScienceFoundation

(DivisionofMathematicalSciences).

CorrespondenceandrequestsformaterialsshouldbeaddresdtoD.J.W.(e-mail:djw24@).

8

a

0.35

0.3

r

half

0.25

0.2

0.15

0.00010.0010.010.11

p

b

1

0.8

TpT

() /(0)

LpL

() /(0)

0.6

0.4

0.2

0

0.00010.0010.010.11

p

Figure3Simulationresultsforasimplemodelofdiaspreading.The

communitystructureisgivenbyonerealizationofthefamilyofrandomlyrewired

graphsudinFig.1.a,Criticalinfectiousnessr

half

,atwhichthediainfects

halfthepopulation,decreaswithp.b,ThetimeT(p)requiredforamaximally

infectiousdia(r¼1)tospreadthroughouttheentirepopulationhasesn-

tiallythesamefunctionalformasthecharacteristicpathlengthL(p).Evenifonlya

fewpercentoftheedgesintheoriginallatticearerandomlyrewired,thetimeto

globalinfectionisnearlyasshortasforarandomgraph.

442

Nature © Macmillan Publishers Ltd 1998

NATUREVOL3934JUNE1998

||