溫巧林，司守奎，任東彥，謝宇鵬

（海軍航空工程學(xué)院 a.研究生管理大隊(duì)；b.基礎(chǔ)部，山東 煙臺(tái) 264001）

0 引言

隨著人類生活日益網(wǎng)絡(luò)化，各種網(wǎng)絡(luò)信息急劇增長(zhǎng)，網(wǎng)絡(luò)搜索的重要作用也越來(lái)越明顯。目前關(guān)于網(wǎng)絡(luò)搜索仍有許多基本理論問(wèn)題有待深入研究，例如何種網(wǎng)絡(luò)才可以快速搜索？網(wǎng)絡(luò)結(jié)構(gòu)對(duì)網(wǎng)絡(luò)搜索的效率有何影響？如何實(shí)現(xiàn)網(wǎng)絡(luò)的快速搜索等等。

上世紀(jì)60年代，Stanley Milgram的小世界實(shí)驗(yàn)率先揭示了社會(huì)網(wǎng)絡(luò)的小世界特性以及可搜索特性[1]。隨后科學(xué)家們對(duì)網(wǎng)絡(luò)搜索展開(kāi)了一系列研究：先是Kleinberg在理論上對(duì)網(wǎng)絡(luò)的搜索能力進(jìn)行了研究[2-3]，然后Watts 等人又對(duì)此問(wèn)題做了進(jìn)一步的研究[4]，Adamic 等人則對(duì)Watts 等人的研究成果在Email網(wǎng)絡(luò)上進(jìn)行了驗(yàn)證[5-7]，而Clauset 等人提出了一個(gè)基于Kleinberg網(wǎng)格模型的動(dòng)態(tài)網(wǎng)絡(luò)模型[8]，他們也得出了和Kleinberg相似的結(jié)論。而關(guān)于網(wǎng)絡(luò)搜索的算法研究，目前主要集中在提高搜索速度和控制算法本身對(duì)網(wǎng)絡(luò)資源的占用這兩個(gè)方面。當(dāng)前，常見(jiàn)搜索算法在綜合解決這兩個(gè)方面問(wèn)題時(shí)效果并不明顯，本文將在分析常見(jiàn)搜索算法優(yōu)劣的基礎(chǔ)上提出一種綜合改善這兩方面因素的混合搜索算法。

1 幾種常見(jiàn)搜索算法

通常用消息的傳遞過(guò)程來(lái)描述網(wǎng)絡(luò)的搜索算法。搜索開(kāi)始時(shí)，源節(jié)點(diǎn)按照一定的規(guī)則向它的一個(gè)或多個(gè)鄰居傳遞查詢消息。如果收到查詢的鄰居節(jié)點(diǎn)上不含有目標(biāo)節(jié)點(diǎn)的信息，那么這些鄰居節(jié)點(diǎn)再繼續(xù)將查詢傳遞給它們各自的鄰居，重復(fù)這個(gè)過(guò)程直到目標(biāo)節(jié)點(diǎn)被尋找到為止。常見(jiàn)的搜索算法很多，下面重點(diǎn)介紹廣度優(yōu)先搜索、隨機(jī)游走搜索和最大度搜索算法。

1.1 廣度優(yōu)先搜索算法

廣度優(yōu)先搜索算法（breadth-first search，BFS）的基本思想是：從源節(jié)點(diǎn)s 開(kāi)始，首先查詢其所有的鄰居節(jié)點(diǎn)，詢問(wèn)是否含有目標(biāo)節(jié)點(diǎn)g，如果s的鄰居中有節(jié)點(diǎn)含有了此目標(biāo)節(jié)點(diǎn)，則將目標(biāo)節(jié)點(diǎn)返回給源節(jié)點(diǎn)；如果沒(méi)有鄰居含有目標(biāo)節(jié)點(diǎn)，則所有的鄰居將查詢繼續(xù)傳遞給各自的鄰居節(jié)點(diǎn)，一直到搜索到目標(biāo)節(jié)點(diǎn)為止。BFS算法搜索速度很快，能夠很快遍歷網(wǎng)絡(luò)，但其缺點(diǎn)也十分明顯，隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，將會(huì)在網(wǎng)絡(luò)中產(chǎn)生大量查詢消息流量，造成網(wǎng)絡(luò)流量急劇增加從而導(dǎo)致網(wǎng)絡(luò)擁塞。

1.2 隨機(jī)游走搜索算法

隨機(jī)游走搜索算法（rand-walk search，RWS）是一個(gè)基礎(chǔ)的動(dòng)態(tài)過(guò)程，也是研究網(wǎng)絡(luò)結(jié)構(gòu)的一個(gè)很有用的工具。主要有無(wú)限制的隨機(jī)游走搜索（URW）、不返回上一步節(jié)點(diǎn)的隨機(jī)游走搜索（NRRW）和不重復(fù)訪問(wèn)節(jié)點(diǎn)的隨機(jī)游走搜索（SARW）3種方式。三者的主要區(qū)別在于算法對(duì)訪問(wèn)節(jié)點(diǎn)的限制上。其中URW算法在搜索時(shí)不加任何限制地從其所有的鄰居節(jié)點(diǎn)中隨機(jī)選擇一個(gè)作為下一個(gè)訪問(wèn)節(jié)點(diǎn)；NRRW在訪問(wèn)過(guò)程中除上一步訪問(wèn)節(jié)點(diǎn)之外，當(dāng)前節(jié)點(diǎn)在其余的所有鄰居中隨機(jī)選擇一個(gè)鄰居節(jié)點(diǎn)；而SARW算法則將所有已訪問(wèn)節(jié)點(diǎn)排除在訪問(wèn)之外。

1.3 最大度搜索算法

最大度搜索算法（degree search，DS）最初是由Adamic 等人提出的[6-7]。由于對(duì)Gnutella網(wǎng)絡(luò)的統(tǒng)計(jì)結(jié)果表明該網(wǎng)絡(luò)的連接度服從冪律分布，Adamic 等人基于此提出了利用節(jié)點(diǎn)度的冪律分布特性進(jìn)行搜索的構(gòu)想。其基本思想是：源節(jié)點(diǎn)s 首先查詢其度最大的鄰居節(jié)點(diǎn)，詢問(wèn)是否含有目標(biāo)節(jié)點(diǎn)g，如果此節(jié)點(diǎn)存儲(chǔ)了目標(biāo)節(jié)點(diǎn)，則它將目標(biāo)節(jié)點(diǎn)返回給源節(jié)點(diǎn)；若沒(méi)有，則它選擇自己的度最大的鄰居將查詢傳遞過(guò)去，一直到搜索到目標(biāo)節(jié)點(diǎn)為止。

2 基于最大度和隨機(jī)游走的混合搜索算法

上面介紹了幾種常見(jiàn)搜索算法的基本思想，可以看出，幾種算法在搜索過(guò)程中存在著各自的優(yōu)點(diǎn)和不足：廣度優(yōu)先算法搜索速度快，但會(huì)在網(wǎng)絡(luò)中產(chǎn)生大量查詢消息；隨機(jī)游走雖然降低了查詢消息，但搜索速度也隨之下降了；最大度搜索雖能在兩者之間取得一定的平衡，但是其搜索前進(jìn)的“步伐”偏慢，且需要比較每個(gè)節(jié)點(diǎn)的度。因此，下面介紹我們?cè)O(shè)計(jì)的一種基于最大度和隨機(jī)游走的混合搜索算法（degree and rand walk search，DRS）。它綜合利用隨機(jī)游走向前移動(dòng)較快和最大度搜索信息利用率高的優(yōu)點(diǎn)，在保持較快搜索速度的同時(shí)能有效控制查詢消息量。

2.1 基本思想

DRS 搜索算法的基本思想是：在每個(gè)節(jié)點(diǎn)都認(rèn)識(shí)自己的鄰居并知道每個(gè)鄰居的度的前提下，交替運(yùn)用隨機(jī)游走搜索和最大度搜索算法在網(wǎng)絡(luò)中進(jìn)行搜索。其基本過(guò)程如下，首先，源節(jié)點(diǎn)s 查詢其度最大的鄰居節(jié)點(diǎn)，詢問(wèn)是否含有目標(biāo)節(jié)點(diǎn)g，如果找到目標(biāo)節(jié)點(diǎn)，則它將目標(biāo)節(jié)點(diǎn)返回給源節(jié)點(diǎn)；若沒(méi)有，則它隨機(jī)選擇一個(gè)未訪問(wèn)過(guò)的鄰居節(jié)點(diǎn)將查詢傳遞過(guò)去，在下一步中如果節(jié)點(diǎn)依然沒(méi)有搜索到目標(biāo)節(jié)點(diǎn)，則再次運(yùn)用最大度搜索進(jìn)行查詢。這樣交替搜索直到搜索到目標(biāo)節(jié)點(diǎn)為止。其基本搜索示意圖過(guò)程如圖1所示。

圖1 利用DRS算法搜索源節(jié)點(diǎn)s與目標(biāo)節(jié)點(diǎn)g之間的路徑（搜索步數(shù)k=5）

2.2 算法設(shè)計(jì)

基于上面的分析，DRS 搜索算法設(shè)計(jì)如下。

1）構(gòu)造集合E，用于存放已訪問(wèn)的節(jié)點(diǎn)，k=1。

2）判斷源節(jié)點(diǎn)s是否為目標(biāo)節(jié)點(diǎn)g。若是，則目標(biāo)節(jié)點(diǎn)找到，停止搜索；否則，進(jìn)入轉(zhuǎn)步驟3）。

3）計(jì)算當(dāng)前訪問(wèn)節(jié)點(diǎn)所有鄰居節(jié)點(diǎn)尚未訪問(wèn)節(jié)點(diǎn)的度，選擇其中度最大的節(jié)點(diǎn)作為下一步訪問(wèn)節(jié)點(diǎn)，k=k+1；如果這樣的鄰居節(jié)點(diǎn)不止一個(gè)，則在它們中隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為訪問(wèn)節(jié)點(diǎn)；如果所有的節(jié)點(diǎn)都已經(jīng)訪問(wèn)過(guò)，則返回到上一步所訪問(wèn)的節(jié)點(diǎn)。

4）判斷此節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中是否有g(shù)。若有，則目標(biāo)節(jié)點(diǎn)找到，搜索結(jié)束，否則轉(zhuǎn)步驟5）。

5）對(duì)于第k+1步，在第k步訪問(wèn)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中隨機(jī)選擇一個(gè)尚未訪問(wèn)的節(jié)點(diǎn)作為訪問(wèn)節(jié)點(diǎn)。

6）判斷此節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中是否有g(shù)。若有，則目標(biāo)節(jié)點(diǎn)找到，搜索結(jié)束，否則轉(zhuǎn)步驟7）。

7）重復(fù)步驟3）～6），直至目標(biāo)節(jié)點(diǎn)g 被找到。搜索結(jié)束。

3 搜索效率仿真

3.1 搜索效率

搜索算法主要是在提高搜索速度和控制查詢信息量進(jìn)行改進(jìn)，因此本文在評(píng)價(jià)搜索效率時(shí)也將主要考察算法在這兩方面的性能。算法的搜索速度由算法在搜索時(shí)需訪問(wèn)的步數(shù)決定。在一個(gè)節(jié)點(diǎn)數(shù)為N的網(wǎng)絡(luò)中，當(dāng)采用某種搜索算法時(shí)，則從這N個(gè)節(jié)點(diǎn)中隨機(jī)選擇出n個(gè)不同的源節(jié)點(diǎn)，然后對(duì)于每一個(gè)選擇的源節(jié)點(diǎn)i，運(yùn)用此搜索算法搜索源節(jié)點(diǎn)i到節(jié)點(diǎn)j的搜索步數(shù)tij(i≠j)。則源節(jié)點(diǎn)i到其他所有N?1個(gè)節(jié)點(diǎn)所需的搜索步數(shù)Ti為

因此，我們可定義網(wǎng)絡(luò)的平均搜索步數(shù)T為

而算法的查詢信息量則定義為搜索算法在搜索時(shí)查詢鄰居節(jié)點(diǎn)的次數(shù)。

3.2 仿真方法

仿真中構(gòu)造出ER隨機(jī)均勻網(wǎng)絡(luò)、NW 小世界網(wǎng)絡(luò)和BA 無(wú)標(biāo)度網(wǎng)絡(luò)3種網(wǎng)絡(luò)模型。對(duì)于每種網(wǎng)絡(luò)類型分別構(gòu)造出N=20、30、50、75、100、150、200的7種網(wǎng)絡(luò)規(guī)模，根據(jù)3.1節(jié)定義，選擇的源節(jié)點(diǎn)個(gè)數(shù)為總節(jié)點(diǎn)個(gè)數(shù)的1/8，然后分別運(yùn)用BFS、URW、NRRW、SARW、DS和DRS 求出各種算法的平均搜索步數(shù)。同時(shí)，為了比較各種算法在上述搜索過(guò)程中所產(chǎn)生的信息查詢量大小，我們對(duì)仿真中的每個(gè)源節(jié)點(diǎn)，求出其訪問(wèn)網(wǎng)絡(luò)中其他所有節(jié)點(diǎn)的信息查詢量并取平均值，最后求出這些節(jié)點(diǎn)總的平均值從而得出搜索算法在這一網(wǎng)絡(luò)類型中的平均信息查詢量。

其中，對(duì)于ER隨機(jī)均勻網(wǎng)絡(luò)模型，設(shè)定其節(jié)點(diǎn)間連接概率為p=0.815；而NW 小世界網(wǎng)絡(luò)模型的連接概率p=0.2，最近鄰耦合系數(shù)k=2；對(duì)于BA無(wú)標(biāo)度網(wǎng)絡(luò)模型，其網(wǎng)絡(luò)生成方式為初始節(jié)點(diǎn)m0=10，每次新添加m=5個(gè)節(jié)點(diǎn)。

3.3 仿真結(jié)果與分析

圖2分別為幾種搜索算法在3種網(wǎng)絡(luò)類型中的平均搜索步數(shù)對(duì)比。從圖中可以看出，最容易實(shí)現(xiàn)搜索的網(wǎng)絡(luò)類型是小世界網(wǎng)絡(luò)，其次為無(wú)標(biāo)度網(wǎng)絡(luò)，而在均勻網(wǎng)絡(luò)中搜索速度較慢。另外，在均勻網(wǎng)絡(luò)中網(wǎng)絡(luò)的搜索步數(shù)是隨著網(wǎng)絡(luò)規(guī)模的增大而減少的，而在NW 小世界網(wǎng)絡(luò)和BA 無(wú)標(biāo)度網(wǎng)絡(luò)中，搜索步數(shù)卻隨著規(guī)模的增大而增加的。而單純就幾種算法的搜索速度而言，BFS的搜索速度最快，DRS和DS次之，幾種隨機(jī)游走算法搜索速度最慢。

對(duì)于各種算法在搜索時(shí)對(duì)網(wǎng)絡(luò)的信息查詢量，從表1中統(tǒng)計(jì)數(shù)據(jù)可以看出，BFS 雖然平均搜索步數(shù)最少，但由于其每次都需詢問(wèn)所有的鄰居節(jié)點(diǎn)，因此產(chǎn)生了非常大的查詢消息量。在其他搜索算法中，查詢消息從少到多依次是DRS算法、DS算法和3種隨機(jī)搜索算法。雖然這幾種搜索算法的平均信息查詢量差距似乎不太明顯，但是對(duì)于一個(gè)上百萬(wàn)甚至千萬(wàn)級(jí)的網(wǎng)絡(luò)，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的一次查詢就會(huì)在網(wǎng)絡(luò)中產(chǎn)生大量的查詢消息。因此，對(duì)于整個(gè)網(wǎng)絡(luò)而言這樣的改進(jìn)是非常有意義的。

圖2 各種搜索算法在均勻網(wǎng)絡(luò)、NW 小世界網(wǎng)絡(luò)和BA 無(wú)標(biāo)度網(wǎng)絡(luò)中的平均搜索步數(shù)

表16 種搜索算法在不同網(wǎng)絡(luò)類型中的平均信息查詢量

從上述仿真可以看出，DRS 搜索算法無(wú)論是在提高搜索速度方面還是在控制搜索過(guò)程中的信息查詢量都比較好，因此是一種較為理想的搜索算法。

4 結(jié)論

隨著網(wǎng)絡(luò)理論研究的不斷興起，網(wǎng)絡(luò)搜索問(wèn)題正逐漸引起研究人員的注意。在網(wǎng)絡(luò)搜索算法研究中，如何在提高網(wǎng)絡(luò)搜索速度的同時(shí)控制好搜索過(guò)程中所產(chǎn)生的查詢消息，是需要深入研究的問(wèn)題。本文所提出的基于最大度和隨機(jī)游走的搜索算法綜合利用最大度搜索利用鄰居節(jié)點(diǎn)信息充分和隨機(jī)游走快速訪問(wèn)遠(yuǎn)程連接的優(yōu)勢(shì)，在提高了網(wǎng)絡(luò)搜索速度的同時(shí)也較好地控制了信息查詢量，搜索效果比較理想。

[1]MILGRAM S.The small world problem[J].Psychology Today,1967,2∶60-67.

[2]KLEINBERG J.Navigation in a small world[J].Nature,2000,406∶845.

[3]KLEINBERG J.The small-world phenomenon∶an algorithmic perspective[C]//Proceedings of the 32nd Annual ACM Symposium on Theory of Computing.New York,2000∶163-170.

[4]WATTS D J,DODDS P S,NEWMAN M E J.Identity and search in social networks[J].Science,2002,296∶1302-1305.

[5]ADAMIC L A,ADAR E.How to search a social network[J].Social Networks,2005,27(3)∶187-203.

[6]ADAMIC L A,LUKOSE R M,PUNIYANI A R,et al.Search in power-law networks[J].Phys.Rev.E.,2001,64∶046135.

[7]ADAMIC L A,LUKOSE R M,HUBERMAN B A.Local Search in Unstructured Networks[M].In S.Bornholdt and H.G.Schuster (eds.),Handbook of Graphs and Networks,Berliln∶Wiley-VCH,2003.

[8]CLAUSET A,MOORE C.Cond-mat/0309415.How do networks become navigable[K].