在大规模社会网络中基于路径评分的个人关系发现方法

摘要

在大规模社会网络中基于路径评分的个人关系发现方法属于互联网中社会网络搜索技术领域，其特征在于基于通用的社会网络，首先定义基于权重的路径评分，再查找出每两个人之间的最短路径，然后开始查找指定的两个人之间的路径长度不大于最短路径的基于倍数的所有路径，最后按照路径评分的顺序把所有路径返回给用户。本发明能应用于节点数超过百万的社会关系网络中，进行人与人之间的关系快速查找或使用于研究者的关系发现。

说明书

技术领域

本发明属于互联网技术领域，尤其涉及互联网下的社会网络搜索。

背景技术

个人关系发现是指下一代互联网中自动的发现人和人之间的相连关系的方法，将会给 互联网带来巨大的用户和使用频率，是体现互联网新的技术以及经济价值的重要手段。查 找人和人之间的路径是个人关系发现的基本方法，其目标是为了在两个不直接认识的人之 间找到一条路径，该路径的节点为人，该路径的相邻两个人为互相认识的关系，通过这些 人的介绍，可以将两个不直接认识的人联系起来，从而使得两个不直接认识的人能够找到 一种建立连接的方式。

基于路径来查找个人关系是这一个领域中的重要方法，其目标是先把社会网络建模成 为图，用节点来表示人，用连接节点的边表示人和人之间的关系。在大多数方法中，查找 人和人之间的关系是通过在图中查找两个节点可能存在的路径来达到目标。

在已提出的个人关系发现方法中存在以下一些局限性：第一，仅考虑了“最小路径” 的简单情形，也就是说，只查找长度最短的一条路径，这个长度最短的路径有可能是具有 的边最少的路径，也有可能是根据边的权重和边的个数计算出来的最短路径。第二，缺少 路径评分机制，在进行多条路径查找的时候，可以根据路径评分结果去掉分数较低的路径， 提高系统的效率，这在大规模的社会网络中应用时非常重要。

针对上述不足，本发明提出了一种基于路径评分的个人关系发现系统(Path Ranking based Association Search，简称PRAS)。本发明通过引入一种路径评分机制，更好的提高 了个人关系发现的效率，能够被应用在节点数超过百万的社会关系网络中，进行人和人之 间关系的快速查找，并且还可以将其应用于研究者的关系发现。

发明内容

有鉴于此，本发明的目的在于提供一种在大规模社会网络下基于路径评分的个人关系 发现方法和系统。

该个人关系发现方法包括个人关系的模型搭建子模块，个人关系最短路径计算子模块 以及基于路径评分的个人关系发现子模块和个人关系发现结果展示子模块。本发明的核心 在于基于路径评分的个人关系发现子模块，其他子模块为核心模块提供数据服务。

本发明所提出的方法的思路在于：采用一种通用的社会网络描述模型，首先基于该模 型定义路径评分方式；然后基于该模型构建的社会网络图先查找出每相邻两个人之间的最 短路径；然后开始查找指定的两个人之间路径长度不大于最短路径某个倍数的所有路径； 最后按照路径评分的顺序将所有的路径返回给用户。

所述方法是基于一个已经存在的社会网络依次按以下步骤实现的，所采用的步骤框图 请见图1，该方法包括如下步骤：

步骤1：构建社会网络图：

设：社会网络为G＝(V，E)，其中G为有向图，其中V为节点的集合，E为边的集合， 任何一个节点v∈V代表社会网络中的一个人，e^r_ij∈E代表有向图中的一条有向边，表示社 会网络中的人v_i和v_j之间存在的一种关系r，因为两个人之间可能存在多种关系。

其中e^r_ij的小标ij表示该边的起始节点是v_i，结束节点是v_j，这个关系类型是r。

在这个图之中，我们限定一个人只能在图中出现一次，也就是说，图中的两个节点不 可能表示同一个人。

在这个图上定义个人关系，个人关系指的是图中任意两个节点之间可能出现的一条路 径，路径在这里的定义是两个人之间通过若干条边组成的一种可以连通的关系，如果节点 之间只有一条边，那么退化成为e^r_ij∈E这种类型的关系。因此，在这里，两个人之间的关 系既可以是由一条相互之间关联的边组成，也可以由多条边组成。

个人关系的输入是两个人v_i和v_j，输出是这两个人之间的关系，按关系的评分从高到 低排列，其中某一个关系的表示如下：

{e^r_i1，e^r₁₂，…，e^r_1j}，这个集合中的元素个数大于或者等于1

其中e^r_m(m+1)∈E，表示为图中的一条边，在这里v_i被定义为起点，v_j定义为终点。

设v_i和v_j的一个路径之间有n条边，其中路径的长度定义为：

d＝∑α_k(v_i，v_j)，k＝1，2，…，n

其中α_k(v_i，v_j)为v_i和v_j路径上的第k条边的权重，所以这个公式表示为从起点到终 点的这条路径上所有的边的权重的和。本发明中的路径长度即路径评分表示的是两个人之 间的亲密程度，如果路径评分低，则说明两个人之间具有的这个路径显示的亲密程度比较 高，这个路径比较重要；如果路径评分高，则说明两个人之间具有的这个路径显示的亲密 程度比较低，这个路径不重要。

在本发明中处理的所有关系以及权重表示如表1：

表1，本发明处理的所有关系以及权重

  关系   所表达的意义   权重   同文章作者   两个人为同一篇论文的作者   2   被…所指导   一个人是另一个人的学生   4   在同一个项目中工   作   两个人在同一个项目中工作   3   是朋友   两个人是好朋友   1

关系权重的给定方法由人为给定，目前所采用的方法是随机调研10个人，让每个人对 于每个关系都给出一个1-10分之间的分值，计算平均值后进行四舍五入的取整，就是该关 系的权重。

下面举例说明一个社会网络，一个真实的基于实验室的社会网络如图2所示，在这个 图中，我们可以发现对于两个人“小洪”和“王教授”之间存在着如下的关系：

1)小洪-被…所指导-蔡教-在同一个项目中工作-王教授

2)小洪-同文章作者-唐博士-被…所指导-王教授

所以，关系1)的分数为4+3＝7；关系2)的分数为2+4＝6

步骤1就是创建一个社会网络的图，图中的节点就是人，图中的边就是表1中定义的 4种边。社会网络存储在关系数据库中，本发明采用如下的数据库结构来存储社会关系网络：

1)关系以及权重表，该表存储社会关系网中的所有关系以及权重，如下所示：

表2，社会网络图中的关系类型以关系权重表

  关系标识   关系名称   说明   权重   1   同文章作者   两个人为同一篇论文的作者   2   2   被…所指导   一个人是另一个人的学生   4   3   在同一个项目中工作   两个人在同一个项目中工作   3   4   是朋友   两个人是好朋友   1

2)节点表，该表存储社会网络中的所有人，如表3所示：

表3，社会网络图中的节点表

  节点标识   节点名字   节点说明   1   唐博士   清华大学博士生   2   小洪   清华大学硕士生   3   王教授   清华大学博士生导师   4   蔡教授   清华大学硕士生导师

3)节点关系表，标识社会网络中的人之间的关系，如表4所示：

表4，社会网络节点关系表

  关系类型   源节点   目标节点   1   1   2   1   1   3   3   1   2   2   1   3   1   2   1   3   2   1   2   2   4   1   3   1   3   3   4   3   4   3

实际上，图中的每一条边在表4中都有一条(双向边是两条)相应的记录(表1中的 行)。

至此，一个社会网络构建完毕。

步骤2：根据社会网络图，计算图中每两个人之间的最短路径的评分；

在步骤1结束后，整个社会网络已经构建完毕，在步骤2中，我们将计算社会网络图 中任意两个节点之间的最短路径，以便让步骤三使用。社会网络途中任何两个节点的最短 路径计算方法利用基于Dijkstra的图最短路径计算方法，算法如下：

算法的输入，社会关系图上的任意两个节点v和t，v和t分别代表两个人。

输出：v和t之间的最短路径的评分。

算法中的变量说明：

1)dis(a)的值表示图中的节点a到v的最短路径的评分；

2)path(v)的值表示该条路径到达v后的下一个节点；

3)c(a)的值表示这个节点是否被遍历过，0为还没有遍历过，1为遍历过了；

4)(u，v)表示某一条边(u，v)的开始和结束节点，其中u表示开始节点，v表示结束 节点。

5)w(e)表示边e的权重。

1.首先对于除去t之外的所有G中的点a∈V\t，设{dis(a)为(2-2^-52)·2¹⁰²³； path(a)为0；c(a)为0；}；

2.令dis(t)为0；

3.创建一个最小堆heap；

4.将t插入到最小堆中；

5.当(最小堆不为空的时候)，做下面的循环{

6.从最小堆中取出一个节点，设为v_min；如果v_min不为v，继续，否则回到第5步；

7.c(v_min)设为1；

8.得到所有指向v_min的边的集合E(v_min)；

9.(对于每个在E(v_min)中的边，设为e_min)，做下面的循环{

10.得到e_min的起始和终结节点(u，v_min)；

11.如果(c(u)为0并且w(e_min)+dis(v_min)＜dis(u))则做如下操作{

12.令dis(u)为w(e_min)+dis(v_min)；

13.令path(u)为v_min；

14.if(如果节点u存在于最小堆中)则做如下操作{

15.将u从最小堆中移除；

16.}如果节点u不存在于最小堆中，则做如下操作{

17.将u插入到最小堆中；

18.}

19.}

20.}

21.}

22.输出dis(v)的值，该值就是v到t之间的最短路径；

算法的一个例子如附图3所示，在附图3中，求v和t之间的最短路径，算法的计算 流程如下所示：

1)初始化

先初始化算法的所有参数：

dis(v)＝(2-2^-52)·2¹⁰²³，dis(a)＝(2-2^-52)·2¹⁰²³，dis(b)＝(2-2^-52)·2¹⁰²³，dis(c)＝ (2-2^-52)·2¹⁰²³，

path(v)＝-1，path(a)＝-1，path(b)＝-1，path(c)＝-1，

c(v)＝0，c(a)＝0，c(b)＝0，c(c)＝0；dis(t)＝0

2)算法开始，创建最小堆，将t插入最小堆；

3)最小堆不为空，开始循环，取出节点，这时候为t，于是V_min为t，于是c(t)＝1；

4)得到所有指向t的边的集合，设为E(t)＝{(a，t)，(b，t)}

5)对于E(t)中的边，开始循环：

6)首先处理(a，t)，因为c(a)＝0并且w((a，t))+dis(t)＝5+0＝5＜dis(a)＝(2-2^-52)·2¹⁰²³， 所以dis(a)＝5，path(a)＝t；将a入最小堆；

7)然后处理(b，t)，因为c(b)＝0并且w((b，t))+dis(t)＝6+0＜dis(b)＝(2-2^-52)·2¹⁰²³， 所以dis(b)＝6，path(b)＝t；将b入最小堆；

8)因为最小堆不为空，所以开始循环，取出节点，这时候为a，于是c(a)＝1；

9)得到所有指向a的边的集合E(a)＝{(v，a)}；

10)对于E(a)中的边，开始循环：

11)处理(v，a)，因为c(v)＝0，并且w((v，a))+dis(a)＝2+5＝7＜dis(v)＝(2-2^-52)·2¹⁰²³， 所以dis(v)＝7，path(v)＝a；将v入最小堆；

12)因为最小堆不为空，所以开始循环，取出节点，这时候为b，于是c(b)＝1；

13)得到所有指向b的边的集合E(b)＝{(v，b)}；

14)对于E(b)中的边，开始循环：

15)处理(v，b)，因为c(v)＝0；而且w(v，b)+dis(b)＝3+6＞dis(v)＝6，所以不做动作。

16)最小堆不为空，所以开始循环，取出节点，这时候为v，于是退回循环；

17)此时最小堆为空，则输出dis(v)＝6，就是v和t之间的最短路径；

上面是图3节点v和t之间最短路径计算的例子，对于图3中的任意两个节点，都利 用上述方法计算出最短路径并且存放在数据库中。数据库表的结构包括三列：源节点；目 标节点和最短路径。如表5所示，表5表示了图2中的社会网络的任意两个节点之间的最 短路径在数据库中存放的实际情况。

表5，任意两个节点之间最短路径记录表

  源节点   目标节点   最短路径   1   2   2   1   3   2   1   4   5   2   1   2   2   3   4   2   4   4   3   1   2   3   2   4   3   4   3   4   1   5   4   2   7   4   3   3

这个表记录了社会关系图中任意两个节点之间的最短路径，如果这两个节点并不连通， 那么采用双精度实数的最大值作为无穷大，该值为(2-2^-52)·2¹⁰²³。

在步骤2中，对步骤1所产生的社会关系网络中的任意两个节点的最短路径进行计算， 并且将结果保存在数据库中。

步骤3：根据路径评分，对于任意指定的两个人，查找他们之间的社会关系；

当步骤1和步骤2把社会网络图以及图中任意两个人的最短路径都生成完毕后，就可 以进行社会网络中任意两个人之间的关系的快速查找了，设社会网络图中的两个人为v_i和 v_j，并且设定所返回的路径不能大于最短路径的倍数β，可以开始按照下面的方法进行社 会网络中的关系的查找：

其中参数β的作用是用来过滤一些不亲密的关系，因为前面已经提到，一个关系的评 分越低，说明它越重要，比如β＝1.2，那么，所有分数高于v_i和v_j的最短路径长度乘于1.2 的路径都将被过滤掉。只返回那些重要的关系可以加快关系查找的速度，同时又兼顾到用 户关心的重要的关系，为本发明的核心。

该方法步骤如下，其中对应的变量和步骤2中查找两个人之间的最短路径的方法的变 量的意义保持一致。增加了如下变量：

1)d(a)，表示从节点a到节点v_i的路径长度；

2)L_min，表示v_i和v_j之间的最短路径；

1.首先初始化边的权重，对于社会网络中所有的边e_mn∈E，令这些边的权重为 w(e_mn)，为方便起见记作w_mn，其中w_ij为v_i和v_j之间的关系e_ij的权重，这些关系的权重列 表见表1；

2.其次对于除去终点v_j的所有的点v∈V＼v_j，令dis(v)等于从v到v_j的最短路径长 度；

3.设L_min为v_i和v_j之间的最短路径，所以有L_min为dis(v_i)；

4.将v_i入栈；

5.定义如下两个变量：d(v)，c(v)。d(v)表示从v_i到v的路径长度，c(v)表示v 是否已经在路径中出现过。并且对于任何图中的节点v，都初始化d(v)＝0，c(v)＝0。因为 v_i已经在路径中，所以c(v_i)＝1；

6.如果(栈还不为空)，那么进行跳到7，如果(栈为空)，那么跳到13；

7.得到栈顶的节点s，将起点是s的边的集合记为E(s)；

8.对于E(s)中的任何边e_s，进行如下操作；

9.假设边e_s是从s指向u的，那么如果u还未在路径中，并且满足从v_i到s的路径 长度+从s到u的路径长度+从u到v_j的长度小于βL_min，则跳到10，否则跳到12；

10.如果u＝v_j，那么一条路径已经找到，对该路径进行评分，加到返回结果集中；

11.如果u并不等于v_j，那么将u加入到栈顶，并且标记u为在路径中的节点， c(u)＝c(u)+1，并且更新u到v_i的值，d(u)＝d(s)+w(e_su)

12.说明该条边已经被淘汰，将s是否在路径中的值减1，c(s)＝c(s)-1；

13.得到所有的关系结果。

算法的一个例子如附图4所示，输入为v_i和v_j，参数为β＝1.2，就是找到所有关系长 度小于1.2*7＝8.4的v_i和v_j之间的关系。

在这个算法中，用队列变量A来存储所有得到的路径。

1)算法初始化：

得到所有边的权重：

w(v_i，a)＝1，w(v_i，b)＝2，w(v_i，c)＝3，w(v_j，d)＝2，w(v_i，f)＝5，w(a，v_j)＝7，w(b，v_j)＝5， w(c，v_j)＝6，w(d，e)＝8w，w(e v_j)＝2，

初始化dis(v)：

dis(v_i)＝7，dis(a)＝7，dis(b)＝5，dis(c)＝6，dis(d)＝10，dis(e)＝2；dis(f)＝∞， dis(v_j)＝0；

令L_min＝dis(v_i)＝7，

建立一个栈，并且将(v_i，NULL)插入栈，

对于图中所有的节点，初始化d(v)和c(v)，令

d(v_i)＝d(a)＝d(b)＝d(c)＝d(d)＝d(e)＝d(f)＝d(v_j)＝0，

c(v_i)＝c(a)＝c(b)＝c(c)＝c(d)＝c(e)＝d(f)＝c(v_j)＝0

令c(v_i)＝1；

2)因为栈不为空，所以弹出栈顶元素，为(v_i，NULL)，得到v_i作为起始节点的所有边 的集台E(v_i)＝{v_i，a)，(v_i，b)，(v_i，c)，(v_i，d)}，对于每个E(v_i)中的边，进行循环 处理；

3)处理(v_i，a)，因为c(a)＝0，而且d(v_i)+w(v_i，a))+dis(a)＝0+1+0＝1＜βL_min＝8.4，

而且又因为a不是v_j；所以将(a，(v_i，a))加入栈，并且c(a)＝c(a)+1，d(a)＝d(v_i)+ w((v_i，a))＝1；

4)返回到算法2中的步骤6，因为栈不为空，所以弹出栈顶元素，为(a，(v_i，a))，得 到a作为起始节点的所有边的集合E(a)＝{(a，v_j)}，对于E(a)中的边，进行循环处理；

5)处理(a，v_j)，因为c(v_j)＝0，而且d(a)+w((a，v_j))+dis(v_j)＝1+7+0＝8＜8.4，而且因为 v_j就是该边的终点，所以将栈中在(v_i，a)之前的所有边得到，作为一条路径，就是(v_i， a)(a，v_j)，将该条路径存储到A中，并且记录该条路径的长度；并且弹出(a，(v_i，a))， 并且c(a)＝c(a)-1；

6)处理(v_j，b)，因为c(b)＝0，而且d(v_i)+w((v_i，b))+dis(b)＝0+2+0＝2＜βL_min＝8.4， 而且又因为b不是v_j；所以将(b，(v_i，b))加入栈，并且c(b)＝c(b)+1，d(b)＝d(v_i)+ w(v_i，b))＝2；

7)返回到算法2中的步骤6，因为栈不为空，所以弹出栈顶元素，为(b，(v_i，b))，得 到b作为起始节点的所有边的集合E(b)＝{(b，v_j)}，对于E(b)中的边，进行循环处理；

8)处理(b，v_j)，因为c(v_j)＝0，而且d(b)+w((b，v_j))+dis(v_j)＝2+5+0＝7＜8.4，而且因为 v_j就是该边的终点，所以将栈中在(v_j，b)之前的所有边得到，作为一条路径，就是(v_i， b)(b，v_j)，将该条路径存储到A中，并且记录该条路径的长度；并且弹出(b，(v_i，b))， 并且c(b)＝c(b)-1；

9)处理(v_i，c)，因为c(c)＝0，而且d(v_i)+w((v_i，c))+dis(c)＝0+3+0＝3＜βL_min＝8.4， 而且又因为c不是v_j；所以将(c，(v_i，c))加入栈，并且c(c)＝c(c)+1，d(c)＝d(v_i)+ w((v_i，c))＝3；

10)返回到算法2中的步骤6，因为栈不为空，所以弹出栈顶元素，为(c，(v_i，c))， 得到c作为起始节点的所有边的集合E(c)＝{(c，v_j)}，对于E(c)中的边，进行循环处 理；

11)处理(c，v_j)，因为c(v_j)＝0，而且d(c)+w((c，v_j))+dis(v_j)＝3+6+0＝9＞8.4，因此弹 出(c，(v_i，c))，并且c(c)＝c(c)-1；

12)处理(v_i，d)，因为c(d)＝0，而且d(v_i)+w(v_i，d))+dis(d)＝0+2+0＝2＜βL_min＝ 8.4，而且又因为d不是v_j；所以将(d，(v_i，d))加入栈，并且c(d)＝c(d)+1，d(d)＝d(v_i)+ w((v_i，d))＝2；

10)返回到算法2中的步骤6，因为栈不为空，所以弹出栈顶元素，为(d，(v_i，d))， 得到d作为起始节点的所有边的集合E(d)＝{(d，e)}，对于E(d)中的边，进行循环处 理；

11)处理(d，e)，因为c(e)＝0，而且d(e)+w((d，e))+dis(e)＝2+8+0＝10＞8.4，因此弹出 (d，(v_i，d))，并且c(d)＝c(d)-1；

12)栈为空，退出循环；

13)输出A，A包含了两条路径(v_i，b)(b，v_j)，(v_i，a)(a，v_j)

步骤4：根据不同条件设置进行路径输出；

A中包含了本方法返回的路径，其中包含如下信息：

1.路径的长度，按照边的权重计算得出，在算法2中的14行计算得到该值；

2.每条路径的边的个数，因为返回的路径组织成边的形式，所以能够得到每条路径的 边的个数。

在排序的时候，本发明允许用户利用这两个参数得到相应的排序结果，缺省情况下， 本发明所返回的路径按照路径长度排序。

系统的硬件结构图见图5，基于路径评分的个人关系发现的4个子系统分别实现了方 法的4个步骤，而这4个子系统用4个装置实现。说明如下：

其中装置4社会网络生成服务器负责生成社会网络结构图，并且将社会网络结构图存 储在装置3数据库服务器上。装置4负责步骤1的工作，生成了表1，表2，表3和表4， 然后通过网络将这些表存储在装置3中；

装置3是系统的数据服务器，接受装置4传过来的表1-4，同时利用步骤2的方法， 读取表1-4的数据生成表5，于是装置3上就有了所有系统的数据，包括表1-表5，给装置 2提供服务；

装置2社会网络计算服务器接受Web服务器传过来的查询两个人的社会关系的请求， 通过步骤3的方法读取装置3数据库服务器的信息并且计算出两个人之间的社会关系然后 返回给装置4；

装置4是Web服务器。装置4提供了界面，接受用户的查询请求并且将得到的结果显 示给用户。用户通过浏览器来访问Web服务器，输入查询请求并且得到结果。

附图说明

图1，基于路径评分个人关系发现系统的的步骤框图；

图2，基于路径评分个人关系发现系统的一个社会关系网络的例子；

图3，基于路径评分个人关系发现系统的最短路径算法的一个例子；

图4，基于路径评分个人关系发现系统的社会关系发现算法的一个例子；

图5，基于路径评分个人关系发现系统的硬件结构图。

具体实施步骤

利用本发明的步骤1-4，创建了一个研究者的社会网络，并且使用该社会网络中查找 研究者之间的关系的任务来验证本文的发明。

(1)研究者社会网络的构建

研究者的社会网络的构建主要使用了如下步骤：首先基于发表文章，通过对特定的学 术论文网站(http://www.informatik.uni-trier.de/~ley/db/)的数据分析，首先得到论 文列表，接着得到每一篇论文的作者，对于每一篇论文的作者，做如下步骤：

如果该作者不存在节点表中，则将该作者添加到节点表中；接着，对于该论文的每两 个作者，在节点关系表中插入“同文章作者”关系。

经过这种构建方法，收集了448,551个在计算机科学的研究者，他们之间的“同文章 作者”数目大到了2,413,208个。

接着，采用人工的方式，利用这些计算机科学研究者中具有个人主页的研究者，进行 “被…所指导”，“在同一个项目中工作”以及“是…的朋友”关系的建立。

其中“被…所指导”和“在同一个项目中工作”可以通过阅读该研究者的网页内容所 得到，一般来说，研究者会在个人主页上说明自己的导师以及自己从事过的项目。

相对而言，“是…的朋友”很多情况下并不能直接得到，我们采取利用网页链接的方法 得到，比如研究者A的主页上放了研究者B的主页的链接，那么我们认为研究者A和研究 者B直接存在朋友的关系。

经过人工构建，这些研究者之中“被…所指导”的关系达到10,300个，“在同一个项 目中工作”的关系达到35,020个，“是…的朋友”关系达到14,700个。

在上述步骤完成后，社会网络建立完毕，再通过算法1来计算这个社会网络中任意两 个人之间的最短路径，于是可以进行算法2的验证了。

(2)测试集的建立

在上述的社会网络上，我们创建了9个测试集，每个测试集分别包含369-1000个关 系查询。

在测试集生成中，我们首先随机选择了1000对人(一对人(A，B)表示从A到B的关系 查询)作为第一个基础测试集，对于余下的8个测试集，我们每次都从这1000对人里面选 择不同领域的两个人。我们选择了计算机中的本体映射、语义Web、数据挖掘、信息抽取、 Boosting学习、规划问题以及机器学习的研究者。构建出的测试集表6所示：

表6，九个测试集

  No.   测试集   多少对人   领域1   领域2   1   Random   1000   Random   2   SW_SW   1000   SW   3   IE_IE   1000   IE   4   DM_DM   1000   DM   5   BS-PL   369   BS   PL   6   DM-SW   1000   DM   SW   7   ML-IE   1000   ML   IE   8   PL-DM   1000   PL   DM   9   SW-0A   1000   SW   0A

其中SW代表语义网络，IE代表信息抽取，DM代表数据挖掘，BS代表Boosting学习， PL代表规划问题，ML代表机器学习，OA代表本体映射。

测试集中的“Random”表示随机选取两个人，共有1000对人；“SW_SW”表示两个人 都是语义Web领域的研究者，“IE_IE”表示两个人都是信息抽取领域的研究者；“DM_DM” 表示两个人都是数据挖掘领域的研究者；“BS-PL”表示两个人中的一个是Boosting学习领 域的研究者，另外一个人是规划问题领域的研究者；“DM-SW”表示其中一个人是数据挖掘 领域的研究者，另外一个人是语义Web的研究者；“ML-IE”表示其中一个人是机器学习领 域的研究者；另外一个人是信息抽取领域的研究者；“PL-DM”表示其中一个人是规划问题 领域的研究者，另外一个人是数据挖掘领域的研究者；“SW-OA”表示其中一个人是语义Web 领域的研究者，另外一个人是本体映射领域的研究者。这种训练集的设计可以充分的考虑 到不同研究者之间社会关系距离的远近，因为同一个研究领域的研究者之间会通过比较少 的节点产生关系，而不同领域的研究者之间会通过比较多的节点产生关系，所以测试集既 考虑了通过少的节点产生关系的两个研究者，也考虑了通过多的节点产生关系的研究者， 在这样的测试集下面取得的结果很有说服力。

测试集里面的每个测试单元是两个研究者，在同以往方法比较的时候，采用了在所构 建的社会网络中查找测试集上的每个测试单元中的两个研究者的关系所需要的时间平均 值。本发明中所述的方法与常用的图遍历法进行比较，图遍历算法被广泛的应用于基于图 节点关系的查找之中，实验结果如表7所示：

表7，本文发明和遍历法的实验结果比较

  测试集   方法   总时间   平均时间   Random   遍历法   669000   669.00   本发明方法   3553   3.5   SW_SW   遍历法   161050   161.05   本发明方法   2752   2.75   IE_IE   遍历法   1002285   1002.29   本发明方法   2710   2.71   DM_DM   遍历法   16474   164.74   本发明方法   2734   2.73   BS-PL   遍历法   162520   162.52   本发明方法   1034   2.80   DM-SW   遍历法   969437   969.44   本发明方法   3010   3.01   ML-IE   遍历法   240746   240.77   本发明方法   3029   3.03   PL-DM   遍历法   601309   601.31   本发明方法   3181   3.18   SW-0A   遍历法   373250   373.25   本发明方法   2714   2.71   Average   遍历法   482708   482.71   本发明方法   2941   2.94

从实验结果可以看出，利用本发明所提出的方法能够提高在社会网络中查找个人关系 的时候的速度。本发明所提出的个人关系发现的快速性质体现在以下几点：(1)两个人之 间的最短路径预先计算出来并且存储完成，作为查找其他路径的基础，在查找其他路径的 时候最短路径不用重复计算；(2)在查找其他路径的时候，通过对于长度大于某个阈值的 路径直接进行忽略，大大减少了需要查找的路径的数目。

综上所述，利用本发明，能够有效的提高在社会网络中进行个人关系查找的效率，本 发明应用在网站http://www.arnetminer.com上，提高了用户在搜索研究者之间关系的效 率，使得网站防问量剧增，已经从未运行该发明所提供的系统之前的2,000次/天提升到 20,000次/天。