LETTERSCatastrophiccascadeoffailuresininterdependentnetworksSergeyV.Buldyrev1,2,RoniParshani3,GeraldPaul2,H.EugeneStanley2&ShlomoHavlin3Complexnetworkshavebeenstudiedintensivelyforadecade,butresearchstillfocusesonthelimitedcaseofasingle,non-interactingnetwork1–14.Modernsystemsarecoupledtogether15–19andthere-foreshouldbemodelledasinterdependentnetworks.Afun-damentalpropertyofinterdependentnetworksisthatfailureofnodesinonenetworkmayleadtofailureofdependentnodesinothernetworks.Thismayhappenrecursivelyandcanleadtoacascadeoffailures.Infact,afailureofaverysmallfractionofnodesinonenetworkmayleadtothecompletefragmentationofasystemofseveralinterdependentnetworks.Adramaticreal-worldexampleofacascadeoffailures(‘concurrentmalfunction’)istheelectricalblackoutthataffectedmuchofItalyon28September2003:theshutdownofpowerstationsdirectlyledtothefailureofnodesintheInternetcommunicationnetwork,whichinturncausedfurtherbreakdownofpowerstations20.Herewedevelopaframeworkforunderstandingtherobustnessofinteractingnetworkssubjecttosuchcascadingfailures.Wepresentexactana-lyticalsolutionsforthecriticalfractionofnodesthat,onremoval,willleadtoafailurecascadeandtoacompletefragmentationoftwointerdependentnetworks.Surprisingly,abroaderdegreedistri-butionincreasesthevulnerabilityofinterdependentnetworkstorandomfailure,whichisoppositetohowasinglenetworkbehaves.Ourfindingshighlighttheneedtoconsiderinterdependentnetworkpropertiesindesigningrobustnetworks.Today’snetworksarebecomingincreasinglydependentononeanother.Diverseinfrastructuressuchaswatersupply,transportation,fuelandpowerstationsarecoupledtogether.Weshowthatowingtothiscoupling,interdependentnetworksareextremelysensitivetorandomfailure,suchthatarandomremovalofasmallfractionofnodesfromonenetworkcanproduceaniterativecascadeoffailuresinseveralinterdependentnetworks.Electricalblackoutsfrequentlyresultfromacascadeoffailuresbetweeninterdependentnetworks,andtheproblemhasbeendramaticallyexemplifiedbytheseverallarge-scaleblackoutsthathaveoccurredinrecentyears.InthisLetter,wedemonstrateacascadeoffailuresusingreal-worlddatafromapowernetworkandanInternetnetwork(asupervisorycontrolanddataacquisitionsystem)thatwereimplicatedintheblackoutthataffectedmuchofItalyon28September200320.Thesetwonetworksfeatureabidirectionaldependencesuchthatpowerstationsdependoncommunicationnodesforcontrolandcommunicationnodesdependonpowerstationsfortheirelectricitysupply.Figure1showsthetwonetworksandtheconnectionsbetweenthem,basedontherealgeographicallocations.Thefigureexemplifiesasituationinwhichaninitialfailureofonlyonepowerstationmayleadtoaniterativecascadeoffailuresthatcausesbothnetworkstobecomefragmented.Foranisolatedsinglenetwork,asignificantnumberofthenetworknodesmustberandomlyremovedbeforethenetworkbreaksdown.However,whentakingintoaccountthedependenciesbetweenthenetworks,removalofonlyasmallfractionofnodescanresultinthecompletefragmentationoftheentiresystem.Tomodelinterdependentnetworks,weconsiderforsimplicity,andwithoutlossofgenerality,twonetworks,AandB,withthesamenumberofnodes,N.ThefunctioningofnodeAi(i51,2,…,N),innetworkA,dependsontheabilityofnodeBi,innetworkB,tosupplyacriticalresource,andviceversa.IfnodeAistopsfunctioningowingtoattackorfailure,nodeBistopsfunctioning.Similarly,ifnodeBistopsfunctioningthennodeAistopsfunctioning.Wedenotesuchadependencebyabidirectionallink,Ai«Bi,thatdefinesaone-to-onecorrespondencebetweennodesofnetworkAandnodesofnetworkB.WithinnetworkA,thenodesarerandomlyconnectedbyA-linkswithdegreedistributionPA(k),wherethedegree,k,ofeachnodeisdefinedasthenumberofA-linksconnectedtothatnodeinnetworkA.Analogously,withinnetworkB,thenodesarerandomlyconnectedbyB-linkswithdegreedistributionPB(k)(Fig.2).Webeginbyrandomlyremovingafraction,12p,ofthenodesofnetworkAandremovingalltheA-linksconnectedtotheseremovednodes(Fig.2a).Owingtothedependencebetweenthenetworks,allthenodesinnetworkBthatareconnectedtotheremovedA-nodesbyA«Blinksmustalsoberemoved(Fig.2b).AnyB-linksconnectedtotheremovedB-nodesarethenalsoremoved.Asnodesandlinksaresequentiallyremoved,eachnetworkbeginstofragmentintocon-nectedcomponents,whichwecallclusters.TheclustersinnetworkAandtheclustersinnetworkBaredifferentbecauseeachnetworkisconnecteddifferently.Asetofnodes,a,innetworkAandthecor-respondingsetofnodes,b,innetworkBformamutuallyconnectedsetif(1)eachpairofnodesinaisconnectedbyapaththatconsistsofnodesbelongingtoaandlinksofnetworkA,and(2)eachpairofnodesinbisconnectedbyapaththatconsistsofnodesbelongingtobandlinksofnetworkB.Wecallamutuallyconnectedsetamutuallyconnectedclusterifitcannotbeenlargedbyaddingothernodesandstillsatisfytheconditionsabove.Onlymutuallyconnectedclustersarepotentiallyfunctional.Toidentifythesemutuallyconnectedclusters,wefirstdefinethea1-clustersastheclustersofnetworkAremainingafterafraction12poftheA-nodesareremovedastheresultofanattackormal-function(Fig.2b).Thisstateofthenetworksisthefirststageinthecascadeoffailures.Nextwedefinetheb1-setsasthesetsofB-nodesthatareconnectedtoa1-clustersbyA«Blinks.Accordingtothedefinitionofmutuallycon