descents and nodal load in scale-free networksnew

《descents and nodal load in scale-free networksnew》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Descentsandnodalloadinscale-freenetworksEliasBareinboimandValmirC.BarbosaProgramadeEngenhariadeSistemaseComputa¸c˜ao,COPPE,UniversidadeFederaldoRiodeJaneiro,CaixaPostal68511,21941-972RiodeJaneiro-RJ,BrazilTheloadofanodeinanetworkisthetotaltrafficgoingthro

2、ughitwheneverynodepairsustainsauniformbidirectionaltrafficbetweenthemonshortestpaths.Weshowthatnodalloadcanbeexpressedintermsofthemoreelementarynotionofanode’sdescentsinbreadth-first-search(BFSorshortest-path)trees,andstudyboththedescentandnodal-loaddistri

3、butionsinthecaseofscale-freenetworks.Ourtreatmentisbothsemi-analytical(combiningagenerating-functionformalismwithsimulation-derivedBFSbranchingprobabilities)andcomputationalforthedescentdistribution;itisexclusivelycomputationalinthecaseoftheloaddistribu

4、tion.Ourmainresultisthattheloaddistribution,eventhoughitcanbedisguisedasapower-lawthroughsubtle(butinappropriate)binningoftherawdata,isinfactasuccessionofsharplydelineatedprobabilitypeaks,eachofwhichcanbeclearlyinterpretedasafunctionoftheunderlyingBFSde

5、scents.Thisfindisinstarkcontrastwithpreviouslyheldbelief,basedonwhichapowerlawofexponent−2.2wasconjecturedtobevalidregardlessoftheexponentofthepower-lawdistributionofnodedegrees.PACSnumbers:89.20.Hh,89.75.Da,89.75.Fb,89.75.HcI.INTRODUCTIONnetworksothat,g

6、lobally,goodstatisticalpropertiesareachieved(suchasexpectingdeliverytooccurformostnodes,forexample).However,whendisseminatinginfor-Inascale-freenetwork,nodeconnectivities(ordegrees)mationgloballyisthegoal,wefindthatdesigningheuris-aredistributedaccording

7、toapowerlaw,thatis,theticsbasedonnodedegrees,eventhoughmeritoriousbyprobabilitythatarandomlychosennodehasdegreekis−τtheireminentlylocalnature,issomewhatlackinginplau-proportionaltokforsomeτ>1.Scale-freenetworkssibility,sinceimportantperformance-relatedn

8、otions,likearethereforestrictlydiversefromnetworksoftheclassiclocallyavailablebandwidthandandnodecongestion,forErd˝os-R´enyitype[1],inwhichnodedegreesarePoisson-example,remaininadequatelyaccounted.distributed.Theimportanceofscale