small-world graphs models, analysis and applications in network designs

《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