Exploring-complex-networks

insightreviewarticles268NATURE|VOL410|8MARCH2001|—andwithgoodreason.On10August1996,afaultintwopowerlinesinOregonled,throughacascadingseriesoffailures,toblackoutsin11USstatesandtwoCanadianprovinces,leavingabout7millioncustomerswithoutpowerforupto16hours1.TheLoveBugworm,theworstcomputerattacktodate,spreadovertheInterneton4May2000andinflictedbillionsofdollarsofdamageworldwide.Inourlightermomentsweplayparlourgamesaboutconnectivity.‘SixdegreesofMarlonBrando’brokeoutasanationwidefadinGermany,asreadersofDieZeittriedtoconnectafalafelvendorinBerlinwithhisfavouriteactorthroughtheshortestpossiblechainofacquaintances2.AndduringtheheightoftheLewinskyscandal,theNewYorkTimesprintedadiagram3ofthefamouspeoplewithin‘sixdegreesofMonica’.Meanwhilescientistshavebeenthinkingaboutnetworkstoo.Empiricalstudieshaveshedlightonthetopologyoffoodwebs4,5,electricalpowergrids,cellularandmetabolicnetworks6–9,theWorld-WideWeb10,theInternetbackbone11,theneuralnetworkofthenematodewormCaenorhabditiselegans12,telephonecallgraphs13,coauthor-shipandcitationnetworksofscientists14–16,andthequintessential‘old-boy’network,theoverlappingboardsofdirectorsofthelargestcompaniesintheUnitedStates17(Fig.1).Thesedatabasesarenoweasilyaccessible,courtesyoftheInternet.Moreover,theavailabilityofpowerfulcomputershasmadeitfeasibletoprobetheirstructure;untilrecently,computationsinvolvingmillion-nodenetworkswouldhavebeenimpossiblewithoutspecializedfacilities.Whyisnetworkanatomysoimportanttocharacterize?Becausestructurealwaysaffectsfunction.Forinstance,thetopologyofsocialnetworksaffectsthespreadofinforma-tionanddisease,andthetopologyofthepowergridaffectstherobustnessandstabilityofpowertransmission.Fromthisperspective,thecurrentinterestinnetworksispartofabroadermovementtowardsresearchoncomplexsystems.InthewordsofE.O.Wilson18,“Thegreatestchallengetoday,notjustincellbiologyandecologybutinallofscience,istheaccurateandcompletedescriptionofcomplexsystems.Scientistshavebrokendownmanykindsofsystems.Theythinktheyknowmostoftheelementsandforces.Thenexttaskistoreassemblethem,atleastinmathematicalmodelsthatcapturethekeypropertiesoftheentireensembles.”Butnetworksareinherentlydifficulttounderstand,asthefollowinglistofpossiblecomplicationsillustrates.1.Structuralcomplexity:thewiringdiagramcouldbeanintricatetangle(Fig.1).2.Networkevolution:thewiringdiagramcouldchangeovertime.OntheWorld-WideWeb,pagesandlinksarecreatedandlosteveryminute.3.Connectiondiversity:thelinksbetweennodescouldhavedifferentweights,directionsandsigns.SynapsesinExploringcomplexnetworksStevenH.StrogatzDepartmentofTheoreticalandAppliedMechanicsandCenterforAppliedMathematics,212KimballHall,CornellUniversity,Ithaca,NewYork14853-1503,USA(e-mail:[e-mail])Thestudyofnetworkspervadesallofscience,fromneurobiologytostatisticalphysics.Themostbasicissuesarestructural:howdoesonecharacterizethewiringdiagramofafoodwebortheInternetorthemetabolicnetworkofthebacteriumEscherichiacoli?Arethereanyunifyingprinciplesunderlyingtheirtopology?Fromtheperspectiveofnonlineardynamics,wewouldalsoliketounderstandhowanenormousnetworkofinteractingdynamicalsystems—betheyneurons,powerstationsorlasers—willbehavecollectively,giventheirindividualdynamicsandcouplingarchitecture.Researchersareonlynowbeginningtounravelthestructureanddynamicsofcomplexnetworks.Dynamicalsystemscanoftenbemodelledbydifferentialequationsdx/dt4v(x),wherex(t)4(x1(t),…,xn(t))isavectorofstatevariables,tistime,andv(x)4(v1(x),…,vn(x))isavectoroffunctionsthatencodethedynamics.Forexample,inachemicalreaction,thestatevariablesrepresentconcentrations.Thedifferentialequationsrepresentthekineticratelaws,whichusuallyinvolvenonlinearfunctionsoftheconcentrations.Suchnonlinearequationsaretypicallyimpossibletosolveanalytically,butonecangainqualitativeinsightbyimagininganabstractn-dimensionalstatespacewithaxesx1,…,xn.Asthesystemevolves,x(t)flowsthroughstatespace,guidedbythe‘velocity’fielddx/dt4v(x)likeaspeckcarriedalonginasteady,viscousfluid.Supposex(t)eventuallycomestorestatsomepointx*.Thenthevelocitymustbezerothere,sowecallx*afixedpoint.Itcorrespondstoanequilibriumstateofthephysicalsystembeingmodelled.Ifallsmalldisturbancesawayfromx*dampout,x*iscalledastablefixedpoint—itactsasanattractorforstatesinitsvicinity.Anotherlong-termpossibilityisthatx(t)flowstowardsaclosedloopandeventuallycirculatesarounditforever.Suchaloopiscalledalimitcycle.Itrepresentsaself-sustainedoscillationofthephysicalsystem.Athirdpossibilityisthatx(t)mightsettleontoastrangeattractor,asetofstatesonwhichitwandersforever,neverstoppingorrepeating.Sucherratic,aperiodicmotionisconsideredchaoticiftwonearbystatesflowawayfromeachotherexponentiallyfast.Long-termpredictionisimpossibleinarealchaoticsystembecauseofthisexponentialamplificationofsmalluncertaintiesormeasurementerrorsBox1Nonlineardynamics:terminologyandconcepts97©2001MacmillanMagazinesLtdthenervoussystemcanbestrongorweak,inhibitoryorexcitatory.4.Dynamicalcomplexity:thenodescouldbenonlineardynamicals