本文關(guān)鍵詞：搜索引擎PageRank算法的改進(jìn)，由筆耕文化傳播整理發(fā)布。

改進(jìn)的PageRank算法在搜索引擎中的應(yīng)用

計(jì) 算 機(jī) 工 程 第 35 卷 第22期

Vol.35 No.22 Computer Engineering ·軟件技術(shù)與數(shù)據(jù)庫(kù)·

文章編號(hào)：1000—3428(2009)22—0035—03

文獻(xiàn)標(biāo)識(shí)碼：A

2009年11月

November2009

中圖分類(lèi)號(hào)：TP391

搜索引擎PageRank算法的改進(jìn)

楊勁松，凌培亮

(同濟(jì)大學(xué)機(jī)械工程學(xué)院，上海 200092)

摘 要：為了解決企業(yè)快速?zèng)Q策時(shí)信息檢索的問(wèn)題，，提出一種改進(jìn)的PageRank算法。在考慮網(wǎng)頁(yè)產(chǎn)生時(shí)間因素的同時(shí)，通過(guò)錨文本與網(wǎng)頁(yè)主題的相似度分析按權(quán)重分配網(wǎng)頁(yè)各正向鏈接PageRank值，產(chǎn)生的PageRank值更貼合主題搜索引擎的要求，并保持算法的簡(jiǎn)潔性。實(shí)驗(yàn)結(jié)果證明該改進(jìn)算法能有效減少主題漂移現(xiàn)象，恰當(dāng)提升新網(wǎng)頁(yè)P(yáng)ageRank值。 關(guān)鍵詞：搜索引擎；錨文本；向量空間模型

Improvement of PageRank Algorithm for Search Engine

YANG Jin-song, LING Pei-liang

(College of Mechanical Engineering, Tongji University, Shanghai 200092)

【Abstract】In order to solve the problems in information retrieval when enterprise making rapid decision, this paper proposes an improvedPageRank algorithm. Considering the time factor by Web page, it distributes the forward link different PageRank value based on the proportion bythe similarity analysis between anchor text and Web page text. The final PageRank value is more suitable for topic-specific search engine and keepssimplicity of algorithm. Experimental result shows that the improved algorithm can effectively reduce the phenomenon of topic-drift and enhance thePageRank value of new Web page.

【Key words】search engine; anchor text; Vector Space Model(VSM)

面對(duì)持續(xù)膨脹的海量互聯(lián)網(wǎng)資源，目前通用搜索引擎(General Search Engine, GSE)的信息檢索無(wú)法完全滿足企業(yè)快速?zèng)Q策的信息需求，主題搜索引擎(Topic-specific Search Engine, TSE)應(yīng)運(yùn)而生并引起研究者的重視。本文結(jié)合主題搜索引擎的使用需求，使改進(jìn)的PageRank算法適應(yīng)于主題搜索引擎，并進(jìn)行實(shí)驗(yàn)驗(yàn)證。

1 PageRank算法研究現(xiàn)狀

Google使用PageRank算法[1]構(gòu)造的搜索引擎獲得了巨大成功。簡(jiǎn)單的說(shuō)，PageRank是代表互聯(lián)網(wǎng)上某個(gè)頁(yè)面重要性的一個(gè)數(shù)值，該值僅僅依賴于網(wǎng)絡(luò)的鏈接結(jié)構(gòu)。PageRank 算法的具體思路是將某個(gè)頁(yè)面的PageRank值除以存在于該頁(yè)面的正向鏈接，由此得到的值分別和正向鏈接所指向頁(yè)面的PageRank值相加，得到被鏈接頁(yè)面的PageRank值。算法基于“從許多優(yōu)質(zhì)的網(wǎng)頁(yè)鏈接過(guò)來(lái)的網(wǎng)頁(yè)，必定還是優(yōu)質(zhì)網(wǎng)頁(yè)”的回歸關(guān)系判定所有網(wǎng)頁(yè)的重要性。若一個(gè)網(wǎng)頁(yè)的得票越多，則認(rèn)為它的重要性也越高，投票網(wǎng)頁(yè)的重要性決定了票的重要程度。

當(dāng)計(jì)算某個(gè)網(wǎng)頁(yè)P(yáng)ageRank值時(shí)考慮所有的反向鏈接，頁(yè)面u的PageRank值計(jì)算公式如下：

PR(u)=(1 d)+d×∑

PR(v)

(1)

v∈B(u)Nv

其中，PR(u)代表頁(yè)面u的PageRank數(shù)值；B(u)代表有鏈接

直接指向頁(yè)面u的網(wǎng)頁(yè)集；Nv表示網(wǎng)頁(yè)v正向鏈接的數(shù)量；

PR(v)

表示網(wǎng)頁(yè)v將自己的PageRank值平均分配給自身的正Nv

接瀏覽，而不產(chǎn)生隨機(jī)跳躍的概率值，在實(shí)際應(yīng)用中，加入阻尼系數(shù)d能保證計(jì)算結(jié)果總是收斂。

由式(1)可知，計(jì)算某個(gè)網(wǎng)頁(yè)的PageRank值總是依賴于其他的相關(guān)頁(yè)面，在實(shí)際計(jì)算PageRank值時(shí)大都采取迭代法，遞歸地用給定矩陣乘以一個(gè)任意初始向量，直到其收斂，計(jì)算結(jié)果的精確程度依賴于初值的選取和迭代的次數(shù)。由于PageRank值的作用在于給網(wǎng)頁(yè)排序，因此只要在認(rèn)為網(wǎng)頁(yè)排序趨于穩(wěn)定的時(shí)候就可以停止遞歸計(jì)算而不一定要得到實(shí)際的PageRank值。在實(shí)際運(yùn)算中，確定網(wǎng)頁(yè)重要順序的計(jì)算次數(shù)比得到準(zhǔn)確PageRank值的次數(shù)要少得多。

由于PageRank值僅僅依賴于網(wǎng)絡(luò)的鏈接結(jié)構(gòu)，網(wǎng)頁(yè)的PageRank值是按存在于該頁(yè)面的正向鏈接數(shù)來(lái)平均分配的，

容易發(fā)生主題因此用于被鏈接的頁(yè)面的PageRank值的計(jì)算，

漂移現(xiàn)象，在主題搜索引擎應(yīng)用時(shí)該缺陷將非常明顯，會(huì)使得搜索結(jié)果中存在過(guò)多與查詢主題無(wú)關(guān)的網(wǎng)頁(yè)，同時(shí)由于網(wǎng)頁(yè)的PageRank值是由反向鏈接的數(shù)量和質(zhì)量決定的，因此PageRank算法傾向于舊網(wǎng)頁(yè)，而企業(yè)快速?zèng)Q策非常關(guān)注新網(wǎng)頁(yè)產(chǎn)生時(shí)間短，被引用次數(shù)少，PageRank值偏低。針對(duì)這些缺陷，許多學(xué)者提出相應(yīng)的改進(jìn)算法，如文獻(xiàn)[3]提出一種主題敏感的PageRank改進(jìn)算法，文獻(xiàn)[4]提出一種結(jié)合鏈接分析和文本內(nèi)容的PageRank改進(jìn)算法，文獻(xiàn)[5-6]分別提出具有時(shí)間反饋的PageRank改進(jìn)算法。上述算法有效地改進(jìn)了PageRank算法的固有缺陷，但在不同程度上增加了計(jì)算的復(fù)雜程度和實(shí)用難度。本文在研究和分析PageRank算法的基礎(chǔ)

作者簡(jiǎn)介：楊勁松(1976－)，男，講師、博士研究生，主研方向：搜索引擎，分布式計(jì)算；凌培亮，教授、博士

收稿日期：2009-06-12 E-mail：yangjinsong@

向鏈接[2]；d是阻尼系數(shù)，0<d<1，通常取0.85，由于用戶

在互聯(lián)網(wǎng)瀏覽時(shí)可能不按當(dāng)前頁(yè)面中的鏈接前進(jìn)，而隨機(jī)跳躍到完全無(wú)關(guān)頁(yè)面，因此d實(shí)際上代表的是用戶跟隨網(wǎng)頁(yè)鏈

—35—

  本文關(guān)鍵詞：搜索引擎PageRank算法的改進(jìn)，由筆耕文化傳播整理發(fā)布。