基于LBSN中锚链接方法的链路预测模型

黄寿孟，夏王霞

(三亚学院 信息与智能工程学院，海南 三亚 572022)

0 引言

大数据环境下的社交网络，数据具有多维性和关联性，那么如何充分利用好这些特性呢？这就需要构建数学模型来挖掘出这些数据之间的潜在关系信息，比如基于地址位置的社交网络(Location-based Social Network，简称LBSN)，一般包含两种数据[1]67：一种是网络中用户本身的数据，另一种是用户间存在的关系数据。从LBSN中挖掘出用户间的时空信息进行各种应用活动[2]79，比如好友推荐[3]7、兴趣推荐[4]、轨迹恢复[5]108、行为预测[6]120等应用场景。其实在社交网络分析中，链路预测一直是信息推荐系统的研究热点，它是从网络中已知节点信息找出可能存在节点链接的信息。就目前社交网络而言，在链路预测领域，可根据用户签到记录和社交网络两种数据来实现信息推荐。Li Zhepeng等人[1]1938提出在LBSN中这两种异构数据融合的预测方法，利用网络表示学习和矩阵分解数据节点信息，通过拼接融合方案完成预测任务。Hu Wei等人[2]206运用概率学方法将网络用户时间行为与社会理论融合构建链路模型。Li Jichao等人[7]10利用网络结构与节点形成时间的关联信息构建预测方法，而Liang Wenxin等人[8]1111量化用户节点社交图属性、用户档案信息和移动特征之间的关联来建模预测好友关系，并综合用户话题特征和节点拓扑结构构建联合预测模型。Ling Jiang等人[9]211研究了网络交叉视图，通过学习链路表示与用户属性表示来完成链路预测任务。从不同角度完成复杂网络链路预测任务的还有异构数据源进行混合预测[10]305、基于聚类分析[11]144、从信息学分析角度[12]、基于节点局部相似性[13]、基于资源传输匹配度[14]、基于互信息[15]57等。为了进一步提升链路预测性能和准确度，本研究提出一种锚链接方案取代文献[1]中的数据拼接融合方案[1]1938，更深入挖掘LBSN中节点链接信息及其关联，锚链接节点就是两种不同数据的公共节点，它们的映射关系由神经网络算法完成。

1 相关工作

1.1 网络表示学习

提取网络节点的信息方法有很多，目前比较流行的是网络表示学习方法[16]，它是运用深度学习技术对网络空间量化降维过程，从而提取出网络中各节点的特征向量。如图1所示，Deep Walk[7]12实现网络表示学习获取用户节点向量化的大致流程。

图1 网络表示学习流程

目前在LBSN的好友推荐领域，利用网络表示学习可以完成低维空间向量表示、节点分类与聚类等任务，通过挖掘社交用户网络拓扑结构中的潜在关系规律及特征，对LBSN网络关系进行建模，得到以向量表示出LBSN社交关系拓扑结构中的各用户节点和各节点之间的用户关联信息。

1.2 矩阵分解

矩阵分解其实是一种矩阵的变换方法，为了完成矩阵的降维任务，将原矩阵拆分为多个相关联的矩阵[17]。推荐系统中常常使用矩阵分解来过滤某些数据从而完成推荐任务[18]。比如用户给电影打分，假设从观影购票系统获取所有数据，构建出用户评分表，如图2所示，行值为用户ID，列值为电影ID，符号？表示缺失评分值，即某用户对某电影未观看不评分的现象。现在需要预测出这些缺失的评分值(假设分值范围为1～5)，首先将评分表矩阵分解为用户矩阵与电影矩阵的乘积关系，希望相乘结果与原评分矩阵的分值尽可能接近(损失函数的条件)，经过不断的迭代多轮训练优化后得到收敛模型(即损失函数)，从而将相乘得到的新矩阵代替原矩阵中缺失的值，即预测出该用户对未观看的电影兴趣值。

图2 矩阵分解观影评分图

1.3 相关的预测模型

Walk2friends[15]57模型仅提取用户移动特征；DeepWalk[7]15模型通过游走方式提取用户节点序列；LINE[9]211模型采用节点共现与条件概率建模；GraRep[2]81模型构造转移矩阵提取节点相似性；Node2vec[11]144利用网络局部与全局属性提取节点的领域；Struc2vec[8]1111模型捕获节点结构向量化建模。本研究采用节点信息(用户签到记录)和节点结构关系(矩阵表示)来进行潜在关系建模，并使用锚链接算法将两者数据融合进行点对关系的向量化，通过训练集与测试集来优化预测性能。

2 预测方法

2.1 基本定义

任意两个社交网络Gv=(Uv,Ev)和Gn=(Un,En)，传统锚链接方法直接预测两个用户ui∪Uv和uj∪Un是否同一个人(即ui=uj)，而本文构建AL-P模型是通过两个LBSN中的共同用户来调整两者的向量空间，即锚链接满足二进制鉴别函数φ：Uv×Un→{0,1}，其对应的公式为

其中：()DEC表示用户节点的向量编码，即节点相似度的量化值；()ENC表示最大维度保存网络属性，即节点向量化维度值；P()是由用户定义的节点间相似性度量值。

2.2 预测模型

图3 AL-P预测模型

2.3 锚链接算法

输入：两个异构网络Gv和Gn；预训练函数φ和F；参数W和b，有标签的锚链接集合Ev。

1:repeat

2: for each epoch do

3:for i = 1 to N do

6:根据更新参数W和b

7:end for

8:计算y=Ftrue和a=o′(Fpredicted)

9:再次更新参数W和b

10:end for

11:until 收敛

3 实验分析

3.1 实验准备工作

本实验采用基于LBSN的Gowalla和Foursquare两种不同的开源数据集[9]213(其中@NY表示纽约，@TY表示东京，@WHG表示华盛顿，@CCG表示芝加哥)，如表1所示，从中提取用户关系拓扑图和用户签到记录，以及对相关数据进行预处理操作，其结果如下表2所示。

表1 实验数据集情况

表2 数据预处理结果

本实验对照基准模型有Walk2friends[5]108和DeepWalk[6]122，其中Walk2friends提取用户移动特征，而DeepWalk提取用户节点序列，两种模型的操作方法统一用随机选择平均Average。评估指标有AUC、精度、查全率和F1值(精度与查全率的调和平均)。

3.2 实验结果

评估指标AUC可以检测链路预测模型的性能，它表示正/负样本的概率值，其实验结果如表3所示，说明在不同的数据集中，AL-P模型的AUC值都优于现有模型Walk2friends，DeepWalk，LINE，GraRep，Node2vec和Struc2vec，这里的数据融合操作统一采用Average操作。

表3 AL-P的AUC预测结果

对于Foursquare数据集(@NY与@TY)和Gowalla数据集(@WHG与@CCG)，完成评估指标精度、查全率、F1值的衡量实验，其中表4是Foursquare数据集的预测结果，表5是Gowalla数据集的预测结果。从表4和表5中可以得到在链路预测任务中，AL-P预测效果在两个数据集中是最佳的，这是因为AL-P模型加入用户签到偏好信息，让社交网络信息比用户移动信息更具有指示性，有效提升链路预测的准确度，而walk2friends结果差是由于预测时缺少用户网络结构信息。

表4 Foursquare数据集的预测结果

表5 Gowalla数据集的预测结果

4 结语

为了提升链路预测的效果，本研究提出一种锚链方法，通过用户向量对齐完成两个异构空间的映射，得到新的用户访问偏好向量，训练融合后更新出社交关系向量，从而进一步提升链路预测的综合性能。不足之处是从移动数据和社交数据中如何学到更好的用户表示，挖掘相关用户数据的潜在价值，若在时空行为上建模，则能更好完成预测任务。

(责任编辑：潘姝静)