一種基于BBV 網(wǎng)絡(luò)的局部搜索策略

曾 成

(貴州省網(wǎng)絡(luò)信息安全技術(shù)維護(hù)管理中心,貴州 貴陽(yáng) 550001)

0 引言

在很長(zhǎng)一段時(shí)間里, 搜索問(wèn)題是復(fù)雜網(wǎng)絡(luò)中比較熱門(mén)的一個(gè)研究課題,大部分學(xué)者將主要研究放在了無(wú)權(quán)網(wǎng)絡(luò)上,也就是將現(xiàn)實(shí)中的網(wǎng)絡(luò)抽象化,接著再將其弱化為布爾網(wǎng)絡(luò)來(lái)研究[1-4]。 大量實(shí)驗(yàn)結(jié)果證明了網(wǎng)絡(luò)節(jié)點(diǎn)之間連接關(guān)系的緊密程度是不一樣的,并不全都是布爾關(guān)系,人們把這類(lèi)網(wǎng)絡(luò)稱為加權(quán)網(wǎng)絡(luò)[5]。由此可知,研究加權(quán)網(wǎng)絡(luò)中高效的搜索方法已變得很有意義,能將復(fù)雜網(wǎng)絡(luò)的搜索問(wèn)題具體地描述成信息之間的傳遞過(guò)程。 常用的局部搜索策略有:隨機(jī)游走(Rand Walk,RW)策略和最大度搜索(High Degree Seeking,DS)策略[6]。 2005 年,Thadakamalla 等[7]提出一種適用于加權(quán)網(wǎng)絡(luò)的搜索算法,他們?cè)诰哂袃缏煞植嫉募訖?quán)網(wǎng)絡(luò)中使用一種利用局部介數(shù)(Local Betweenness Centrality,LBC)的分步式算法,并得到了很好的效果。 Yan 等[8]提出的利用加權(quán)網(wǎng)絡(luò)搜索算法。 在具有冪律分布的網(wǎng)絡(luò)中,最大局部介數(shù)搜索策略在搜索時(shí)間和搜索代價(jià)這一系列參數(shù)上要明顯優(yōu)于RW 策略和DS 策略。 以上的搜索算法雖然效率很高,但忽視了邊權(quán)值[9]大小對(duì)節(jié)點(diǎn)搜索信息量的影響,所以在同時(shí)考慮邊權(quán)值和節(jié)點(diǎn)聚類(lèi)系數(shù)及復(fù)雜網(wǎng)絡(luò)聚類(lèi)與局部搜索[10]的基礎(chǔ)上,結(jié)合了BBV 網(wǎng)絡(luò)[11]的特性,本文提出一種結(jié)合節(jié)點(diǎn)聚類(lèi)系數(shù)和邊權(quán)值大小的搜索算法,即最小聚類(lèi)系數(shù)最小距離(Minimum Clustering Coefficient and Distance,MCD)搜索算法。

1 理論分析

BBV 網(wǎng)絡(luò)與其他網(wǎng)絡(luò)存在較大差異性,當(dāng)路線選擇不理想時(shí),會(huì)增添很多不必要的損耗。 與此同時(shí),在BBV 網(wǎng)絡(luò)中存在一種hub 的節(jié)點(diǎn),這種hub 節(jié)點(diǎn)有著密集的節(jié)點(diǎn)結(jié)構(gòu)。 它雖然不會(huì)產(chǎn)生數(shù)據(jù)包,但有著強(qiáng)大的數(shù)據(jù)包轉(zhuǎn)發(fā)能力,能讓數(shù)據(jù)包縮短找到目標(biāo)節(jié)點(diǎn)的時(shí)間。 所以hub 節(jié)點(diǎn)附近的網(wǎng)絡(luò)線路會(huì)比較復(fù)雜、搜索信息量大,則相對(duì)于其他網(wǎng)絡(luò)更容易形成堵塞[12]。

和無(wú)權(quán)網(wǎng)絡(luò)不同的是,加權(quán)網(wǎng)絡(luò)在一定程度上可以表現(xiàn)出節(jié)點(diǎn)之間關(guān)聯(lián)程度的不同。 在搜索進(jìn)行時(shí),這種關(guān)聯(lián)程度的不同會(huì)直接影響到鄰居節(jié)點(diǎn)的選擇。用選擇因子Cij來(lái)表示這種影響(其中Cij是節(jié)點(diǎn)i和j之間的邊lij對(duì)應(yīng)的): 下一個(gè)節(jié)點(diǎn)被選中的概率與Cij有關(guān),Cij的值越大選中概率就越大。 然而,在加權(quán)網(wǎng)絡(luò)中,權(quán)值的具體表示決定了Cij怎么計(jì)算。

最短路徑在網(wǎng)絡(luò)中是節(jié)點(diǎn)與節(jié)點(diǎn)聯(lián)系最緊密的路徑,且搜索代價(jià)也是最小的路徑。 在加權(quán)網(wǎng)絡(luò)里,在選擇下一節(jié)點(diǎn)的時(shí)候,其選擇概率與選擇因子是成正比的。 這種情況下邊lij(選擇因子為Cij)下一步選擇節(jié)點(diǎn)的概率定義為:

其中,N(i) 為節(jié)點(diǎn)i附近所有相鄰節(jié)點(diǎn)的集合,p為上一步走過(guò)的節(jié)點(diǎn),Csum(i) 是節(jié)點(diǎn)i對(duì)相鄰各邊計(jì)算選擇因子Cij后進(jìn)行的求和。 此時(shí),節(jié)點(diǎn)i的搜索信息值則可以定義為:

BBV 網(wǎng)絡(luò)模型中每個(gè)節(jié)點(diǎn)之間的流量是用權(quán)值來(lái)表示的,如果節(jié)點(diǎn)之間流量過(guò)大,那么搜索的難度也會(huì)隨之增加,由于以上原因,選擇因子與權(quán)值成反比,則由Cij=。 可以看出,如果加權(quán)網(wǎng)絡(luò)中路徑越短,那么流量就越小,道路就越暢通。

鄰近節(jié)點(diǎn)之間的集團(tuán)性質(zhì)是由該節(jié)點(diǎn)的聚類(lèi)系數(shù)體現(xiàn)出來(lái)的,如果各個(gè)節(jié)點(diǎn)聯(lián)系越緊湊,那么該頂點(diǎn)的聚類(lèi)系數(shù)就會(huì)越高。 加權(quán)網(wǎng)絡(luò)集聚系數(shù)[13]是由Barrat和他的團(tuán)隊(duì),根據(jù)無(wú)權(quán)網(wǎng)絡(luò)集聚系數(shù)的基礎(chǔ)上被定義的,加權(quán)網(wǎng)絡(luò)集聚系數(shù)為:

由以上信息,并結(jié)合聚類(lèi)系數(shù)與搜索信息,如果想要很快地找尋目標(biāo)節(jié)點(diǎn),只需要在搜索時(shí)把信息送達(dá)流量比較小、聚類(lèi)系數(shù)比較小的鄰居節(jié)點(diǎn)即可。

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

根據(jù)影響搜索算法的權(quán)值、借點(diǎn)聚類(lèi)系數(shù)和BBV網(wǎng)絡(luò)的特點(diǎn),提出了一種結(jié)合節(jié)點(diǎn)聚類(lèi)系數(shù)與邊權(quán)值的搜索算法。 為達(dá)到動(dòng)態(tài)規(guī)劃中的最優(yōu)搜索路徑算法的想法,只能在搜索過(guò)程中的每一步達(dá)到局部最優(yōu)。在包含節(jié)點(diǎn)的聚類(lèi)系數(shù)和其相連的邊的權(quán)值情況下,假定網(wǎng)絡(luò)中有且只有自己的鄰居節(jié)點(diǎn)信息,MCD 搜索算法如下。

(1)初始階段先任意選擇一對(duì)源節(jié)點(diǎn)s和目標(biāo)節(jié)點(diǎn),且將源節(jié)點(diǎn)s賦上值給s0。

(2)節(jié)點(diǎn)s0在選擇下一個(gè)相鄰節(jié)點(diǎn)時(shí)確認(rèn)是否有目標(biāo)節(jié)點(diǎn)t;如果存在,則搜索結(jié)束;否則轉(zhuǎn)第3 步。

(3)s0確認(rèn)相鄰節(jié)點(diǎn)中是否存在節(jié)點(diǎn)d1(d1∈M)。 如果有此節(jié)點(diǎn),則把攜帶的信息傳遞給d1,然后把d1的值賦給節(jié)點(diǎn)s0;否則根據(jù)第2 種規(guī)則進(jìn)行選擇。

(4)重復(fù)2 和3 的步驟,直到找到目標(biāo)節(jié)點(diǎn)t為止。 當(dāng)?處于在0 ≤?≤1 時(shí),節(jié)點(diǎn)的聚類(lèi)系數(shù)和邊權(quán)值都相對(duì)較小的點(diǎn)才是要找的節(jié)點(diǎn)。

3 仿真實(shí)驗(yàn)

圖1 搜索代價(jià)與網(wǎng)絡(luò)規(guī)模的關(guān)系

由上圖可知,在BBV 網(wǎng)絡(luò)中,LBC 搜索策略與DS搜索策略明顯劣于MCD 搜索策略。 MCD 搜索算法有效地結(jié)合了LBC 搜索策略的優(yōu)勢(shì),并融合了節(jié)點(diǎn)聚類(lèi)系數(shù)及邊權(quán)值對(duì)網(wǎng)絡(luò)的影響,提高搜索效率。 在局部信息的搜索代價(jià)上,MCD 搜索算法也優(yōu)于LBC 搜索策略。 可得出結(jié)論,在加權(quán)非均勻網(wǎng)絡(luò)中,要利用邊權(quán)值的搜索算法才能更高效地提高搜索效率。

仿真2,該實(shí)驗(yàn)對(duì)比3 種搜索策略的搜索時(shí)間(在不同網(wǎng)絡(luò)規(guī)模中)。 在仿真中,搜索時(shí)間用搜索步數(shù)替換,假定每一步的耗時(shí)都相同(t),搜索時(shí)間T=step×t(步數(shù)用step 表示)。 BBV 模型利用r=2 來(lái)模擬網(wǎng)絡(luò),實(shí)驗(yàn)結(jié)果如圖2 所示。

由圖2 可以看出,網(wǎng)絡(luò)中LBC 和 MCD 搜索時(shí)間明顯要優(yōu)于DS 所用時(shí)間。 MCD 搜索策略BBV 網(wǎng)絡(luò)的特點(diǎn),很大程度上運(yùn)用了hub 節(jié)點(diǎn)的高鏈路負(fù)載的特點(diǎn),由于BBV 網(wǎng)絡(luò)服從冪率分布,各邊的權(quán)值分布不均等,這樣就高效率地避免了網(wǎng)絡(luò)擁塞,減少了搜索時(shí)間和搜索步數(shù)。

圖2 搜索時(shí)間與網(wǎng)絡(luò)規(guī)模的關(guān)系

從圖3 可以發(fā)現(xiàn),?值取極大和極小,對(duì)應(yīng)的搜索時(shí)間都偏大。 因此,在MCD 搜索算法中,MCD 搜索策略的搜索時(shí)間隨著?值的增大或減小而逐漸增大,且在?值取中間值的時(shí)候搜索時(shí)間最小。 因此,參數(shù)?的選擇相當(dāng)關(guān)鍵,算法中聚類(lèi)系數(shù)和邊權(quán)值都會(huì)由于此參數(shù)的變化而變化。

圖3 不同?值時(shí)的搜索時(shí)間

4 結(jié)語(yǔ)

本文在BBV 網(wǎng)絡(luò)性質(zhì)的基礎(chǔ)上提出了MCD 搜索算法,此算法綜合了聚類(lèi)系數(shù)和邊權(quán)值這兩個(gè)加權(quán)網(wǎng)絡(luò)中重要的參數(shù)對(duì)搜索效率的影響,在搜索時(shí)間和搜索代價(jià)上都要強(qiáng)于DS 算法和LBC 算法,且MCD 算法在尋找下一節(jié)點(diǎn)時(shí)所需要的局部信息量也要小于LBC算法。 因此,在BBV 網(wǎng)絡(luò)中,邊權(quán)值的大小對(duì)于節(jié)點(diǎn)的搜索效率有著很大的影響,結(jié)合節(jié)點(diǎn)聚類(lèi)系數(shù)和邊權(quán)值的搜索策略的效率相對(duì)較高。 本文對(duì)于生成的BBV網(wǎng)絡(luò)的邊權(quán)沒(méi)有采取任何限制,考慮到在現(xiàn)實(shí)的網(wǎng)絡(luò)里,邊權(quán)重不可能無(wú)休止地增加,所以將來(lái)會(huì)在考慮節(jié)點(diǎn)強(qiáng)度的基礎(chǔ)上重點(diǎn)考慮網(wǎng)絡(luò)中邊權(quán)重的限制,使BBV 網(wǎng)絡(luò)模型更加接近真實(shí)世界,符合真實(shí)網(wǎng)絡(luò)的特點(diǎn)。