PageRank算法的应用

PageRank 算法是 Google 搜索引擎进行网页排名的一种算法，那么它如何映射到其他领域？

比如，我们如何在文献排名中应用PageRank算法呢？

对文献的质量进行排序是对文献价值进行评估的一种重要手段，目的是为了方便人员在检索时查阅。

统计文献的被引次数是一种非常直观的统计方式，在此基础之上，我们引入了 PageRank算法：该算法基于网页之间的链接关系评估网页的价值，由于互联网与文献引用网络之间存在着较大的相似性，所以基于文献之间的引用网络使用 PageRank 算法可以更合理的对于文献的价值评估。

该算法基于一种投票关系：A 文对 B 文进行了引用是因为 A 文认为 B 文质量较高，即通过引用的方式给B文投票，之后再通过投票关系对文献进行排名。

根据PageRank的原理，在文献排名的过程中，PageRank 算法同样遵循以下两个基本假设：

1. 数量假设。如果一篇文献 A 被其他文献引用，说明其他文献认为文献 A 比较重要，也就是其他文献将自己的 PageRank 值贡献给 A。表明 A 是一篇有质量的文献，所以文献 A 的 PageRank 值会比较高。
2. 质量假设。如果一篇高 PageRank 值的文献引用了一篇其他的文献，则被引用的文献的 PageRank 值也因此而提高。

算法的公式形式不变，如下所示，但是其中各个量的含义会发生变化。

看下面的例子，假如这是迭代过程中的一个片段，PR值的分配传递过程如下图所示：

伪代码如下：

PageRank算法基于时间的改进和迭代优化

针对传统 PageRank 算法迭代过程复杂、时效性不强、执行速度慢等缺点，可以进行了优化迭代过程、增加时间因子影响函数、并行化三点改进。

我们将改进的算法称为NTMP 算法——在优化迭代过程时，通过对于被引文献的特征进行统计，按照权威度的方式进行 NTMP 值分配。根据文献被引半衰期这一特征，使用时间因子影响函数更好的对文献价值进行评价。最后将改进后的算法进行了基于MapReduce 计算框架的并行化处理，最终构成 NTMP 算法。

加入时间影响因子

NTMP 算法进行文献评价时有如下三点假设：

1）数量假设

2）质量假设

3）影响力衰减假设：一篇文章的影响力不是一成不变的，其影响力会根据时间的推移进行适当衰减。如果不对文献的影响力在时间上进行约束，就会造成在文献排名时，影响力较大的总是那些发表时间久远、被引次数多的文献，新发表的文献不能被很好的评价，这就导致了新发表的文献在排名时一直处于比较靠后的位置，不能受到很好的重视。所以仅考虑文献之间的引用关系而忽略时间因素在文献排名过程中的不利影响是不够的。尤其研究者们应该重视那些新发表的文献，这些文献代表着当前研究趋势、研究热点。

这里引入了文献半衰期的概念。

半衰期是指放射性元素的原子核有半数发生衰变时所需要的时间。

这里给出的定义如下：在 N 年（某一年时间内）被引用的文献中，较新的一半是在最近 X 内发表的。这个 X 就是文献被引半衰期。例如某一年，整个数据集中共发表文献 176922 篇，其中累积引用计算机学科文献 289421 频次，再根据定义求得文献被引半衰期为 6.78 年。

根据定义：

有了这个半衰期的定义，我们建立一个时间影响因子函数：

迭代优化

在进行 PR 值的传递时，传统算法会将每篇文献的 PR 值平均分给该文献所引用的其他文献。

 NTMP算法的改进：将NTMP 值向着那些重要的文献流动，提升分配效率和收敛速度。

BC_Sum是文献集合R(X)中所有文献 Pj 的被引次数之和。

W(X,p)是计算集合R(X)某一篇文献 P 被引次数的所占比重，可以理解为文献 P 在分配 X 的 NTMP 值时所占权重。

NTMP 算法的输入是基础文献信息，包括文献发表时间，文献引用关系等，输出是各待评价样本的 NTMP 值，可以根据 NTMP 值对待评价样本进行排名。

根据上述改进方法，NTMP 算法的公式为：

其中 xi 引用了文献 P 的施引文献，NTMP(xi)表示上一次迭代结束后 x 的 NTMP值，函数 W(Xi,P)是之前提出的 NTMP 值分配方式，函数 HL(t)是时间因子影响函数，d 是阻尼系数一般取 0.85，CTotal 是数据集中的文献总量。

PageRank算法在分布式集群中的应用

Map阶段：计算出每条样本给其参考文献所贡献的 NTMP 值

Reduce阶段：将 Map 阶段所传出的每一篇 Xi 为 P所贡献的 NTMP 值相加，再乘以阻尼 d，之后加上调整项即为文献 P 的 NTMP 值

具体过程如下：

map阶段：

reduce阶段：

本文参考论文《基于Hadoop的学术文献排名及作者影响力评价算法》崔景洋