阿布力米提·艾西丁

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

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

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）04-0169-02

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

1 邏輯分析

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

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

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

表1 搜索算法比較

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

2 性能分析

2.1 無(wú)標(biāo)度網(wǎng)絡(luò)

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

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

為了解決準(zhǔn)確測(cè)量與采樣中的困難，我們?cè)谶@里采用無(wú)標(biāo)度網(wǎng)絡(luò)模型。本文中，我們應(yīng)用冪律圖來(lái)評(píng)估搜索性能，如果冪律分布的隨機(jī)圖的度指數(shù)是[τ]，[pk]跟[k-τ]是成正比，那么：

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

2.2 成功率[SR]

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

2.3 搜索有效性[SE]

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

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

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

3 結(jié)語(yǔ)

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

參考文獻(xiàn)：

[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é)報(bào)（信息與管理工程版）， 2007（6）.