融合社交信任的多属性元路径好友推荐方法
2020-10-20朱文强
朱文强，徐 军
1(江西财经大学 软件与物联网工程学院，南昌 330013) 2(江西财经大学 统计学院，南昌 330013)
1 引 言
随着社交网络的蓬勃发展，好友推荐成了社交网络的重要服务之一[1].如Facebook会基于用户手机号、邮箱地址、MSN号等属性信息为用户进行好友推荐，微信提供了“摇一摇”来进行基于地域距离的好友推荐，QQ则可根据共同好友数量或手机通讯录进行好友推荐，新浪微博也提供了为用户推荐微博好友的功能.通过好友推荐，用户可快速扩展朋友圈，使信息来源变得丰富多样，进行更好的信息共享、过滤和筛选，从而使目前Internet上的信息过载问题得以缓解.
好友推荐的主要任务是为用户推荐好友候选人，以便他更加有效的选择朋友，因此最大的挑战是如何精确的计算目标用户的需求，为其发现他真正需要的朋友[2,3].现有的好友推荐方法大致可以分为三类：基于友情关联的好友推荐，基于用户属性特征的好友推荐和基于位置的好友推荐.
其中，基于友情关联的好友推荐是根据用户的交互、情感表达或社交相似度等进行好友推荐.因为用户可以看成是节点，而友情关联可以看成为边，因此这类推荐方法通常也可被解释为链路预测推荐方法[4].
基于用户属性特征的好友推荐，是根据用户的属性特征内容，进行兴趣点分析，进而计算用户之间的兴趣相似度，为目标用户进行候选好友推荐.该类推荐方法基于以下假设，具有共同兴趣的人，往往在情感上更加容易有共鸣，因此可以基于用户属性特征进行好友推荐[5].
基于位置的好友推荐，则是根据用户之间的地域距离和日常访问地点来进行好友推荐.人们的活动范围通常都只局限于某一地理区域，在该范围的用户如果有一些经常访问的共同地点，则他们之间可能有共同的行为习惯，因此也具备成为好友的可能性[6].
基于友情关联、用户属性和位置的好友推荐，本质上都可解释为基于异构网络的好友推荐.然而，上述的好友推荐方法大多基于用户的兴趣偏好、行为轨迹或社交信息来为目标用户推荐候选好友，未考虑好友推荐所基于的社交网络的异构网络特征，同时也容易受到恶意用户的托攻击，从而使目标用户的利益受到损害[7,8].
基于上述分析，本文提出了一种融合社交信任的多属性元路径好友推荐方法，该方法分析了在线社交的异构网络特征，使用元路径理论对好友推荐的异构网络进行抽象和形式化，提出了ULTNM(User Local Trust Network Model)信任模型.该信任模型考虑了元路径上的用户社交圈子相似度和统计兴趣偏好相似度等多种属性特征，构建了目标用户的本地信任网络，并通过Ford Fulkerson算法对信任网络进行搜索和排序，进行目标用户的候选好友推荐.基于真实数据集的对比实验表明，该推荐方法有更好的推荐准确率和召回率，能更好的对抗恶意用户的托攻击行为，且运行效率具有一定的优势.
2 相关工作
有效的好友推荐，能迅速扩大用户的社交范围，增加用户的社会影响力，为用户提供有效的感情联络、信息咨询及资源共享等功能，成为了当下推荐系统的研究热点.现有的好友推荐方法大致可分为以下三类.
1)基于用户之间的友情关联，进行好友推荐.Zheng等人[9]从最大化用户社交影响力的角度进行研究，考虑多路径友情传导，计算用户的社会影响力扩散效果，提出了一个概率近似为1-1/ε的贪婪好友推荐算法.基于好友关联、用户的历史评价和项目的评论标签，文献[10]提出了一个混合好友推荐算法GBLP(Group-Based Link Prediction Model)，该模型先通过不同的社交属性特征来区分社交圈子，然后计算用户的社交圈子归属度，并将归属度融合进用户的社交目的模型，进而为目标用户进行好友推荐.Yang等人[11]基于交互频率对用户进行区分，并根据用户的属性特征进行社交网络相似度计算，最后预测用户的交友兴趣和目的.文献[12]将好友推荐分为两个阶段，首先，它根据用户发布的信息和友情关联来进行候选好友筛选；在此基础上，利用用户的兴趣属性特征来进行结果修正，取得了较好的实验效果.
2)基于用户的兴趣属性特征，进行好友推荐.Khalid等人[13]通过融合蚁群算法、社交过滤、授权得分等内容，提出了一个基于云框架的优化好友推荐算法，在好友筛选的过程中，使用了好友兴趣相似度来进一步提高推荐算法的精度.通过研究推荐方法的属性选择过程，Ding等人[14]提出了一个有效的属性过滤方法，以过滤掉不相关和冗余的用户属性特征，从而提高好友推荐方法的效果.文献[15]研究了用户的活动频率数据，设计了一个FP-Growth增长模型来预测用户的活动趋势，并使用多层阈值过滤来过滤用户的行为数据噪音，提出了一个FRF好友推荐框架为进行好友推荐.用户之间的友情常常是主观的，因此模糊数学在表示好友关系方面有较好的优势，文献[16]在用户标签和项目描述的基础上，构建了两个模糊数据集，提出了使用模糊关联来表达用户签名的概念，通过为每个用户构建用户签名，可以更精确的找到用户兴趣点，从而产生相似性好友推荐.
3)基于用户的地理位置信息，进行好友推荐.Lin等人[17]通过对现有的好友推荐算法进行分析研究，提出了三个改进后的好友推荐方法，即基于社交相似度的好友推荐方法、基于经典协同过滤的好友推荐方法和基于用户地理轨迹签到信息的好友推荐方法，并使用线性框架对它们进行融合，取得了较好的实验效果.通过对用户的居住点和活动区域进行区分，文献[18]提出了一个基于区域挖掘的好友推荐方法，该方法使用θ-ADBSCAN区域算法来挖掘用户所在区域的日常活动轨迹和居住点，并使用分段活动地点和用户活动轨迹来代替用户区域，然后将这些内容转化为多层次的地理位置编码，最后基于这些内容对用户的行为相似性进行分析，进行好友推荐.用户的线上好友信息和线下活动行为是用户交友倾向和位置偏好的重要参考内容，基于此，文献[19]提出了一个基于用户位置偏好的好友推荐方法，取得较好的实验对比效果.
另外，从信息安全的角度考虑，也有不少研究人员对好友推荐的隐私保护进行了分析研究.为避免好友推荐的随机性和不可靠性，文献[20]基于隐私保护协议提出了一个安全有效的好友推荐框架，当目标用户发送好友请求到授权中心时，授权中心通过基于隐私保护的标签匹配从所有用户中选出好友候选人，并根据他们与目标用户的相似性阈值来为目标用户进行好友推荐.Zhang等人[21]针对目前好友推荐方法中存在的身份窃取和隐私泄露等问题，提出了一个K度匿名好友推荐框架，该框架首先建立了在线社交网络超图，然后提出边分割算法来隐藏用户的身份信息和社交关系，再根据用户的兴趣特征，来计算用户之间的相似性，最后融合用户相似性和边分割算法进行好友推荐.
综合分析，现有的好友推荐算法存在以下问题：
1)未深入考虑好友推荐所基于的社交网络的异构网络特征，导致好友推荐准确度不高.
2)大多基于用户的兴趣偏好或行为轨迹来进行好友推荐，不能有效抵御恶意用户的托攻击，导致目标用户的利益受损.
3)基于整个用户-用户社交矩阵和用户-项目评价矩阵计算用户之间的隐含友情关联，计算工作量较大.
3 ULTNM信任模型
3.1 理论基础
3.1.1 异构网络
异构网络是指存在不同性质节点的信息网络，可采用三元组G
图1 好友推荐所基于的异构网络结构Fig.1 Example of heterogeneous network for friend recommendation
在本文中，我们将好友推荐所基于的社交网络构建为带权值的异构网络，用四元组G
1)U={u1,u2,…,un}为用户节点集合，n为用户集的大小；
2)I={i1,i2,…,im}为项目集合，m为项目集的大小；
3)E=EUU∪EUI∪EII为异构网络中所有边的集合.EUU={uk,uj|uk∈U,uj∈U}表示用户之间的边集合，即他们之间的社交关系；EUI={uk,ij|uk∈U,ij∈I}表示用户与项目之间的边集合，即用户与项目的使用关系；EII={ik,ij|ik∈I,ij∈I}表示项目与项目之间的边集合，即项目与项目之间的关联关系.在本文中，我们认为是EUU有向边,因为用户之间的友情往往不是对等的，比如用户A认为用户B是他最好的朋友，但反过来不一定成立.EUI同样也是有向边，因为只存在用户使用项目的情况.而EII是无向边，即两个项目相关的话，他们是对等的.为了方便处理，我们统统将这三类关系作为有向边进行计算；
4)W=WUU∪WUI∪WII是异构网络中边的权重.WUU={w(uk,uj)|(uk,uj)∈EUU}表示用户边的权重集合，即他们之间的社交亲密程度；WUI={w(uk,ij)|(uk,ij)∈EUI}表示用户与项目之间权重集合，即用户对项目的偏好程度；EII={w(ik,ij)|(ik,ij)∈EII}表示项目与项目之间权重集合，即项目与项目之间的相似程度.
3.1.2 元路径
元路径(meta-path)主要用来描述异构网络中节点间不同连接类型[22].元路径的相关定义如下.
根据六度空间理论[24]和三度影响力理论[25]，在社交网络中，3跳以内的连接可信度较好，而3跳以外的连接可信度相对较弱，因此本文主要考虑路径长度不大于3的元路径，元路径集包括以下几类.
Ⅰ类元路径：U-U-U与U-U-U-U，目标用户与好友的好友具备成为好友的可能性.U-U-U和U-U-U-U元路径是本文好友推荐算法所基于的主要元路径，称之为I类元路径.
Ⅱ类元路径：U-I-U，对于有相同项目兴趣的用户，他们具备成为好友的可能性.
Ⅲ类元路径：U-I-U-U，目标用户与有相同项目兴趣用户的好友，也可能会成为好友.
Ⅳ类元路径：U-U-I-U，如果目标用户的好友与其他用户具有相同项目兴趣，那么目标用户与这些用户也具有成为好友的可能性.
3.1.3 Advogato信任模型
本文认为好友的产生和延续，其主要基础为社交信任和兴趣偏好，兴趣偏好决定两个用户能否成为好友，而社交信任决定友情的持续性[26].
Advogato是经典的信任模型，在检测入侵、识别可信用户方面尤为有效，在构建节点信任网络方面也有较好的优势，因此本文基于Advogato信任模型研究这四类元路径所构建的信任网络[27，28].
构建Advogato信任模型需要用到3个定义.
信任容量(Trust Capacity)，节点扩展其他节点信任网络或构建自身信任网络的能力.
信任流量(Trust Flow)，当前节点根据自身对后续节点的信任程度，而分配到信任边上的权重内容.信任流量越多，分配给后续节点的信任容量越大，后续节点扩展信任网络的能力也就越强.
源节点，也称为Seed节点，拥有最大的信任容量，用来作为整个信任网络的根节点，即授权中心.整个Advogato信任网络构建在源节点之上.
Advogato信任模型的构建可分为3个步骤.
第1步.确定当前节点，然后使用广度优先搜索算法搜索后续节点，并根据公式(1)为其分配信任容量.
(1)
其中，Capsuc代表后续节点的信任容量，Capcur代表当前节点的信任容量，(out-degree)cur为当前节点的出度.通过这一步，便得到了整个信任网络中每个节点的信任容量.
第2步.对整个信任网络中的节点进行处理，转换为Advogato信任网络(图2所示).步骤为：每个节点被拆分为正向节点和负向节点；节点的信任容量减去信任阈值1并使其流向正向节点；减去的信任阈值注入称为超级汇点的节点上(superlink).
第3步.使用文献[29]的Fold-Fulkerson算法对新的信任网络进行网络最大流增量路径查找，以获得源节点信任网络中的可信节点集合.
基于Advogato信任模型，本文提出了目标用户本地信任网络模型ULTNM(User Local Trust Network Model)，其与Advogato模型存在以下区别.
1)Advogato信任网络只有一个或几个源节点，而ULTNM模型则将每个用户当成一个源节点来计算，根据用户与其他节点的信任关系来计算其他节点的信任容量，从而构建自己的信任网络.
2)Advogato中每个节点的信任容量是全局信任值，而ULTNM信任模型则是为每个用户构建本地信任网络，不同节点的信任容量对于每个目标用户来讲，都是不一样的.
图2 信任网络转化为Advogato信任网络的步骤Fig.2 Steps of transforming a trust network into the Advogato structure
3)在计算后续节点信任容量时，Advogato信任模型是根据当前节点的出度计算，而ULTNM信任模型则是根据节点间的社交相似度和统计兴趣相似度计算.
4)Advogato信任模型在构建superlink节点时，为每个节点减去1个固定信任容量，而ULTNM信任模型在构建superlink节点时，则是通过用户的信任阈值来构建，从而可确保信任网络中每个节点的可信程度.具体区别见表1所示.
表1 ULTNM信任模型与Advogato信任模型的区别Table 1 Differences between ULTNM and Advogato trust model
3.2 ULTNM信任模型的形式化
定义 1.信任网络G=(U,I,E,W)代表一个以信任为基础的面向好友推荐的社交网络.其中，U代表用户节点集，每个节点代表网络中的一个用户.I代表节点集，每个节点代表网络中的一个项目.E为信任网络中的边集，E∈(U×U∪U×I∪I×I)，每条边代表所连接两个节点间的关系.W为信任网络中连接边的权重集合.
定义 2.节点k的本地信任网络Gk=(Uk,Ik,Ek,Wk).对于一个节点k，以k为源节点派生出来的信任网络Gk=(Uk,Ik,Ek,Wk)为信任网络G的一个子图，称为节点k的本地信任网络Gk=(Uk,Ik,Ek,Wk).其中Uk∈U,为节点k根据Ⅰ类元路径可到达的有限路径内的可信用户节点集.Ik∈I,为节点k通过Ⅱ类元路径、Ⅲ类元路径和Ⅳ类元路径可达的项目.Eu⊆E，为节点k本地信任网络内的边集合.Wu⊆W，为节点k本地信任网络所有边上的权重集合.
定义 3.m跳朋友.在节点k的本地信任网络Gk=(Uk,Ik,Ek,Wk)中，如果存在一条路径P=(
定义 4.信任容量Capk.节点k构建本地信任网络的能力，称为信任容量Capk.
定义 5.信任强度F.对于给定的节点k和它的1跳朋友vp，称k对vp的信任流量为k到vp的信任强度，用Fk,p表示.
3.3 目标节点的本地信任网络构建
对于不同的用户来讲，不同的社交关系可信程度不同，比如有些用户认为“远亲不如近邻”，而有些用户则认为“打虎亲兄弟，上阵父子兵”.在社交网络中，我们常常难以对这些关系进行提取.因此，我们需要对用户的社交网络进行重构，对其中的用户进行信任度区分.本小节将根据前述的4类元路径来构建用户的本地信任网络.
3.3.1 基于Ⅰ类元路径的本地信任网络构建
为了方便处理，在构建信任网络时，为每个源节点统一分配信任容量为1.节点间的信任强度按照公式(2)进行计算.
(2)
其中，Wi,j代表用户i和用户j的信任强度，SocSimi,j为用户i和用户j的社交相似度，StaSimi,j为用用户i和用户j的统计兴趣相似度.当StaSimi,j为0时，我们则使用社交相似度SocSimi,j来表达用户i和用户j之间的信任强度，以应对冷启动用户的数据稀疏问题.而如果SocSimi,j为0时，我们则使用统计兴趣相似度StaSimi,j来表达用户i和用户j之间的信任强度.社交相似度SocSimi,j的计算采用公式(3)计算，其中的社交圈子重合度JaSimi,j采用公式(4)计算，社交亲密度Intimi,j采用公式(5)计算.
SocSimi,j=log2(JaSimi,j+Intimi,j)
(3)
(4)
(5)
JaSimi,j为用户i和用户j的社交圈子重合度，采用Jaccard相关性公式，即公式(4)进行计算，Soci、Socj别代表用户i和用户j的社交关系圈子节点集，也包括节点自身.Intimi,j表示用户i和用户j的亲密度，采用公式(5)计算.在公式(5)中，Interi,j表示用户i和用户j的互动次数，avg(Interall)表示整个社交网络所有节点的平均互动次数.通过使用avg(Interall)可以对公式(3)进行平衡，以防止某一对节点互动次数过多，而成为奇异点的情况，从而克服恶意用户通过提高交互次数来增加自身影响的情况.
在计算统计兴趣相似度StaSim时，我们考虑两个因素，一个是用户间共同项目选择的数量，一个是对于项目的评价情况.已有的研究文献在计算用户的兴趣相似度时，通常采用Pearson公式(见公式(6))进行计算，但忽略了用户的共同项目数量信息.比如用户A和B恰好只评价了一个共同项目，但评分一致，则根据Pearson公式计算，他们的兴趣相似度为1，这样不能客观反映用户之间的兴趣相似度.因此，我们对Pearson公式进行修正，将用户的兴趣分为统计兴趣相似度StaSim和基础兴趣相似度BasSim.采用公式(6)计算基础兴趣相似度BasSim，而采用公式(8)进行计算StaSim.
(6)
(7)
(8)
通过使用公式(2)，我们计算得到了节点i,j之间的信任强度Wi,j.而后，我们就可以对本地信任网络中后续节点的信任容量进行计算，采用公式(9)进行.
Capj=Capi×Wi,j
(9)
其中，Capi为当前节点i的信任容量，j代表它的后续节点.如果i为目标节点，则它的信任容量为1.如果从目标节点i到达后续节点j的存在多条路径，那么我们则使用文献[29]Ford Fulkerson算法的思想，来计算节点j的信任容量.
假定目标节点U基于Ⅰ类元路径的本地信任网络如图3所示，根据本文的算法，节点U的信任容量为1，通过公式(2)计算得到节点U与节点A之间的信任强度为0.72，那么节点A的信任容量即为CapA=1×0.72=0.72.通过同样的方式，我们可以计算得到节点B, C, D的信任容量.对于与目标节点A距离为2跳的朋友节点也采用同样的方式进行计算，从而得到节点E和F的信任容量.对于节点G的信任容量计算，存在两条传播路径PathUBG和PathUCG，因此前述方法，我们选择一条信任流量最大的传播路径.根据PathUBG路径的计算结果，节点G的信任容量为0.577，而根据PathUCG路径的计算结果，节点G的信任容量为0.774，因此，G的最终信任容量为0.774.同理可得到节点D和节点H的信任容量.根据前面提到的三度影响力理论[25]，我们将节点基于Ⅰ类元路径的的本地信任网络构建深度设为3,即目标节点的朋友不能超过3跳关系.
图3 信任流量传递中的路径选择Fig.3 Path choosing while transiting trust flow
3.3.2 目标节点的本地信任网络扩展
上节计算了用户节点间的信任强度，即Ⅰ类元路径的情况，接下来我们对其他3类元路径进行分析.
1)Ⅱ类元路径(U-I-U)的信任强度计算
对于Ⅱ类元路径(U-I-U)实例的两个用户节点，我们使用公式(10)来计算他们之间的信任强度.
Wi,j=StaSimi,j
(10)
我们假定节点i和节点j之间没有社交相似度SocSimi,j(同时存在有社交相似度的话，则该两个节点也属于Ⅰ类元路径，这涉及到多路径实例的情况，后面会进一步分析)，因此我们使用统计兴趣相似度StaSimi,j来表达节点i和节点j之间的信任强度，统计兴趣相似度StaSimi,j仍然使用公式8进行计算.
2)Ⅲ类元路径(U-I-U-U)的信任强度计算
对于Ⅲ类元路径，实际上可将它转换为Ⅱ类元路径信任强度计算及其后续用户节点的信任强度计算.因此，对于一条实例路径Path(uk-il-up-uq)，节点k对节点q的信任强度Wk,q可由公式(11)计算.
(11)
3)Ⅳ类元路径(U-U-I-U)的信任强度计算
Ⅳ类元路径的信任计强度算与Ⅲ类元路径的类似，可以将它转换为当前节点和后续Ⅱ类元路径(U-I-U)的信任强度计算.对于一条实例路径Path(uk-up-il-uq)，节点k对节点q的信任强度Wk,q可由公式(12)计算.
(12)
公式(12)与公式(11)的不同在于，它先计算节点k对节点p的信任强度Wk,p，然后再计算节点p对节点q的信任强度Wp,q，最后产生元路径实例节点k对节点q的信任强度Wk,q.对于归属于多条实例路径的节点，本文仍使用前述方法进行信任流量传播.如图4所示.
在图4中，方形节点K为项目节点，圆形节点U、J、L、M、N、O为用户节点.节点U到节点N之间存在3条元路径实例，分别为PathUJN、PathUKN、PathUJKN，分别对应I类元路径、Ⅱ类元路径和Ⅳ类元路径.其中，StaSimJ,N=0.92、StaSimU,N=0.78、StaSimU,L=0.83，因此，根据前述的计算公式可以得到基于PathUJN的WU,N=0.577，基于PathUKN的WU,N=0.78，基于PathUJKN的WU,N=0.8556，因此，节点E的最终信任容量为0.8556.节点U到节点O之间存在2条元路径实例，分别为PathULO、PathUKLO，分别对应Ⅰ类元路径和Ⅲ类元路径.同理可以计算得到O的最终信任容量为0.764.
图4 多条元路径实例下的信任容量计算Fig.4 Computation of trust capacity for multi meta-path instances
4 融合社交信任的多属性元路径好友推荐算法(ComULTNM)
在本节中，我们将使用算法1对目标节点的本地信任网络进行转换，并根据目标节点的信任阈值对其本地信任网络进行搜索，然后返回目标节点的候选好友列表.ComULTNM推荐方法的算法如下.
算法1.融合社交信任的多属性元路径好友推荐算法(ComULTNM)
输入：目标节点u，全局邻接矩阵GUM，节点u的本地信任网络邻接矩阵LUM，LUM中所有节点的信任容量表capList,邻接矩阵LUM的秩N，节点u的信任阈值Thu
输出：目标节点的有序候选好友列表Fru
1. i=0,Fru=0,n=N, th=Thu
2. for i in range(n):
3. for j in range(n):
4. ifCapi,j>Thu:
5.Capi,j=Capi,j-Thu
6. setSuperlink(LUM, LUM[i][j],u)
7. capList[i][j]=Capi,j
8. if not isRelated(GUM,u, LUM[i][j]):
9.Fru.append(LUM[i][j])
10. endif
11. endif
12. endfor
13. endfor
14.Fru.sort()
15. returnFru
其中，Capi,j为LUM中下标为i,j的节点信任容量，伪代码4-7行用来判断当前节点LUM[i][j]的信任容量Capi,j是否大于u的信任阈值Thu，如果大于，则调用方法setSuperlink(LUM,nodei,j,u)方法在LUM中为节点nodei,j,u建立关联，并对Capi,j的信任容量进行更新.
伪代码8-10行用来判断在全局邻接矩阵GUM中，目标节点u与LUM[i][J]是否存在连接，即是否为1跳朋友关系.如果不是1跳朋友关系，则说明当前节点LUM[i][j]还不是u的朋友，因此将该节点添加到u的候选好友列表Fru中.否则u与LUM[i][j]已经是朋友关系，则不作处理.
伪代码14-15行用来对u的候选好友列表Fru进行排序，并将列表返回.
图5 采用算法1对目标用户的本地信任网络重建和搜索Fig.5 Research and rebuild on local trust network of target user with algorithm 1
通过算法1，我们结合图3和图4对目标节点u的本地信任网络进行搜索和重建(如图5所示)，最终得到目标节点的候选好友列表：N,G,O,H,E,F,M(这里设置Thu=0.1，限于篇幅，E, F, L, J, K, M, N, O节点没有画出).
5 实验与分析
5.1 实验数据集
目前用于好友推荐的公开实验数据集主要有：Gowalla数据集、Foursquare数据集、Epinions数据集等，也有不少研究者使用网络爬虫对新浪微博、Twitter等网站的数据进行爬取，用于好友推荐实验.其中，Gowalla数据集和Foursquare数据集主要用于基于地理位置的好友推荐，而使用网络爬虫从新浪微博或Twitter爬取数据，很难获得用户间的完整社交关系.因此，本文选取Epinions作为实验数据集.其统计信息如表2所示.
表2 Epinions数据集的统计信息Table 2 Statistics of the Epinions dataset
该数据集包含了139738个项目，664824条项目评分，项目评分区间为[1-5].还包含了49290个用户和487181对朋友关系，数据集的朋友关系数据稀疏度为99.98%，属于极度稀疏数据.
在将本文的ULTNM信任模型应用于Epinions数据集时，考虑到公式(5)中用户间的互动次数Interi,j在Epinions数据集中没有直接对应的数据，因此我们采用用户共同访问项目数量来作为替代，其他的参数都可在数据集中找到对应的数据内容或计算得出.在进行实验时，将数据集的487181对朋友关系分成两份，90%作为训练集，10%作为测试集，以检测推荐方法的有效性.
5.2 实验评价指标
本文选取推荐系统中常用的准确率(precision)、召回率(recall)作为推荐方法实验效果的评价指标.具体计算方式如公式(13)、公式(14)所示.
(13)
(14)
其中，R(u)表示推荐给用户u的候选好友集合，T(u)表示用户u在测试集中真实的好友集合.准确率是指推荐的候选好友列表中，真实为用户好友的比例占推荐用户总数的比例，反映的是推荐方法的精度.召回率是指推荐的候选好友列表中，真实为用户好友的比例，占测试集中用户真实好友数量的比例，反映的是推荐方法的覆盖率.这两个指标数值越大，表明推荐方法的总体效果越好.
5.3 源节点信任阈值设置
本文提出的ComULTNM推荐方法所使用的实验参数大多可根据数据集内容计算得到，只有源节点的信任阈值Thu需要设置.因此我们通过实验来验证源节点信任阈值Thu取值对推荐方法召回率的影响，来考察推荐方法的覆盖率.本实验中，我们将Thu值设为[0, 1]，步长0.1.实验结果如表3所示.
表3 不同信任阈值下的召回率对比Table 3 Comparison of recall under different trust threshold
通过表3可以看出，随着信任阈值Thu的不断上升，在Thu为0.1时，ComULTNM推荐方法的召回率最高，而后则不断下降，在Thu为1时达到最低，只有0.009.这是因为能够进入源节点可信社交网络的用户越来越少，当信任阈值达到1时，意味着源节点基本只信任自己，因此很难为他推荐好友.因此我们在后续的实验中，都将信任阈值Thu设为0.1.
5.4 实验对比方法
为了验证本文提出的推荐方法，我们将使用以下方法进行对比.
1)User-based CF，经典的基于用户兴趣相似度的协同过滤推荐方法，根据用户的兴趣相似度来进行候选好友推荐[30].
2)Praveen Model，文献[31]提出的好友推荐方法，该文章将社交网络按照拓扑结构进行重建，并将好友推荐方法分为两个阶段，首先基于用户之间的兴趣偏好和共同好友进行好友候选人筛选，然后再根据候选好友的影响力进行排序，从而完成目标用户的好友推荐.
3)PAFR，文献[32]提出的好友推荐方法，该文章基于协同分析和隐私保护云技术设计了一个好友推荐框架，该框架利用用户之间共同邻居的行为、兴趣，来推测目标用户的交友兴趣，并使用同态加密技术来保护用户的隐私信息.
在和这三个推荐方法进行实验对比时，我们将好友候选人的Top-N值，分别设为n=5，10，15，20，实验结果取100次执行结果的平均值.
5.5 推荐效果对比
图6(a)、图6(b)分别展示了4个推荐方法在Epinions数据集上的准确率和召回率.
图6 4种推荐方法的推荐效果对比Fig.6 Comparison of the four recommendation methods
通过对图6所示的实验结果进行分析，可以得到以下结论.
1)随着推荐候选好友Top-N数量的增加，这4个推荐方法的准确率都有所下降，而召回率却都逐渐上升.准确率从高到低顺序依次为：ComULTNM、Praveen Model、PAFR和User-based CF，召回率方面，推荐效果最好的方法依次为：ComULTNM、Praveen Model、PAFR和User-based CF.因此，本文提出的推荐方法总体效果最好，这说明我们提出的推荐方法是有效的.
2)在这4个推荐方法中，User-based CF的推荐效果最不理想，其原因可能是该推荐方法只考虑了用户的兴趣相似度，而忽略了重要的社交因素和信任因素在推荐方法中的作用.
3)对比Praveen Model和PAFR方法，Praveen Model的推荐效果比PAFR方法好.虽然这两个推荐方法都考虑了目标用户的共同好友因素，但Praveen Model还将好友候选人的影响力因素引入，因此有更好的效果，这与现实生活中的情况一致，人们总是更愿意接受有影响力的朋友推荐的好友.
4)对比Praveen Model和PAFR方法，ComULTNM的推荐效果最优.虽然这两个推荐方法也都考虑了目标用户的共同好友即社交圈子因素，但在计算兴趣相似度时，ComULTNM不仅考虑了项目的兴趣相似度，还进一步考虑了基于共同选择项目数量的统计兴趣相似度.在此基础上，ComULTNM方法还进一步考虑了基于互动次数和社交圈子相似度的亲密度因素，因此取得了最佳的推荐效果.
5.6 抗托攻击效果对比
托攻击是恶意用户通过模拟目标用户的项目评分，提高自身与目标用户兴趣相似度，从而将具有欺骗性的项目推荐给目标用户，导致目标用户利益受损的常用攻击手段.本节的实验通过模拟恶意用户的托攻击行为，来检测这4种推荐方法在托攻击下的表现.本实验中，我们将Top-N的n值设为20，然后增加恶意用户的比例.实验结果如图7(a)、图7(b)所示.
通过对图7所示的实验结果进行分析，可以得到以下结论.
1)随着恶意用户比例的增加，这4个推荐方法的准确率和召回率都有所下降.在没有恶意用户出现的时候，推荐准确率和召回率的实验效果从高到底排序为：ComULTNM、Praveen Model、PAFR和User-based CF.当恶意用户比例超过10%时，Praveen Model推荐方法受到了较大的影响，这时准确率和召回率的实验效果从高到底排序为：ComULTNM、PAFR、Praveen Model和User-based CF.
图7 4种推荐方法的抗托攻击效果对比Fig.7 Comparison of the four recommendation methods under Shilling attacks
2)随着恶意用户比例的增加，User-based CF受影响最大，其推荐精度下降最快.其原因是托攻击本身就是针对该方法设计，因此该方法受影响最大.
3)Praveen Model受恶意用户增加的影响仅次于User-based CF推荐方法，在恶意用户比例为0时，它的推荐效果要优于PAFR方法，但当恶意用户比例增加到10%时，它的推荐精度下降较迅速，以至于被PAFR推荐方法超越.这可能是该方法也是基于User-based CF的思想设计，所以当恶意用户增加过多时，推荐精度也受到了较大的影响.
4)相比较而言，当恶意用户逐渐增加时，本文的ComULTNM推荐方法一直保持效果最好，但PAFR推荐方法却最稳定.虽然ComULTNM方法也考虑了用户的兴趣偏好，也受到恶意用户比例增加的影响，但由于使用了统计兴趣偏好、社交相似度这些因素进行纠偏，所以仍然保持了最好的推荐效果.而PAFR推荐方法由于使用了同态加密技术和隐私保护云技术，可以隐藏用户的身份信息，从而导致恶意节点模仿目标节点的兴趣相似度存在一定的困难，因此稳定性最好.
5.7 运行效率对比
本实验对4个推荐方法的运行效率进行对比.在本实验中，我们将Top-N的n值设为20，随机选10个目标用户进行好友推荐，将每个推荐方法运行100次，然后取平均运行时间.为了方便对比，我们将User-based CF方法的运行时间作为基础，用无量纲值1来表示，对比其他推荐方法的运行时间.实验结果如图8所示.
通过对图8所示的实验结果分析，可以得到以下结论.
1)这4种推荐方法的运行效率排序为：ComULTNM、Praveen Model、User-based CF和PAFR.即本文提出的ComULTNM运行效果推荐方法运行所需时间最少，而PAFR推荐方法耗时最多.
2)ComULTNM、Praveen Model及User-based CF三个方法相比，由于User-based CF在为目标用户进行候选好友推荐时，需要计算全局邻接矩阵中每个用户与目标用户的兴趣相似度，而Praveen Model方法在计算用户兴趣相似度的基础上，还需要计算全局邻接矩阵中每个用户与目标用户的共同好友数量，然后根据候选好友的影响力排序，因此它的时间消耗比User-based CF略高.对于ComULTNM方法，由于不需要进行全局邻接矩阵运算，但在计算过程中，需要构建目标用户的本地信任网络，且需要计算社交亲密度、统计兴趣相似度等内容，但因为它所采用的元路径长度不大于3，因此减少了许多的计算量，其计算耗时相对比User-based CF略少些.
图8 4种推荐方法的运行效率对比Fig.8 Time cost of the four recommendation methods
3)对于PAFR方法，因为其不仅需要计算用户之间的共同邻居行为相似度，还需要计算他们之间的兴趣相似度，在计算这些数据时，还需要使用同态加密技术和隐私保护云技术，因此耗时量最大，要远高于其他3个对比方法.
6 总 结
社交网络的日益普及，促进了在线社交的发展，好友推荐成为了目前大多数社交应用的主流服务，也成了推荐系统的研究热点.有效的好友推荐，能帮用户快速扩大自己的社交范围，得到更多的社会资源和信息.然而，现有的好友推荐方法，大多基于用户偏好或行为轨迹进行好友推荐，未考虑在线社交的异构网络特征，且容易受到托攻击的影响，导致推荐精度降低.从这一研究角度出发，本文分析了在线社交的异构网络特征，使用元路径理论对好友推荐的异构网络进行抽象和形式化，提出了ULTNM(User Local Trust Network Model)信任模型.该信任模型综合考虑元路径上节点的社交相似度和统计兴趣偏好相似度等多种属性特征，构建了目标用户的本地信任网络，并通过Ford Fulkerson算法对信任网络进行搜索和排序，进行目标用户的候选好友推荐.基于真实数据集的对比实验表明，该推荐方法有更好的推荐准确率和召回率，能更好的抵御恶意用户的托攻击行为，且运行效率具有一定的优势.
下一步工作将考虑基于时间序列的用户兴趣偏好对好友推荐的影响，并进一步考虑小世界理论在好友推荐中的应用.
