基于最大度和隨機游走的混合搜索算法

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

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

0 引言

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

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

1 幾種常見搜索算法

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

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

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

1.2 隨機游走搜索算法

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

1.3 最大度搜索算法

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

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

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

2.1 基本思想

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

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

2.2 算法設計

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

1）構造集合E，用于存放已訪問的節(jié)點，k=1。

2）判斷源節(jié)點s是否為目標節(jié)點g。若是，則目標節(jié)點找到，停止搜索；否則，進入轉步驟3）。

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

4）判斷此節(jié)點的鄰居節(jié)點中是否有g。若有，則目標節(jié)點找到，搜索結束，否則轉步驟5）。

5）對于第k+1步，在第k步訪問節(jié)點的鄰居節(jié)點中隨機選擇一個尚未訪問的節(jié)點作為訪問節(jié)點。

6）判斷此節(jié)點的鄰居節(jié)點中是否有g。若有，則目標節(jié)點找到，搜索結束，否則轉步驟7）。

7）重復步驟3）～6），直至目標節(jié)點g 被找到。搜索結束。

3 搜索效率仿真

3.1 搜索效率

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

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

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

3.2 仿真方法

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

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

3.3 仿真結果與分析

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

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

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

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

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

4 結論

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

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