基于多子网复合复杂网络模型的物质扩散推荐算法

周 双，宾 晟，邵峰晶，孙更新

(青岛大学数据科学与软件工程学院,山东 青岛 266071)

0 引言

目前，个性化推荐技术主要分为基于图的推荐[9]、协同过滤推荐[10]、混合推荐[11]、基于内容的推荐[12]。其中，协同过滤推荐算法又分为两种，一种是基于用户的协同过滤推荐算法，另一种是基于项目的协同过滤推荐算法,如物质扩散算法[13]和热传导算法[14]等。物质扩散算法在推荐时执行速度快且准确率高，因此成为目前应用最为广泛的推荐算法之一。传统的物质扩散算法，将物理动力学中的物质扩散能量分配原理引入到二部图中，通过能量扩散计算不同商品间的相似度，进而为用户进行推荐。

郭强等人[15]通过引入产品流行度的可调参数，提出了一种考虑产品流行度对用户兴趣偏好影响的物质扩散算法。胡吉明等人[16]将词汇引入关联图中，探讨了基于用户、资源、词汇三部图的推荐实现机理，并提出了二部图和能量分配双重加权的三部图推荐实现策略。周涛等人[17]利用用户-产品的二部分图建立关联网络，并运用关联矩阵提出基于网络结构的物质扩散算法。以上研究只是利用用户-商品评分矩阵对用户进行推荐，并没有充分考虑用户之间存在的多种关系对推荐结果的影响，所以推荐结果并不十分准确。因此，本文通过构建多关系复合复杂网络，将用户间的多种社交关系引入到推荐系统中，从而提高了推荐算法的准确率。

1 多子网复合复杂网络模型

复合网模型可以使用一个四元组G=(V,E,R,F)表示：

1)V={v1,v2,…vm}表示节点的集合，m=|V|是集合中元素的个数；

2)E={〈vh,vl〉|vh,vl∈V,1≤h,l≤m}⊆V×V，表示节点间连边的集合；

3)R=R1×…×Ri×…×Rn={(r1,…,ri,…,rn)|ri∈Ri,1≤i≤n},Ri表示节点间一种相互作用关系集合，ri表示节点间的一种相互作用关系,n是节点间相互作用关系的总数，当n>1时，表示节点间有多种相互关系；

图1 复合网G=(V,E,R,F)示例图

图1为复合网G=(V,E,R,F)的示例图，节点可以表示不同类型的个体，连边表示节点之间的关系，其中R=R1×R2,R1={r1},R2={r2}。从图1中可以看出，边〈v1,v2〉、〈v1,v3〉、〈v2,v3〉只具有R1关系，边〈v2,v5〉、〈v3,v5〉、〈v4,v5〉只具有R2关系，边〈v3,v4〉既具有R1关系又具有R2关系。

2 基于复合网的物质扩散算法

2.1 物质扩散算法

周涛等[17]首次提出了物质扩散(Mass Diffusion,MD)算法。MD算法基于用户-商品二部图网络，它首先给用户选择过的商品赋予一个单位的能量，没有被选择过的商品初始能量为0，这作为初始状态。从初始状态出发，带有能量的节点将能量平均分配给选择过它的用户，这样能量就从商品扩散到了所有用户。经过商品到用户的第一步传播后，用户ui获得的能量hi为

(1)

其中，kβ为商品oβ的度，n为商品的个数，fβ为商品oβ的能量，若商品oβ被用户ui选择过，则aiβ=1，否则aiβ=0。

(2)

其中，di为用户ui的度，m为用户的个数。

(3)

由式(1)、(2)、(3)可得整个物质扩散的过程为

(4)

图2 用户-商品二部图物质扩散过程

2.2 基于复合网的物质扩散算法

传统的物质扩散算法只是根据用户对商品的评分进行推荐，并没有考虑用户间社交关系对推荐的影响。通过构建多关系复合网，商品节点的初始能量通过连边在复合网中扩散，从而达到了引入社交网络信息进行推荐的目的。

设复合网中用户和商品的选择关系为r1，若引入了用户之间的某一种社交关系，则此关系为r2。假设r1和r2的关系强度均为1，r1关系强度比例系数为sf1,r2关系强度比例系数为sf2，且sf1+sf2=1。设sf1为p,则sf2为1-p，p∈(0,1)。当引入用户之间的一种社交关系时，基于复合网的物质扩散算法(简称SMD)流程为

1)为目标用户选择过的商品赋1个单位的能量，为该商品的初始能量。

2)商品中的能量通过连边向用户传播，用户节点ui获得的能量hi为

(5)

(6)

(7)

4)在复合网络中传播后的用户的能量又进一步传给了商品：

(8)

所以，商品oα获得的能量gα为

(9)

(10)

对用户没有选择过的商品按照最终能量的大小进行排序，进而形成推荐列表。当p=1时，即关系r2的强度系数为0，SMD算法退化为传统的MD算法。图3为一个简单示例来描述引入一种用户间社交关系的基于复合网的物质扩散算法(简称SMD1)过程，其中假设p=0.5。

图3 引入一种用户间社交关系的基于复合网的物质扩散过程

(11)

图4为引入两种用户间社交关系的基于复合网的物质扩散算法(简称SMD2)过程，其中假设p=0.5,q=0.5。

当q=0或q=1时，即关系r3的强度系数或者关系r2的强度系数为0，引入两种用户间关系的基于复合网的物质扩散算法SMD2就退化为引入一种用户间关系的基于复合网的物质扩散算法SMD1。

3 实验结果与分析

3.1 实验数据

本文采用推荐算法测试中常用的Epinions数据集和FilmTrust数据集对提出的推荐算法进行评估。Epinions数据集包括40 163个的用户，139 738个的商品，487 182条用户和用户之间的信任关系，以及664 823个用户对商品的评分，通常用数值1～5表示。Film Trust数据集包括1 050个用户，2 071个商品，1 853条用户和用户之间的信任关系，35 497个用户对商品的评分。当用户对商品的评分大于2时，则代表用户喜欢这个商品，用户和商品之间有选择关系，即用户和商品之间建立连边。此外还对数据集里的数据进行预处理，剔除其中的孤立点，确保每个用户都至少选择过一个商品。

图4 引入两种用户间社交关系的基于复合网的物质扩散过程

3.2 评价指标

为了验证算法的性能，采用五折交叉验证的方法将数据集随机分成了5份，在每次实验中，随机选取一组作为测试集，其余四组作为训练集。5次实验保证每组数据集都被测试，实验最终结果是5次实验结果的均值。主要采用平均排序分(Ranking Score，RS)[15]来评价推荐结果的准确性，汉明距离(Hamming Distance)[24]来衡量推荐列表的多样性。

平均排序分[15]是评价推荐算法准确率的一个重要指标，该指标数值越低，表示推荐算法的准确率越高。对于一个目标用户ui，假设他在测试集中选择了商品oj，计算oj在推荐的列表中的位置rij，测试集中用户喜欢的所有商品的排序分的平均值越小，代表推荐算法把用户喜欢的商品排在前面，说明算法的准确率越高。某一用户ui排序分的定义为

(12)

对于用户u和t,可以用汉明距离来评价两个用户推荐列表的多样性，具体定义为

(13)

其中，Qut(L)表示用户u和t推荐列表中相同商品的数目，L表示推荐列表的长度。所有用户的汉明距离的平均值就是整个推荐系统的汉明距离。汉明距离越大，表示推荐的多样性越高。

3.3 实验结果分析

在实验过程中首先利用仿真来确定p、q的取值。当q=0时，p取不同值时Epinions数据集的平均排序分RS值的变化如图5所示。

由图5可知，在Epinions数据集中,当p=0.4时，RS的值达到最小值，这表明，在该数据集中，SMD1算法在p=0.4时准确率最高。在FilmTrust数据集中,RS在p=0.9时取得最小值，这表明，SMD1算法在p=0.9时准确率最高。

用Ou、Ov分别表示用户u和v购买过的商品集合，u和v共同购买的商品越多，则他们越有可能有共同的兴趣并相互影响，具体定义为

图5 引入一种用户间社交关系的基于复合网的物质扩散仿真结果

(14)

当fuv>0.2，则代表用户之间的兴趣相似，设满足这个条件的用户之间的关系为r3。继续加载r3关系，当p、q取不同的值时，平均排序分RS值的变化如图6所示。

图6 引入两种用户间社交关系的基于复合网的物质扩散仿真结果

由图6可知，当p=0.4、q=0.2时，RS的值最小，这表明在Epinions数据集中，SMD2算法在p=0.4、q=0.2时准确率最高。同理可知，在FilmTrust数据集中SMD2算法在p=0.9、q=0.9时准确率最高。在FilmTrust数据集中，由于用户之间的r3关系比r2关系密集，所以当q趋于1时，推荐算法的准确性更高。

为了对比本文提出算法的性能，分别在Epinions数据集和FilmTrust数据集上测试了目前较为常用的推荐算法HeatS和Hybrid[25-26]。Hybrid算法在这两个数据集上的RS最优值分别在调节参数λ为0.67和0.5时得到。当p、q取最佳参数值时，在Epinions数据集和FilmTrust数据集采用不同推荐算法获得的RS值如表1所示：

表1 不同算法实验结果

由表1可知，在Epinions数据集和FilmTrust数据集上，SMD2算法的推荐准确率比SMD1算法准确率高，且这两种算法的准确率明显高于其他推荐算法。这表明，引入用户之间的多种社交关系，可以较为显著地提高推荐结果的准确率。

除了准确性，推荐列表的多样性也是推荐算法的重要评价指标。由式(13)可知，推荐列表长度不同，平均汉明距离的值不一样。图7和图8分别为各推荐算法在Epinions数据集和FilmTrust数据集中不同推荐列表长度下的推荐多样性的变化。

图7 Epinions上不同算法多样性实验结果

图8 FilmTrust上不同算法多样性实验结果

由图7和图8可知，在同一个数据集和同一个算法中，当推荐列表长度L取不同值时，推荐多样性不一样，且L值越大，推荐多样性越低。这表明，推荐列表越长，不同用户的推荐列表相似度越高。在Epinions数据集和FilmTrust数据集上，SMD2算法和SMD1算法的推荐多样性比传统的物质扩散算法的低。这说明当考虑了用户之间的社交关系时，用户的推荐列表不仅受自己历史评分数据的影响，还受到与该用户有关系的其他用户的历史评分数据的影响，即用户的推荐列表会和与该用户有社交关系的用户的相似度偏高一些，从而导致推荐多样性偏低。HeatS算法相当于是凹透镜一样把用户的历史评分信息发散到了那些不流行的物品上，所以推荐的多样性比传统的MD算法高。从而表明本文所提基于多子网复合复杂网络模型的物质扩散推荐算法能更好地在兴趣相似的用户间进行精准推荐。

4 结论

本文通过融合社交网络信息，基于多子网复合复杂网络模型构建多关系复合网，通过实验证明了本文所提的基于复合网进行物质扩散的算法有效地提高了推荐的准确率。这说明将社交网络中存在的多种关系引入到推荐系统中可以更好地识别用户的潜在感兴趣的商品。实验结果还证明融入两种用户间社交关系比融入一种社交关系以及不考虑社交关系的推荐效果更好，由此可知，将越多的用户间社交关系引入到推荐系统中将会使得推荐结果的准确率越高。进一步发现用户间存在的隐式社交关系，以及这些社交关系对推荐结果的影响，是在今后的研究中需要进一步探索的主要方向。