资源描述：
《complex networks and decentralized search algorithms》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、ComplexNetworksandDecentralizedSearchAlgorithmsJonKleinberg∗Abstract.Thestudyofcomplexnetworkshasemergedoverthepastseveralyearsasathemespanningmanydisciplines,rangingfrommathematicsandcomputersciencetothesocialandbiologicalsciences.Asignificantamountofrecentworkinthi
2、sareahasfocusedonthedevelopmentofrandomgraphmodelsthatcapturesomeofthequalitativepropertiesobservedinlarge-scalenetworkdata;suchmodelshavethepotentialtohelpusreason,atagenerallevel,aboutthewaysinwhichreal-worldnetworksareorganized.Wesurveyoneparticularlineofnetworkr
3、esearch,concernedwithsmall-worldphe-nomenaanddecentralizedsearchalgorithms,thatillustratesthisstyleofanalysis.Webeginbydescribingawell-knownexperimentthatprovidedthefirstempiricalbasisforthe“sixdegreesofseparation”phenomenoninsocialnetworks;wethendiscusssomeprobabili
4、sticnetworkmodelsmotivatedbythiswork,illustratinghowthesemodelsleadtonovelalgorithmicandgraph-theoreticquestions,andhowtheyaresupportedbyrecentempiricalstudiesoflargesocialnetworks.MathematicsSubjectClassification(2000).Primary68R10;Secondary05C80,91D30.Keywords.Rand
5、omgraphs,complexnetworks,searchalgorithms,socialnetworkanal-ysis.1.IntroductionOverthepastdecade,thestudyofcomplexnetworkshasemergedasathemerunningthroughresearchinawiderangeofareas.ThegrowthoftheInternetandtheWorldWideWebhasledcomputerscientiststoseekwaystomanageth
6、ecomplexityofthesenetworks,andtohelpusersnavigatetheirvastinformationcontent.Socialscientistshavebeenconfrontedbysocialnetworkdataonascalepreviouslyunimagined:datasetsoncommunicationwithinorganizations,oncol-laborationinprofessionalcommunities,andonrelationshipsinfin
7、ancialdomains.Biologistshavedelvedintotheinteractionsthatdefinethepathwaysofacell’smetabolism,discoveringthatthenetworkstructureoftheseinteractionscanpro-videinsightintofundamentalbiologicalprocesses.Thedrivetounderstandall∗SupportedinpartbyaDavidandLucilePackardFoun
8、dationFellowship,aJohnD.andCatherineT.MacArthurFoundationFellowship,andNSFgrantsCCF-0325453,IIS-0329064,CNS-0403340,andBCS-0537606.2JonKle
