基于二部圖的P2P資源挖掘方法

瀘州醫學院現代教育技術中心 李 瑾

1.引言

P2P是英文Peer-to-Peer(對等)的簡稱，又被稱為“點對點”。“對等”技術，是一種網絡新技術。在P2P網絡中計算機以對等的身份進行連接，既是服務器又是客戶機。P2P系統的數據資源分布于各個節點中，資源共享必須通過檢索才能獲得。因此P2P資源檢索成了P2P技術研究最活躍的領域之一。

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

2.關鍵字與資源關系采集

分析P2P網絡中的海量的檢索和下載行為采集關鍵字和資源的對應關系，及兩者的相關度，相關度表示根據某個關鍵字下載某個資源的次數。關鍵字和資源的對應關系保存在虛擬空間MetaSpace中。MetaSpace建立在基于分布式哈希表DHT的結構化P2P網絡之上的。系統開始運行時，MetaSpace不包含任何數據，結點提交的檢索請求全部由底層系統原有的檢索機制完成。在系統的運行過程中，每個結點將本地結點的檢索和下載行為記錄到一個緩沖區中，經過一段時間后，對這些行為進行批量分析，生成關鍵字和資源的對應關系，僅保留相關度較大的＜k，r>關系對在metaspace中。

3.關鍵字與資源關系的圖形表示

將關鍵字與資源的關系轉化為圖形。

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

下面舉例說明，假設有如下關鍵字與資源的關系對。

＜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>

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

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

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

4.基于二部圖的社區發現算法

4.1 相關定義

定義6（k-r二部圖社區結構）k-r二部圖中，若干個關鍵字和資源節點構成社區，同一個社區中的節點間連線較多，不同社區之間連線較少。

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

4.2 算法思想

二部圖的社區結構發現方法思想是：由于完全二部圖的連線緊密，因此通過尋找完全二部圖的方法來尋找社區。k-r圖中一類是關鍵字節點，一類是資源節點，設兩個關鍵字ki和kj，它們指向的相同資源越多，則ki和kj聯系越緊密，則與ki關聯的所有資源也很可能與kj相關。按照這個原則，因此尋找一個完全二部圖的時候對資源節點的個數有要求，對關鍵字節點個數無要求。

首先，將每個關鍵字節點與其對應的資源節點構成一個完全二部圖，然后通過合并生成滿足條件的更大的完全二部圖，最后將一個完全二部圖中關鍵字節點與其相連的所有資源節點構成一個社區。

4.3 算法描述和分析

算法2 二部圖社區發現算法

輸入：二部圖BG（K，R，|K|，|R|），|K|、|R|表示節點個數

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

1)輸入參數p，q；

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

9)for(i=1；i＜=m；i++)//假設S中的關鍵字節點數為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++)//假設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中的關鍵字節點與其對應的所有資源節點構成一個社區。

27)S=S-core；28)}

29)w=w-1；

30)}

5.擴展關鍵字與資源關系對

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

6.仿真實驗與結果分析

6.1 實驗目的與方案

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

本文設計了以下的實驗方案：

（1）采用Maz系統中的檢索下載日志，生成＜k.r>關系對；

（2）構建k-r二部圖，再進行社區發現，用不同的參數進行測試，得出不同的社區個數，和擴展的關鍵字與資源關系對個數；

6.2 仿真實驗的實現

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

（1）取關鍵字節點個數為500，資源節點個數取值從150到1500以50為間隔遞增，進行測試，得出的結果如圖2、圖3所示。可以看出當關鍵字節點個數一定時，隨著資源節點個數的增加，發現的資源社區的個數變化不大，而擴展的關鍵字與資源關系對的個數呈上升趨勢。

（2）取資源節點個數為500，關鍵字節點的個數取值從150到1500，以50為間隔遞增，進行測試，得出結果如圖4、圖5所示。可以看出，當資源節點個數一定時，隨著關鍵字節點個數的增加，發現的資源社區的個數逐漸增大，擴展的關鍵字與資源關系對上升到一定數量后基本平衡。

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

7.結束語

為了提高P2P資源檢索的查全率與查準率，本文提出了基于二部圖的P2P資源挖掘方法。通過分析用戶的檢索和下載行為收集關鍵字與資源的關系對，然后利用二部圖的資源社區發現算法發現關鍵字與資源關系網的網絡社區，由此挖掘出更多的關鍵詞與資源的潛在關系。

[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環境下基于用戶行為的語義檢索方案[J].軟件學報,2007,18(9):2216-2225.

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