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

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

0 引言

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

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

1 幾種常見搜索算法

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

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

廣度優(yōu)先搜索算法（breadth-first search，BFS）的基本思想是：從源節(jié)點(diǎn)s 開始，首先查詢其所有的鄰居節(jié)點(diǎn)，詢問是否含有目標(biāo)節(jié)點(diǎn)g，如果s的鄰居中有節(jié)點(diǎn)含有了此目標(biāo)節(jié)點(diǎn)，則將目標(biāo)節(jié)點(diǎn)返回給源節(jié)點(diǎn)；如果沒有鄰居含有目標(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ò)大，將會在網(wǎng)絡(luò)中產(chǎn)生大量查詢消息流量，造成網(wǎng)絡(luò)流量急劇增加從而導(dǎo)致網(wǎng)絡(luò)擁塞。

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

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

1.3 最大度搜索算法

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

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

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

2.1 基本思想

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

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

2.2 算法設(shè)計

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

1）構(gòu)造集合E，用于存放已訪問的節(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）計算當(dāng)前訪問節(jié)點(diǎn)所有鄰居節(jié)點(diǎn)尚未訪問節(jié)點(diǎn)的度，選擇其中度最大的節(jié)點(diǎn)作為下一步訪問節(jié)點(diǎn)，k=k+1；如果這樣的鄰居節(jié)點(diǎn)不止一個，則在它們中隨機(jī)選擇一個節(jié)點(diǎn)作為訪問節(jié)點(diǎn)；如果所有的節(jié)點(diǎn)都已經(jīng)訪問過，則返回到上一步所訪問的節(jié)點(diǎn)。

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

5）對于第k+1步，在第k步訪問節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中隨機(jī)選擇一個尚未訪問的節(jié)點(diǎ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)，因此本文在評價搜索效率時也將主要考察算法在這兩方面的性能。算法的搜索速度由算法在搜索時需訪問的步數(shù)決定。在一個節(jié)點(diǎn)數(shù)為N的網(wǎng)絡(luò)中，當(dāng)采用某種搜索算法時，則從這N個節(jié)點(diǎn)中隨機(jī)選擇出n個不同的源節(jié)點(diǎn)，然后對于每一個選擇的源節(jié)點(diǎn)i，運(yùn)用此搜索算法搜索源節(jié)點(diǎn)i到節(jié)點(diǎn)j的搜索步數(shù)tij(i≠j)。則源節(jié)點(diǎn)i到其他所有N?1個節(jié)點(diǎn)所需的搜索步數(shù)Ti為

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

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

3.2 仿真方法

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

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

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

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

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

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

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

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

4 結(jié)論

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

[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].