一種對(duì)網(wǎng)頁(yè) PageRank 算法的改進(jìn)的方法

【摘 要】本文提出一種對(duì)網(wǎng)頁(yè) PageRank 算法的改進(jìn)方法，通過(guò)引進(jìn)常數(shù)，使得PR值更加合理化，PageRank算法不對(duì)垃圾網(wǎng)站的影響做處理，引入一個(gè)鏈接參數(shù)L，滿足一定的條件下，會(huì)讓用戶經(jīng)過(guò)搜索得到的網(wǎng)頁(yè)質(zhì)量更高，考慮到網(wǎng)頁(yè)隨時(shí)間因素的影響，越新的網(wǎng)頁(yè)獲得的PR值越大，帶入時(shí)間參數(shù)t，通過(guò)分析t與新PageRank的算法之間的聯(lián)系，做出驗(yàn)證。

【關(guān)鍵詞】PageRank；信息檢索；相似度；網(wǎng)頁(yè)

0 引言

近年來(lái)搜索引擎技術(shù)以龐大數(shù)據(jù)容量與快速的用戶響應(yīng)贏得了人們的普遍歡迎。傳統(tǒng)搜索引擎以PageRank算法對(duì)網(wǎng)頁(yè)優(yōu)先度進(jìn)行排序，被認(rèn)可最多的消息權(quán)重最大，排在最前面。本文對(duì)Pagerank進(jìn)行分析，再與原PageRank驗(yàn)證對(duì)比。，PageRank的算法優(yōu)點(diǎn)在于萬(wàn)維網(wǎng)彼此相連，通過(guò)多鏈接關(guān)系，每個(gè)網(wǎng)頁(yè)的權(quán)值最終通過(guò)迭代區(qū)域一個(gè)穩(wěn)定值，對(duì)于任意一個(gè)不外聯(lián)集合，總權(quán)值數(shù)一定，使得其具有收斂性。但有不足的地方，PageRank算法沒(méi)有考慮到權(quán)值沉淀的問(wèn)題，因?yàn)镻ageRank算法的計(jì)算具有全局性，如果要算一個(gè)網(wǎng)頁(yè)的 PR 值就要算出所有網(wǎng)頁(yè)的 PR值，所以計(jì)算量很大[1]；檢索主題與PageRank算法的公式計(jì)算出的 PR值無(wú)關(guān)；一些頁(yè)面引用了別的網(wǎng)頁(yè)而PageRank算法不會(huì)提高了PR值。

1基于PageRank算法的改進(jìn)

PageRank算法是google公司前期用于劃分網(wǎng)頁(yè)之前存在的鏈接價(jià)值而提出的算法，算法的核心內(nèi)容就是：如果網(wǎng)頁(yè)Ti指向一條網(wǎng)頁(yè)A的鏈接，則認(rèn)為A得到了Ti的認(rèn)可，如果有許多高質(zhì)量的網(wǎng)頁(yè)指向了A，就說(shuō)明A很重要，這個(gè)質(zhì)量值就由PageRank值來(lái)代替，簡(jiǎn)稱PR值[2] [3]。

（1）

其中：：網(wǎng)頁(yè)A的PR值；：網(wǎng)頁(yè)Ti存在指向A的鏈接，且是Ti在上一次迭代時(shí)的PR值；：網(wǎng)頁(yè)Ti的外鏈數(shù)量；d：阻尼系數(shù)，0

無(wú)論怎么迭代，迭代的結(jié)果收斂，最終趨于穩(wěn)定，這是PageRank算法的重要特性，但當(dāng)網(wǎng)頁(yè)的集合連接成一個(gè)環(huán)，且不指向這個(gè)環(huán)外部的網(wǎng)頁(yè)，PR算法就會(huì)使權(quán)值累積變大，這種現(xiàn)象叫權(quán)值沉淀。

要改善權(quán)值沉淀，使網(wǎng)頁(yè)消息的權(quán)值會(huì)隨著數(shù)量的增多而改變，引入常數(shù)N。N為萬(wàn)維網(wǎng)中的頁(yè)面總數(shù)，網(wǎng)頁(yè)A的PR值是受到鏈接源數(shù)目的影響，源數(shù)目越多，在默認(rèn)每個(gè)網(wǎng)頁(yè)阻尼d都相同的情況下成正比，由于google在對(duì)PageRank算法中引入了對(duì)隨機(jī)沖浪模型的討論，不妨擬定參數(shù)L，L（A）為A的鏈接源頁(yè)面數(shù)，而L[C（Ti）]表示Ti順向鏈接的子點(diǎn)的源網(wǎng)頁(yè)得到的公式2為：

萬(wàn)維網(wǎng)中存在獨(dú)立網(wǎng)頁(yè)，如果使用PageRank公式，那得到的PR值為（1-d），顯得過(guò)大，經(jīng)改善，N可以理解為每個(gè)頁(yè)面都有1/n的可能跳轉(zhuǎn)到其他網(wǎng)頁(yè)去，用迭代法最終得到獨(dú)立網(wǎng)頁(yè)的PR值不再為1-d，增加了內(nèi)外頁(yè)面之間的相對(duì)流動(dòng)性。由公式趨于穩(wěn)定時(shí)總和為1，說(shuō)明結(jié)果正確。經(jīng)過(guò)驗(yàn)證新公式對(duì)權(quán)值的重要性影響比原算法好，低權(quán)值的信息排名比以前更低，高權(quán)值的信息排名更高，更容易引起人們的重視，結(jié)果符合情理，參數(shù)的設(shè)定還有待斟酌。

同時(shí)社會(huì)上的網(wǎng)頁(yè)消息需要根據(jù)時(shí)間進(jìn)行篩選，大多是定期排序更新消息的，所以設(shè)置變量t，可以盡可能的按照消息類別對(duì)權(quán)值產(chǎn)生影響。權(quán)值必須為足夠大，無(wú)可爭(zhēng)議變量使新算法得到的PR值盡可能的大。針對(duì)定期性進(jìn)行變量的引進(jìn)t，t為爬蟲訪問(wèn)到網(wǎng)頁(yè)的時(shí)間與當(dāng)前期刊網(wǎng)頁(yè)的更新之間的時(shí)間（天）， t為Number類型 >=1。那么搜索引擎可以引入時(shí)間變量t。令K（H）=1-e-dt，d為常數(shù)。改進(jìn)的Page Rank算法如公式3。

2 結(jié)論

本文對(duì)Page Rank算法進(jìn)行了改進(jìn)。構(gòu)建了一個(gè)新的Page Rank算法公式，增加了內(nèi)外頁(yè)面之間的相對(duì)流動(dòng)性，權(quán)值的重要性影響上比原PageRank算法好，考慮到了時(shí)間等影響因數(shù)。比原公式更加準(zhǔn)確，提高了Page Rank算法公式的合理性。

參考文獻(xiàn)：

[1] 劉金桂，李緒蓉.基于網(wǎng)頁(yè)相似度的 Page Rank算法的改進(jìn)[J]. 淮陰工學(xué)院學(xué)報(bào). 2006（01）

[2] Brin S， Page L. T he anatomy of a large-scale hyper-textual Web-search engine[A]. Proc 7th International World Wide Web Conference[C]. Brisbane： SIGIR， 1998. 146- 164

[3] Jughoo Cho， Hector G M ， Lawrence P. Efficient crawling through URL ordering[A] . Proc 7th International World Wide Web Conference[C] . Brisbane： SIGIR， 1998. 220- 235.

作者簡(jiǎn)介：

王碩（1993-），男，內(nèi)蒙古赤峰市，學(xué)生，本科。研究方向：通信工程專業(yè)。

王萍 （1992-） ， 女， 吉林省公主嶺市，學(xué)生， 本科。研究方向：通信工程專業(yè)。