元路径选择和矩阵分解的跨社交网络链路预测*

王 瑶，寇 月，申德荣，聂铁铮，于 戈

东北大学 计算机科学与工程学院，沈阳 110819

1 引言

随着微博、知乎、豆瓣等社交网络的普及，在线社交网络成为人们生活中必不可少的交流工具。依据第42 次《中国互联网网络发展状况统计报告》[1]中的统计，2018 年我国互联网的普及率为57.7%，网民规模有8.02 亿，可以看出互联网发展迅速。网络中的链路预测是指通过已知的网络节点以及网络结构等信息，预测网络中尚未产生连边的两个节点之间产生链接的可能性[2]。

在现实世界里，信息实体是广泛连接的，通过各种各样的连接彼此相互关联，这些连接一起形成不同领域的信息社交网络[3]。现有的链路预测研究工作主要涉及单一的社交网络，通过分析社交网络内用户的结构特征，找出两个节点之间存在链接的可能性。实际上，面向多个社交网络上的链路预测也具有重要意义，单一的网络可能不能满足需求，且单一网络提供的用户信息不如多个社交网络用户信息丰富。利用多个网络上锚链接[4]用户进行网与网连通之后，目标网络的节点信息可以通过源网络的节点信息得到补充，克服由于数据信息稀疏造成的冷启动问题。然而，当前研究具有如下的局限性：（1）网络数据稀疏，发现的链接只占所有链接的小部分，节点特征复杂，节点特征筛选方法不够明确，属性和数据字段利用率不高，节点相关性依赖于网络的特点，不能直接包含在网络中，挖掘信息不够充分；（2）元路径表示信息较少，基于给定的元路径不能全面地捕捉节点之间信息；（3）对于异构社交网络的链路预测研究较少，大部分在同构网络中进行研究。

本文研究了基于元路径的跨社交网络的链路预测。例如，为了在微博中选择可能感兴趣的用户推荐给特定用户，需要分析用户之间的偏好、朋友关系等一系列特征。同时，依据豆瓣转发至微博的用户群体在豆瓣网上分享电影以及对电影的评分等信息，对用户喜爱偏好进行筛选，偏好相似的用户形成连接的可能性越大。

本文的主要贡献如下：

（1）提出了一种结合节点活跃度和边的活跃度的自动提取元路径的跨社交网络链路预测方法，通过锚链接将多网联系到一起，提取符合要求的特征。该方法可以有效提取相似度高的元路径，提高预测准确性。

（2）提出了对元路径相似性矩阵进行矩阵分解的方法，获得一个隐藏特征空间相似性的表示，将网络中与目标类型对象相关的元路径信息显示。该方法可以有效整合个性化信息在网络中表现的社会特征。

（3）提出了基于元路径选择和矩阵分解的ACPMF-LP（autochoose path-matrix factorization-link prediction）时间复杂度上优于对比算法。

本文第2章介绍了链路预测的相关工作；第3章对本文问题进行定义；第4章提出基于元路径选择和矩阵分解的跨网络链路预测模型；第5章提出基于节点和边的活跃度的元路径提取方法；第6章提出了对相似性矩阵的分解；第7章对相应方法进行优化；第8章为实验部分，对提出的模型和算法进行测试；最后对全文进行总结，并指出下一步研究计划。

2 相关工作

最早的链路预测问题是由Liben-Nowell和Kleinberg[5]提出，他们利用邻居节点或路径信息等非监督方法计算相似度值，有Adamic-Adar、Jacard、SimRank、Katz 等指标。接着，Hasan 等人[6]将局部社交网络转换为拓扑图进行预测，提高了预测结果，并利用监督方法将相似性转换为特征向量，即转换为二分类问题进行研究。Lv[7]将链路预测分为三个研究方向，分别是：（1）基于相似性方法；（2）基于最大似然；（3）概率模型。

近年来，随着网络规模不断扩大，一些预测方法无法适应网络的变化，达不到令人满意的计算速度和计算效果[8]，因此又相继提出了同构网络和异构网络的概念。同构网络即节点和边为单一种类的实体，异构网络是节点和边为多种实体的网络。并在异构网络的基础上提出了跨网的链路预测问题。链路预测中基本思路是挖掘特征，特征包括两方面：节点和边。

针对单网上的社交网络链路预测研究，Han 等人[9]提出了异构社交网络上基于元路径PathSim的相似性指标，即将节点对通过不同的关系进行连接，衡量相同类型对象的相似性，但不具有广泛的适应性。为了衡量不同类型节点的相似性，Ni等人[10]提出了基于路径的随机游走模型，但从路径两端分别游走的结果不相同，非对称条件限制了其应用环境。Shi 等人[11]提出了HeteSim 算法度量异构网络中任意节点对的相似性，可以计算不同类型的对象且有对称性；但该方法复杂度高，而且对路径的长度按照奇偶分类比较繁琐。Shang等人[12]提出了基于元路径的ESim 相似性指标的链路预测方法;上述方法中均是在单网上提取元路径，没有涉及多网问题，且元路径是固定给定的，灵活性差，不能准确地切合语境，显示节点之间的本质联系；其他方法主要集中于提取特征和构造模型，对于机器学习难以表达的复杂细节很难识别。

针对网络耦合方面，网络耦合是将高维网络转换为低维空间上相对应的节点，降维后的网络计算链路预测更加便捷。Huang 等人[13]提出了对异构网络的耦合，利用不同节点之间的连边信息刻画不同的元路径，利用损失函数最小化后计算距离进行预测。Swami 等人[14]使用meta-path 的随机游走重构节点的邻居，并运用异构的skip-gram[15]模型求解节点的网络表示,上述方法均在单网上进行研究。

与已有工作相比，本文工作具有如下优势：（1）将多个社交网络中可能存在的链接关系应用元路径自动提取算法进行分类，运用在大规模信息网络中。（2）利用矩阵分解转化为低维、稠密、实值的向量表示网络中的节点，含有语义关系，利于计算存储，自适应性强，且可以将异质信息投影到同一个低维空间中方便进行预测。（3）利用优化策略减少计算时间复杂度。

3 问题定义

给出两个网络1、网络2和训练节点对的信息，利用查找出的元路径对目标节点对之间形成的链接概率进行预测。本章主要介绍对跨社交网络链路预测的定义及问题描述。

社交网络上的链路预测是指通过对网络中的信息进行提取获得特征，预测网络中节点存在链接的可能性的大小。首先，给出相关概念；之后，在此基础上给出基于元路径提取和矩阵分解的跨社交网络链路预测问题的描述；最后，给出相关的解决方案。

定义1（社交网络）给定G(V,E)来表示社交网络，其中V代表用户集合，E代表用户间的关系集合。

定义2（网间链接）存在于多个网络之间的网间链接，例如给定两个异构社交网络Gs、Gt，以及两个用户vi∈Vs⊆Gs,vj∈Vt⊆Gt，即vi和vj是两个不同社交网络的用户节点集合，若在现实生活中两个用户为同一个用户，则称两者之间存在链接。

定义3（元路径[8]）定义在网络模式上的存在链接的两类对象的一条路径，即表示对象类型之间的一种复合关系，R1°R2°…°Rl，其中°代表关系之间的复合关系，Ai表示对象类型，Ri表示关系类型。

定义4（节点活跃度）节点在不同元路径的活跃度不同，在某条元路径上邻居节点越多，代表在此元路径上越活跃，对网络结构的影响越大。

定义5（边活跃度）假设两个节点的连边在多条元路径上均出现过，这条边在网络中的活跃度比其他边要高。

定义6（基于元路径耦合的跨社交网络链路预测）给出m个社交网络的用户信息社交图Gi(i=1,2,…,m)，给出在网络Gi中两个目标对象(i,j)，找出两个目标用户之间形成连接的概率。

4 基于元路径选择和矩阵分解的跨社交网络链路预测模型

如图1 所示，此模型包括跨社交网络构建、对节点特征进行处理、元路径的自动提取、提取潜在空间特征和预测四部分。

Fig.1 ACP-MF-LP model framework图1 ACP-MF-LP模型框架

4.1 跨社交网络构建

不失一般性，本文以两个社交网络为例，介绍两个网络如何构造关联。如图2 给定网络G1、G2为微博和豆瓣两个社交网络，图中用户1和用户2是同一实体在不同网络上的同一用户。利用这种连接关系将两个网络融合为一个网络。跨社交网络的构建是给定源网络和中间的锚链接，确定目标网络中相关节点之间的链接的可能性大小。如图2 为跨网络的连接，图2中有两个网间链接，用户1和用户2是同一个用户，用户3和用户4是同一个用户。利用网间的锚链接[4]将两个网络连接起来。

4.2 ACP-MF-LP模型的基本思想

如图1 所示是基于元路径选择和矩阵分解的ACP-MF-LP 链路预测模型框架，首先对网络节点进行特征处理，之后利用节点和边的活跃度利用ACP算法对元路径进行提取，对元路径进行整合后计算相似性矩阵并进行矩阵分解，最后利用集成分类方法选择最优解结果。

（1）元路径的自动选择

已有方法基于的是给定的元路径集合，现实的社交网络数据巨大，对元路径不能一一列举，也不能充分地表示训练集合中用户节点之间的关系，因此需要提出一种可以针对网络进行自动筛选元路径的方法，能够将提取的元路径特征按照不同的贡献权重表示出来。

Fig.2 Connect across social networks图2 跨社交网络连接

（2）基于相似性矩阵的分解

将提取的元路径按照不同的权重整合后对给定的用户节点进行预测，得到对用户之间相似性的衡量矩阵，对相似性矩阵指标进行矩阵分解，可以得出在隐藏空间中的相似性特征，从而更好地进行链路分析预测。

4.3 对节点特征进行降维处理

在属性较多的情况下，例如在微博网络中，一个用户的属性可能包含用户名、爱好、关注用户、关注话题、转发话题等一系列特征。这些特征之间可能存在相关性，不利于对特征进行挖掘；因此采用主成分分析（principal component analysis，PCA）方法对数据属性进行降维，在确保数据信息丢失最少的原则下，用较少的综合变量代替较多的变量，且变量之间的相关性最小。

输入的源网络中的节点V∈(V,I)，V表示节点的集合(V1,V2,…,Vm)，I表示节点的属性(I1,I2,…,In)，将这n维特征映射到k维上(k

算法1特征处理算法

输入：特征属性矩阵Am×n，k为需要提取的k个特征。

输出：降维后的特征矩阵A'm×k。

1.Fori=1 tom

2.Forj=1 ton

3.uji=+aji

4.End for

6.Forj=1 ton

8.End for

9.End for

10.求出矩阵A′m×n的协方差矩阵Cn×n

11.求出协方差矩阵的特征值及对应的特征向量

12.对特征值进行排序求前k个特征值对应的特征向量组成矩阵A′m×k

13.输出A′m×k

算法的1～5 行为将矩阵的每一列属性进行均值化；6～9 行对每一列属性进行零均值化；10 行求出零均值后矩阵的协方差矩阵；11 行计算协方差矩阵的特征值和特征向量；12～13 行从大到小将特征值对应的前k个特征向量组成矩阵即为降维后的特征值矩阵。

5 基于节点活跃度和边活跃度的元路径选择

元路径为链路预测提取的特征，因此利用用户节点的活跃度和边的活跃度来选择元路径，之后计算每条元路径的权重，衡量元路径对预测的贡献程度。

5.1 元路径下的节点活跃度

节点在不同元路径下的活跃度：两个对象之间可能在不同领域形成连接，在某个元路径下的邻居数越多，互相影响越大，可能形成连接的可能性越大。因此，可对节点在某个元路径下的活跃程度进行衡量。

元路径p下的节点u的活跃度为：

其中，Γu,p是节点u在元路径p条件下的邻居节点集合，|Γu,p|是节点u在元路径p下的邻居节点数，|Γu,P|是节点u在网络中的所有元路径P中邻居节点数。假设在元路径p下的节点u的邻居数量占总邻居数量的比例越高，说明在元路径p下节点的活跃度高，这条元路径是u主要的交互途径。

5.2 元路径下的边的活跃度

两个节点间的连边在多条元路径下都存在，说明这条边关系紧密；其次，边的活跃度计算有助于消除节点间建立关系时的条件影响。例如在元路径p1条件下两个节点建立20次关系，而在元路径p2 条件下建立5次关系，如果选择了元路径p2，则建立条件较低可能会带来弱关系的连边。因此，通过建立边的活跃度可以降低产生弱连接的概率。

元路径p下的边e的活跃度为：

算法2自动筛选元路径算法ACP(G,φ)

输入：G=(V,E)，φ为训练的节点集合，θ为阈值。

输出：γ为选择的元路径集合，M为在元路径γ下每个训练集合的相似性矩阵。

1.建立初始结构，把元路径候选集插入T

2.WhileT∉∅do

3.m←{0,0,…,0};/*长度为|φ|，训练集节点对在元路径上匹配的相似性*/

4.W←选择候选集T中相似性分数S最大的集合

5.For每个节点对(i,j)∈Wdo

6. If(i,j)∈φthen

7.m←S=VA(i,p)*VA(j,p)*EA(ij,p);end for

8.Ifm中有非0元素then

9.将W中的元路径Π加入到γ中

10.M←M⋃m；

11.Break；

12.Else

13.新建一个空的集合E；

14. For每个节点对(i,j)∈Wdo

15. Forj的邻居节点s∈Vdo

16.ed←j到s节点的边的类型，d=1 表示正向，d=-1表示反方向；

17.IfE中没有这种边的类型then

18.将ed加入到E中；

19.Π←E中元路径；

20.计算m(i,s)的值；

21.End for

22.End for

23. For每个结构K∈Edo

24.K.S=∑m(i,j)

25.IfK.S>θthen

26.将结构K加入候选集T；

27. End if

28.End for

29.Returnγ,M

算法的5～8 行是对节点对之间的相似性进行计算；9～12 行是对相似性分数值最高的候选集对应的元路径进行提取；13～23行对节点对进行广度优先搜索，把元路径的种类列举出来；24～29 行把阈值内的集合加入候选集中，设置阈值是为了防止路径无休止迭代下去。

5.3 元路径的权重计算

按照以往元路径不加以权重区分的情况下，例如图3是微博中对用户-话题-用户（U-T-U）这条元路径进行计算时相对应的用户之间相似性矩阵。利用PathSim 计算，针对不同的用户用同样的权重衡量时，则用户之间的相似性如图3 上部分所示，用户2和用户1、用户3之间均存在相似性；而实际情况是在相同的话题上用户1和用户3更具有一致的偏向性，即拥有相同兴趣爱好，形成链接的可能性越大。因此，元路径针对不同的用户权重也不相同，从而对元路径权重进行衡量，能使得预测模型更有针对性。

Fig.3 User similarity by different weights on meta-path图3 不同权重元路径衡量用户相似性

权重的大小衡量了元路径在用户关系之间起的作用，两个用户在某条元路径下相似性大，关系紧密，但在另一条元路径下，关系稀疏。因此，不同元路径对同一实体相似性的衡量指标不同。对提取出来的元路径进行整合，计算不同元路径对网络的影响权值，设置每条元路径Π的权值ωi(i=1,2,…,|γ|)，且，使用分类方法中的线性回归对g(ω)={ω1M1+，其中Mi是训练集在每条元路径下的相似性值的大小，对{ω1,ω2,…,ωγ}进行训练，设置目标函数为，利用批量梯度下降的方法迭代更新ω的值。

最后一项是为了防止过拟合，{ω1,ω2,…,ωγ}为不同元路径对预测产生的影响程度，即各个元路径特征在预测中的作用，基于训练集的线性回归方法获得{ω1,ω2,…,ωγ}的值。g(ω)的值为两个节点在元路径下的相似性分数。

6 基于元路径相似性矩阵的分解方法

求解出元路径及所有元路径的权重ωi=[ω1,ω2,…,ωi]后，对每条元路径对应的结构特征进行加权组合，得出节点之间的相似性矩阵，然后使用矩阵分解MF选择潜在空间最大的特征向量，发现节点之间潜在特征，去除不同元路径之间的相关性。

具体的算法流程如下：

算法3提取潜在空间特征的矩阵分解算法

输入：根据元路径得到的相似性矩阵Mij、迭代次数steps，选择K维，正则化参数α、β，阈值τ。

输出：矩阵分解后的矩阵MiK、MKj、M′ij。MiK和MKj为矩阵分解后的特征矩阵，M′ij为矩阵分解后节点之间相似性矩阵。

1.MiK、MKj～N(0,δ2)/*根据正态分布矩阵变量初始化，生成随机矩阵*/

2.Forstep∈(0,steps)do

3.Forp∈(0,i)do

4. Forq∈(0,j)do

5.error=Mpq

6. Fork∈(0,K)do

7.error-=Mpk×Uqk

8. Fork∈(0,K)do

9.Mpk+=α(2×error×Mqk-βMqk)

/*基于梯度下降的优化方法，将元素更新*/

10.Mkq+=α(2×error×Mpk-βMkq)

/*基于梯度下降的优化方法，将元素更新*/

11.M′pq=Mpk×Mkq

12. End for

13.End for

14.End for

15.loss=0

16.loss+=(M′pq-error)2/*计算每一次迭代后损失值*/

17.Ifloss<τ

18.Break

19.End for

20.ReturnMiK、MKj、M′ij

7 优化策略

7.1 利用树结构解决元路径的选择

利用树的结构有三方面的优势：首先在启发式的搜索方式中可以减少搜索空间，其次计算多个节点对的元路径可以最大限度地减少共同计算的次数，通过使用树结构显示可能出现的路径；树结构可以回溯重新使用，进行多次扩展。

在图4 中，每个树的节点存储的是一系列节点对，树的边存储的是元路径的种类。

算法4元路径搜索树的算法ACP-T（AutoChoose-Path-Tree）（G，g，l）

输入：图G，节点对g(u,v)，元路径长度l。

输出：元路径p。

数据：树T。

1.初始化根节点T

2.Whileu可以扩展do

3.While 节点n是u的邻居and 树的深度

4.将(u,n)加入到T的一个节点的集合中；

5.并将根节点到边类型作为一条元路径放入p中；

6.将T的子节点作为T继续进行搜索，直到不符合条件为止；

7.End if

8.输出符合要求的元路径集合p

Fig.4 Structure of tree图4 树的构造

7.2 节点类的选择

在真实的数据集中，节点可以有很多类。例如：微博中某个明星既有演员的身份，又有作家的身份。这些类如果不按一定的规则约束，会增加满足元路径的条数，之前的方法并没有规定节点的类型，这里提出规范节点类型的方法。即用标签的分数LableScore确定节点类的属性。

其中，a(φ)是节点对中符合类型的数量，b(φ)是在数据集中符合类型的数量。

如图5 是将节点的标签列举出来。例如：节点（明星）对应图4中（1,2）和（3,4），即节点对有2个，则a(φ)=2，在整个数据集中，假设有b(φ)=42 个，则，比其他节点标签按分数值计算得要大，因此将明星作为节点的类标签，作为元路径中的节点标签。

7.3 基于集成分类器的模型优化

一般用于分类的算法应用于链路预测问题上时，都会忽略样本少的类别，达到最大化总体分类的精度，因此不能得到很好的分类效果。

Fig.5 Node tag图5 节点类标签

在链路预测问题中，正例样本和负例样本的数据不平衡是普遍存在的，因此将数据分为多个同少数类样本数相同的数据，获得多个相同数量的数据子集。对每个数据子集进行学习，建立多个分类器，最后通过投票方法集成分类器，使得集成的分类数据效果最好。

如图6 所示，这部分由平衡数据、创建基本分类器、集成分类器三部分组成。这样做既没有添加网络额外信息，也没有忽略原有信息，保持了样本分类情况。采取将大多数类随机取样，无放回地放入每个集合中，这样保证每个训练集合中正例和负例的样本数量相等，就能避免数据不平衡的问题。

Fig.6 Ensemble classification flow chart图6 集成分类流程图

8 实验与分析

在本章中，基于提出的链路预测模型，在数据集微博-豆瓣上测试本文提出的算法。

8.1 数据集

本文使用的数据集为真实的微博-豆瓣数据集，微博-豆瓣数据集包括抓取的用户信息，用户之间的评论和关注话题，豆瓣用户以及用户对电影评分、电影导演及演员等信息。具体信息如表1 所示。在提取元路径时选择阈值θ为0.8。

Table 1 Weibo-Douban statistics of datasets表1 微博-豆瓣数据集统计

8.2 实验设置及对比实验

将本文提出的ACP 算法与已有的算法进行对比。评价指标：一是AUC（area under curve），用来衡量链路预测算法的精确度；二是精确度Precision，定义在前L个预测边中预测准确的比例；三是运行时间。本文比较了以下算法在表1 数据集上的运行效果。

PathSim[9]：每条元路径是按相同的权重进行计算，即按两个对象之间元路径的条数进行计算。

PCRW（path-constrained random walks）[16]：基于随机游走的相似性计算方法，利用路径衡量对象之间游走的相似性大小。PCRW-X中X代表的是元路径的长度，即元路径规定在2到4之间取值。

ACP：本文提出的自动选择元路径的方法。

ACP-T：优化查找元路径的方法。

实验环境：Intel®CoreTMi7-6700，8GB内存，3.40GHz，操作系统Windows 8。

8.3 实验和结果

（1）预测性能比较

Fig.7 ROC curve图7 ROC曲线

由图7可以看出，ACP相较于其他方法可以选出更有用的元路径表示节点之间的关系，在实验参数选择最优的情况下，可以看出本文提出的算法在精确度ROC上优于基础算法。

（2）权重的影响

提取的元路径的权重可以分为：设为统一的权重1，即为PathSim 的方法；设为随机的元路径权重；设为经过学习的权重。很明显，由图8 可以看出，通过权重学习的元路径预测效果要好于其他两种。由于基于随机分配的权重可能使得关联程度大的元路径分的权重小，因此基于随机的元路径权重效果最差。

Fig.8 Influence of weight图8 权重影响

（3）训练集大小的影响

实验比较了不同训练集大小对预测准确性的影响，从图9 可以看出，在一定范围内随着训练集数目增多，预测效果变好；训练集数目超过一定范围之后，训练集的大小对预测结果影响不大；因为训练集数量少不能挖掘充分的元路径，训练集过多则可能导致引入过多的噪音，所以设置合适的训练集可以节省空间和训练性能高的预测模型。

Fig.9 Influence of training size图9 训练集大小影响

（4）矩阵分解中K、α、β值选择

在实验数据集上，选取正则化参数α、β和阈值τ为最优值的前提下，观察K取值不同对实验结果造成的影响。由图10可以看出，随着K取值的增加，实验结果AUC的值也在不断增加，当AUC值增加到一定值时，随着K的增加，AUC 值趋于平缓；由此看出K的选择过小，用户之间的隐式特征不能很好地表现出来，如果K值过大，则计算的复杂度就会增大，造成过拟合。

Fig.10 Influence of K图10 K值影响

在K=15 且α选择取最优值的前提下，图11 是β在区间[0,0.2]上的预测精度。由图11可以看出，β参数的改变能够影响预测精度，在某个区间呈现上升趋势，在β=0.08 时达到最优值。

Fig.11 Influence of parameter图11 参数影响

在K=15 且β选择取最优值的前提下，图11是α在区间[0,0.1]上的预测精度。由图11可以看出，α参数改变能够影响预测精度，在α=0.02 时达到最优值。

（5）运行时间比较

实验比较了几种算法在元路径固定长度为2～4下的运行时间以及不同训练集下时运行时间的比较。从图12可以看出，在给定元路径长度的情况下，随着训练集数目的增多，运行时间也在增加，总体上本文提出的算法在运行时间上优于对比算法；随着元路径数目的增加，基于随机游走的方法PCRW-2到PCRW-4运行时间明显增加，本文提出的算法更适用于元路径数目较多的情况下；在此基础上，提出利用树结构存储元路径，可以便于遍历和回溯，能够有效提高运行时间。

（6）类标签的选择

在选择类标签的时候，最好的方法是选择最具代表性、LabelScore分数高的类别作为元路径节点对象，实验比较了进行类标签选择和不进行类标签选择情况下的ROC的值。从图13可以看出，进行Label Select之后预测效率提升。

Fig.12 Running time图12 运行时间

Fig.13 Influence of label selection图13 类标签选择影响

9 总结

本文提出了一种将多个网络联系到一起进行链路预测的模型。提出了一种结合节点活跃度和边活跃度的自动提取元路径的方法，在此基础上改进方法，从而实现对特征提取的目的，解决了对于用户给定元路径造成信息提取不够完善的弊端。本文提出的链路预测方法通过实验证明在召回率、准确率和运行时间上达到基本满意的效果。下一步，将本文的预测方法扩展到动态的多个网络，使其更加符合现实情况，并设计出更高效的特征选择方法。