欢迎来到天天文库
浏览记录
ID:34103296
大小:1.08 MB
页数:152页
时间:2019-03-03
《small-world graphs models, analysis and applications in network designs》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、VanK.NguyenMay2006ComputerScienceSmall-WorldGraphs:Models,AnalysisandApplicationsinNetworkDesignsAbstractSmall-worldpropertiesarecommoninmanylarge-scalereal-worldnetworkssuchassocialnetworks,theInternet,orbiologicalnetworks.In2000,Kleinbergproducedanewmodelforastrikingaspectofacquaintancenetworks
2、:thatshortchainscanbefoundusinglimitedlocalinformationonly(e.g.asearchbasedona¯rst-namebasis).Thismodeladdedrandomlinkstoa2Dgrid,suchthattherandomlinksweremorelikelytoconnectclosernodes.WeexpandKleinberg'sworktoamoregeneralstudyofgraphsformedbyaddingagenericdistribution(oftennon-uniform)ofrandoml
3、inkstoaclassoflocal-contactgraphs.Westudygeneralrulesandcharacteristicswhichproducesmall-world(andrelated)properties.Wealsouseourobservationstodesignpracticalnetworks.Wefocusontheabstractpropertiesoftherandomlinkdistributionswhichintroduceshortpaths(typically,withlengthasapoly-logofnetworksize)be
4、tweenthesitesofthelocal-contactgraph.By¯ndingsuchgeneralproperties,wegiveathoroughanalysisofKleinberg'ssmall-worldmodels.Wealsodevelopnewtechniquesforanalyzingstructureswithnon-uniformrandomlinks.Moreover,wedevelopageneralframeworktoconstructsmall-worldgraphs,fea-turingahierarchicalfamilyofclasse
5、sofrandomstructureswhereshortpathsareavailableandcanbefoundusingdecentralizedroutingstrategiesinourmorere¯nedclasses.Ouranalysisalsosuggestsapplicationsindesigningpracticalnetworks.Weproposeroutingstrategies(androutingdatastructures)thatexploitthespecialfeaturesofournetworkconstructions.Wealsocon
6、siderotherissuessuchasconstructioncost2andcongestion,whichhelptoidentifyandcharacterizepossiblygoodnetworktopolo-gies,suggestedbyournetworkconstructionmethod.Thus,wedevelopaframeworkthathasatwo-foldcontribution:1)asatheoret-icalplatformformodelingandanalyzingsmall-worldnetworks,and2)asadesigntool
7、toconstructcost-e®ectiveroutingnetworkswheremultipledesignfactorsaresimultaneouslyoptimized.Also,wehavestartedstudyingmoregeneralmodelsthatconsidergeographicalnon-uniformities:forexample,welookatthelocalitiesintheInter
此文档下载收益归作者所有