基于在线社交网络的用户信任传递建模与分析

阳 雨,胡亚洲,郭 勇,邓 波

(北京系统工程研究所,北京 100101)

0 概述

随着移动互联网的发展,在线社交网络[1]在人们生活中扮演着重要的角色。人们通过在线社交平台(如微博、微信、QQ等),不仅能够维护社交网络中的好友关系,而且可以更加便捷地获取感兴趣的信息。在社交网络中,人们不仅倾向于关注已认识的朋友,而且希望与兴趣相似的新朋友建立联系[2]。因此,在线社交网络平台相继推出好友推荐服务,例如,QQ推出“可能认识的人”服务,微博推出“可能感兴趣的人”“可能喜欢的大咖”等推荐服务。社交网络好友推荐主要有基于链接和基于内容2种基本推荐形式。基于链接的推荐方式是根据用户之间的网络链接关系,利用基于链接的用户权威度排序算法(例如PageRank[3]、HITS[4]、TrustRank[5]等)或其变形进行好友推荐;基于内容的推荐方式则是根据标签、关键词、地理位置等信息进行相似性推荐[6-7]。

尽管在线社交平台提供不同的推荐服务,但是普遍缺乏对推荐好友信任度和实时性的分析,时常存在推荐的好友并不是用户最希望建立链接的情况。同时,用户的互动和转发行为是在线社交平台信息传播的重要途径,用户之间的信任度是影响互动和转发行为的重要因素。因此,在线社交网络中用户信任成为需要关注的重要问题。但是,目前针对用户信任度的研究大多是直接对用户信任度量化,缺乏对于用户信任度传递的建模和分析。

针对上述问题,本文建立在线社交网络的用户信任传递模型。首先通过分析邻接用户之间的共同好友、互动关系、互动时间等因素对邻接用户信任度进行量化,将量化结果作为链接边权值;然后根据链接关系计算2个用户之间的信任值;最后结合好友链接的建立和互动情况对构建的信任传递模型进行评估。

1 相关工作

目前,在线社交平台中的用户可信度引起了学术界的广泛关注。文献[8]提出了基于局部信息的信任推荐系统,该系统通过计算朋友之间的信任度进行推荐,能够有效解决冷启动等问题;文献[9]对资源层和属性层的信任进行研究,验证了信任对于推荐准确度的影响;文献[10]提出基于信任的个性化推荐方法;文献[11]利用微博内容的可信度来描述用户的可信度;文献[12]分析了Tweet可信度感知结果,同时对特征用户对可信度评估的影响进行分析;文献[13]通过人工评估的方法对Tweet信息的可信度进行评估分析;文献[14]提出一种基于信任隐私保护的好友推荐方法,该方法通过研究用户和推荐者之间的链接信任关系,同时考虑略去用户的隐私信息进行好友推荐;文献[15]提出基于信任概率的推荐模型,该模型将用户之间兴趣的相似程度作为转移到目标节点的转移概率,以驱动商品推荐;文献[16]则将用户间的相似性和可信度纳入社区演化的分析研究中。

此外,文献[17]将用户间的好友关系强度定义为信任度并引入到相邻边拓扑信息相似性计算中,结合用户兴趣模型导出用户社交圈,提出一种好友推荐算法;文献[18]利用用户之间信息的相似度进行用户聚类,提出了一种基于用户信息的社交网络信任评估方法;文献[19]针对当前社交网络中基于用户信任的Web服务推荐算法覆盖率不足的问题,提出了一种新的混合信任度算法,用以解决因单一信任度算法数据稀疏性造成推荐结果不佳的问题;文献[20]针对数据稀疏问题和联系不可靠现象对传统社交网络推荐带来的影响,提出一种基于信任关系重建和社交网络传递的推荐算法。

通过分析可知,当前研究工作存在以下问题:1)研究重点关注信任的分析、度量,缺乏对于信任在链接网络中传递的考虑;2)未考虑信任度会随着时间的变化而衰减变化的特性,从而影响用户的行为和好友推荐的准确度;3)未将用户间的互动性纳入到用户间信任度量中。

2 建模分析

为建立用户信任传递模型,本节从用户链接、用户信任和信任传递3个方面对信任传递中的基本问题和概念进行分析。

2.1 用户链接

在线社交网络平台中的众多不同用户通过用户之间好友关系建立链接。如果2个用户是好友关系,则两者之间有一条边。因此,在线社交网络平台的用户链接网络可以用G=(N,E)表示,其中,N为链接网络中所有用户节点集合,E为链接网络中所有边的集合。为形式化描述链接网络,以图1中用户节点A为例,A的好友集合为{B,C,D,E}。

图1 用户链接网络

为方便下文描述,本文定义k跳好友和陌生人的概念。

定义1(k跳好友) 从原始用户节点经过最短k条边到达的目标用户节点,称为原始用户节点的k跳好友。如图1中,用户节点B为A的1跳好友,用户节点I为A的3跳好友。

定义2(陌生人) 从原始用户节点不能经过有限条边到达目标用户节点的用户,称为原始用户节点的陌生人。如图1中,用户节点J为A的陌生人。

本文使用邻接矩阵T来描述用户社交网络的链接关系,如果用户1加用户2为好友(或是用户1关注用户2),则邻接矩阵元素T12=1且T21=1,否则T12=0。图1中所示用户链接网络的邻接矩阵如下:

可以看出上述矩阵是对称矩阵,即对于用户i和用户j,有Tij=Tji。

2.2 用户信任

信任是指相信对方是诚实、可信赖的,通常用于描述2个用户之间的特征,在社交网络平台中,用户之间的信任很难被直观量化。文献[21]针对单一用户的可信值进行分析研究,但是没有考虑到用户信任是2个用户之间的关系特征。本文将用户信任作为2个用户之间关系好坏的评价指标,用户信任会影响用户之间的互动行为和用户链接网络的改变,将T1→2记作用户1对于用户2的信任值。

类比真实社交网络可以发现,当两用户间的共同好友越多、互动越多、兴趣点越相似时,可以认为两用户是越亲密、越信任的。以图1中用户A、B为例,当A和B拥有较多共同好友和共同兴趣,且A和B经常相互转发、评论、点赞时,可以认为A、B之间信任值TA→B和TB→A较高。同时,两用户之间的信任会随着时间的变化而变化。例如,当A、B之间长时间没有互动,则可以认为A、B的信任值TA→B和TB→A比A、B经常互动时低。

2.3 信任传递

在社交网络中,人与人之间的信任具有传递性,以图1中A、E、G为例,A与E是好友,E与G是好友,则A对E的信任值TA→E经E和G的链接传递到给G,形式化表述为:

TA→G=TA→E⊗TE→G

(1)

其中,TA→G、TA→E、TE→G分别为AG、AE和EG之间的信任值,⊗是信任传递运算符。

信任值具有可合并特征,以图1中A、B、C、H节点为例,A与H的信任值可以表述为:

TA→H=TA→B⊗TB→H⊕TA→C⊗TC→H

(2)

其中,⊕是信任合并运算符。

3 信任传递模型

本节提出一种信任传递模型,该模型基于用户链接网络和用户社交信息,通过用户之间的信任和衰减因子,对源用户和目标用户之间的信任值进行评估。

3.1 模型流程

如图2所示,信任传递模型主要包括用户信任计算和信任传递分析两部分内容。

1)用户信任计算是通过分析用户链接网络和用户社交信息,对具有好友关系(1跳好友)的用户之间信任值进行度量分析。

2)信任传递分析是通过分析信任值在链接网络中的传播规律,计算源用户节点对目标用户节点的信任值。

信任传递分析的结果同时可以反馈给用户链接网络和用户社交信息。例如,计算出源用户节点到目标用户节点之间的信任值之后,可以给源用户节点进行好友和热门信息的推送,从而影响用户链接网络的结构和用户社交信息的内容。

图2 信任传递模型框图

3.2 用户信任计算

用户信任计算是对具有好友关系(1跳好友)的用户之间信任值进行度量评估,是信任传递模型中重要的部分。

用户之间的信任值可以从亲密度、互动情况和时间衰减三方面考虑,表示为:

Trustij=(Siij,Inij,Atij)

(3)

其中,Trustij是用户i对用户j的信任值,Siij是用户i、j之间的亲密度,Inij反映了用户i、j之间的互动情况,Atij是用户i、j之间的时间衰减因素。下面对这三方面进行详细介绍。

1)用户亲密度

用户亲密度用于描述用户i、j之间的社交关系中的亲密性和相似程度,包括用户之间的共同好友和共同兴趣。通过分析可知:当用户之间的共同好友越多时,用户之间的社交重叠越大,用户之间的社交信任值越高;当用户之间的共同兴趣越多时,用户相似度越高,用户之间的信任值越高。

假设用户i的所有好友集合为Fi,关注的兴趣集合为Ii,用户j的所有好友集合为Fj,关注的兴趣集合为Ij,则用户i、j之间的共同好友为Fi∩Fj,用户i、j之间的共同兴趣为Ii∩Ij。因此,用户i对用户j的亲密度可以表述为:

(4)

2)用户互动情况

用户之间的互动情况是用户信任程度的重要体现,在其他条件相同的情况下,用户之间互动越密切,可以认为用户之间信任程度越高。

在线社交网络之间常见的用户互动行为包括转发、评论和点赞。转发是指用户将别人发布的内容转载成自己的内容;评论是指对别人的内容发表自己的看法;点赞是指对别人发布的内容表示赞同、赞许。文献[21]对微博用户的转发行为进行了分析,指出用户的转发行为与转发来源的关系。

假设用户i从好友处转发的状态数目总和为Ni,从好友j处转发的状态数目为Nij,用户i给所有好友评论次数总和为Ci,给好友j评论次数为Cij,用户i给所有好友点赞次数总和为Pi,给好友j点赞次数为Pij,则用户i对用户j的互动情况可以表述为:

(5)

其中,α、β、λ代表转发、评论和点赞在互动情况中重要性的比例。根据对真实社交网络的研究可以发现,转发、评论和点赞行为对用户互动情况重要性的影响是依次递减的,因此,实验中设定转发、评论和点赞行为的重要性比例为α=0.5,β=0.3,λ=0.2。

3)时间衰减

时间衰减因素是指用户之间的信任关系会随近期交互时间而衰减变化。如果2个用户近期经常有互动行为(转发、评论和点赞),则2个用户的信任程度较高;反之,如果2个用户之间很久没有交互,则其间信任程度会降低。因此,本文引入时间衰减因素Atij来描述用户信任程度随时间而变化的规律,如下式所示:

Atij=e-kt

(6)

其中,k是参数,t是用户i和用户j之间最后一次交互距信任值计算时刻的时间间隔(单位为d)。根据实验结果分析,当实验中设置k=-1/1000时,可以较好地反映时间衰减因素Atij相对时间的变化规律。

为量化用户i对用户j的信任值Trustij,同时考虑到用户i和用户j之间的亲密度、互动情况和时间衰减因素均会对用户i、j产生影响,本文使用量化公式如下:

Trustij=Siij·Inij·Atij

(7)

3.3 信任传递分析

信任传递分析主要包括3个步骤:信任值归一化,链接路径搜索和信任值计算。

2)链接路径搜索:在用户链接网络中搜索从源用户到目标用户的所有无环路径,路径集合为EE。链接路径搜索是后续信任值计算的基础。本文使用改进的广度优先搜索算法,即从源节点搜索到目标节点时不直接返回,而是遍历所有无环链路之后返回所有路径集合EE。

3)信任值计算:依据链接路径搜索结果和链接传播规律,计算从源用户到目标用户之间的信任值。

用户信任值计算具体过程如算法1所示。

算法1用户信任值计算算法

输入用户社交网络G和参数α、β、λ、k、αa

输出用户信任值矩阵Ts

1.Initialize α,β,λ,k,αa

2.for∀Tij∈T//计算邻接好友间信任值

3.if Tij==1

4.calculate Trustij

5.end if

6.end for

7.for∀Tij∈T //信任值归一化

9.end for

10.if Tij==1//用户i、j为1跳好友

12.else

13.find EEij//链接路径搜索

14.for eek∈EEij//信任计算

16.end for

17.end if

18.return Ts

4 实验与结果分析

4.1 实验设置

由于微博数据相对开放并易于获取,本文基于微博数据开展用户信任传递建模研究。

实验首先通过新浪微博的API接口,选取10个活跃的用户作为种子节点,以用户的链接关系共计爬取12 648个用户数据。由于大V用户在信任传递中具有意见领袖作用,同时微博好友和粉丝数严重不对等,因此在实验中不对大V用户的信任传递进行分析。同时,根据以下条件筛选出不活跃用户:1)好友总数和关注好友总数均小于20;2)用户转发、评论和点赞微博数均小于20;3)用户超过1个月没有微博或好友数据更新。最后得到2 034个用户,共计486 921条微博数据。

实验采用文献[21]中提出的微博分析方法,对用户微博数据的转发、评论和点赞进行处理,以对用户互动情况进行量化分析。

实验采用交叉验证的方法,将数据集分为训练集(Train)和测试集(Test)两部分,比例分别为80%和20%。针对从新浪微博获取的数据集中的好友数据和微博数据,对于单个用户来说,可以将该数据集分为好友数据集和微博数据集,使用全部好友和微博数据的前80%作为训练集,后20%数据作为测试数据集。

4.2 评价指标

为评价用户信任传递模型的有效性,本文使用的评价指标包括准确率Precision、召回率Recall、F1值F1-score和平均逆序数Invave。这4种评价指标的定义如下:

(8)

(9)

(10)

(11)

其中,Trustk为信任值排序集合,Inve是逆序对数。

准确率、召回率和F1值是为了分析信任传递模型对用户好友添加、互动行为预测而引入的评价指标。

平均逆序数是为了评价信任传递中信任值大小排序问题而引入的评价混乱度的指标。当平均逆序数较小时,一定程度上反映信任传递中信任排名的正确程度较高;反之则反映信任排名的正确程度较低。

4.3 结果分析

图3为信任值传递结果,从图3中可以看出,随着好友跳数的增加,用户信任值会迅速下降,当好友跳数为3时,好友信任值总和会下降到0.4以下。实验结果也验证了用户对好友以及好友的好友信任度较高,对跳数较远的人信任度较低的现象。同时可以发现,随着衰减因子的增加,相同跳数的用户信任值也相应降低。由此可知,信任衰减因子越大,用户的信任值传递下降得越快。

图3 信任值传递结果

表1给出了在不同测试集中用户信任值传递的分析结果,下文将针对好友数据集和微博数据集分别开展分析。

表1 数据集分析结果

针对好友数据集,如图4所示,随着数据量的增大,用户信任传递分析的添加好友准确率逐渐下降,召回率不断升高,F1值在两者之间,呈现先增加后减少的趋势,平均逆序对数则呈现逐渐增大的趋势。由此可知,当取测试集中前一部分好友时,用户信任传递分析的结果准确率较高,同时对于好友添加顺序的分析准确度也越高。

图4 好友数据集分析结果

针对微博数据集,如图5所示,随着数据集数据量的增大,用户信任值传递分析的用户互动行为的准确率、召回率和F1值变化规律和好友数据集类似,但是平均逆序数的变化规律和好友数据集的变化不同,随着数据集增大,平均逆序数变化规律呈递减趋势。通过分析可知,由于用户信任传递分析的是用户互动行为,互动行为的排名随数据集的增大而变得与测试集的规律更相近,因此,平均逆序数会呈现递减的变化规律。

图5 微博数据集分析结果

5 结束语

用户信任值是用户在社交网络中行为的重要影响因素,然而目前针对在线社交网络的研究,缺乏对用户信任及其传递规律的研究分析。为此,本文建立了在线社交网络的用户信任传递模型。首先通过分析用户信任值影响因素,量化用户信任值;然后根据链接关系,建立信任传递模型并进行评估分析。基于对微博数据的分析可知,信任传递模型能够准确描述好友之间的信任传递,对好友互动和好友建立具有较好的预测和推荐意义。

本文建立的信任值量化模型主要依据用户亲密度、互动行为和时间衰减因素,然而在实际在线社交网络中,信任值的影响因素可能不止这3种,未来将研究如何科学、合理地对用户信任值进行量化分析。同时,信任传递模型基于图搜索算法,当用户数量增大时,算法执行时间会迅速增长。因此,优化、改进信任传递算法也是下一步的研究方向。