无标度和加权网络的搜索问题研究

《无标度和加权网络的搜索问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、上海交通大学硕士学位论文无标度和加权网络的搜索问题研究摘要复杂网络中的搜索在现实生活中应用非常广泛。近年来，许多研究者利用复杂网络理论对搜索问题进行了研究。由于现实网络的高度复杂性使人们难以获得网络的全局信息，因此设计基于局部信息的有效搜索策略一直是该领域内研究的重点之一。此外，随着对搜索过程和网络拓扑认识的深入，可搜索性的研究也逐渐成为科研工作者关注的新方向。本文综述了搜索领域的研究现状，研究了适用于大范围幂律指数的无标度网络的搜索策略，分析了加权网络的可搜索性。论文的主要内容和成果总结如下：1.基于无标度网络的特性，提出了最大—最小度搜索

2、算法。该算法仅需利用网络的局部信息，运算复杂度低，搜索步数和网络规模成次线性关系。根据网络的度分布特性，该算法可通过调节参数实现从最大度搜索到随机游走的过渡，因而在不同幂律指数的无标度网络中均有良好的搜索效果。理论分析和仿真结果表明，该算法是最大度算法的有效改进和扩展。2.基于加权网络的特性，提出了定量衡量搜索难易程度的参量，并重点研究了两类加权网络模型的可搜索性。仿真结果表明，这两类加权网络的可搜索性均和网络规模成对数关系。相同耦合关系I上海交通大学硕士学位论文的加权网络比无权网络难于搜索，且难度增加量与加权方式有关。节点的度和权值的差异性

3、是网络搜索中的重要影响因素。此外，对节点层次的搜索信息的研究表明，节点的隐藏能力和获取能力会随权值的改变发生规律性的变化。关键词：复杂网络，搜索，最大—最小度，加权网络，可搜索性II上海交通大学硕士学位论文SEARCHINSCALE-FREEANDWEIGHTEDNETWORKSABSTRACTSearchincomplexnetworksiswidelyusedinreallife.Inrecentyearsscientistshavedelvedintosearchanalysiswiththehelpofcomplexnetworkth

4、eory.Accordingtothehighly-complexity,theglobalinformationofrealnetworksisnearlyunavailabletousers.Thus,howtodesignanefficientsearchalgorithmbasedonlocalinformationhasalwaysbeenoneofthekeysubjectsinthisarea.Moreover,asthefurtherunderstandingofnetworktopologyandsearchprocess,

5、searchabilityhasbecomeanewfocusingfield.Inthisthesis,wereviewtherecentworkofsearchandthenprovideourlocalsearchstrategysuitableforscale-freenetworkswithlargerexponents.Wealsostudythesearchabilityinweightednetworks.Thecontributionsofthisthesisareasfollows:1.Onthebasisofscale-

6、freenetworkcharacteristics,weproposeamax-mindegreesearchstrategy.Thisalgorithmrequiresonlylocalinformationofnetworksandthusthecomplexityislow,inwhichthesearchcostscalessublinearlywithnetworksizes.Besides,byadjustingtheparameter,itcantransitfromhigh-degreeseekingtoIII上海交通大学硕

7、士学位论文randomwalkandthusisapplicabletoscale-freenetworkswithdifferentexponents.Boththeoreticalanalysisandsimulationresultsaregiventoindicatethatthisalgorithmisasuccessfulimprovementandextensionofhigh-degreeseeking.2.Accordingtothecharacteristicsofweightednetwork,weproposeanew

8、parametertoquantifythesearchabilityofweightednetworksandthenapplyittotwokindsofwei