復(fù)雜網(wǎng)絡(luò)的搜索策略研究.pdf

1、復(fù)雜網(wǎng)絡(luò)的搜索包括社會網(wǎng)絡(luò)中的搜索、Internet中的搜索、萬維網(wǎng)中的搜索、P2P網(wǎng)絡(luò)中的搜索等。在復(fù)雜網(wǎng)絡(luò)中,如果每個(gè)節(jié)點(diǎn)都知道網(wǎng)絡(luò)的全局信息,也就是每個(gè)節(jié)點(diǎn)都知道在最少的步數(shù)內(nèi)到達(dá)目標(biāo)節(jié)點(diǎn),這是最優(yōu)的搜索結(jié)果。但現(xiàn)實(shí)的很多網(wǎng)絡(luò)都比較復(fù)雜,比如萬維網(wǎng)網(wǎng)頁的數(shù)量多達(dá)十幾億個(gè)。節(jié)點(diǎn)往往只能利用一些局部的鄰居節(jié)點(diǎn)的相關(guān)信息等來進(jìn)行搜索,因此對局部搜索策略的研究具有現(xiàn)實(shí)的意義。搜索效率和網(wǎng)絡(luò)的阻塞是一對矛盾。例如,廣度優(yōu)先搜索(BFS)策略

2、可以在很短的時(shí)間搜遍整個(gè)網(wǎng)絡(luò),而與此同時(shí)也會在網(wǎng)絡(luò)中產(chǎn)生大量的查詢消息極易引起網(wǎng)絡(luò)的阻塞。另外,網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)對搜索效率的影響是很大的,自從復(fù)雜網(wǎng)絡(luò)的小世界性和無標(biāo)度性被發(fā)現(xiàn)以來,研究者開始從網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)角度出發(fā)提出了一些新的搜索策略和算法,并研究搜索效率和拓?fù)浣Y(jié)構(gòu)的關(guān)系。論文首先簡單介紹了復(fù)雜網(wǎng)絡(luò)的基本概念和幾種基本的搜索策略,并以P2P網(wǎng)絡(luò)為例介紹了廣度優(yōu)先搜索(BFS)策略的應(yīng)用,在仿真實(shí)驗(yàn)中分析了無標(biāo)度網(wǎng)絡(luò)中的最大度搜索(DS

3、)策略。在此基礎(chǔ)上,論文將廣度優(yōu)先搜索(BFS)策略與最大度搜索(DS)策略結(jié)合起來,充分利用兩者的優(yōu)點(diǎn),提出了一種基于二叉樹的搜索(BBS)策略,選擇Matlab作為仿真工具,模擬了BBS策略的過程。重點(diǎn)研究了此策略在幾種典型的網(wǎng)絡(luò)拓?fù)淠Ｐ椭械乃阉餍?分析了拓?fù)浣Y(jié)構(gòu)和搜索效率的關(guān)系,驗(yàn)證其可行性和有效性。本搜索策略使用較少的副本,進(jìn)一步提高了網(wǎng)絡(luò)的搜索效率,并產(chǎn)生了較少的信息量。最后將此策略應(yīng)用到非結(jié)構(gòu)化P2P(Gnutella2)

4、網(wǎng)絡(luò)中,實(shí)驗(yàn)表明其性能良好。論文主要研究以下幾個(gè)方面:
　　1.詳細(xì)介紹了廣度優(yōu)先搜索(BFS)策略在非結(jié)構(gòu)化P2P網(wǎng)絡(luò)的應(yīng)用,介紹了隨機(jī)游走(RW)及最大度(DS)策略在不同復(fù)雜網(wǎng)絡(luò)模型中的仿真實(shí)驗(yàn)。
　　2.設(shè)計(jì)了基于二叉樹的搜索(BBS)策略,在各種網(wǎng)絡(luò)模型中進(jìn)行仿真實(shí)驗(yàn),并詳細(xì)分析了算法的性能,通過和現(xiàn)有的搜索策略對比,證明了算法的可行性和有效性。
　　3.將基于二叉樹的搜索(BBS)策略應(yīng)用在非結(jié)構(gòu)化P2P(