融合节点标签与强弱关系的链路预测算法

王曙燕，巩婧怡

西安邮电大学 计算机学院，西安710121

链路预测通过已知的网络结构和节点信息等因素[1]，预测网络中两节点连接的可能性或发现已存在但未识别的隐式连边。在社交网络中，将用户视为节点，各用户社会关系视为连边，对可能存在关系的用户进行链路预测[2]。

常见的链路预测方法有：基于节点属性信息、基于网络结构和最大似然估计法[3]。然而，仅对网络节点属性的预测不能够真实精确地反映出目标网络的特性，并且与节点的属性信息相比，更容易获得网络的结构信息，而且网络的结构信息也相对比较可靠[4]。Liben-Nowell等[5]通过网络节点的拓扑结构相似性分析社交网络。后来出现的基于节点度的共同邻居CN（common neighbors）[6]根据节点的共同邻居进行推荐。王智强等[7]认为可借助链路预测检测由于信息或数据的噪声产生的不必要链接。

根据研究发现，仅考虑节点属性或网络拓扑结构的链路连接很难对节点信息进行较完全的刻画并不能更加精确地对节点进行链路预测。本文提出一种融合节点标签与强弱关系的链路预测（node labels and strong &weak relationships link prediction，NRLP）算法。该算法提取社交网络部分子图，通过对局部子图生成的目标矩阵进行分解，并将子网络结构融入节点标签、文本属性与关系强度的动态权重。该算法得到的节点向量兼顾网络结构属性、关系强弱与节点属性，且通过局部子图分析预测可能性比全图降低算法运行时间。

1 相关工作

链路预测是预测网络中的两个节点是否可能具有链路[8]。……