基于优先连接和用户属性的链路预测算法研究

初晓宇，高守玮

(上海大学 机电工程与自动化学院，上海 200000)

1 概 述

链路预测作为一门典型的交叉学科，已经成为网络信息挖掘和预测领域最具活力的研究方向之一，其应用场景生活中随处可见(如图1所示)。当然，链路预测作为复杂网络中的重要研究课题，其主要功能是根据已知的网络拓扑结构和节点的相关信息来预测网络中节点之间是否存在连接或发现已存在但尚未被发现的边。在微博社交网络中，用户代表网络节点，用户之间的关系即代表节点之间的连边，而链路预测就是预测用户间关系的重要方式。

图1 链路预测的应用

基于网络拓扑结构的链路预测相似性算法是根据网络结构特征衡量节点间相似性并预测节点间连接的可能性。在社交网络(微博)中的表征为预测两个陌生用户成为好友的可能。Liben-Nowell和Kleinberg[1]是最早通过计算社会网络中节点的拓扑结构的结构接近性来分析社会网络的；后来出现的基于节点度的共同邻居(common neighbor，CN)[2]是指两个节点拥有的共同邻居越多，那么二者越倾向于构成连边。Adamic-Adar(AA)指标[3]考虑两节点共同邻居的度信息，并为每个节点分配权重。20世纪末，Barabási和Albert通过对无标度网络的研究，提出了优先连接[4](PA)。PA是指在网络中两个节点连边与否取决于二者节点度的乘积，并将它应用于解释在自然、技术以及社会体系中普遍出现的无标度网络，研究成果颇丰。傅颖斌和陈羽中根据节点的特征向量和节点间相似性信息进行微博用户分析[5]，最终发现用户的属性特征对用户关系的产生具有重要影响；李博等提出了JAFLink混合算法[6]来进行好友推荐，结果显著。

研究发现，社交网络错杂纷繁，仅仅通过节点属性或者拓扑结构某一信息很难对节点对进行刻画和预测，节点属性都缺乏一定的普适度。因此，文中基于社交网络(新浪微博)提出了一种综合考虑网络结构与用户属性的PAA算法。该算法兼顾社交网络拓扑结构和用户属性信息，更加全面地对整个网络进行剖析和考究，从而为用户提供更加精准的推荐服务。

2 社交网络的模型构建

网络中最重要的两个因子是节点和连边。社交网络是一个具象的复杂网络[7]，在保留复杂网络本身特征[8]的同时，也衍生了自己独特的属性。

社交平台的核心是用户，亿万级的在线用户是一个社交平台的价值所在。如果把整个社交网络系统比作神经系统，那么用户之间的相互关系，即“关注”和“粉丝”，便是“神经元”。一个用户A关注了另一个用户B，用户A也可以查看用户B的关注。从另一个方向考虑，用户A成为了用户B的粉丝，用户B本身作为粉丝也给他的关注带来了新的粉丝。当一个用户的粉丝数很多，即被关注度很高，那么他的一些言行举止多会对整个社交网络产生巨大的影响。从网络知识的角度解释，当一个节点与很多节点产生了连边关系，那么该节点在整个网络中的影响是巨大的。

对于复杂网络建模的研究[9]在近年来成为热点，各种数学模型的涌现为复杂网络建模提供了构造器。目前比较成熟完善的网络模型大致包括四种：规则网络、随机网络、小世界网络和无标度网络。其中，无标度网络[10]的一个显著特征是大多数节点只存在几个链路，而一些节点与其他节点具有大量的连接，其度值完全符合幂律分布[11]。

尽管关键节点的存在使得无标度网络对突发故障具有较强容忍能力[12]，但同时也更容易受到协同攻击。现实中许多网络都带有无标度的特性，而社交网络恰恰位列其中。豆瓣网的网络结构度分布如图2所示。

图2 豆瓣网的网络结构度分布

豆瓣网的度分布如图3所示。

图3 豆瓣网的度分布

由图3所示，随度值增大，节点数呈指数型下跌。因此，可认为豆瓣网的度分布为幂律分布，即可说明类似豆瓣网在线社交网络[13-14]都属于无标度网络的范畴。

3 链路预测算法描述

3.1 链路预测相似性算法

优先连接指标[15](professional attachment，PA)是一种基于节点度的相似性指标，主要用于构建无标度网络。文献[2]中表明，在无标度网络中，一个新边将被添加到节点x的概率与节点x的度值k(x)成正比。因此可以得出结论，当一条新边将要连接两个节点x和y时，与两个节点度的乘积成正比。该算法的复杂度较其他算法低，因为需要的信息量最少。

Sxy=k(x)×k(y)

(1)

对于网络中的节点x，定义它的邻居为τ(x)，k(x)=τ(x)为节点x的度。

3.2 社交网络用户个人属性

社交网络[10,13-14]除网络结构属性外还具备较强的节点个性化属性。日常生活中，在远离家乡的地方，人们更愿意与同一家乡、同一行业、同一学校、相似年龄的人成为好友，这就意味着用户属性的相似性对是否成为好友具有重要的意义，特别是在社交网络[14]上，不能只考虑网络结构而忽视它的存在。因此，在链路预测中加入用户属性相似度信息将有利于提升好友推荐精确度。

3.3 精确度测量

文中选择的测评链路预测精确度的方法是“ROC曲线下面积法”[1](area under curve，AUC)。AUC适用于从整体上衡量算法的精确度，是链路预测中对结果进行精度评价的最普遍的量化方法。在实验过程中，为了保证待测算法的精度和准度，文中将数据全集E分为训练集ET和测试集EP两组独立的数据集。在数学上的表示[2]即E=ET∪EP，且ET∩EP=∅。在此，将属于U但不属于E的边定义为不存在的边。

AUC可理解为在测试集中连边的分数值比随机选择一个不存在的边的分数值高的概率。每次随机地从测试集中选一条边与随机选择的不存在的边进行比较，如果测试集中边的分数值大于不存在边的分数值，就加1分；如果两个分数值相等，就加0.5分。独立比较n次，如果测试集中有n的边的分数值大于不存在的边的分数，有n次两边的分数值相等，则AUC定义为：

(2)

如果所有边是随机产生的，AUC=0.5。因此AUC的数值大小衡量了算法的精确程度。

4 算法选择与构建

4.1 链路预测的相似性指标选择

文中将用Python模拟无标度网络模型，并将基于相似性的链路预测方法应用到无标度网络模型中，探究针对无标度网络精确度最高的指标。模拟无标度网络共包含200个节点，18 078条边，如图4所示。

图4 模拟无标度网络

模拟无标度网络的度分布如图5所示。

图5 模拟无标度网络的度分布

由图5可知，模拟的无标度网络图严格服从幂律分布。随度值增大，节点数呈指数型下降。将链路预测相似性指标应用于该网络，测评结果如表1所示。

表1 9种相似性指标评测结果

实验结果表明，PA指标在考虑网络拓扑结构的情况下，针对无标度网络是最优的选择。

此外，对于社交网络而言，用户的属性特征具有不可忽视的存在意义。在社交网络这一复杂网络中，用户个体作为网络节点的具象存在，其自身所具备的用户属性因网络的社交性成为一项重要算法指标。因此，文中提出一种基于社交网络关系推荐的混合链路预测算法，它是在考虑社交网络拓扑结构的同时兼顾节点自身特性，改进原有算法，提升链路预测精确度。

4.2 用户属性相似度指标构建

混合算法考虑的社交网络属性包括用户的地域、用户粉丝数、用户关注数、用户的个人标签信息等属性，这些属性将被量化成计算相似度的矩阵，与基于网络结构测量用户相似的PA指标一起构建混合相似性指标，从而计算用户之间的相似度，相似度高的将被推荐为好友。相似程度的衡量是通过计算矩阵之间的余弦相似度来表征的，如式3所示：

sim(x,y)=cos(x,y)+a

(3)

两个向量由用户的属性来充当。x,y分别为邻居节点和目标节点(表示向用户x进行好友推荐)，a为调节变量，通过调整该变量使所有节点都能在计算中发挥作用，避免出现无效状态。

4.3 混合相似性指标构建

结合PA指标、社交网络用户属性特征相似度的混合链路预测公式如下：

PAA(x,y)=Sxy×sim(x,y)=k(x)×k(y)×[cos(x,y)+a]

(4)

其中，k(x)、k(y)为x,y节点的节点度。式中矩阵相乘，代表两个矩阵中对应元素相乘，其结果依然是一个N*N的矩阵(N代表用户数量)。

5 实验结果与分析

实验数据采用的是新浪微博上的部分用户关系数据，数据中包含用户关系以及用户的个人属性信息，如性别、地域、粉丝数、关注度。数据集中共包含用户数9 104人，用户关系数61 297。微博数据集结构如图6所示。

图6 微博数据集结构

结合上文给出的混合相似性指标，本节对微博数据集进行实证分析。具体步骤如下：

步骤1：数据处理，去除无效数据(没有关系连边的用户)；

步骤2：按7∶3的比例产生训练集和测试集；

步骤3：选择PA指标与用户属性值计算混合指标；

步骤4：计算指标精确度并进行比较。

混合指标与PA指标/用户属性相似度对比的试验测评效果如图7所示。

图7 对比试验测评效果

由图7所示，优先连接指标的测量精确度为0.82，用户属性测量的精确度为0.59，文中构造的结合用户属性的优先连接指标的测量精确度为0.89，比原始指标提升了0.07。效果提升较为明显，说明加入用户属性相似度对掌握在线社交网络的整体结构具有一定的积极作用。

6 结束语

通过对复杂网络和链路预测的学习，首先验证了社交网络呈幂律分布，满足无标度网络的典型特性；同时，通过分析微博社交网络数据，得出在链路预测中优先连接指标(PA)表现最优；最后，考虑到社交网络的社交性和用户的个性，在算法中加入用户属性这一重要因子。最终提出了基于优先连接和用户属性的链路预测算法PAA。实验结果表明，PAA算法的AUC值明显大于仅仅考虑优先连接或者用户属性的数值结果，表明该算法可以更加精准地为用户提供好友推荐。