高燕1，薛苑2，张永恒1
（1.榆林学院信息工程学院，陕西榆林719000；2.中国电信股份有限公司榆林分公司，陕西榆林719000）
摘要：针对如何对交友网站中的用户进行朋友推荐的问题，提出一种依据信任度进行朋友推荐的模型。通过用户之间的信任关系，建立信任模型，计算出该用户和其信任距离在3个跳转之内的所有其他用户的信任度。在计算用户之间的间接信任度时引入了衰减因子，改进了常见的间接信任度算法，从而达到依据信任度的高低依次对用户进行朋友推荐的目的。通过应用该模型对一个实例模型关系进行分析的结果表明，该朋友推荐模型能够有效地对用户进行朋友推荐，体现了用户对于有直接指向关系用户的信赖程度。
教育期刊网 http://www.jyqkw.com
关键词 ：信任模型；信任度；衰减因子；朋友推荐模型
中图分类号：TN911?34 文献标识码：A 文章编号：1004?373X（2015）16?0020?03
收稿日期：2015?02?26
基金项目：陕西省教育厅科研项目（14JK1864）
0 引言
随着Internet 的普及，越来越多的人生活在网上。网民们不仅在网上购物，娱乐，而且还在网上交友相亲，希望通过更多的渠道认识新的朋友，从而扩展自己的社交圈。然而交友网站在给人带来方便与快捷的同时也产生了信息冗杂、难以辨别的问题[1]。尤其对于新注册的用户，如何有效快速地对其进行朋友推荐成为了亟待解决的问题。
从交友网站出现一直到今天，无数的学者对其进行了研究，并推出了大量的朋友推荐模型。如文献[2]提出了一种综合信任评价度和兴趣评分相似度进行好友推荐方法；文献[3]对博客进行了分析，提出了依据博主聚类后结果进行好友推荐的方法；文献[4]提出了一个新的社会图上基于局部随机游走的朋友推荐方法，为用户提供个性化朋友推荐；文献[5]提出了一种根据用户签到位置的相似度及好友关系的综合相似度进行潜在用户推荐的模型；文献[6]提出了一种基于用户间社交圈的相似程度为用户进行朋友推荐的在线社交网络朋友推荐算法。本文针对交友网站的特点，结合以上论文的研究成果，提出了一种基于用户信任度的朋友推荐模型。该模型能够实现对交友网站的用户进行更为方便准确的朋友推荐。
1 信任关系模型
在信任网中，若用户A 信任用户B，则通常在图中用节点A 到节点B 的一条有向线段来表示[7]，如图1所示。用户A 指向用户B 的有向线段上的数值表示用户A 对用户B 的信任程度，简称为信任度，记作T（A，B）。任意2个用户之间存在的某一条链路上的跳数在本文中被称为信任距离。本文中只考虑用户A 指其他用户的有向信任关系，不考虑其他用户指向A 的有向信任关系。而且所取最长信任距离为3，信任距离太远难免会失去参考意义。
1.1 信任模型的建立
当一个新用户在交友网站进行注册时，首先要求该用户从网站已有的老用户中选择若干个可信的用户，并对这些用户的信任度进行打分，分数可取从0~1之间的任意小数，0表示完全不信任，1表示完全信任；接着将这些可信用户以及他们的信任度值存入该用户对应的数据表中，作为该用户拥有直接信任关系的用户。随着该用户在交友网站中的不断交流和互动，可以添加、更改或者删除拥有直接信任关系的用户，并对他们的信任度进行修改。从而实现对该用户信任关系的动态更新。
接下来依据该用户选择的直接信任用户，从数据库中再次读取与这些直接信任用户拥有直接信任关系的用户以及他们的信任度，建立该新用户的第二层间接信任关系；以此类推，建立起最长信任距离为3的最终信任关系图。本文以用户A 为例，按照上述过程建立用户A 的信任关系模型如图1 所示。图中的有向线段指向体现了用户之间的信任关系，有向线段上的数值体现了用户之间的信任度。
1.2 信任度计算
在信任网络中，信任度的计算已经成为不可回避的问题。在已有的关于信任网络的文献中，对于信任度的取值和计算各有不同，而主要的计算难度集中在用户间的间接信任度计算上。
1.2.1 直接信任度计算
直接信任指在信任关系图中和用户A 有直接指向关系的用户。如在图1中和用户A 有直接指向关系的用户有B，C，D。在图1 中用户A 对用户B，C，D 的信任度分别是0.7，0.5 和0.4，可用T（A，B）=0.7，T（A，C）=0.5，T（A，D）=0.4来表示。
1.2.2 常用间接信任度计算
对于间接信任度的计算有许多文献都对其进行了描述。现在假设用户X 和用户Y 存在间接信任关系，用IN[X，Y]表示从用户X 到用户Y 的信任链上所有有向线段上信任度的乘积。文献[2]提到了一种通过利用IN[X，Y]除以该条信任链的跳数计算间接信任度的方法；文献[8]中提到了一种取该条信任链上所有有向线段上信任度的最小值作为间接信任度的方法；文献[9]提到了一种将从用户X 到用户Y 每条信任链的IN[X，Y]除以该条信任链上的跳数，并从中选取最大值作为间接信任度的方法；文献[10]提到了一种首先将用户X 到用户Y的所有信任链上跳数最少的信任链选出，其次将该最短信任链的IN[X，Y]除以该条信任链跳数的所得值作为间接信任度的方法。
但是上述文献中提到的这些计算方法均没有考虑信任传递时的信任衰减问题。例如在图1中，用户A 和用户F 之间的信任链有3条，分别是A→B→F，A→C→F和A→C→B→F。若按照文献[10]中的计算方法，首先从中挑选出跳数最短的信任链A→B→F 和A→C→F，因为有2条相同跳数的信任链，接着计算这2条信任链上间接信任度的平均值，将其作为A，F 之间信任程度。由此可得：
然而该方法存在如下2个缺陷：
（1）对于用户A 来说，其对于B 的直接信任度要高于该用户对于C 的直接信任度，因此用户A 会更倾向于相信B 的意见。该方法并没有体现这一点。
（2）有些情况下，这种方法会计算出一个并不理想的信任度值。例如，用户A 和用户G 之间的信任链有4 条，分别是A→D→G，A→B→F→G，A→C→F→G 和A→C→B→F→G。若按照文献[10]中的计算方法，首先从中挑选出跳数最短的信任链A→D→G，通过计算会发现这条信任链计算出的间接信任度是最低的。这不太符合现实生活中的情况。
1.2.3 改进后的间接信任度计算
本文中在计算间接信任度时考虑到了信任传递时的信任衰减的问题，将2个用户之间某信任链上前一级的信任度作为衰减因子引入到了该条信任链信任度的计算中。例如，假设用户A 和用户Z 之间存在一条信任链，A→B→C→…X→Y→Z，则改进后的信任链上用户A和用户Z 之间的间接信任度的计算公式为：
若2个用户之间存在多条信任链，则取所有信任链的间接信任度的最大值作为两用户之间的最终间接信任度。改进后的公式显著体现了信任链上的用户对于有直接指向关系用户的信赖程度，同时避免了按照常用间接信任度方法时没有考虑信任衰减的问题，以及有可能选出两用户之间最低信任度的情况，而且也保留了信任链上的跳数越多，则信任度有可能会越低的结果。
1.3 朋友推荐过程
第1 步：依据1.1 小节提到的信任关系模型的建立方法，建立用户的信任关系模型；
第2步：依据已有的信任关系图，利用1.2小节提到的计算公式算出用户和信任关系图中的所有用户之间的信任度；
第3步：按照计算出的信任度高低依次对用户进行朋友推荐。
第4步：若用户对拥有直接信任关系的用户及其信任度进行更新，则从第一步开始重新建立用户的信任关系模型，重新计算和信任关系图中的所有用户之间的信任度，按照新的信任度取值重新对用户进行朋友推荐。
2 实例及结果分析
在实例分析中，以图1中用户之间的信任关系为例对用户A进行朋友推荐。
首先按照直接信任度的计算方法计算出和用户A有直接信任关系的3 个用户B，C，D 的信任度分别为：T（A，B）=0.7，T（A，C）=0.5，T（A，D）=0.4。其次，按照间接信任度的计算方法计算出用户A 和用户E，F，G 之间的信任度。
用户A 和用户E 之间的信任链有2 条，分别是A→B→E 和A→C→B→E。接下来依次计算每条信任链上的间接信任度，并从中选取最大值。
取其最大值可得T（A，E）=0.441。计算结果明确显示出用户A 对于用户B，用户B 对于用户C 意见的重视程度，数据更符合实际情况。
用户A 和用户F 之间的信任链有3 条，分别是A→B→F，A→C→F 和A→C→B→F。接下来依次计算每条信任链上的间接信任度，并从中选取最大值。
取其最大值可得T（A，F）=0.196。计算结果明确显示出用户A 对于用户B 的意见的重视程度，数据更符合实际情况。同理，用户A 和用户G 之间的信任链有4条，分别是A→D→G，A→B→F→G，A→C→F→G 和A→C→B→F→G。接下来依次计算每条信任链上的间接信任度，并从中选取最大值。
取其最大值可得T（A，G）=0.081。计算结果避免了按照常用间接信任度方法有可能选出两用户之间最低信任度的情况，而且也保留了信任链上的跳数越多，则信任度有可能会越低的结果，数据更符合实际情况。
因此对于用户A 进行朋友推荐时，按照信任度的高低对用户A 进行朋友推荐的顺序依次为：B，C，E，D，F，G。
3 结语
当今社会交友网站蓬勃发展，越来越多的人选择在网上扩展自己的社交圈，因此如何快速有效对用户进行朋友推荐成为了众多学者关注的问题。针对这一现象，构造出一种基于信任度的朋友推荐模型。通过分析用户信任关系，建立可动态更新的信任关系模型，计算出某用户对于和他有信任关系的用户的信任度。尤其是对常见的间接信任度计算方法进行了改进，考虑到对于有直接指向关系用户的信赖程度的问题，引入了衰减因子。通过实例分析表明，该模型能够有效地按照信任度值的高低对用户进行朋友推荐。
教育期刊网 http://www.jyqkw.com
参考文献
[1] 郑杨，谭玲.个性化好友推荐系统在社交网站上的应用研究[J].今传媒，2014（6）：117?119.
[2] 黄亮，杜永萍.基于信任关系的潜在好友推荐方法[J].山东大学学报：理学版，2013（11）：73?79.
[3] 牛庆鹏.博客朋友推荐技术的研究[D].沈阳：东北大学，2009.
[4] 俞琰，邱广华.基于局部随机游走的在线社交网络朋友推荐算法[J].系统工程，2013（2）：47?54.
[5] 孙晓晨，徐雅斌.位置社交网络的潜在好友推荐模型研究[J].电信科学，2014，30（10）：71?77.
[6] 王玙，高琳.基于社交圈的在线社交网络朋友推荐算法[J].计算机学报，2014（4）：801?808.
[7] 周超，李博.一种基于用户信任网络的推荐方法[J].北京邮电大学学报，2014（4）：98?102.
[8] 卢竹兵.基于信任关系的协同过滤推荐策略研究[D].重庆：西南大学，2008.
[9] 龚钢军，熊琛，许刚.基于层次分析判断矩阵的配用电通信业务模型的研究[J].电力系统保护与控制，2013（22）：19?24.
[10] 李静，陈蜀宇，文俊浩.基于信任网络的网格资源发现机制[J].重庆大学学报：自然科学版，2007，30（1）：86?88.
作者简介：高燕（1979—），女，陕西榆林人，讲师，硕士。主要研究方向为计算机控制系统和嵌入式系统。