资源描述：
《search in power-law networks》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、PHYSICALREVIEWE,VOLUME64,046135Searchinpower-lawnetworks1,*RajanM.Lukose,1,²2,³1,§LadaA.Adamic,AmitR.Puniyani,andBernardoA.Huberman1HPLabs,PaloAlto,California943042DepartmentofPhysics,StanfordUniversity,382ViaPuebloMall,Stanford,California94305~Received29April2001;revisedmanuscriptreceived22
2、June2001;published26September2001!Manycommunicationandsocialnetworkshavepower-lawlinkdistributions,containingafewnodesthathaveaveryhighdegreeandmanywithlowdegree.Thehighconnectivitynodesplaytheimportantroleofhubsincommunicationandnetworking,afactthatcanbeexploitedwhendesigningef®cientsearcha
3、lgo-rithms.Weintroduceanumberoflocalsearchstrategiesthatutilizehighdegreenodesinpower-lawgraphsandthathavecostsscalingsublinearlywiththesizeofthegraph.WealsodemonstratetheutilityofthesestrategiesontheGNUTELLApeer-to-peernetwork.DOI:10.1103/PhysRevE.64.046135PACSnumber~s!:89.75.Fb,05.50.1q,05
4、.40.2a,89.75.DaI.INTRODUCTIONbytherecentemergenceofpeer-to-peernetworks,whichhavegainedenormouspopularitywithuserswantingtoshareAnumberoflargedistributedsystems,rangingfromso-theircomputer®les.Insuchnetworks,thenameofthetargetcial@1#tocommunication@2#tobiologicalnetworks@3#dis-®lemaybeknown,
5、butduetothenetwork'sadhocnature,playapower-lawdistributionintheirnodedegree.Thisdis-thenodeholdingthe®leisnotknownuntilareal-timesearchtributionre¯ectstheexistenceofafewnodeswithveryhighisperformed.IncontrasttothescenarioconsideredbyKlein-degreeandmanywithlowdegree,afeaturenotfoundinberg,the
6、reisnoglobalinformationaboutthepositionofthestandardrandomgraphs@4#.Alarge-scaleillustrationofsuchtarget,andhenceitisnotpossibletodeterminewhetheraanetworkisgivenbytheAT&Tcallgraph.Acallgraphisstepisamovetowardsorawayfromthetarget.Onesimpleagraphrepresentationoftelephonetraf®conagivendayinwa
7、ytolocate®les,implementedbyNAPSTER,istouseawhichnodesrepresentpeopleandlinksthephonecallscentralserverthatcontainsanindexofallthe®leseveryamongthem.Asshownby@1#,theout-linkdegreedistribu-nodeissharingastheyjointhenetwork.Thisistheequiva-tionforamas
