基于二部图的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).