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

1.引言

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

P2P資源檢索機制可分為非結(jié)構(gòu)化和結(jié)構(gòu)化兩大類。非結(jié)構(gòu)化P2P系統(tǒng)采用泛洪法和隨機漫步機制，容易造成網(wǎng)絡(luò)流量增大，導(dǎo)致網(wǎng)絡(luò)擁塞，而結(jié)構(gòu)化P2P系統(tǒng)是采用分布式哈希表方式構(gòu)造覆蓋網(wǎng)的方式，可以保證搜索結(jié)果的質(zhì)量，也可以控制消息數(shù)量，可擴展性好、自適應(yīng)性強。但是它也存在著一個缺點：它是基于單關(guān)鍵字搜索的，通常給定一個搜索關(guān)鍵字，系統(tǒng)通過哈希計算將關(guān)鍵字轉(zhuǎn)換成標識符，再通過DHT算法進行搜索。而實際上，在很多情況下，人們并不能準確描述所要搜索的目標，而只能給出搜索目標的大致特征描述，并且通過哈希計算很相近的詞，在實際意義上相差很遠。為了提高P2P資源檢索的查全率和查準率，本文在結(jié)構(gòu)化P2P系統(tǒng)的基礎(chǔ)上提出一種基于二部圖的P2P資源挖掘方法，挖掘關(guān)鍵字與資源的潛在關(guān)系。首先根據(jù)用戶的檢索和下載行為收集關(guān)鍵字與資源的關(guān)系對，然后利用二部圖的資源社區(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)鍵字和資源的對應(yīng)關(guān)系，及兩者的相關(guān)度，相關(guān)度表示根據(jù)某個關(guān)鍵字下載某個資源的次數(shù)。關(guān)鍵字和資源的對應(yīng)關(guān)系保存在虛擬空間MetaSpace中。MetaSpace建立在基于分布式哈希表DHT的結(jié)構(gòu)化P2P網(wǎng)絡(luò)之上的。系統(tǒng)開始運行時，MetaSpace不包含任何數(shù)據(jù)，結(jié)點提交的檢索請求全部由底層系統(tǒng)原有的檢索機制完成。在系統(tǒng)的運行過程中，每個結(jié)點將本地結(jié)點的檢索和下載行為記錄到一個緩沖區(qū)中，經(jīng)過一段時間后，對這些行為進行批量分析，生成關(guān)鍵字和資源的對應(yīng)關(guān)系，僅保留相關(guān)度較大的＜k，r>關(guān)系對在metaspace中。

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

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

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

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

＜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(二部圖)一個二部圖BG(T，I)是一個圖，其節(jié)點可以分成兩個非空的集合T和I，使得任何一條邊的兩個端點分別在T，I中。

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

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

4.1 相關(guān)定義

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

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

4.2 算法思想

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

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

4.3 算法描述和分析

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

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

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

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

2)每個關(guān)鍵字節(jié)點ki與其對應(yīng)的資源節(jié)點構(gòu)成一個完全二部圖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é)點為w的二部圖，選取S中的部分元素，選取原則為：如果二部圖BG（K，R）中K集的一個關(guān)鍵字節(jié)點對應(yīng)的資源節(jié)點數(shù)小于w，則這些節(jié)點必然不包含在任何一個完全二部圖CBG（Ki，Ri，|Ki|，w）中，其中Ki∈K，Ri∈R。

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

10){

11)對于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中任選一個元素后剩余m個元素。

20){

21)對于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é)點與其對應(yīng)的所有資源節(jié)點構(gòu)成一個社區(qū)。

27)S=S-core；28)}

29)w=w-1；

30)}

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

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

6.仿真實驗與結(jié)果分析

6.1 實驗?zāi)康呐c方案

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

本文設(shè)計了以下的實驗方案：

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

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

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

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

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

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

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

7.結(jié)束語

為了提高P2P資源檢索的查全率與查準率，本文提出了基于二部圖的P2P資源挖掘方法。通過分析用戶的檢索和下載行為收集關(guān)鍵字與資源的關(guān)系對，然后利用二部圖的資源社區(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)境下基于用戶行為的語義檢索方案[J].軟件學報,2007,18(9):2216-2225.

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