資源描述:
《無標(biāo)度和加權(quán)網(wǎng)絡(luò)的搜索問題研究》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、上海交通大學(xué)碩士學(xué)位論文無標(biāo)度和加權(quán)網(wǎng)絡(luò)的搜索問題研究摘要復(fù)雜網(wǎng)絡(luò)中的搜索在現(xiàn)實生活中應(yīng)用非常廣泛。近年來,許多研究者利用復(fù)雜網(wǎng)絡(luò)理論對搜索問題進(jìn)行了研究。由于現(xiàn)實網(wǎng)絡(luò)的高度復(fù)雜性使人們難以獲得網(wǎng)絡(luò)的全局信息,因此設(shè)計基于局部信息的有效搜索策略一直是該領(lǐng)域內(nèi)研究的重點之一。此外,隨著對搜索過程和網(wǎng)絡(luò)拓?fù)湔J(rèn)識的深入,可搜索性的研究也逐漸成為科研工作者關(guān)注的新方向。本文綜述了搜索領(lǐng)域的研究現(xiàn)狀,研究了適用于大范圍冪律指數(shù)的無標(biāo)度網(wǎng)絡(luò)的搜索策略,分析了加權(quán)網(wǎng)絡(luò)的可搜索性。論文的主要內(nèi)容和成果總結(jié)如下:1.基于無標(biāo)度網(wǎng)絡(luò)的特性,提出了最大—最小度搜索
2、算法。該算法僅需利用網(wǎng)絡(luò)的局部信息,運(yùn)算復(fù)雜度低,搜索步數(shù)和網(wǎng)絡(luò)規(guī)模成次線性關(guān)系。根據(jù)網(wǎng)絡(luò)的度分布特性,該算法可通過調(diào)節(jié)參數(shù)實現(xiàn)從最大度搜索到隨機(jī)游走的過渡,因而在不同冪律指數(shù)的無標(biāo)度網(wǎng)絡(luò)中均有良好的搜索效果。理論分析和仿真結(jié)果表明,該算法是最大度算法的有效改進(jìn)和擴(kuò)展。2.基于加權(quán)網(wǎng)絡(luò)的特性,提出了定量衡量搜索難易程度的參量,并重點研究了兩類加權(quán)網(wǎng)絡(luò)模型的可搜索性。仿真結(jié)果表明,這兩類加權(quán)網(wǎng)絡(luò)的可搜索性均和網(wǎng)絡(luò)規(guī)模成對數(shù)關(guān)系。相同耦合關(guān)系I上海交通大學(xué)碩士學(xué)位論文的加權(quán)網(wǎng)絡(luò)比無權(quán)網(wǎng)絡(luò)難于搜索,且難度增加量與加權(quán)方式有關(guān)。節(jié)點的度和權(quán)值的差異性
3、是網(wǎng)絡(luò)搜索中的重要影響因素。此外,對節(jié)點層次的搜索信息的研究表明,節(jié)點的隱藏能力和獲取能力會隨權(quán)值的改變發(fā)生規(guī)律性的變化。關(guān)鍵詞:復(fù)雜網(wǎng)絡(luò),搜索,最大—最小度,加權(quán)網(wǎng)絡(luò),可搜索性II上海交通大學(xué)碩士學(xué)位論文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上海交通大學(xué)碩
7、士學(xué)位論文randomwalkandthusisapplicabletoscale-freenetworkswithdifferentexponents.Boththeoreticalanalysisandsimulationresultsaregiventoindicatethatthisalgorithmisasuccessfulimprovementandextensionofhigh-degreeseeking.2.Accordingtothecharacteristicsofweightednetwork,weproposeanew
8、parametertoquantifythesearchabilityofweightednetworksandthenapplyittotwokindsofwei