您好，欢迎访问三七文档
VOLUME85,NUMBER21PHYSICALREVIEWLETTERS20NOVEMBER2000ResilienceoftheInternettoRandomBreakdownsReuvenCohen,1,*KerenErez,1Danielben-Avraham,2andShlomoHavlin11MinervaCenterandDepartmentofPhysics,Bar-IlanUniversity,Ramat-Gan52900,Israel2PhysicsDepartmentandCenterforStatisticalPhysics(CISP),ClarksonUniversity,Potsdam,NewYork13699-5820(Received11July2000;revisedmanuscriptreceived31August2000)Acommonpropertyofmanylargenetworks,includingtheInternet,isthattheconnectivityofthevariousnodesfollowsascale-freepower-lawdistribution,Pkck2a.Westudythestabilityofsuchnetworkswithrespecttocrashes,suchasrandomremovalofsites.Ourapproach,basedonpercolationtheory,leadstoageneralconditionforthecriticalfractionofnodes,pc,thatneedstoberemovedbeforethenetworkdisintegrates.Weshowanalyticallyandnumericallythatfora#3thetransitionnevertakesplace,unlessthenetworkisfinite.InthespecialcaseofthephysicalstructureoftheInterneta2.5,wefindthatitisimpressivelyrobust,withpc.0.99.PACSnumbers:84.35.+i,02.50.Cw,05.50.+q,64.60.AkRecentlytherehasbeenincreasinginterestinthefor-mationofrandomnetworksandintheconnectivityofthesenetworks,especiallyinthecontextoftheInternet[1–9].Whensuchnetworksaresubjecttorandombreak-downs—afractionpofthenodesandtheirconnectionsareremovedrandomly—theirintegritymightbecompro-mised:whenpexceedsacertainthreshold,p.pc,thenetworkdisintegratesintosmaller,disconnectedparts.Be-lowthatcriticalthreshold,therestillexistsaconnectedclusterthatspanstheentiresystem(itssizeispropor-tionaltothatoftheentiresystem).Randombreakdowninnetworkscanbeseenasacaseofinfinite-dimensionalpercolation.TwocasesthathavebeensolvedexactlyareCayleytrees[10]andErd˝os-Rényi(ER)randomgraphs[11],wherethenetworkscollapseatknownthresholdspc.Percolationonsmall-worldnetworks(i.e.,networkswhereeverynodeisconnectedtoitsneighbors,plussomeran-domlong-rangeconnections[12])hasalsobeenstudiedbyMooreandNewman[13].Albertetal.haveraisedthequestionofrandomfailuresandintentionalattackonnet-works[1].HereweconsiderrandombreakdownintheInternet(andsimilarnetworks)andintroduceananalyticalapproachtofindingthecriticalpoint.ThesiteconnectivityofthephysicalstructureoftheInternet,whereeachcom-municationnodeisconsideredasasite,ispowerlaw,toagoodapproximation[14].Weintroduceanewgeneralcriterionforthepercolationcriticalthresholdofrandomlyconnectednetworks.Usingthiscriterion,weshowanalyti-callythattheInternetundergoesnotransitionunderran-dombreakdownofitsnodes.Inotherwords,aconnectedclusterofsitesthatspanstheInternetsurvivesevenforar-bitrarilylargefractionsofcrashedsites.Weconsidernetworkswhosenodesareconnectedran-domlytoeachother,sothattheprobabilityforanytwonodestobeconnecteddependssolelyontheirrespectiveconnectivity(thenumberofconnectionsemanatingfromanode).Wearguethat,forrandomlyconnectednetworkswithconnectivitydistributionPk,thecriticalbreakdownthresholdmaybefoundbythefollowingcriterion:ifloopsofconnectednodesmaybeneglected,thepercolationtran-sitiontakesplacewhenanode(i),connectedtoanode(j)inthespanningcluster,isalsoconnectedtoatleastoneothernode—otherwisethespanningclusterisfragmented.Thismaybewrittenaskiji$jXkikiPkiji$j2,(1)wheretheangularbracketsdenoteanensembleaverage,kiistheconnectivityofnodei,andPkiji$jisthecon-ditionalprobabilitythatnodeihasconnectivityki,giventhatitisconnectedtonodej.But,byBayesruleforcondi-tionalprobabilitiesPkiji$jPki,i$jPi$jPi$jjkiPkiPi$j,wherePki,i$jisthejointprobabilitythatnodeihasconnectivitykiandthatitisconnectedtonodej.Forrandomlyconnectednet-works(neglectingloops)Pi$jkN21andPi$jjkikiN21,whereNisthetotalnumberofnodesinthenetwork.Itfollowsthatthecriterion(1)isequivalenttokk2k2,(2)atcriticality.Loopscanbeignoredbelowthepercolationtransition,k,2,becausetheprobabilityofabondtoformaloopinans-nodesclusterisproportionaltosN2(i.e.,pro-portionaltotheprobabilityofchoosingtwositesinthatcluster).ThefractionofloopsinthesystemPloopisPloop~Xis2iN2,XisiSN2SN,(3)wherethesumistakenoverallclusters,andsiisthesizeoftheithcluster.Thus,theoverallfractionofloopsinthesystemissmallerthanSN,whereSisthesizeofthelargestexistingcluster.BelowcriticalitySissmallerthanorderN(forERgraphsSisoforderlnN[11]),sothefractionofloopsbecomesnegligibleinthelimitofN!`.Similarargumentsapplyatcriticality.46260031-90070085(21)4626(3)$15.00©2000TheAmericanPhysicalSocietyVOLUME85,NUMBER21PHYSICALREVIEWLETTERS20NOVEMBER2000Considernowarandombreakdownofafractionpofthenodes.Thiswouldgenericallyaltertheconnectivitydistributionofanode.Consider,indeed,anodewithinitialconnectivityk0,chosenfromaninitialdistributionPk0.Aftertherandombreakdownthedistributionofthenewconnectivityofthenodebecomesk0k12pkpk02k,andthenewdistributionisP0k`Xk0kPk0µk0k∂12pkpk02k.(4)(Quantitiesafterthebreakdownaredenotedbyaprime.)Usingthisnewdistribution,oneobtainsk0k0312pandk20k2012p21k0p12p,sothecriterion(2)forcriticalitymaybereexpressedask20k012pc1pc2(5)or12pc1k021,(6)wherek0k20k0iscomputedfromtheoriginaldis-tribution,beforetherandombreak
三七文档所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
扫描二维码
wuwuzhazhabihua
本文标题：Resilience-of-the-Internet-to-Random-Breakdowns
链接地址：https://www.777doc.com/doc-5790295 .html