資源描述:
《complex networks and decentralized search algorithms》由會員上傳分享,免費在線閱讀,更多相關內容在教育資源-天天文庫。
1、ComplexNetworksandDecentralizedSearchAlgorithmsJonKleinberg?Abstract.Thestudyofcomplexnetworkshasemergedoverthepastseveralyearsasathemespanningmanydisciplines,rangingfrommathematicsandcomputersciencetothesocialandbiologicalsciences.Asigni?cantamountofrecentworkinthi
2、sareahasfocusedonthedevelopmentofrandomgraphmodelsthatcapturesomeofthequalitativepropertiesobservedinlarge-scalenetworkdata;suchmodelshavethepotentialtohelpusreason,atagenerallevel,aboutthewaysinwhichreal-worldnetworksareorganized.Wesurveyoneparticularlineofnetworkr
3、esearch,concernedwithsmall-worldphe-nomenaanddecentralizedsearchalgorithms,thatillustratesthisstyleofanalysis.Webeginbydescribingawell-knownexperimentthatprovidedthe?rstempiricalbasisforthe“sixdegreesofseparation”phenomenoninsocialnetworks;wethendiscusssomeprobabili
4、sticnetworkmodelsmotivatedbythiswork,illustratinghowthesemodelsleadtonovelalgorithmicandgraph-theoreticquestions,andhowtheyaresupportedbyrecentempiricalstudiesoflargesocialnetworks.MathematicsSubjectClassi?cation(2000).Primary68R10;Secondary05C80,91D30.Keywords.Rand
5、omgraphs,complexnetworks,searchalgorithms,socialnetworkanal-ysis.1.IntroductionOverthepastdecade,thestudyofcomplexnetworkshasemergedasathemerunningthroughresearchinawiderangeofareas.ThegrowthoftheInternetandtheWorldWideWebhasledcomputerscientiststoseekwaystomanageth
6、ecomplexityofthesenetworks,andtohelpusersnavigatetheirvastinformationcontent.Socialscientistshavebeenconfrontedbysocialnetworkdataonascalepreviouslyunimagined:datasetsoncommunicationwithinorganizations,oncol-laborationinprofessionalcommunities,andonrelationshipsin?n
7、ancialdomains.Biologistshavedelvedintotheinteractionsthatde?nethepathwaysofacell’smetabolism,discoveringthatthenetworkstructureoftheseinteractionscanpro-videinsightintofundamentalbiologicalprocesses.Thedrivetounderstandall?SupportedinpartbyaDavidandLucilePackardFoun
8、dationFellowship,aJohnD.andCatherineT.MacArthurFoundationFellowship,andNSFgrantsCCF-0325453,IIS-0329064,CNS-0403340,andBCS-0537606.2JonKle