0 引言

新浪微博、Facebook等各类社交网络的普及和发展对人们的生活产生了积极影响.不断扩大的社交网络规模、源源不断产生的网络信息, 一方面让社交网络用户难以发现自己感兴趣的内容, 另一方面也提出了如何提升用户活跃度的新挑战.好友推荐作为社交网络服务的一项重要功能, 主要通过网络用户或内容的紧密度, 发现与特定用户具有一致兴趣的新用户, 并将其作为潜在好友推送给特定用户.好友推荐能有效提升用户的活跃程度并加强社交网络对用户的粘度.但是, 庞大的用户规模、用户间联系的稀疏性等问题的存在, 使得好友推荐应用面临巨大挑战.

基于社交网络的图结构, 采用图上随机游走的策略来实现推荐应用, 具有很好的可扩展性, 能够有效提升庞大用户基下的推荐性能, 并能应对数据稀疏性带来的挑战^[1].近年来多项好友推荐的研究就是基于该策略进而改进实现的.然而, 当前基于随机游走的好友推荐未能充分地权衡用户间社交亲密度的巨大差异及其对推荐的内在影响, 并忽略了隐式的反向社交影响力因素.这些不足为该角度开展推荐研究提供了空间.对此, 本文引入一种高效的频繁项挖掘算法FP-growth^[2]来计算用户间社交置信度, 借此表示用户亲密度进而辅助优化随机游走的转移概率矩阵, 进而与表达反向社交影响力传播的局部反向搜索相结合以实现更加有效的好友推荐.

另外, 基于随机游走的好友推荐主要根据用户相互间的社交关系, 在图上开展好友关系搜索, 但该方法未能充分兼顾用户局部信息(如用户属性)的利用.用户属性包含诸如用户标签、社交时间、感兴趣的内容等多方面的信息, 对潜在好友关系的判定具有重要价值.鉴于基于用户属性的潜在好友关系推断的不确定性, 而贝叶斯网络作为一种概率推理网络模型, 在应对不确定性问题上具有优势^[3], 本文进一步提出了一种面向用户属性、基于贝叶斯推理的好友关系推理模型, 并与随机游走改进模型协同应用来提升推荐性能.本文算法在DBLP、Facebook、Epinions和Slashdot等真实数据集上与经典算法FOAF、PageRank进行了实验对比与分析, 实验结果充分验证了本文提出算法的有效性.

本文后续内容组织如下:第1节对相关研究工作进行综述; 第2节详细介绍本文提出的算法及其实现; 第3节开展实验分析; 第4节对本文研究工作进行总结.

1 相关工作

按照推荐策略的不同, 社交网络好友推荐可以划分为基于协同过滤的推荐、基于内容的推荐以及基于社交关系的推荐等3类. Bian等^[4]提出了基于个性匹配的协同过滤好友推荐系统MatchMaker, 其允许网络用户与类似的电视角色进行匹配, 并使用电视节目中的角色关系构建并行比较矩阵, 向该用户推荐最适合自己的个性化用户. Wang等^[5]提出了一种基于多维相似度的移动社交网络好友推荐方法, 该方法的优势是支持从空间、时间和兴趣这3个维度通过"差异距离"对用户的相似度进行计算. Huang等^[6]提出了一种基于社交网络间关联的好友推荐算法, 该算法基于网络的特征对各个网络进行不同的"社会角色"关联, 并在网络关联后最大化地保留网络结构, 进而发现用户间的关系, 提出好友推荐建议.

随机游走策略的有效性在多种场合的应用中得到了验证^[7-9], 在推荐问题上的广泛应用也促使其针对特定需求呈现出诸多改进方法. Cheng等^[10]提出了一种基于多特征集的随机游走推荐算法, 该算法根据项目的多种相异特征构建$k$部图, 并在$k$部图上进行随机游走实施推荐. Fouss等^[11]采用主成分分析获取数据中节点特征的相似性, 并将该信息映射到无向加权图中进行随机游走, 进而做出项目协同推荐. Jiang等^[12]提出了一种混合随机游走模型, 其通过构建以社会领域为中心并连接其他域的星型图结构, 允许游走者在辅助域中选择转让项目, 并能够准确预测目标域的用户项目的链接. Zhang等人^[13]的研究兼顾了用户对部分类别项目的偏好, 提出了一种计算每个项目等级分数的随机游走推荐模型, 其可以避免流行项目的主导从而一定程度上保证推荐的覆盖率.

贝叶斯网络在故障定位^[14]、风险评估^[15]、疾病诊断^[16]等多个领域应用广泛, 其在不确定性问题推理方面的优势也为用户间的好友关系推断提供了一种新思路.结合随机游走在应对信息过载、数据稀疏等问题的有效性, 本文贡献了一种将两者加以融合的好友推荐新策略.

2 好友推荐模型 2.1 随机游走改进模型(IRRWR)

社交网络由用户集合和用户之间的社交关系组成.用图对社交网络进行描述, 一个图$G$代表一个社交网络, $G=\langle V, E\rangle$, 其中$V$为$G$的节点集, 描述社交网络中的用户; $E$为$G$的边集, 对应社交关系集合.边集$E$可以等价转换为一个邻接矩阵$A$, $A$内元素的取值规则为

$ \begin{align} a_{i, j}=\left\{ \begin{array}{l} 1, \quad (i, j)\in E, \\ 0, \quad \mbox{其他}, \end{array} \right. \end{align} $

(1)

其中, $i$和$j(i\neq j)$为图中任意两个节点, 当节点$i$和$j$之间有边连接时$a_{i, j}=1, $反之$a_{i, j}=0$.图上随机游走根据邻接矩阵$A$得到转移概率矩阵$P$为

$ \begin{align} p_{i, j}=\frac{a_{ij}}{d_0}, \end{align} $

(2)

其中$d_0$为节点$i$的出度, 即由节点$i$连接到其他节点的边的数目.

用户之间的社交频繁程度对好友推荐具有重要价值, 用"亲密度"来刻画特定用户与其好友之间发生社交互动的频繁程度.在标准的随机游走模型中, 游走者从当前节点等概率地走向其邻接点, 即不同用户间的社交亲密度默认为是等同的.但在实际的社交网络中, 不同社交用户之间的亲密度往往是不等的, 推荐应用需要对用户社交亲密度因素加以权衡.通过对用户数据的频繁项挖掘^[2], 可以得到用户两两间的社交置信度, 表示为

$ \begin{align} c(i, j)=\frac{\sigma (i, j)}{\sigma (j)}, \end{align} $

(3)

其中, $\sigma (i, j)$表示用户$u_i$、$u_j$之间非负面社交互动的次数, $\sigma (i, j)$表示用户$u_j$所有的非负面社交活动总数.置信度$c(i, j)$的大小代表了用户间互动次数$\sigma (i, j)$占单个用户社交活动次数$\sigma (j)$的比重, 可以以此来衡量用户$u_i$对于用户$u_j$的社交亲密度大小.在频繁项挖掘、计算用户置信度的基础上, 即可构造新的随机游走标准化转移概率矩阵$P'^{\text T}$, 定义为

$ \begin{align} p'_{i, j}=\frac{c(i, j)}{\sum\limits_{m=1}^nc(i, m)}, \end{align} $

(4)

其中, $n$为图中节点总数.对于一个确定的节点$i$, 由于分母值是固定的, 因此式(4)所示转移概率与用户亲密度是呈正相关的.此外对于$i$的所有相邻接点, 有$\sum\nolimits_{m=1}^np'_{i, m}=1$, 即转移概率是标准化的.将$P'^{\text T}$带入随机游走模型, 有

$ \begin{align} x_i^{(t)}=\alpha P'^{\text T}\cdot x_i^{t-1}+(1-\alpha)x_i^{(0)}. \end{align} $

(5)

基于FP-growth的随机游走模型能够使随机游走过程充分考虑用户间的社交频繁度, 游走过程中让亲密度较高的用户之间获得更多的访问机会.

随机游走模型通过游走者在网络图中随机漫步, 计算从一个节点出发到达网络中其余节点的概率, 这个过程其实可以看成是对特定用户社交影响力传播情况的搜索.社交影响力可以解释成, 当一个网络用户的行为及思想发生变化时, 与其邻近的用户也表现出类似变化的一种效应.在上述模型中, 社交影响力被认为是由目标用户施加给其余用户, 称之为正向社交影响力.然而在现实生活中, 人们也比较倾向于被动地接受外来的社交影响, 并做出相应的行为, 这种效力称之为反向社交影响力.

给定网络图$G=(V, E)$和目标节点$i$, $i$受到的反向社交影响代表着$G$中所有非$i$节点对$i$施加的正向社交影响, 用$x_{i, l}^\text {Reverse}(j)$来表示$i$所受单个节点$j$的反向影响并定义为

$ \begin{align} x_{i, l}^\text {Reverse}(j)=x_{j, l}(i), \quad \forall j\in V, j\neq i, \end{align} $

(6)

其中, $j$为待测节点, $l$为反向搜索的步数.根据"小世界"理论^[17], 社交网络节点之间最短路径的长度一般不会超过6, 因此本文设定步长$l$在2~6之间.

最后通过系数$\beta$来对随机游走正向搜索和局部反向搜索两者加以平衡, 有

$ \begin{align} \text {Rec}_i=\beta x_i+(1-\beta)x_{i}^\text {Reverse}, \end{align} $

(7)

则好友推荐得分是正向搜索和反向搜索的综合, 其中$x_i$为分布收敛的随机游走正向搜索概率分布向量, $x_{i}^\text {Reverse}(j)$为反向搜索概率分布向量, 对$x_{i}^\text {Reverse}(j)$有

$ \begin{align} x_{i}^\text {Reverse}(j)=\frac{1}{\Delta}\sum\limits_l x_{i, l}^\text {Reverse}(j), \end{align} $

(8)

其中, $x_{i, l}^\text {Reverse}(j)$为步长$l$下的反向搜索向量, $\Delta$为局部反向搜索次数(本文$l$在2~6之间取值, 故此处$\Delta$等于5).最后将推荐得分向量Rec$_i$按元素值倒序排序, 去掉其中与目标用户已存在连接关系的节点, 并取前$k$个节点即构成Top-$k$推荐列表.

2.2 融合贝叶斯推理的好友推荐模型(BN-IRRWR)

贝叶斯网络用有向无环图来表述变量间的依赖关系, 并且通过条件概率表(Conditional Probability Table, CPT)来表示变量取值的联合概率分布.具体地讲, 一个贝叶斯网络$B$由两部分构成:结构$G$和参数$\varTheta$.网络结构$G$是一个有向无环图, 包括节点和有向边两部分, 其中节点代表单个变量(属性), 认为有因果关系的变量则用有向边来连接; 而参数$\varTheta$为这种依赖关系的概率化描述.

任意一个用户, 其包含了若干个社交属性, 用集合$A=\{a_1, a_2, \cdots, a_n\}$表示.对于一个特定用户$u_p$和网络中另一个用户$u_i$, 两者对应属性的对比结果, 构成向量$X=\{x_1, x_2, \cdots, x_n\}$, 基于属性值类型, $x_i$可以有不同的取值方式.将其中的每一个元素映射为网络中的一个节点, 再加上用户对是否互为好友的结果变量$f$, 即构成了贝叶斯用户关系推理网络的节点集$\{x_1, x_2, \cdots, x_n, f\}$.为了均衡每个用户属性对结果的影响程度, 假设集合$X=\{x_1, x_2, \cdots, x_n\}$中任意两个变量之间是相互独立的, 共同作用于结果变量"$f$", 如图 1所示.对应联合概率分布为

$ \begin{align} P(x_1, x_2, \cdots, x_n, f)=P(x_1)P(x_2)\cdots P(x_n)P(f|x_1, x_2, \cdots, x_n). \end{align} $

(9)

在网络结构已知情况下, 只需要对训练样本进行计数, 近似估算出节点的CPT即可.考虑到训练样本可能会出现不完备的情况, 即用户属性有可能观察不到, 例如部分用户在注册账号时跳过了相关信息的填写, 此种情况则难以直接通过样本计数完成网络参数估计.用$B$表示已观测的变量集合, 用$H$表示无法观测的变量构成的隐变量集.现对$\varTheta$进行最大似然估计,

$ \begin{align} L_{\max}(\varTheta|B, H)=\max\ln P(B, H|\varTheta). \end{align} $

(10)

由于$H$无法观测, 无法直接对式(10)进行求解.这里可以采用EM算法^[18]来对隐变量$H$求期望, 从而最大化$B$的边缘似然.计算公式为

$ \begin{align} L_{\max}(\varTheta|B, H)=\max\ln P(B, H|\varTheta)=\max\ln \sum\limits_H P(B, H|\varTheta) \end{align} $

(11)

EM算法以初值$\theta^0$为起点, 迭代以下步骤直到收敛.

(1) E步.根据当前的参数分布$\theta^t$计算$L(\varTheta|B, H)$关于隐变量$H$的期望值, 并用$Q(\varTheta|\theta^t)$表示, 为

$ \begin{align} Q (\varTheta |\theta ^t)=\text E_{H|B, \theta ^t}L (\varTheta|B, H). \end{align} $

(12)

(2) M步.求参数$\theta ^t$的最大期望似然, 更新参数分布$\theta ^{t+1}$, 公式为

$ \begin{align} \theta ^{t+1}=\text {argmax} Q(\varTheta|\theta ^{t}). \end{align} $

(13)

确定了用户关系推理的贝叶斯网络结构和参数, 即可进行用户潜在好友关系推断.贝叶斯网络推理有两种方式: ①当网络结构简单且节点数少时, 可以通过贝叶斯定理以及联合概率分布来准确计算查询变量后验概率的"精确推理"; ②当网络节点较多或结构复杂时, 可采用吉布斯采样^[19]方法进行"近似推理".

通过贝叶斯网络推理可以得出用户$j$与目标用户$i$之间存在潜在好友链接的概率大小$p_{f|A}(i, j)$, 作为好友推荐的依据之一.为了综合权衡用户属性与社交关系两方面的因素提升推荐性能, 引入系数$\delta$对式(7)所示好友推荐得分的计算方式做进一步的优化

$ \begin{align} \text {Rec}_i(j)=\delta (\beta x_i(j)+(1-\beta)x_i^\text {Reverse}(j))+(1-\delta)p_{f|A}(i, j), \end{align} $

(14)

其中Rec$_i(j)$为将用户$j$推荐给目标用户$i$的得分.

融合贝叶斯推理模型与随机游走优化模型的好友推荐算法见算法1.

3 实验 3.1 数据集与评价指标

本文共使用4个真实的社交网络数据集来测试本文所提算法的有效性.各个数据集概要信息见表 1所示.

实验采用准确率(Precision)和平均倒数排名(Mean Reciprocal Rank, MRR)两个评价指标对好友推荐算法的性能进行考察, 两个指标的说明如下.

(1) 准确率

推荐准确率(Precision)为受推荐节点与目标节点$i$之间确实存在未知好友链接的比例, 为

$ \begin{align} \text {Precision}(i)=\frac{N_a(i)}{k}, \end{align} $

(15)

其中, $N_a(i)$为推荐列表中确实与$i$存在好友链接的节点数, $k$为推荐列表长度.

(2) 平均倒数排名

平均倒数排名(MRR)为真实的目标用户好友在好友推荐列表中排名倒数的均值, 为

$ \begin{align} \text {MRR}(i)=\frac{1}{N}\sum\limits_{j=1}^{N}\frac{1}{L_j}, \end{align} $

(16)

其中, $L_j$为用户$i$的真实好友在好友推荐列表中的排名, $N$为好友数量.显然推荐列表中位置靠前的用户往往更容易受到目标用户的注意.因此当真实好友在推荐列表中的位置越靠前, 即MRR值越大, 则说明推荐的效果越好.

3.2 参数设定

该部分通过实验确定正向搜索的游走步数以及重启动系数这两个参数的取值.为了给不同数据集确定一组统一的参数, 该部分实验结果以4个数据集上的平均值进行展示, 见图 2所示.

(1) 游走步数

当游走步数足够, 随机游走正向搜索将达到收敛, 此时状态向量内元素取值不再变化.在不同的游走步数下随机游走模型收敛程度的实验结果如图 2(a)所示.从图 2(a)可以看出, 随着游走步数的增加, 随机游走模型迅速收敛, 当游走步数达到100时已达到绝对收敛.因此, 将正向随机游走的搜索步数定为100.

(2) 重启动系数

图 2(b)显示了本文针对$\alpha$取值对MRR值影响情况的实验结果.从图 2(b)中可以看出, MRR的最大值在$\alpha$取0.85附近, 即当$\alpha$取0.85左右时随机游走模型性能最好.因此实验中设定重启动系数$\alpha$的值为0.85.

3.3 实验结果

IRRWR算法引入随机游走局部反向搜索对反向社交影响力效应进行表达, 并通过系数$\beta$来平衡正向搜索与反向搜索的影响权重.图 3表示了IRRWR算法在$\beta$的不同取值下MRR指标的变化情况, MRR的值取4个数据集上的平均值, 以为不同数据集确定统一的$\beta$值.显然, MRR值呈现出随着$\beta$值的增加先升高后下降的趋势, 并且在$\beta$为0.5附近时MRR取得最大值, 说明当$\beta$取0.5左右时IRRWR算法推荐性能最好.因此在接下来的实验中$\beta$值设置为0.5.

本文将IRRWR算法在DBLP、Facebook、Epinions和Slashdot数据集上与经典算法FOAF以及PageRank算法进行了对比实验, 实验中推荐长度设为20.图 4(a)展示了准确率Precision的实验对比结果.整体上看, IRRWR算法在这几个数据集上推荐性能都要优于FOAF以及PageRank算法, 其中, 在DBLP及Facebook数据集上IRRWR算法具有较明显的优势; 而在Epinions和Slashdot数据集上的准确率提升相对较小.此外PageRank算法也在指标Precision上整体优于FOAF算法, 仅在Facebook数据集上略逊于后者.

图 4(b)显示了IRRWR算法、PageRank算法及FOAF算法在DBLP、Facebook、Epinions和Slashdot这4个数据集上关于MRR指标的对比实验结果.可以看出, PageRank算法在4个数据集上的MRR值均要高于FOAF算法; 而IRRWR算法在MRR指标上比PageRank算法表现得更好.这说明IRRWR算法具有更好的推荐效果.

由于数据集中的属性信息限制, 本文仅在DBLP数据集上进行了BN-IRRWR算法的对比实验.选取DBLP数据集中作者的"合作者"、"发表论文的期刊或会议"、"论文标题的关键词"以及"发表论文时间"这几个属性, 在作者对之间构成"是否有共同合作者C"("是/否"取值"Y/N")、"是否在相同期刊或会议上发表论文J"("是/否"取值"Y/N")、"发表论文的标题中有无相同或相似的关键词K"("有/没有"取值"Y/N")、"3年内是否有过合作T"("是/否"取值"Y/N")这几个观测变量, 以及查询变量"是否为好友F"(即测试集中有过合作关系的作者, "是/否"取值"Y/N").从训练集中共随机抽出104个作者组成52个作者对, 进行贝叶斯好友推理网络参数训练, 其中50%为有合作关系的作者对, 另外50%为无合作关系的作者对.

图 5显示了不同$\delta$取值下的BN-IRRWR算法的MRR值变化情况.可以看出MRR值随着$\delta$取值的增加而缓慢提高, 到$\delta=0.8$附近时取得最大值, 之后随着$\delta$取值的增加有小幅下降.由于当$\delta$在0.7$\sim $0.9时, BN-IRRWR的MRR值要高于$\delta=1$时的MRR取值, 而当$\delta=1$时BN-IRRWR算法将退化为IRRWR算法, 这说明在合适的$\delta$取值下, 应用BN-IRRWR算法比应用IRRWR算法能获得更佳的推荐效果.

4 结论

好友推荐服务对提升社交网络的粘度以及用户的活跃度具有重要作用, 本文基于随机游走策略的优势以及当前研究的不足, 将基于随机游走的好友推荐算法在通过引入频繁项挖掘优化转移概率矩阵, 与局部反向搜索相结合两个角度上进行了改进.此外, 为了充分利用用户属性信息的价值, 本文提出了一种基于贝叶斯推理的用户潜在好友关系判定模型, 并与随机游走相结合实现好友推荐. DBLP、Facebook、Epinions和Slashdot等真实数据集上的对比实验展现了本文提出的好友推荐方法的有效性.