PageRank算法的應用

PageRank 算法是 Google 搜索引擎進行網頁排名的一種算法，那么它如何映射到其他領域？

比如，我們如何在文獻排名中應用PageRank算法呢？

對文獻的質量進行排序是對文獻價值進行評估的一種重要手段，目的是為了方便人員在檢索時查閱。

統計文獻的被引次數是一種非常直觀的統計方式，在此基礎之上，我們引入了 PageRank算法：該算法基于網頁之間的鏈接關系評估網頁的價值，由于互聯網與文獻引用網絡之間存在著較大的相似性，所以基于文獻之間的引用網絡使用 PageRank 算法可以更合理的對于文獻的價值評估。

該算法基于一種投票關系：A 文對 B 文進行了引用是因為 A 文認為 B 文質量較高，即通過引用的方式給B文投票，之后再通過投票關系對文獻進行排名。

根據PageRank的原理，在文獻排名的過程中，PageRank 算法同樣遵循以下兩個基本假設：

數量假設。如果一篇文獻 A 被其他文獻引用，說明其他文獻認為文獻 A 比較重要，也就是其他文獻將自己的 PageRank 值貢獻給 A。表明 A 是一篇有質量的文獻，所以文獻 A 的 PageRank 值會比較高。

質量假設。如果一篇高 PageRank 值的文獻引用了一篇其他的文獻，則被引用的文獻的 PageRank 值也因此而提高。

算法的公式形式不變，如下所示，但是其中各個量的含義會發生變化。

其中 p 代表某個待評價的學術文獻，d是阻尼系數。CTotal 是文獻總量。N 表示 N 篇引用了 p 的文獻，Xi 表示第 i 個引用了 p的文獻，C(Xi)表示 Xi 這篇文獻總的參考文獻數目。

看下面的例子，假如這是迭代過程中的一個片段，PR值的分配傳遞過程如下圖所示：

偽代碼如下：

PageRank算法基于時間的改進和迭代優化

針對傳統 PageRank 算法迭代過程復雜、時效性不強、執行速度慢等缺點，可以進行了優化迭代過程、增加時間因子影響函數、并行化三點改進。

我們將改進的算法稱為NTMP 算法——在優化迭代過程時，通過對于被引文獻的特征進行統計，按照權威度的方式進行 NTMP 值分配。根據文獻被引半衰期這一特征，使用時間因子影響函數更好的對文獻價值進行評價。最后將改進后的算法進行了基于MapReduce 計算框架的并行化處理，最終構成 NTMP 算法。

加入時間影響因子

NTMP 算法進行文獻評價時有如下三點假設：

1）數量假設

2）質量假設

3）影響力衰減假設：一篇文章的影響力不是一成不變的，其影響力會根據時間的推移進行適當衰減。如果不對文獻的影響力在時間上進行約束，就會造成在文獻排名時，影響力較大的總是那些發表時間久遠、被引次數多的文獻，新發表的文獻不能被很好的評價，這就導致了新發表的文獻在排名時一直處于比較靠后的位置，不能受到很好的重視。所以僅考慮文獻之間的引用關系而忽略時間因素在文獻排名過程中的不利影響是不夠的。尤其研究者們應該重視那些新發表的文獻，這些文獻代表著當前研究趨勢、研究熱點。

這里引入了文獻半衰期的概念。

半衰期是指放射性元素的原子核有半數發生衰變時所需要的時間。

這里給出的定義如下：在 N 年（某一年時間內）被引用的文獻中，較新的一半是在最近 X 內發表的。這個 X 就是文獻被引半衰期。例如某一年，整個數據集中共發表文獻 176922 篇，其中累積引用計算機學科文獻 289421 頻次，再根據定義求得文獻被引半衰期為 6.78 年。

根據定義：

其中，W 是所求的被引半衰期，U 是累積百分比小于且最接近 50%的年數，X 為統計年至 U 年的被引累積百分比，Y 為統計年至 U+1 年的被引累計百分比。

有了這個半衰期的定義，我們建立一個時間影響因子函數：

其中，HL(t)為文獻價值剩余百分比，CTotal 代表的是該數據集中初始時刻(t=0 時)所有文獻的數量，t 是衰變時間，T 為計算機學科文獻被引半衰期。時間因子影響函數HL(t)的含義是在計算機學科中，某一篇文獻從發表(t=0 時)開始，經過 t 時間后，文獻的剩余價值變為原來的 HL(t)倍。

迭代優化

在進行 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的學術文獻排名及作者影響力評價算法》崔景洋

總結

以上是生活随笔為你收集整理的PageRank算法改进的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。