一种基于节点局部相似性的复杂网络链路预测算法

2020-05-16马云龙张为子

计算机应用与软件 2020年5期

白桦马云龙毕玉张为子

1(上海高重信息科技有限公司上海 200072)2(同济大学上海 201804)

0 引言

许多领域中，不同种类的数据都可以表示为具有代表个体的节点和代表它们之间交互关系的边的网络。在理解社会网络中的信息传播，人与人之间的相互作用，蛋白质的结构相似性以及人、公司或国家之间的商业关系框架等问题中，复杂网络有着重要的作用，并且得到了广泛的研究。与人们生活关系密切的社交网络就是复杂网络的一个经典例子。人们之间可能相距很远，有不同的文化、不同的语言，但是人与人之间的相互作用通过网络媒介交织在一起构成了复杂的社交网络。社交网络有助于人们接收来自世界各地的新闻、与朋友保持联系、促进学术和文化交流等。复杂网络的另一个例子是信息网络，它也被称为“知识网络”[1]，且具有与社交网络类似的结构特征。信息网络最常见的例子是引文网络，在其中作者们通过共同出版学术文献或者共同引用参考文献来互动[2]。生物网络可能为复杂网络提供另一个例子，节点代表蛋白质、代谢物质或者生物体，相应的连边代表蛋白质-蛋白质相互作用、代谢途径或生物体之间的遗传相互作用。无论在何种网络中，个体及其在网络结构中的不同关系可以简单地抽象为由一组节点(顶点)和边(链接)组成的图。这样的图可以定义为G=〈V，E〉，其中V是顶点集，E是图中的边集[3]。

网络科学中最早的研究对象是基于Erdös和Rényi提出的随机图[4]，在n(n-1)/2条可能的边上以p的概率随机连接n条边。Aiello等[5]对随机图进行了更深入的研究，证明了网络的共同特性及其概率分布，并为长期以来的研究提供了新的研究思路。后来的研究者将他们的注意力转移到了真实的网络(而不是随机产生的)，并解释了它们的形成和演变机制。网络科学研究主要包括复杂网络的统计分析[6]、社区检测和节点分类[7]、动态网络随时间的演变机制[8]、信息扩散和级联分析[9]、网络数据挖掘[10]和可视化[11]等。其中一个长期存在的挑战是复杂网络中的链路预测问题。链路预测是指通过已知的网络拓扑结构以及网络节点属性等信息，预测网络中尚未产生连边的两个节点之间产生链接的可能性或者推断网络中缺失的连边[12]。

链路预测的通用框架是计算节点之间的相似性：如果两个节点更相似，则它们将来更可能被连接。基于此假设，设未连接节点对(x,y)之间的相似性为Sxy，具有高相似性得分的Sxy尚未存在的节点对之间有高概率被链接起来。这些方法完全基于网络的结构信息，可以分为三种类型：全局、局部和准局部。

本文主要针对基于局部相似性的方法展开。基于局部相似性的方法假设：如果节点对具有共同的邻居结构或节点对中的某一节点已经具有更高的度，则它们可能形成链接。因为它们仅适用基于邻居相关结构的局部拓扑信息而不是考虑整个网络结构，所以它们比基于全局相似性的方法更快。许多研究表明在动态网络上，它们的性能比起基于全局相似性的方法更加优越。它们被限制为仅计算节点对的所有可能组合的相似性，因为它们仅对距离为2的节点之间的相似性进行排序。

1 链路预测算法

1.1 CN指标

因为CN(Common-Neighbor)高效简单，所以CN在链路预测中使用很广泛。其思路为：未来两个节点产生链接的概率受其共同节点数量的影响，即如果两个节点具有更多共同邻居，则很可能建立链接。对于网络中的节点x，定义它的邻居为Γ(x)，节点x的度为k(x)=|Γ(x)|，则CN指标的相似性分数可定义为：

Sxy=|Γ(x)∩Γ(y)|

(1)

1.2 AA指标

AA(Admic-Adar)指标于2003年被提出，主要用于社交网络中的链路预测计算。该指标的相似性分数定义如下：

(2)

1.3 RA指标

RA(Resource-Allocation)指标于2009年被提出，其目的是应用于各种网络中的链路预测。该指标的相似性分数定义如下：

(3)

1.4 ERA指标

ERA(Enhanced-Resource-Allocation)指标综合了AA和RA的思想，共同邻居节点中度小的节点贡献度更大，可以更进一步增加小度节点的相似度，减少大度节点的相似度。该指标的相似性分数定义如下：

(4)

对于无向图中任意一个顶点x而言，其所有的邻居节点之间互相都有共同的邻居顶点x。首先，从无向图中获得带权的边的集合，其中边的权为源点的度。然后根据边的源节点v进行分组，这样每组中的目的节点相互都有共同的邻居节点，为源节点v。所以将每组中的目的节点两两组合起来，并加上源点的度的常用对数的倒数的平方，就得到一个集合，该集合中的所有元组中的两个节点都有一个共同邻居。最后，将该集合中两个节点对应相等的元组结合起来，并将元组两顶点共同邻居的常用对数的倒数的平方的值degree加起来就得到了ERA相似性分数。ERA的算法描述如下：

输入：无向图graph

输出：图graph中所有节点对之间的EAA相似性分数

1. 从graph中得到边集DataSet>edge

2. 将边集edge按照source vertex id分组，分为n组，其中source vertex id相等的元组组成同一组，记为group1i(其中，i=0,1,…，n-1)

3. FOR i←0 TO n-1

IF group1i中元素个数>1

用数组list[m]按照target vertex id从小到大的顺序存储group1i中所有的元素

FOR j←0 TO m-2

FOR k←j+1 TO m-1

产生元组Tuple3

1/(lg(source vertex degree))2>

将该元组加入收集器Collector1

END FOR

END IF

END FOR

4. DataSet>tem←Collector1

5. 将数据集tem按照first vertex id和second vertex id分组，分为p组，其中各自first vertex id和second vertex id都相等的元组组成同一组，记为group2u(其中，u=0,1,……，p-1)

6. FOR u←0 TO p-1

将group2u中所有的元组的第三个域inverse of degree相加得到score

产生元组Tuple3，并加入收集器Collector2

END FOR

7. DataSet>result←Collector2

1.5 评价方法

链路预测的主要评价指标有AUC、Precision和Ranking Score三种，本文中使用AUC作为评价指标。AUC是ROC曲线之下和x轴之间的面积，因为ROC曲线一般处于y=x直线的上方，所以AUC的范围在0.5～1之间。对链路预测算法进行多次AUC的抽样比较后，如果测试边集中的测试结果大于不存在边集的测试结果，则取值为1，如果相等则取值0.5。AUC可通过以下公式计算[13]：

(5)

2 实验

2.1 实验设置

在本文中使用AUC指标来评价链路预测算法的表现，为了计算AUC，需要划分训练集和测试集，在划分训练集和测试集时为了避免随机性对结果的干扰，将进行多次划分重复计算AUC。具体实验过程如下：

步骤1 从图文件读取边集E。

步骤2 将边集划分为训练集ET和测试集EP。

步骤3 对训练集ET运用ERA、AA、RA和CN算法算出各节点对的相似性分数。

步骤4 从不存在的边的集合EN和测试集EP中各选出一条边，并比较其相似性分数的大小，重复n次，根据式(5)计算AUC。

步骤5 重复执行步骤2-步骤4，重复20次，并计算AUC的平均值。

2.2 实验数据集

本实验中使用的五种网络分别为NS科学家合作网络、PB美国政治博客网络、美国航空路线图USAir网络、Yeast蛋白质网络和C.Elegans网络。各网络的主要参数如表1所示。其中：V表示节点数，E表示边数，AD表示平均度，GD表示图密度，ACC表示平均聚类系数。

表1 各数据集的网络属性

2.3 实验结果分析

以AUC作为评价预测精度的指标，并以AA、RA和CN这三种基于局部相似性的链路预测算法作为基准进行比较，将改进后的ERA算法应用于NS、PB、USAir、Yeast和C.Elegans五个网络数据集中。实验过程中，对测试集的比例划分为1%、10%、20%、33%。随着测试集比例的上升，预测精度出现了明显的降低，故不再对高于40%的测试集进行测试。测试结果见图1，柱状图的顺序从左到右为ERA、AA、RA和CN。

(a) NS

(b) PB

(d) Yeast

(e) C.Elegans图1 不同数据集的中的AUC评估值

可以看出，ERA算法的整体预测精确度优于AA、RA和CN算法。从表2可以看出，ERA在NS数据集上的平均预测精度相较于AA、RA和CN算法分别提升了0.07%、0.19%、0.48%；在PB数据集上分别提高了0.31%、0.13%、0.60%；在USAir数据集上分别提高了0.53%、0.06%、1.57%；在Yeast数据集上分别提高了0.07%、0.09%、0.07%；在C.Elegans数据集上分别提高了0.48%、-0.13%、2.75%。从表3可以看出，93.3%的ERA算法的预测精确度高于对比算法的预测精确度，个别预测精度没有达到预期的情况，这种情况和所使用的数据集和抽样的随机性有一定关系。