信任社交网络中基于图熵的个性化推荐算法

蔡永嘉 李冠宇 关皓元

摘 要：随着社交网络的飞速发展引起了人们对推荐系统（RS）的广泛关注。针对社交网络中现有推荐方法仍存在冷启动问题以及未考虑用户所处的社交网络信息的情况，提出了在信任社交网络中基于图熵的个性化推荐算法（PRAGE）。首先，根据用户物品和它们之间的反馈信息建立用户物品图（UIG），同时引入信任机制建立用户信任图（UTG）;其次，通过对两个图使用随机游走算法得到用户与物品的初始相似度和基于信任机制的新的用户物品相似度;重复随机游走过程直至相似度稳定到收敛值;然后，使用UIG和UTG的图熵对两组相似度进行加权并最终相应地得出目标用户的最终推荐列表。在真实的数据集Epinions和FilmTrust上的实验结果表明，相比经典的基于随机游走算法，PRAGE的精确率分别提高了34.7%和19.4%，召回率分别提高了28.9%和21.1%，能够有效地缓解推荐的冷启动问题且在精确率和覆盖率指标上均优于对比算法。

关键词：社交网络;信任机制;随机游走;图熵;推荐算法

中图分类号： TP301.6; TP18

文献标志码：A

Abstract： Widespread attentions have been drawn to Recommendation Systems （RS） as rapid development of social networks. To solve the cold-start problem and neglect to users social network information in current recommendation algorithms， a novel Personalized Recommend Algorithm based on Graph Entropy （PRAGE） in trust social network was proposed. Firstly， a weighted User-Item Graph （UIG） was built based on feedback information， and a trust mechanism was introduced to establish a User Trust Graph （UTG）. Secondly， by using random walk algorithm on two graphs， the initial similarity of user and item and new user-item similarity based on trust mechanism were obtained; the above algorithm process was repeated until the similarity value reaches convergence value. Then， a method to weight two sets of similarity values with graph entropies of both UIG and UTG was proposed and final recommendation list was accordingly created. The experimental results on two real-world datasets named as Epinions and FilmTrust reveal that， compared with classical Random Walk algorithm， the accuracy of PRAGE is increased by about 34.7%and 19.4% respectively， and its recall is increased by 28.9% and 21.1% respectively， which can alleviate cold start problem effectively and has better performance in accuracy and coverage.

Key words： social network; trust mechanism; random walk; graph entropy; recommendation algorithm

0 引言

随着电子商务的飞速发展，推荐系统（Recommendation System， RS）被广泛用于这些网站为用户提供相应的产品，但是如何从海量的数据中提取有效的信息是目前RS亟待解决的问题[1]。个性化推荐旨在克服信息过载为用户提供感兴趣的物品而在RS上广泛运用。换言之，个性化的推荐系统挖掘用户潜在兴趣从大量可用选择找到用户感兴趣的物品。为了提供高质量的推荐，这些方法需要预测和比较物品的效用从而确定要推荐的物品。目前个性化推荐方法主要有基于用户历史数据进行推荐[2]、基于关联规则的推荐[3]、基于上下文信息的推荐[4]、基于社交网络结构进行推荐[5]等。

目前基于用户行为数据的推荐算法主要有基于内容推荐算法[6]和协同过滤（Collaborative Filtering， CF）算法[7]。前者是通过分析用户和物品的配置文件，根据用户购买或浏览的物品更新配置文件从而找出相似度高的物品推荐给用户，推荐结果直观但不能挖掘用户潜在的兴趣点;后者为当下应用最广泛的算法，CF基于用户对物品的评分反馈信息计算用户之间的相似度，通过邻居用户对物品的反馈来预测目标用户对物品的偏好程度[8]。目前CF算法主要分为基于存储和基于模型的方法。基于存储的方法使用相似性度量标准直接对包含所有评级的用户项目评分矩阵进行操作来表示用户对物品的偏好[9]。相似性度量基于它们各自的评级来计算两个用户之间或两个项目之间的相似性。基于模型的方法主要有图模型、概率模型等，其中基于图的推荐是一种更直观、灵活的推荐算法[10]。它将用户和物品之间的联系用二分图形式化表示，通过在二分图上展开随机游走（Random Walk）算法计算相似度从而得到与目标用户最为相似的物品。最早的图推荐算法为Haveliwala等[11]提出的基于随机游走的TSPR（Topic-Sensitive PageRank）算法，該算法采用一阶马尔可夫链在用户物品二分图上计算游走概率直至收敛到稳定值再推荐。Park等[12]提出了在推荐系统中矩阵分解和Random Walk之间比较研究，其中Random Walk在隐式分解下表现更好。基于用户反馈数据的推荐能够挖掘用户的兴趣点，但也存在数据稀疏和冷启动问题，导致推荐性能下降。

基于关联规则的推荐旨在挖掘用户和物品之间的关联规则，通过这种规则向用户推荐物品，但该方法的规则抽取难度较大且不易捕捉用户的个性化信息。另一方面，为了能够缓解RS中的冷启动和数据稀疏问题，许多文献提出基于社交网络结构的推荐方法。Li等[13]考虑了社交推荐系统中用户之间的直接联系，提出了一种具有社交影响力的推荐方法，在社交网络平台上影响力越大其推荐的权重也越大。Liu等[14]提出了将用户好友信息加入到协同推荐算法中，主要思想为通过计算用户间相似度矩阵得出用户邻居集，若其中含有用户好友则增加权重来预测物品进行推荐。该方法引入好友信息虽能一定程度缓解冷启动问题，但算法性能依旧不好，仍存在数据稀疏问题。

Eirinaki等[15]提出了信任感知推荐系统，通过定义信任度来建立用户间的信任传播网络，将信任度代替用户间相似度从而计算用户最信任的邻居集来对目标用户进行推荐。Moradi等[16]提出了一种基于信任的图聚类推荐算法，该方法将用户群基于皮尔森系数和信任值的加权构建成一个无向图，在其中寻找最稀疏子图来聚类从而获得目标用户的最相似邻居集，进而对其推荐。基于社交网络结构的推荐算法考虑了用户的好友信息和所处的社交网络信息，在一定程度上改善了推荐算法的性能并缓解了RS的冷启动问题。

针对目前基于社交网络的推荐算法仅考虑用户相似邻居集来推荐而忽略了用户对物品的多反馈信息的问题，且考虑如何权衡两者的权重，本文提出了一种在信任社交网络中基于图熵的个性化推荐算法（Personalized Recommend Algorithm based on Graph Entropy， PRAGE）。首先，根据用户物品及反馈信息构建用户物品二分图（User-Item Graph， UIG）;其次，根据信任机制构建用户间信任图（User Trust Graph， UTG）;然后，根据Random Walk算法的思想在两图上游走并重复直至得到反馈图中用户物品相似度和信任图中相似度的收敛值;最后，为了获取推荐相似度的平衡，采用图熵的方法对两组相似度进行加权来获得最终的用户物品相似度用以推荐。在真实的数据集上实验结果表明，该算法能够很好地缓解冷启动问题，并在用户反馈数据稀疏的情况下，在推荐的精确率、召回率、覆盖率等度量指标上仍取得很好的性能。

1 算法设计

本文提出的PRAGE将随机游走的思想应用于所提出的用户物品二分图和用户间信任图上：前者生成基于用户对物品反馈信息的用户物品相似度;后者生成基于信任用户的相似度。重复迭代算法在相似度稳定到收敛值后，基于图熵来分配两个相似度值的权重得到最终的相似度。最后，根据最终的用户物品相似度计算每个用户的推荐列表。算法流程如图1所示。

1.1 构建用户物品图

首先，PRAGE需要根据用户和相关的物品构建UIG。由G（V，E）表示，V表示包括用户节点和物品节点的集合，E为用户和物品边的集合，且边上的权重表示用户对该物品的感兴趣程度。如何确定用户与物品边上的权重是确定用户物品相似度的关键。譬如目前的图推荐算法利用用户对物品的评分信息来度量相似度，但却忽略了多反馈对相似度的影响，譬如用户对物品的收藏、评论、分享、屏蔽等都将影响用户对该物品的相似度权重。

对此将考虑用户多种反馈行为对其造成的影响，不同的用户反馈对用户物品相似度权重的影响是不同的。譬如用户对一部电影的收看和收藏所体现出来用户的兴趣程度明显后者更高。根据这个考虑，用户物品边的权重设计如下：假如用户对物品产生了N种反馈，为每种反馈的权重具体情况进行分析设计权重。譬如用户对物品的评分为3（总分为5），那么就评分而言其所占权重为0.6。假如用户收藏了该物品，那么基于该反馈权重设置为1。综上某用户对物品的反馈融合成的权重计算公式如下所示：

其中：N表示用户对物品产生了反馈类型数; frep表示用户对物品的屏蔽或举报反馈信息，如有设置为0，无该信息则设置为1; fj（u，i）分别表示用户对物品各种反馈信息的值。图2为用户物品图的一个例子。假如用户A观看了a、b、c三部电影，收藏了b、c，并分别对其评分2、3、4分;则w（A，a）、w（A，b）、w（A，c）分别为0.4、0.8、0.9。

1.2 构建用户信任图

本文所提出的PRAGE中不仅仅只考虑了用户对物品的相关反馈信息来计算用户和物品的相似度，同样的，也考虑了用户之间的信任关系。首先构建UTG，目的是在信任社交网络上找寻与目标用户相似度高的用户，使得目标用户对没有选择的物品分配相应的权重，这样有利于推荐的多样性。首先用户间的信任度[17]公式计算如下：

其中：dA，B表示用户A、B在信任社交网络上的信任传播距离;dmax表示在信任社交网络上允许用户间传播的最大距离，计算公式如式（3）所示：

其中n和k分别表示系统中信任网络范围大小和平均度[18]。

构建用户间信任图之后，基于信任的用户物品相似度计算方法如下：

其中：NT为与目标用户有信任度的用户集合;NT表示其用户节点个数;simF（u′，i）表示基于用户反馈信息的用户物品相似度;Tu′，u表示由式（2）计算得出的用户信任度。图3为UTG的一个例子，本文认为计算用户间信任度是相互的，故用无向图表示，那么对用户A基于信任用户的相似度信息可以计算为如下：

1.3 Random Walk和基于图熵推荐

1.3.1 基于图模型进行Random Walk

如图1所示本文提出的PRAGE的步骤，在构建完UIG和UTG之后，需要基于这两个图进行Random Walk，该过程的主要思想为以每个用户自身为出发点，每到达下一个节点时，需要判断是以概率β继续向下个节点游走还是以1-β的概率返回出发节点重新游走;如果往下個节点游走，则按权重比例随机选择下个节点作为游走节点;一轮Random Walk之后，各节点被访问到的概率即为用户和该节点的相似度;重复迭代游走过程直至用户和各节点的游走概率收敛到稳定值。假设simn（u，i）表示完成第n轮Random Walk之后用户u和各节点的相似度收敛值，i∈V，则simn（u，i）计算公式如下：

其中：Vi、Vj分别表示在图中与节点i、 j直接相连的节点集合。在UIG上根据式（1）和Random Walk游走公式可以算出基于用户对物品反馈的收敛相似度simnF（u，i），同时根据式（4）和Random Walk游走公式可以得出基于信任用户的各节点相似度的收敛值simnT（u，i）。

1.3.2 基于图熵的推荐

在对图进行Random Walk之后，最终用户与各节点的相似度如式（6）所示，其中λ∈[0，1]为调节参数，它综合考虑了用户对物品的反馈信息和信任用户的信息。

由于UIG和UTG包含不同的信息量和不同的结构，因此本文提出基于图熵来计算λ，图熵在复杂网络中被广泛应用以捕获图的结构信息量[19]。加权系数λ计算公式如下：

其中：HF、HT分别表示用户物品图和用户信任图的熵，我们认为图的信息量越丰富，它所占的权重就越多。本文采用文献[20]中的图熵计算方法，图熵计算方法公式如下：

它首先基于图的拓扑结构多样性信息来计算图中的节点熵：其中rij是图中节点ni到节点nj的转移概率。在计算节点熵时只考虑整个图的拓扑结构而不区分节点类型，因此，与使用多个相邻矩阵来描述不同节点类型之间的连接不同，本文使用单个相邻矩阵来描述整个主图的拓扑结构，然后图的熵是图中所有节点熵的总和。

1.4 算法描述分析

PRAGE描述伪代码如下。

有序号的程序——————————Shift+Alt+Y

程序前

输入：构建用户物品图和用户信任图，分别用G1、G2表示; β为Random Walk转移概率。

输出：对目标用户按照相似度降序的Top-N推荐列表。

程序后

从算法描述可以看出假如算法输入图为m个用户对n个物品的反馈信息及m个信任用户的信任图，第3）～6）行表示计算得到基于UIG的相似度;第7）～10）行表示计算基于UTG得到的相似度;然后根据Random Walk迭代得到相似度收敛值;第12）～14）行表示基于图熵得到最终相似度并对目标用户进行Top-N推荐，并且假设t轮概率收敛从PRAGE可以看出其时间复杂度为：

2 实验结果和分析

本章主要介绍实验平台和实验所需要的数据集以及在几个度量指标上对实验结果进行分析，并且将所提出的PARGE算法与现有相关算法作对比分析。

2.1 实验平台和数据集

实验平台运行在Windows 10系统上，处理器为Core i5-6500U，内存为8GB，实验工具为Visual Studio 2015。为评估PRAGE的推荐效果和性能，将采用拓展的数据集Epinions和FilmTrust来检测该算法的有效性，前者来自网站http：//www.trustlet.org/wiki/Downloaded_Epinions_dataset，后者来自网站http：//trust.mindswap.org/FilmTrust;同时为了更好地推荐和捕获用户的偏好，将获取数据集中在评分3以上（总分5）的数据。表1为处理之后的数据。此外数据集被随机地分为9∶1，其中90%作为训练集，10%为测试集。实验每次随机划分数据后将进行10次取平均值比较推荐结果。

2.2.1 准确率

推荐的准确率（ P）描述的是在推荐列表中有多少是符合目标用户偏好的，也就是对用户生成的最终推荐列表中推荐测试数据集数目Ti（L）所占的比例，公式如下：

2.2.2 召回率

推荐召回率（R）是指推荐列表中正确命中数和测试数据集中用户实际选择的物品数的比值[22]。同样反映了用户推荐命中的比例，R数值越大，表示推荐的效果越好。R计算公式如下：

2.2.3 F1指标

F1是用来衡量推荐算法准确度的一种度量指标，它同时兼顾考虑了算法的P和R，是两种度量指标的加权平均。计算公式如下所示：

2.2.4 覆盖率

推荐覆盖率（请补充CVR的英文全称CVR）表示在全部物品中推荐列表Top-N所占的比例，该指标用于反映推荐的多样性性能。CVR越高表示推荐给用户的物品多样性越大，越有新颖性。计算公式如下：

其中：VI为物品集合，R（u）表示给用户推荐物品集合。

2.3 实验结果分析

首先本文所提出的PRAGE总结了在两个数据集Epinions和FilmTrust上对于不同划分的数据集后图的熵和加权系数λ的结果，多次实验得到权值都是相似的结果，将取均值来获得最好的推荐。观察到UIG熵由于其较为复杂的拓扑结构而大于用户信任图熵。随着信任用户群增加，图熵也相应地增加，加权系数λ的值则减小，这很好地反映了PRAGE的设计目标，即很好地利用用户所处的社交网络信息来对用户作出合理的推荐。

表2表示在Epinions和FilmTrust数据集上各算法在P、R、F1和CVR这几个度量指标上的比较结果，且实验最终相似度加权系数λ基于图熵所计算得到的权重分别为0.79和0.55。其中参与和本文提出的PRAGE比较的算法有：基于Random Walk的上下文敏感排名（Topic-Sensitive PageRank， TSPR）算法[11]、融入社交关系的协同过滤（Social network Collaborative Filtering， SCF）算法[14]、基于用户信任的图聚类（Dense Graph Clustering Collaborative Filtering， DGCCF）算法[16]。其中為了验证在用户反馈图上进行Random Walk算法具有更好的推荐效果，以及目前只考虑用户好友信息或信任值，忽略了用户对物品多反馈信息的影响，于是选择了上述对比算法来验证PRAGE的有效性。

从表2可以看出在Epinions数据集上与目前现有的推荐方法相比，所提出的方法获得较好的P和CVR。其中：与TSPR算法相比P提高了34.7%，R提高了28.9%;与TSPR和SCF算法相比，CVR分别提高了30.6%和8.1%。此外，所提出的方法在推荐的召回率上也获得很好的性能，在R度量指标上略微小于DGCCF算法，但就F1衡量指标上仍获得较好的性能。另外，基于这些评估度量的实验在FilmTrust数据集上重复进行，相应的结果如表2所示。所提出的方法比TSPR在P和R上分别提高了19.4%和21.1%，同时在其他评估指标下均获得不错的性能。在两个数据集下的实验结果可以看出，推荐的CVR比对比算法均有提升，由于TSPR存在因数据稀疏造成的冷启动问题且本文提出的PARGE综合考虑了用户对物品的多反馈和信任用户信息很大程度地提升了推荐的多样性和新颖性

由于TSPR存在数据稀疏引起的冷启动问题，而本文提出的PARGE综合考虑了用户对物品的多反馈和信任信息从而很大程度上提升了推荐的多样性和新颖性

此句不通顺，请作相应调整，故可以将新物品推荐给感兴趣的用户或对新用户推荐感兴趣的物品，比对比算法PARGE可以进一步缓解推荐冷启动问题。

另外，在Epinions数据集上对于所有用户基于对目标用户推荐不同的列表长度Top-N其度量指标P和R的实验结果如表3和表4所示。

从表3～4中结果清楚地可以看出，在大多数情况下，随着推荐列表长度Top-N参数的值增加P度量指标降低，而R度量指标反而增加。这是由于P和R指标在本质上显然是相互冲突的[21]。此外，实验结果还表明，所提出的方法在P度量指标上均优于所对比的算法，而在推荐列表为50时推荐的R度量上劣于DGCCF算法，但是在推薦列表10和20时召回率要好于DGCCF算法，这说明在推荐列表相对较短时，所提出的算法推荐效果要好于DGCCF算法。

同时，在FilmTrust数据集上基于不同的推荐列表Top-N推荐的P和R的实验结果亦如表3～4所示。从表中同样可以看出随着推荐列表增加，P减小R增加的趋势，且在该数据集上本文提出的算法的P和R均优于对比算法。该实验结果表明在数据集较小的推荐系统中，所提算法也很高效。

为了进一步阐述算法PRAGE的优越性能，给出了在两个数据集上通过图熵确认在最终用户物品相似度的最优加权系数和推荐列表长度从1到测试集长度下的相应的P-R曲线。如图4所示，所提出的方法在不同推荐列表长度下的准确率和召回率曲线最佳。对于两个数据集从左下到右上的各曲线的顺序表示相应的算法，在P-R曲线上将越接近（1，1）点作为衡量性能的标准，可以看出PRAGE曲线明显优于其他算法曲线，表示在不同的测试集下本文算法准确率和召回率综合优于对比算法，这进一步支持了表3～4的实验结果。

3 结语

本文针对目前推荐系统中仍存在冷启动问题以及未考虑用户所处的社交网络信息的情况，提出了社交网络上基于图熵的个性化推荐算法（PRAGE）。首先根据用户物品及反馈信息构建用户物品二分图;其次根据信任机制构建用户间信任图;然后根据Random Walk在两图上游走并重复直至得到各相似度的收敛值;最后为了获取推荐相似度的平衡，采用图熵的方法来对两组相似度进行加权来获得最终的用户物品相似度用以推荐。在真实的数据集上实验结果表明，该算法能够很好地缓解冷启动问题，并在用户数据稀疏的情况下仍取得很好的性能。当然除了本文考虑到的因素之外，是否还有其他重要因素能对用户推荐产生影响是下一步的研究方向;同时在庞大的用户社交网络上除了信任度，如何更有效地挖掘出用户的隐性个性化信息也是接下来研究的重要方向。

参考文献 （References）

[1] L L， MEDO M， YEUNG C H， et al. Recommender systems [J]. Physics Reports， 2012， 519（1）： 1-49.

[2] JAIN A， LIU X， YU Q. Aggregating functionality， use history， and popularity of APIs to recommend mashup creation [C]// Proceedings of the 2015 International Conference on Service-Oriented Computing. Berlin：Springer， 2015： 188-202.

[3] PERWEZ S K， ZUBAIR H M， GHALIB M R， et al. Association rule mining technique for psychometric personality testing and behaviour prediction [J]. International Journal of Engineering & Technology， 2013， 5（5）： 4349-4361.

[4] HAO F， LI S， MIN G， et al. An efficient approach to generating location-sensitive recommendations in Ad-Hoc social network environments [J]. IEEE Transactions on Services Computing， 2015， 8（3）： 520-533.

[5] AHMADIAN S， MEGHDADI M， AFSHARCHI M. A social recommendation method based on an adaptive neighbor selection mechanism [J]. Information Processing & Management， 2018， 54（4）： 707-725.

[6] 曾春，邢春曉，周立柱.基于内容过滤的个性化搜索算法[J].软件学报，2003，14（5）：999-1004.（ZENG C， XING C X， ZHOU L Z. A personalized search algorithm by using content-based filtering [J]. Journal of Software， 2003， 14（5）： 999-1004.）

[7] PESSEMIER T D. Collaborative recommendations with content-based filters for cultural activities via a scalable event distribution platform [J]. Multimedia Tools & Applications， 2012， 58（1）： 167-213.

[8] 黄创光，印鉴，汪静，等.不确定近邻的协同过滤推荐算法[J].计算机学报，2010，33（8）：1369-1377.（HUANG C G， YING J， WANG J， et al. Uncertain neighbors collaborative filtering recommendation algorithm [J]. Chinese Journal of Computers， 2010， 33（8）： 1369-1377.）

[9] BOJNORDI E， MORADI P. A novel collaborative filtering model based on combination of correlation method with matrix completion technique [C]// Proceedings of the 2012 CSI International Symposium on Artificial Intelligence and Signal Processing. Piscataway， NJ： IEEE， 2012： 191-194.

[10] GORI M， PUCCI A. ItemRank： a random-walk based scoring algorithm for recommender engines [C]// Proceedings of the 2007 International Joint Conference on Artificial Intelligence. San Francisco： Morgan Kaufmann， 2007： 2766-2771.

[11] HAVELIWALA T H. Topic-sensitive PageRank： a context-sensitive ranking algorithm for Web search [J]. IEEE Transactions on Knowledge & Data Engineering， 2003， 15（4）： 784-796.

[12] PARK H， JUNG J， KANG U. A comparative study of matrix factorization and random walk with restart in recommender systems [J]. ArXiv Preprint， 2017， 2017： 1708.09088.

[13] LI C， XIONG F. Social recommendation with multiple influence from direct user interactions [J]. IEEE Access， 2017， 5： 16288-16296.

[14] LIU F， HONG J L. Use of social network information to enhance collaborative filtering performance [J]. Expert Systems with Applications， 2010， 37（7）： 4772-4778.

[15] EIRINAKI M， LOUTA M D， VARLAMIS I. A trust-aware system for personalized user recommendations in social networks [J]. IEEE Transactions on Systems， Man & Cybernetics Systems， 2014， 44（4）： 409-421.

[16] MORADI P， AHMADIAN S， AKHLAGHIAN F. An effective trust-based recommendation method using a novel graph clustering algorithm [J]. Physica A： Statistical Mechanics & Its Applications， 2015， 436： 462-481.

[17] MASSA P， AVESANI P. Trust-aware recommender systems [C]// Proceedings of the 2007 ACM Conference on Recommender Systems. New York： ACM， 2007： 17-24.

[18] YUAN W， GUAN D， LEE Y K， et al. Improved trust-aware recommender system using small-worldness of trust networks [J]. Knowledge-Based Systems， 2010， 23（3）： 232-238.

[19] DEHMER M. Information processing in complex networks： graph entropy and information functionals [J]. Applied Mathematics & Computation， 2008， 201（1/2）： 82-94.

[20] EAGLE N， MACY M， CLAXTON R. Network diversity and economic development [J]. Science， 2010， 328（5981）： 1029-1031.

[21] HERLOCKER J L， KONSTAN J A， TERVEEN L G， et al. Evaluating collaborative filtering recommender systems [J]. ACM Transactions on Information Systems， 2004， 22（1）： 5-53.

[22] DAVIS J， GOADRICH M. The relationship between precision-recall and ROC curves [C]// ICML 06 ： Proceedings of the 2006 International Conference on Machine Learning. New York： ACM， 2006： 233-240.