瀘州醫(yī)學(xué)院現(xiàn)代教育技術(shù)中心 李 瑾

1.引言

P2P是英文Peer-to-Peer(對(duì)等)的簡(jiǎn)稱，又被稱為“點(diǎn)對(duì)點(diǎn)”?！皩?duì)等”技術(shù)，是一種網(wǎng)絡(luò)新技術(shù)。在P2P網(wǎng)絡(luò)中計(jì)算機(jī)以對(duì)等的身份進(jìn)行連接，既是服務(wù)器又是客戶機(jī)。P2P系統(tǒng)的數(shù)據(jù)資源分布于各個(gè)節(jié)點(diǎn)中，資源共享必須通過(guò)檢索才能獲得。因此P2P資源檢索成了P2P技術(shù)研究最活躍的領(lǐng)域之一。

P2P資源檢索機(jī)制可分為非結(jié)構(gòu)化和結(jié)構(gòu)化兩大類。非結(jié)構(gòu)化P2P系統(tǒng)采用泛洪法和隨機(jī)漫步機(jī)制，容易造成網(wǎng)絡(luò)流量增大，導(dǎo)致網(wǎng)絡(luò)擁塞，而結(jié)構(gòu)化P2P系統(tǒng)是采用分布式哈希表方式構(gòu)造覆蓋網(wǎng)的方式，可以保證搜索結(jié)果的質(zhì)量，也可以控制消息數(shù)量，可擴(kuò)展性好、自適應(yīng)性強(qiáng)。但是它也存在著一個(gè)缺點(diǎn)：它是基于單關(guān)鍵字搜索的，通常給定一個(gè)搜索關(guān)鍵字，系統(tǒng)通過(guò)哈希計(jì)算將關(guān)鍵字轉(zhuǎn)換成標(biāo)識(shí)符，再通過(guò)DHT算法進(jìn)行搜索。而實(shí)際上，在很多情況下，人們并不能準(zhǔn)確描述所要搜索的目標(biāo)，而只能給出搜索目標(biāo)的大致特征描述，并且通過(guò)哈希計(jì)算很相近的詞，在實(shí)際意義上相差很遠(yuǎn)。為了提高P2P資源檢索的查全率和查準(zhǔn)率，本文在結(jié)構(gòu)化P2P系統(tǒng)的基礎(chǔ)上提出一種基于二部圖的P2P資源挖掘方法，挖掘關(guān)鍵字與資源的潛在關(guān)系。首先根據(jù)用戶的檢索和下載行為收集關(guān)鍵字與資源的關(guān)系對(duì)，然后利用二部圖的資源社區(qū)發(fā)現(xiàn)算法發(fā)現(xiàn)關(guān)鍵字與資源關(guān)系網(wǎng)的網(wǎng)絡(luò)社區(qū)，由此可以挖掘出更多的關(guān)鍵詞與資源的關(guān)系。

2.關(guān)鍵字與資源關(guān)系采集

分析P2P網(wǎng)絡(luò)中的海量的檢索和下載行為采集關(guān)鍵字和資源的對(duì)應(yīng)關(guān)系，及兩者的相關(guān)度，相關(guān)度表示根據(jù)某個(gè)關(guān)鍵字下載某個(gè)資源的次數(shù)。關(guān)鍵字和資源的對(duì)應(yīng)關(guān)系保存在虛擬空間MetaSpace中。MetaSpace建立在基于分布式哈希表DHT的結(jié)構(gòu)化P2P網(wǎng)絡(luò)之上的。系統(tǒng)開(kāi)始運(yùn)行時(shí)，MetaSpace不包含任何數(shù)據(jù)，結(jié)點(diǎn)提交的檢索請(qǐng)求全部由底層系統(tǒng)原有的檢索機(jī)制完成。在系統(tǒng)的運(yùn)行過(guò)程中，每個(gè)結(jié)點(diǎn)將本地結(jié)點(diǎn)的檢索和下載行為記錄到一個(gè)緩沖區(qū)中，經(jīng)過(guò)一段時(shí)間后，對(duì)這些行為進(jìn)行批量分析，生成關(guān)鍵字和資源的對(duì)應(yīng)關(guān)系，僅保留相關(guān)度較大的＜k，r>關(guān)系對(duì)在metaspace中。

3.關(guān)鍵字與資源關(guān)系的圖形表示

將關(guān)鍵字與資源的關(guān)系轉(zhuǎn)化為圖形。

定義4(k-r圖)k-r圖是利用MetaSpace中的二元組＜k，r>，建立關(guān)鍵字與資源節(jié)點(diǎn)的關(guān)系圖，即無(wú)向圖G=＜V，E>，V=K∪R，K∩R=Φ，(K是關(guān)鍵字節(jié)點(diǎn)集合，R是資源節(jié)點(diǎn)集合)，使得任何一條邊的兩個(gè)端點(diǎn)分別在K和R中。

下面舉例說(shuō)明，假設(shè)有如下關(guān)鍵字與資源的關(guān)系對(duì)。

＜k1，r1>，＜k1，r2>，＜k1，r3>，＜k2，r1>，＜k2，r3>，＜k3，r3>，＜k3，r4>，＜k3，r5>，＜k4，r4>，＜k4，r5>，＜k4，r7>，＜k5，r4>，＜k5，r5>，＜k5，r6>，＜k5，r7>

根據(jù)這些二元組可以建立k-r圖，如圖1所示。

定義5(二部圖)一個(gè)二部圖BG(T，I)是一個(gè)圖，其節(jié)點(diǎn)可以分成兩個(gè)非空的集合T和I，使得任何一條邊的兩個(gè)端點(diǎn)分別在T，I中。

根據(jù)k-r圖的定義，k-r圖有兩個(gè)非空集合K和R，K是關(guān)鍵詞節(jié)點(diǎn)集合，R是資源節(jié)點(diǎn)集合，任何一條邊的兩個(gè)端點(diǎn)分別在K和R中。k-r圖的定義符合二部圖的定義。所以，k-r圖是一個(gè)二部圖。

4.基于二部圖的社區(qū)發(fā)現(xiàn)算法

4.1 相關(guān)定義

定義6（k-r二部圖社區(qū)結(jié)構(gòu)）k-r二部圖中，若干個(gè)關(guān)鍵字和資源節(jié)點(diǎn)構(gòu)成社區(qū)，同一個(gè)社區(qū)中的節(jié)點(diǎn)間連線較多，不同社區(qū)之間連線較少。

定義7（完全二部圖）完全二部圖CBG（K，R，|K|，|R|）是一個(gè)二部圖BG（K，R），其中K中的每一個(gè)節(jié)點(diǎn)都有有向邊指向R中的每一個(gè)節(jié)點(diǎn)，|K|指K集合中元素的個(gè)數(shù)，|R|指R集合中元素的個(gè)數(shù)。

4.2 算法思想

二部圖的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)方法思想是：由于完全二部圖的連線緊密，因此通過(guò)尋找完全二部圖的方法來(lái)尋找社區(qū)。k-r圖中一類是關(guān)鍵字節(jié)點(diǎn)，一類是資源節(jié)點(diǎn)，設(shè)兩個(gè)關(guān)鍵字ki和kj，它們指向的相同資源越多，則ki和kj聯(lián)系越緊密，則與ki關(guān)聯(lián)的所有資源也很可能與kj相關(guān)。按照這個(gè)原則，因此尋找一個(gè)完全二部圖的時(shí)候?qū)Y源節(jié)點(diǎn)的個(gè)數(shù)有要求，對(duì)關(guān)鍵字節(jié)點(diǎn)個(gè)數(shù)無(wú)要求。

首先，將每個(gè)關(guān)鍵字節(jié)點(diǎn)與其對(duì)應(yīng)的資源節(jié)點(diǎn)構(gòu)成一個(gè)完全二部圖，然后通過(guò)合并生成滿足條件的更大的完全二部圖，最后將一個(gè)完全二部圖中關(guān)鍵字節(jié)點(diǎn)與其相連的所有資源節(jié)點(diǎn)構(gòu)成一個(gè)社區(qū)。

4.3 算法描述和分析

算法2 二部圖社區(qū)發(fā)現(xiàn)算法

輸入：二部圖BG（K，R，|K|，|R|），|K|、|R|表示節(jié)點(diǎn)個(gè)數(shù)

輸出：n個(gè)更大的完全二部圖CBG（Ki，Ri，|Ki|，|Ri|）

1)輸入?yún)?shù)p，q；

2)每個(gè)關(guān)鍵字節(jié)點(diǎn)ki與其對(duì)應(yīng)的資源節(jié)點(diǎn)構(gòu)成一個(gè)完全二部圖CBG（{ki}，Ri，1，|Ri|）；

3)S←{C B G（{ki}，Ri，1，|Ri|）}；

4)T←Φ；

5)core←Φ；

6)w=p；

7)While(S≠Φand w>q)

8){//尋找資源節(jié)點(diǎn)為w的二部圖，選取S中的部分元素，選取原則為：如果二部圖BG（K，R）中K集的一個(gè)關(guān)鍵字節(jié)點(diǎn)對(duì)應(yīng)的資源節(jié)點(diǎn)數(shù)小于w，則這些節(jié)點(diǎn)必然不包含在任何一個(gè)完全二部圖CBG（Ki，Ri，|Ki|，w）中，其中Ki∈K，Ri∈R。

9)for(i=1；i＜=m；i++)//假設(shè)S中的關(guān)鍵字節(jié)點(diǎn)數(shù)為m

10){

11)對(duì)于CBG（{ki}，R，1，|Ri|）

12)if(|Ri|>=w)

13)T=T∪CBG（{ki}，Ri，1，|Ri|）；

14)}

15)While(T≠Φ)

16){

17)? CBG（{ki}，Ri，1，|Ri|）∈T

18)core=CBG（{ki}，Ri，1，|Ri|）

19)for(j=1；j＜=m；j++)//假設(shè)T中任選一個(gè)元素后剩余m個(gè)元素。

20){

21)對(duì)于CBG（{kj}，Rj，1，|Rj|）∈T

22)? CBG（{kt}，Rt，1，|Rt|）∈core

23)if（|Rj∩Rt|>w）

24)core=core∪CBG（{ki}，Ri，1，|Ri|）

25)}

26)將core中的關(guān)鍵字節(jié)點(diǎn)與其對(duì)應(yīng)的所有資源節(jié)點(diǎn)構(gòu)成一個(gè)社區(qū)。

27)S=S-core；28)}

29)w=w-1；

30)}

5.擴(kuò)展關(guān)鍵字與資源關(guān)系對(duì)

由上節(jié)可知，k-r圖已被分為若干個(gè)社區(qū)，每個(gè)社區(qū)中的節(jié)點(diǎn)聯(lián)系緊密，假設(shè)其中一個(gè)社區(qū)為二部圖BG（K，R），將K中每一個(gè)元素分別與R中的每一個(gè)元素建立連接，輸出＜k，r>。

6.仿真實(shí)驗(yàn)與結(jié)果分析

6.1 實(shí)驗(yàn)?zāi)康呐c方案

本仿真實(shí)驗(yàn)的目的在于驗(yàn)證本文中所提出的資源挖掘算法的可行性及有效性。

本文設(shè)計(jì)了以下的實(shí)驗(yàn)方案：

（1）采用Maz系統(tǒng)中的檢索下載日志，生成＜k.r>關(guān)系對(duì)；

（2）構(gòu)建k-r二部圖，再進(jìn)行社區(qū)發(fā)現(xiàn)，用不同的參數(shù)進(jìn)行測(cè)試，得出不同的社區(qū)個(gè)數(shù)，和擴(kuò)展的關(guān)鍵字與資源關(guān)系對(duì)個(gè)數(shù)；

6.2 仿真實(shí)驗(yàn)的實(shí)現(xiàn)

本仿真實(shí)驗(yàn)采用Matlab7.0作為編程工具，模擬實(shí)現(xiàn)本文的資源挖掘算法，并在WinXP操作系統(tǒng)下運(yùn)行成功。

（1）取關(guān)鍵字節(jié)點(diǎn)個(gè)數(shù)為500，資源節(jié)點(diǎn)個(gè)數(shù)取值從150到1500以50為間隔遞增，進(jìn)行測(cè)試，得出的結(jié)果如圖2、圖3所示?？梢钥闯霎?dāng)關(guān)鍵字節(jié)點(diǎn)個(gè)數(shù)一定時(shí)，隨著資源節(jié)點(diǎn)個(gè)數(shù)的增加，發(fā)現(xiàn)的資源社區(qū)的個(gè)數(shù)變化不大，而擴(kuò)展的關(guān)鍵字與資源關(guān)系對(duì)的個(gè)數(shù)呈上升趨勢(shì)。

（2）取資源節(jié)點(diǎn)個(gè)數(shù)為500，關(guān)鍵字節(jié)點(diǎn)的個(gè)數(shù)取值從150到1500，以50為間隔遞增，進(jìn)行測(cè)試，得出結(jié)果如圖4、圖5所示?？梢钥闯觯?dāng)資源節(jié)點(diǎn)個(gè)數(shù)一定時(shí)，隨著關(guān)鍵字節(jié)點(diǎn)個(gè)數(shù)的增加，發(fā)現(xiàn)的資源社區(qū)的個(gè)數(shù)逐漸增大，擴(kuò)展的關(guān)鍵字與資源關(guān)系對(duì)上升到一定數(shù)量后基本平衡。

從以上實(shí)驗(yàn)結(jié)果直觀地表明，本方法有效的擴(kuò)展了關(guān)鍵字與資源的關(guān)系對(duì)，挖掘出關(guān)鍵字與資源的深層關(guān)系。

7.結(jié)束語(yǔ)

為了提高P2P資源檢索的查全率與查準(zhǔn)率，本文提出了基于二部圖的P2P資源挖掘方法。通過(guò)分析用戶的檢索和下載行為收集關(guān)鍵字與資源的關(guān)系對(duì)，然后利用二部圖的資源社區(qū)發(fā)現(xiàn)算法發(fā)現(xiàn)關(guān)鍵字與資源關(guān)系網(wǎng)的網(wǎng)絡(luò)社區(qū)，由此挖掘出更多的關(guān)鍵詞與資源的潛在關(guān)系。

[1]DELANEY B.The power of P2P[J].JEEE Multimedia,2001,8(4):100-103.

[2]KUNWADEE SRIPANIDKULCHAI,BRUCE M MAGGS,HUI ZHANG.Ef fi cient content location using interest-based locality in peer-to-peer systems[C].Proc.IEEE INFOCOM.2009,:134-146.

[3]邱志歡,肖明忠,代亞非.一種P2P環(huán)境下基于用戶行為的語(yǔ)義檢索方案[J].軟件學(xué)報(bào),2007,18(9):2216-2225.

[4]沈華偉,程學(xué)旗,陳海強(qiáng),劉悅.基于信息瓶頸的社區(qū)發(fā)現(xiàn)[J].計(jì)算機(jī)科學(xué),2008,(04).