復(fù)雜網(wǎng)絡(luò)搜索算法比較研究

阿布力米提·艾西丁

摘要：許多復(fù)雜網(wǎng)絡(luò)中，單個節(jié)點無法充分掌握整個網(wǎng)絡(luò)的全局信息與目標節(jié)點的具體位置。因為復(fù)雜網(wǎng)絡(luò)具有不斷變化的動態(tài)性，準確地確定網(wǎng)絡(luò)的全局行為是非常困難的。一般在搜索算法中，我們從一個給定的源節(jié)點開始查詢所需要的目標節(jié)點上的文件，按照某一種規(guī)則向源節(jié)點的某一個或是多個鄰居節(jié)點發(fā)送查詢消息，尋找符合目標狀態(tài)節(jié)點的過程。搜索算法的有效性將直接影響到復(fù)雜網(wǎng)絡(luò)的卓越性能。目前復(fù)雜搜索策略中有廣度優(yōu)先搜索算法（BFS）、最大度搜索算法（MD）與隨機游走搜索算法（RW）等比較經(jīng)典及常用的算法。除了這三種算法外，其他算法大都是由這三種算法改進而來。本文上述前三種搜索算法的性能進行邏輯分析與比較。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；網(wǎng)絡(luò)模型；網(wǎng)絡(luò)特性

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2017）04-0169-02

許多復(fù)雜網(wǎng)絡(luò)中，單個節(jié)點無法充分掌握整個網(wǎng)絡(luò)的全局信息與目標節(jié)點的具體位置。因為復(fù)雜網(wǎng)絡(luò)具有不斷變化的動態(tài)性，準確地確定網(wǎng)絡(luò)的全局行為是非常困難的。一般在搜索算法中，我們從一個給定的源節(jié)點開始查詢所需要的目標節(jié)點上的文件，按照某一種規(guī)則向源節(jié)點的某一個或是多個鄰居節(jié)點發(fā)送查詢消息，尋找符合目標狀態(tài)節(jié)點的過程。搜索算法的有效性將直接影響到復(fù)雜網(wǎng)絡(luò)的卓越性能。鑒于搜索問題的重要地位和實際價值，人們會從不同的角度對搜索問題進行分析研究。我們在這里提出了一種新的基于冪律度分布的搜索算法DBM，它引用BFS與MD的各種優(yōu)點進行搜索。DBM算法小范圍引用BFS搜索算法，大范圍引用MD搜索算法，更進一步基于知識進行搜索，提高搜索的效率。為了更可靠地分析并解釋，我們選擇無標度（BA）網(wǎng)絡(luò)模型來驗證DBM搜索算法的有效性與可行性。

1 邏輯分析

以下我們將對復(fù)雜網(wǎng)絡(luò)中基本搜索方式廣度優(yōu)先搜索算法（BFS）與最大度搜索算法（MD）進行比較與分析。首先，BFS是一種經(jīng)典的復(fù)雜網(wǎng)絡(luò)基本搜索算法，它在Internet中獲得了比較廣泛的應(yīng)用。事實上，復(fù)雜網(wǎng)絡(luò)中的單個節(jié)點往往難以全面反映整個網(wǎng)絡(luò)的信息，甚至無法明確復(fù)雜網(wǎng)絡(luò)中目標節(jié)點的所在位置。在這種情況下我們可以應(yīng)用的最簡單地搜索策略就是廣度優(yōu)先搜索算法（BFS）。BFS搜索算法的工作原理如下：當(dāng)源節(jié)點開始在復(fù)雜網(wǎng)絡(luò)中尋找目標文件時，S先查詢所有鄰居節(jié)點，并向鄰居階段詢問是否擁有目標文件，假設(shè)S的某個鄰居節(jié)點上發(fā)現(xiàn)目標文件，目標節(jié)點即將目標文件反饋給源節(jié)點；假設(shè)S的鄰居節(jié)點都不擁有目標文件，S的鄰居節(jié)點則將查詢信息向各自的鄰居節(jié)點傳遞查詢信息，直到發(fā)現(xiàn)目標節(jié)點和產(chǎn)訊到目標文件。廣度優(yōu)先搜索算法BFS示例如圖1所示：

在圖中沒有搜索過的路徑用虛線表示，已經(jīng)搜索過的路徑用實線表示。在這里我們根據(jù)最大度算法的搜索思路分析，在最大度搜索（MD）方式中，搜索過程如下：最大搜索策略的應(yīng)用前提為每個節(jié)點都了解其鄰居節(jié)點度。詳細搜索流程為：源節(jié)點先查詢其度最大的鄰居節(jié)點，假設(shè)此鄰居節(jié)點為目標節(jié)點，則將目標文件反饋回源節(jié)點，假設(shè)非目標節(jié)點，則繼續(xù)挑選度最大的鄰居節(jié)點查詢，截止到發(fā)現(xiàn)目標節(jié)點[9]。在這種最大度搜索MD搜索方式中，雖然搜索效率一般，但其產(chǎn)生的搜索消息流量非常小。最大度搜索MD搜索算法過程示例如圖2所示：

通過比較以上兩種搜索方式，我們得到以下結(jié)論：選用廣度優(yōu)先搜索算法，可以得到比較小的搜索步數(shù)，即可以最快捷地搜索到目標節(jié)點，但是查詢消息流量特別多。最大度搜索算法獲得的查詢消息流量比較小的，其搜索步數(shù)介于隨機游走搜索（MD）和廣度優(yōu)先搜索（BFS）之間。隨機游走搜索算法的查找速度最慢，而產(chǎn)生的查詢信息流量在其他兩種搜索策略之間。具體關(guān)系如表1所示：

表1 搜索算法比較

[搜索算法方式＼&搜索步數(shù)＼&查詢消息流量＼&廣度最先搜索（BFS）＼&最小＼&最高＼&最大度搜索（MD）＼&中＼&最?。?amp;]

2 性能分析

2.1 無標度網(wǎng)絡(luò)

我們把Newman的工作可總結(jié)為隨機圖。用[G0（x）]表示節(jié)點度[k]的分布母函數(shù)，[G0（x）]可以表達為：

在這里[pk]表示一個圖里面隨機選定度恰好為[k]的節(jié)點的概率，[m]是度的最大值。根據(jù)母函數(shù)，這里隨機選擇的節(jié)點的平均度可表達為：

為了解決準確測量與采樣中的困難，我們在這里采用無標度網(wǎng)絡(luò)模型。本文中，我們應(yīng)用冪律圖來評估搜索性能，如果冪律分布的隨機圖的度指數(shù)是[τ]，[pk]跟[k-τ]是成正比，那么：

依照（4），可以得出以下近似冪律分布：

2.2 成功率[SR]

成功率[SR]是查詢成功完成的概率，在這里至少有一個查詢工作成功地完成。假設(shè)查詢源用復(fù)制比[R]統(tǒng)一分配到整個網(wǎng)絡(luò)，[SR]在這里[R]是復(fù)制比，[C]是覆蓋率，這公式說明[SR]是依靠搜索算法的覆蓋率。我們使用（8）獲得的一個非常重要的性能指標是搜索時間[ST]。

2.3 搜索有效性[SE]

搜索有效性[SE]是搜索算法中提出的一個統(tǒng)一的性能指標，[SE]可以定義為：在這里[QH（h）]是在第[h]跳的查詢命中率，[QM]是查詢過程中產(chǎn)生的查詢消息總數(shù)量，[SR]是成功查詢的概率，比如在這里至少有一個查詢命中，[R]是查詢對象的復(fù)制比。當(dāng)然如果考慮成功率[SR]時，假設(shè)查詢對象統(tǒng)一地分布在整個網(wǎng)絡(luò)。這時第[h]跳的查詢命中率等于第[h]跳的覆蓋率與復(fù)制比[R]的乘積。那么公式（9）可以改寫為如下：

在這里是[Ch]是第[h]跳的覆蓋率，[ek]是第[h]跳時所產(chǎn)生的查詢消息。[R]是復(fù)制比。

在這里我們考慮[SE5]，[SE1]兩種類型，不考慮遠程過來的搜索結(jié)果。比如：

3 結(jié)語

我們從一個給定的源節(jié)點開始查詢所需要的目標節(jié)點上的文件，按照某一種規(guī)則向源節(jié)點的某一個或是多個鄰居節(jié)點發(fā)送查詢消息，尋找符合目標狀態(tài)節(jié)點的過程。搜索算法的有效性將直接影響到復(fù)雜網(wǎng)絡(luò)的卓越性能，本文中主要闡述了本文研究目的；主要解說了本文研究的相關(guān)工作；對復(fù)雜網(wǎng)絡(luò)中典型的幾種搜索算法進行了邏輯分析并比較。

參考文獻：

[1] D. Stutzbach， R. Rejaie， N. Duffield， S. Sen， and W. Willinger， Sampling Techniques for Large， Dynamic Graphs[D]. NinthIEEE Global Internet Symp， 2006.

[2] A.H. Rasti， D. Stutzbach， R. Rejaie. On the Long-TermEvolution of the Two-Tier Gnutella Overlay[D]. Ninth IEEEGlobal Internet Symp， 2006.

[3] 吳兆福， 董文永. P2P網(wǎng)絡(luò)搜索技術(shù)研究[J]. 武漢理工大學(xué)學(xué)報（信息與管理工程版）， 2007（6）.