無標(biāo)度和加權(quán)網(wǎng)絡(luò)的搜索問題研究.pdf

1、復(fù)雜網(wǎng)絡(luò)中的搜索在現(xiàn)實(shí)生活中應(yīng)用非常廣泛。近年來，許多研究者利用復(fù)雜網(wǎng)絡(luò)理論對搜索問題進(jìn)行了研究。由于現(xiàn)實(shí)網(wǎng)絡(luò)的高度復(fù)雜性使人們難以獲得網(wǎng)絡(luò)的全局信息，因此設(shè)計(jì)基于局部信息的有效搜索策略一直是該領(lǐng)域內(nèi)研究的重點(diǎn)之一。此外，隨著對搜索過程和網(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)容和成

2、果總結(jié)如下： 1.基于無標(biāo)度網(wǎng)絡(luò)的特性，提出了最大—最小度搜索算法。該算法僅需利用網(wǎng)絡(luò)的局部信息，運(yùn)算復(fù)雜度低，搜索步數(shù)和網(wǎng)絡(luò)規(guī)模成次線性關(guān)系。根據(jù)網(wǎng)絡(luò)的度分布特性，該算法可通過調(diào)節(jié)參數(shù)實(shí)現(xiàn)從最大度搜索到隨機(jī)游走的過渡，因而在不同冪律指數(shù)的無標(biāo)度網(wǎng)絡(luò)中均有良好的搜索效果。理論分析和仿真結(jié)果表明，該算法是最大度算法的有效改進(jìn)和擴(kuò)展。 2.基于加權(quán)網(wǎng)絡(luò)的特性，提出了定量衡量搜索難易程度的參量，并重點(diǎn)研究了兩類加權(quán)網(wǎng)絡(luò)模型的可