0 概述

随着互联网的飞速发展, 各种新型社交平台不断涌现, 人们在社交平台中扮演着不同的角色, 从而形成了复杂的用户社交网络。随着社交网络中的用户数量越来越大, 如何根据输入信息快速准确地搜索到复杂网络中的用户, 是当前研究面临的一个重要问题。基于网页链接结构的PageRank算法^[1]在Google中的成功应用, 证明了该算法的研究和应用价值。然而, 随着对PageRank算法的研究逐步深入, 该算法存在的不足, 如排序结果不唯一、主题漂移等^[2], 也逐渐显现。

针对PageRank算法存在的问题, 许多国内外专家对其进行改进。文献[3]针对PageRank算法在网络节点排序过程中可能出现排序结果不唯一的问题, 提出LeaderRank算法, 在复杂有向网络中加入一个Ground节点, 使复杂有向网络构成强连通图。由于LeaderRank算法排序结果唯一且对网络噪音有更好的容忍性, 因此其在复杂网络节点排序中有较大优势。文献[4]以LeaderRank算法为基础提出加权LeaderRank算法, 使网络中的其他节点可以从Ground节点中获取部分权值。与LeaderRank算法相比, 加权LeaderRank算法的排序结果更加准确且具有更好的鲁棒性。但是, 这2种算法并没有解决主题漂移和LeaderRank值(LR值)均分等问题。为此，本文在加权LeaderRank算法的基础上，提出一种用户社交网络排序算法。引入链入链出权重因子，为链出因子分配较大的权值，以弥补原始算法中权值均分的问题。利用主题相关度因子，以减少权值在无关用户上的扩散。借鉴牛顿冷却定律的思想，引入时间衰减度因子，减弱用户兴趣转移带来的影响。

1 相关研究 1.1 LeaderRank算法

LeaderRank算法的思想是在已知有向网络G(N, M)中添加一个公共节点, 得到具有N+1个节点的有向网络G(N+1, M+2N)。由于公共节点与网络中的其他节点存在双向连接, 因此G构成了一个强连通图, 且图中所有节点的出度和入度均大于0, 避免在复杂网络中出现孤立节点, 以保证算法的收敛性。LeaderRank算法的网络结构如图 1所示。LR值的计算公式如下:

$ L{R_u} = L{R_u}\left( {{t_c}} \right) + \frac{{L{R_g}\left( {{t_c}} \right)}}{N} $

(1)

$ L{R_u}(t + 1) = \sum\limits_{v = 1}^{N + 1} {\frac{{{a_{vu}}}}{{k_v^{{\rm{out }}}}}} L{R_v}(t) $

(2)

其中, LR_u表示节点u的LR值, LR_g表示公共节点g的LR值, t_c为LR_u收敛的时刻, N为网络中除去公共节点后的节点个数, a_vu为网络中节点v到节点u的权值初始值, 当节点v和节点u存在边时, a_vu取值为1, 否则a_vu取值为0, k_v^out表示节点v的出度。

LeaderRank算法的计算结果可以收敛到一个稳定的数值, 尤其适用于大型复杂有向网络, 可解决复杂网络节点中排序结果不唯一的问题, 提高排序的准确性和抗噪声能力^[5-6]。

1.2 加权LeaderRank算法

在加权LeaderRank算法中, 考虑到网络中节点本身的结构特性, 每个节点都有各自的特点, 因此, 允许节点从公共节点中获取一部分权值, 以偏置随机游走算法代替标准随机游走算法。加权LeaderRank算法的计算公式如下:

$ {s_u}(t + 1) = \sum\limits_{v = 1}^{N + 1} {\frac{{{w_{vu}}}}{{\sum\limits_l^{N + 1} {{w_{vl}}} }}} {s_v}(t) $

(3)

$ {w_{ji}} = \left\{ {\begin{array}{*{20}{l}} {{{\left( {k_i^{{\rm{in }}}} \right)}^\alpha },j \to i,j = g}\\ {1,j \to i,j \ne g}\\ {0,j \nrightarrow i} \end{array}} \right. $

(4)

其中, w_vu表示节点之间边的权值, g为添加的公共节点, α为一个可调节参数, k_iⁱⁿ表示节点i的入度, j→i表示节点j存在到节点i的边, j $\not \to $i表示节点j不存在到节点i的边。

由式(3)和式(4)可知, 当Ground节点存在指向i节点的边时, 其权值与节点i的入度有关。因此, 不同的节点从Ground节点获取到的权值是不同的, 在迭代计算过程中, 节点的入度越多, 从Ground节点获取的权值就越大。

加权LeaderRank算法的每个节点从Ground节点获得的权值不同, 可提高算法的准确率, 使其具有更好的鲁棒性。

1.3 其他相关算法

文献[7]根据网页被检索后的点击次数, 对PageRank值进行迭代修正, 提高网页的精确率。文献[8]提出一种基于MapReduce框架的并行算法, 具有较快的执行速度。由于用户易受作弊网页的干扰, 文献[9]通过分析用户搜索行为, 获取链接点击量、页面停留时间等反馈信息, 以提高算法的准确率和鲁棒性。文献[10]通过分析用户之间的情感倾向、评论隐含关系、评论的时间衰减等因素, 基于PageRank算法对用户进行排名, 以挖掘网络中的意见领袖, 但该算法不能保证在快速变化的网络中的收敛性。文献[11]构建一幅TwitterRank好友关系图, 并且在PageRank算法的基础上提出TwitterRank算法。

基于电气LeaderRank算法的电网节点重要度评估方法根据负荷和负荷量的重要程度, 按照不同比例分配网络中所有节点的LR值。文献[12]考虑到用户情感倾向以及恶意注册的问题, 对LeaderRank算法进行改进, 用微博中“赞”的个数来表示用户的情感倾向, 通过添加时间衰减函数, 减弱恶意注册用户的影响。与LeaderRank算法相比, 该算法在一定程度上提高了算法的准确性, 且具有较强的抗干扰能力, 但其考虑的情况较为单一。文献[13]基于LeaderRank算法和加权LeaderRank算法, 对节点进行聚类计算, 以获得网络边的权值。文献[14]通过实验对大量的Twitter数据进行分析, 发现有影响力的用户在各种话题中起重要作用。

综上所述, LeaderRank算法和加权LeaderRank算法在复杂网络节点排序中所起的作用越来越重要。但是, 这2种算法仅考虑Ground节点对其他节点的影响, 未考虑节点之间的相互影响, 对于PageRank算法存在的一些问题, 如网页权值平均分配、偏向旧网页等, LeaderRank算法和加权LeaderRank算法仍未能解决。

2 改进的加权LeaderRank算法

考虑到用户与用户之间存在关注与被关注的关系, 本文假设用户所关注的人比用户的粉丝更重要, 引入链入链出因子。采用深度学习模型GloVe对查询句子与用户的帖子进行向量化表示, 并计算向量化后数据的余弦相似度, 从而得到主题相关度因子。由于用户可能存在兴趣转移的情况, 因此引入时间衰减度因子减弱用户旧帖的影响力。基于此, 本文提出WTLR(LeaderRank based on Weighted and Topic)算法, 其具体的计算过程如式(5)所示。

$ L{R_u}(t + 1) = \sum\limits_{v = 1}^{N + 1} {\frac{{{W_{uv}}}}{{k_v^{{\rm{out }}}}}} L{R_v}(t) + \frac{{{w_{gu}}}}{{\sum\limits_{l = 1}^{N + 1} {{w_{gl}}} }}L{R_g}(t) $

(5)

其中, k_v^out为用户节点v的出度, $\frac{{w_{gu}}}{{\sum\limits _ { l = 1 } ^ { N +1 } } w_{gl}} L R _ { g } ( t )$为Ground节点分配给用户节点u的权值。

在迭代计算之前, 通过分析得到加权LeaderRank算法的初始概率转移矩阵P, 如式(6)所示。

$ \mathit{\boldsymbol{P}} = \left[ {\begin{array}{*{20}{c}} {{W_{11}}}&{{W_{12}}}& \cdots &{{W_{1n}}}\\ {{W_{21}}}&{{W_{22}}}& \cdots &{{W_{2n}}}\\ \vdots & \vdots &{}& \vdots \\ {{W_{n1}}}&{{W_{n2}}}& \cdots &{{W_{nn}}} \end{array}} \right] $

(6)

其中, 矩阵P中的第i行第j列的元素W_ij表示由节点i转移到节点j的概率。

通过引入链入链出因子、主题相关度因子和时间衰减度因子, 重新计算概率转移矩阵。在迭代过程中, 为相关性较大的用户分配较高的权值, 给相关性较小的用户分配较低的权值, 最终使用户获得一个较为合理的权重。本文通过线性拟合的方法得到改进的矩阵元素W_ij, 计算公式如下:

$ {W_{ij}} = \alpha {w_{v,u}} + \beta T\mathit{Sim}(u) + \gamma {\theta _u}(t) $

(7)

其中, u和v为用户节点, w_{v, u}为用户节点的链入链出因子, TSim(u)为主题相关度因子, θ_u(t)为时间衰减度因子。3个特征因子的权重之和为1, 通过多次实验调节权重, 以确定最合理的组合方式。

WTLR算法的具体步骤如算法1所示。

算法1    WTLR算法

输入  查询句子l, 用户网络初始邻接矩阵P₀, 用户及帖子矩阵T, 用户最近发帖时间t₀, 时间衰减系数θ^*

输出   稳定的LR值

1.计算用户网络节点的链入链出因子;

2.利用GloVe模型生成用户帖子向量和查询句子向量;

3.对帖子向量与查询句子向量进行相似度计算;

4.根据用户最近发帖时间t₀与时间衰减度因子, 计算帖子衰减程度;

5.根据式(7)计算用户网络邻接矩阵的转移概率矩阵P;

6.t←0, ▽←1;

7.while(▽>10^－5)

8.LR_u(t+1)= $\sum\limits _ \text{ v = 1 } ^ \text{ N + 1 } \frac { \text{W} _ \text{ uv } } { \text{k} _ \text{ v } ^ { \text { out } } } \text{LR} _ {\rm v } ({\rm t} ) + \frac { {\rm W} _ { \rm {g u} } } { \sum\limits _ { {\rm l} = 1 } ^ { \rm N + 1 } \rm W _ { g l } } {\rm L R _ { g } ( t )}$

9.▽=LR_u(t+1)－LR_u(t)

10.t←t+1

11.end while

12.return LR_u

2.1 链入链出因子

本文借鉴基于链接结构的PageRank算法^[15], 引入链入链出因子, 其主要思想是用户节点的入链和出链越多, 节点越重要, 且节点的链出因子比链入因子更重要。

在复杂有向网络中, 一部分用户具有较高的话语权, 这些用户即为影响力较高的用户。影响力较高的用户在排序过程中应该有更为核心的排序位置, 起到关键的作用, 这就要求节点有较多的入链和出链。然而, 原始的LeaderRank算法和加权LeaderRank算法都是基于节点的正向链接均分节点的LR值, 这会使得一些节点, 如僵尸节点, 分配到较多的LR值, 导致结果中出现不相关的用户, 引起主题漂移, 从而降低排序结果的准确率。因此, 在计算用户节点的LR值时, 要考虑用户节点的入链数目和出链数目, 同时依据重要程度分配LR值, 使影响力高的用户有较靠前的排名。

本文假设用户节点链出因子的重要性高于链入因子, 即用户所关注的人比用户的粉丝更重要。当用户所关注的人和用户的粉丝同时发布帖子时, 通常用户更倾向于查看所关注的人的帖子。因此, 本文在分配链入链出因子时, 为链出因子分配较大的权值, 实验结果表明, 当分配系数μ取0.7时效果最好。链入链出因子w_{v, u}的计算过程如下:

$ {w_{v,u}} = \mu w_{v,u}^{{\rm{out }}} + (1 - \mu )w_{v,u}^{{\rm{in }}} $

(8)

$ w_{v,u}^{{\rm{in}}} = \frac{{{I_u}}}{{\sum\limits_{p = B(v)} {{I_p}} }} $

(9)

$ w_{v,u}^{{\rm{out}}} = \frac{{{O_u}}}{{\sum\limits_{p = B(v)} {{O_p}} }} $

(10)

其中, w_{v, u}ⁱⁿ为链入因子, w_{v, u}^out为链出因子, I_u和O_u分别表示用户节点u的入链和出链, B(v)为用户节点v的粉丝集合, I_p、O_p分别表示用户节点v的粉丝的入链和出链。

2.2 主题相关度因子

目前, 基于加权LeaderRank的改进算法仅考虑主题用户节点的链入链出关系, 这是不全面的。用户影响力排序模型^[16]根据论坛中帖子回复者的倾向性或情感转变程度决定发帖者对回复者的影响程度, 能较好地度量用户的影响力。本文利用搜索句子与用户帖子计算主题相关度, 以分配用户节点的LR值。由于每个用户发表的帖子数量不等, 内容也不同, 因此帖子与搜索句子的内容相关性越大, 用户与搜索句子的相关性也越大。

2.2.1 文本向量化表示

文献[17]提出的GloVe模型是一种基于全局的对数双线性回归模型。该模型分析Skip-gram模型能够挖掘词与词之间线性关系的原因, 结合全局矩阵分解和局部上下文窗口方法的优点, 只对词共现矩阵的非零元素进行训练, 避免在大型语料库中对整个稀疏矩阵或单个上下文窗口进行训练。

GloVe模型采用规定大小的窗口来统计单词出现的次数, 构成共现矩阵X。矩阵元素X_ij表示单词j与单词i在同一个窗口中出现的次数。矩阵X的元素与词向量的关系如式(11)所示。

$ \mathit{\boldsymbol{w}}_i^{\rm{T}}{{\mathit{\boldsymbol{\tilde w}}}_j} + {b_i} + {{\tilde b}_j} = {\rm lb} {X_{ij}} $

(11)

其中, w_i和${ \mathit{\boldsymbol{\tilde w}}_j}$是单词i和单词j的词向量, b_i和$\tilde b_{j}$为对应的偏差项。根据词的出现频率越高则权重越大的原则, 在代价函数中添加权重项, 得到损失函数如下:

$ J = \sum\limits_{i,j = 1}^V f \left( {{X_{ij}}} \right){\left( {\mathit{\boldsymbol{w}}_i^{\rm{T}}{{\mathit{\boldsymbol{\tilde w}}}_j} + {b_i} + {{\tilde b}_j} - {\rm lb} {X_{ij}}} \right)^2} $

(12)

其中, f(X_ij)为权重函数。由于f(X_ij)为非减函数, 且当词频过高时, 权重不能过大, 因此需通过实验确定权重函数, 具体如式(13)所示。

$ f(x) = \left\{ {\begin{array}{*{20}{l}} {{{\left( {\frac{x}{{{x_{\max }}}}} \right)}^{0.75}},x < {x_{\max }}}\\ {1,x \ge {x_{\max }}} \end{array}} \right. $

(13)

GloVe模型与传统的One-hot表示方法不同, 其使用连续的向量值表示单词, 使进行相似度计算的2个词汇不存在完全孤立的情况, 有效消除词汇鸿沟的现象。

本文利用GloVe模型生成用户节点网络中用户每篇帖子的向量表示, 如式(14)、式(15)所示。

$ {\mathit{\boldsymbol{T}}_i} = \left\{ {{\mathit{\boldsymbol{t}}_{i1}},{\mathit{\boldsymbol{t}}_{i2}}, \cdots ,{\mathit{\boldsymbol{t}}_{ik}}, \cdots ,{\mathit{\boldsymbol{t}}_{iM}}} \right\},i \in (1,N) $

(14)

$ {\mathit{\boldsymbol{W}}_i}(j) = \left\{ {{\mathit{\boldsymbol{w}}_{j1}},{\mathit{\boldsymbol{w}}_{j2}}, \cdots ,{\mathit{\boldsymbol{w}}_{jl}}, \cdots ,{\mathit{\boldsymbol{w}}_{jn}}} \right\},j \in (1,M) $

(15)

其中, T_i为第i篇帖子的词向量表示, 由M个词的向量组成, W_i(j)为第i篇帖子的第j个词向量, 由n维向量组成。实验结果证明, 当对短文本进行向量化表示时, 采用词向量相加取平均值的方法较为有效。因此, 本文所得贴子的向量T_i可表示为如下形式:

$ {\mathit{\boldsymbol{T}}_i} = \frac{1}{M}\sum\limits_{x = 1}^N {{\mathit{\boldsymbol{W}}_i}} (j) $

(16)

2.2.2 主题相关度计算

计算文本相似度的方法有很多, 如余弦相似度、欧氏距离、Jaccard相似性系数、Manhattan距离等, 其中最常用的是余弦相似度和欧氏距离的计算方法。余弦相似度可以有效规避个体相同认知中不同程度的差异表现。虽然该方法在本质上与欧氏距离相同, 但在没有归一化的情况下, 欧氏距离多用于需要从维度的大小中体现差异性的情况, 而余弦相似度用于分析用户兴趣的相似度和差异, 因此, 余弦相似度更适合本文的计算。

本文采用余弦相似度计算查询句子与用户帖子的相似度, 计算过程如式(17)所示。

$ IDSi{m_i} = \frac{{\sum\limits_{k = 1}^n {{\mathit{\boldsymbol{t}}_{ik}}} \times {\mathit{\boldsymbol{s}}_{ik}}}}{{\sqrt {\sum\limits_{k = 1}^n {\mathit{\boldsymbol{t}}_{ik}^2} } \times \sqrt {\sum\limits_{k = 1}^n {\mathit{\boldsymbol{s}}_{ik}^2} } }} $

(17)

其中, IDSim_i表示查询句子与帖子的相似度值, t_ik和s_ik分别表示帖子和查询句子的第k维向量。

主题相关度因子的值由帖子与查询句子的相似度值决定。由于每个用户可以发表多篇帖子, 本文将用户发表的所有帖子与查询句子进行相似度计算, 最后取均值作为该用户与查询句子的相似度值。上述方法可有效减少LR值在无关用户上的扩散, 在很大程度上抑制主题漂移的问题。

2.3 时间衰减度因子

用户节点LR值的大小主要由用户节点所链接的数目以及用户所发布的帖子决定, 用户的链接数目以及帖子数目越多, 该用户节点的LR值就越大。实际上, 随着时间的推移, 用户所发表的帖子的时效性降低, 导致难以发现新的有影响力的用户, 在这种情况下, 加权LeaderRank算法不能很好地满足实际的查询需求。文献[9]为解决排序偏向旧网页的问题, 引入时间相关度因子对网页进行补偿, 取得了较好的排序效果。本文引入牛顿冷却定律^[18-19], 并将其作为时间因子使新用户上浮, 以解决排序偏向老用户的问题。

牛顿冷却定律是指当物体温度高于环境温度时, 其向周围媒介传递热量, 使自身温度冷却。牛顿冷却定律没有考虑物体的性质, 不是一个物性方程, 它是关于抽象物体的温度随时间单纯下降的一个数学微分方程, 如式(18)所示。牛顿莱布尼茨公式可以通过求不定积分来计算函数的定积分, 根据物体表面热流密度公式以及牛顿莱布尼茨公式求解定积分, 可以得到时间衰减度, 如式(19)所示。

$ \frac{{{\rm{d}}T'(t)}}{{{\rm{d}}t}} = - \beta \left( {T(t) - {T_h}} \right) $

(18)

$ \theta (t) = {\theta ^*}{{\rm e}^{ - \left( {t - {t_0}} \right)}} $

(19)

其中, 负号代表降温过程, β为传导系数, t₀为用户最近一次发布帖子的时间, T(t)为物体表面温度, 在t₀时, 物体表面温度为T₀, T_h为物体表面附近的气体温度, θ(t)为时间衰减度因子, θ^*为衰减系数。

从式(19)可以看出, 用户节点的LR值从用户最后一次发表帖子的时间开始衰减, 最后趋于稳定。本文结合时间衰减度因子, 可有效抑制僵尸用户, 使新用户上浮, 提高排序准确率。

3 实验结果与分析 3.1 实验数据集

为验证WTLR算法的性能, 本文采用UCI官网收集的microblogPCU数据集作为实验数据集。通过对数据集进行处理, 去除乱码信息, 得到的数据集规模如表 1所示, 数据集的属性信息如表 2所示。

在得到的数据集中, 本文选取其中70%的数据作为训练集, 30%的数据作为测试集。在训练集和测试集的基础上构造本文所需数据集。选取用户的关注关系及用户的ID信息构造微博用户网络, 便于WTLR算法进行迭代计算。利用用户所发表的微博帖子构造帖子数据集, 并使用GloVe模型生成短文本词向量。

3.2 实验环境和度量标准

本文实验环境为Windows7操作系统, 利用MyEclipse作为IDE工具, 采用MySQL5.6数据库管理系统, 开发环境为JDK1.8, Python2.7, 使用Java语言运行LeaderRank算法、加权LeaderRank算法和WTLR算法并进行对比实验。

在结果分析时, 本文采用排序领域常用的精确率(Precision)、点击率(Click Rate)以及归一化折现累积增益(Normalized Discounted Cumulative Gain, NDCG)作为算法的等级质量评价指标, 并将对比结果通过Python进行可视化展示。

1) 精确率

精确率取决于检索语言的专指性和检索策略能否准确表达用户真正的情报需求, 可用来衡量系统检索信息的能力, 是一项常用的评价排序算法的重要指标。精确率的计算如式(20)所示。

$ \mathit{Precision}@N = \frac{1}{Q}\sum\limits_{q = 1}^Q {\frac{{{R_q} \cap {T_q}}}{{{R_q}}}} $

(20)

其中, N表示查询列表长度, Q表示查询次数, R_q是查询列表所查询的N个用户集合, T_q为符合查询情况的用户集合, R_q∩T_q是查询列表中正确的查询结果集合。

2) 点击率

通过统计用户对网页的点击率可以知道用户对排序结果是否满意。一般网页中最多显示10条查询记录。统计结果表明, 用户一般对前3页的内容较感兴趣。因此, 本文采用点击率作为衡量用户满意度的评价指标, 设置查询列表长度T_total为30, 则点击率的计算公式如下:

$ ClickRate@{T_{{\rm{total}}}} = \frac{1}{Q}\sum\limits_{q = 1}^Q {\frac{{{N_{{\rm{cr}}}}}}{{{T_{{\rm{total }}}}}}} $

(21)

其中, N_cr表示用户点击的查询结果个数, Q表示查询次数。通过Q次查询求平均值, 获得最终点击率。

3) 归一化折现累积增益

NDCG中包含增益(Gain)和折扣(Discount)的计算, 既可满足查询句子与列表的相关性, 又可保证整体结果的质量, 它是搜索引擎排序算法的常用指标。NDCG的计算公式如下:

$ NDC{G_p}@N = \frac{{DC{G_p}}}{{IDC{G_p}}} $

(22)

$ DC{G_p} = \sum\limits_{i = 1}^p {\frac{{{2^{re{l_i}}} - 1}}{{ {\rm lb} (i + 1)}}} $

(23)

其中, p为文档在查询列表中的排序位置, rel_i为处在该位置文档的等级相关性, IDCG_p为排序结果按相关性排序之后能得到的最大折现累计增益(DCG)值。

3.3 结果分析

本文从以下5个方面对算法的结果进行分析:

1) 分配系数μ

为使算法达到最佳效果, 本文以控制变量的形式得出结果, 找到合适的分配系数, 结果如图 2所示。由图 2可知, 当0 < μ < 0.7时, 精确率呈上升趋势; 当0.7 < μ < 1时, 精确率呈下降趋势; 当μ值取0.7时, 精确率最高。

2) 算法参数调节

为确保算法的排序效果最佳, 本文利用十折交叉验证方法进行参数调节, 选择查询列表的Top-N个值作为评价指标, N值分别取25、50、75、100。通过α、β、r取不同的值来观察精确率排序, 结果如表 3所示。由表 3可知, 当β取值大于0.5时, 算法的精确率明显上升。综合考虑偏向旧用户的问题以及链入链出因素可以得出, 当α、β、r的取值分别为0.26、0.63和0.11时, 实验效果最佳。

3) 精确率对比

为验证WTLR算法的准确性, 本文将WTLR算法与LeaderRank算法、加权LeaderRank算法进行对比。采用3.1节的实验数据集, 并选择4种不同的用户查询方式, 即查询句子与主题相关、较相关、相关性不大、不相关, 得到3种算法的精确率对比, 结果如图 3所示。

由图 3可知, 在同样的环境和精确率评价标准下, WTLR算法的精确率较LeaderRank算法和加权LeaderRank算法分别提高10.75%和7.80%, 算法精确率有明显提升, 检索到相关用户的能力增强。可以得出, WTLR算法能够提高排序结果的精确率, 进而改善排序算法的质量。

4) 点击率对比

3种算法在点击率指标上的对比结果如图 4所示。从图 4中可以看出, WRLR算法的点击率较LeaderRank算法和加权LeaderRank算法分别提升8.97%和6.73%。这是因为WTLR算法重新定义了用户节点网络中的转移概率, 使算法在概率转移过程中对主题相关等因素进行考虑, 从而改善排序效果。

5) NDCG对比

将WTLR算法与加权LeaderRank算法、LeaderRank算法进行对比实验, 测试出查询列表数目不同时的NDCG值, 结果如图 5所示。由图 5可以看出, 3种算法的变化曲线大致相同, WTLR算法在N=44时取得最大值, 而加权LeaderRank算法和LeaderRank算法则分别在N为51和56时得到最大值。此外, WTLR算法的NDGG值较加权LeaderRank算法和LeaderRank算法分别提高4.75%和7.31%。由此可知, WTLR算法在排序结构和主题相关方面有较好的结果。

4 结束语

本文提出一种用户社交网络排序算法，将链入链出因子、主题相关度因子和时间衰减度因子整合到加权LeaderRank算法中，以解决权值均分和主题漂移的问题。实验结果表明, 与加权LeaderRank算法相比, 该算法的排序质量提高。下一步将研究该算法在由用户与帖子构成的异构网络中的应用, 以提高异构网络中节点排序的准确性, 改善排序效果。