一種改進的PageRank算法—STPR

李宜兵　郭玉堂　潘潔珠

摘 要 PageRank算法是一種基于網(wǎng)頁結(jié)構(gòu)的排序算法。充分考慮了網(wǎng)頁的權(quán)威性質(zhì)，但是沒有考慮內(nèi)容的相關性，與此同時，對權(quán)威性的側(cè)重，導致主題漂移現(xiàn)象更為突出。同時PageRank算法沒有考慮時間對網(wǎng)頁鏈接的影響，在一定的時間范圍內(nèi)，隨后時間推移，網(wǎng)頁的鏈接數(shù)應該越多。本文基于網(wǎng)頁內(nèi)容和網(wǎng)頁的時間對PageRank算法進行了改進，提出了改進算法STPR。

【關鍵詞】PageRank 排序 相關性 時間

PageRank算法首先應用于Google搜索引擎，并且取得了巨大的商業(yè)成功。是一種典型的基于web結(jié)構(gòu)的算法。統(tǒng)計每個頁面web圖的出度和入度，然后通過迭代的方法計算出每個頁面的PageRank值，PageRank值越大，表明網(wǎng)頁的權(quán)重越高。然而，PageRank算法，只注意了網(wǎng)頁的權(quán)威性，沒有考慮相關性。很有可能計算出的結(jié)果與用戶所需要的信息不大。另外PageRank算法對于網(wǎng)頁權(quán)威性計算也有缺陷。沒有考慮到時間對于網(wǎng)頁權(quán)威性的影響，例如一個很重要的網(wǎng)頁，信息發(fā)布之初也很少有其他網(wǎng)頁鏈接指向它。針對以上缺點，本文提出了一個基于網(wǎng)頁內(nèi)容和時間的改進算法PageRank算法——STRP。

1 PageRank算法

PageRank 算法簡單描述如下：將Web 對應成有向圖：G=（V，E），其中V是節(jié)點（網(wǎng)頁）集，E是邊（當且僅當從頁面i到頁面j存在鏈接時）Ni是頁面i指向的所有頁面的集合，Bi是指向頁面i的所有頁面的集合。則頁面i的等級PageRank 值PR（i）的計算公式如公式（1-1）所示。

公式（1-1）有一個很大的缺陷，它是基于互聯(lián)網(wǎng)上網(wǎng)頁處于連通的狀態(tài)，即從任一個網(wǎng)頁出發(fā)都能到達任一個網(wǎng)頁，然而實際上并不是所有的網(wǎng)頁都有向外鏈接，總有一些網(wǎng)頁是處于孤立的狀態(tài)。

為了解決這個問題學者對對其進行了改進， 引入E（u） （等級源）來不斷的補充每個網(wǎng)頁的PageRank值，E（u）對應網(wǎng)頁集的某一向量。則改進的PageRank算法如公式（1-2）所示。

2 基于內(nèi)容改進

PageRank算法一個很大的缺點是主題漂移。所謂的主題漂移，即所查詢結(jié)果與查詢期望不一致。主題漂移使得查詢的相關性造成很大的破壞。PageRank只是基于超鏈接分析排序算法，沒有基于內(nèi)容考慮。PageRank算法解決了權(quán)威性的問題，這反而使得主題漂移現(xiàn)象更為加重。一般情況下如果一個網(wǎng)頁的鏈出網(wǎng)頁與本網(wǎng)頁內(nèi)容是同一個主題，那么該鏈出鏈接應該更具有價值。相反如果是垃圾鏈接，即兩個網(wǎng)頁是毫不相關的，那么該鏈接對權(quán)重的影響應該是很小的。所以在這里引入了兩個網(wǎng)頁內(nèi)容相似性來改進PageRank算法。這樣可以進一步的杜絕網(wǎng)頁作弊者通過不相關的網(wǎng)頁鏈接來提高網(wǎng)頁的排名。算法的改進公式如下：

公式（1-4）中W（v，u）表示網(wǎng)頁v與u的相似度。其中網(wǎng)頁u與v的相似性可以用VSM模型來求得。假設網(wǎng)頁u與v的文檔向量空間為u=（u1， u2， u3…un）， v=（ v1， v2， v3… vn），根據(jù)前面介紹的求文檔之間的相似性知識可知：

3 基于時間改進

在以上基于網(wǎng)頁內(nèi)容和結(jié)構(gòu)的基礎上，考慮網(wǎng)頁的更新時間。一般情況下一個非常重要的信息會在12小時以內(nèi)被廣泛傳播。假定隨著時間推移12小時后，網(wǎng)頁鏈接達到峰值。改進的公式如下：

4 結(jié)論

通過對pageRank算法的研究，基于其存在漂移的問題，進行了內(nèi)容的改進，利用VSM模型解決了相似性問題。針對新上網(wǎng)頁對鏈接解構(gòu)影響，根據(jù)網(wǎng)頁時間對網(wǎng)頁pagerank值進行了權(quán)重系數(shù)。

參考文獻

[1]原福永，張園園.基于鏈接分析的相關排序方法的研究和改進[J].計算機工程與設計，2007，07（28）：1630-1662.

[2]黃德刁，戚華春.PageRank算法研究.計算機工程，2006，32（4）：145-162.

[3]楊炳儒，李巖，陳新中等.Web結(jié)構(gòu)挖掘.計算機工程，2003，29（20）：28-30.

[4]Xing Wenpu，Ghorbani A. Weighted PageRank algorithm[C].Communication Networks and Services Research，Proceedingsof Second Annual Conference，2004：305-314.

作者簡介

李宜兵（1985-），男，安徽省桐城市人。碩士學位?，F(xiàn)為合肥師范學院助教。研究方向為信息檢索和數(shù)據(jù)挖掘。

郭玉堂（1962-），男，安徽省安慶市人。博士學位?，F(xiàn)為合肥師范學院教授、碩士生導師。主要研究方向為人工智能和圖形處理。

作者單位

合肥師范學院計算機學院 安徽省合肥市 230601endprint

摘 要 PageRank算法是一種基于網(wǎng)頁結(jié)構(gòu)的排序算法。充分考慮了網(wǎng)頁的權(quán)威性質(zhì)，但是沒有考慮內(nèi)容的相關性，與此同時，對權(quán)威性的側(cè)重，導致主題漂移現(xiàn)象更為突出。同時PageRank算法沒有考慮時間對網(wǎng)頁鏈接的影響，在一定的時間范圍內(nèi)，隨后時間推移，網(wǎng)頁的鏈接數(shù)應該越多。本文基于網(wǎng)頁內(nèi)容和網(wǎng)頁的時間對PageRank算法進行了改進，提出了改進算法STPR。

【關鍵詞】PageRank 排序 相關性 時間

PageRank算法首先應用于Google搜索引擎，并且取得了巨大的商業(yè)成功。是一種典型的基于web結(jié)構(gòu)的算法。統(tǒng)計每個頁面web圖的出度和入度，然后通過迭代的方法計算出每個頁面的PageRank值，PageRank值越大，表明網(wǎng)頁的權(quán)重越高。然而，PageRank算法，只注意了網(wǎng)頁的權(quán)威性，沒有考慮相關性。很有可能計算出的結(jié)果與用戶所需要的信息不大。另外PageRank算法對于網(wǎng)頁權(quán)威性計算也有缺陷。沒有考慮到時間對于網(wǎng)頁權(quán)威性的影響，例如一個很重要的網(wǎng)頁，信息發(fā)布之初也很少有其他網(wǎng)頁鏈接指向它。針對以上缺點，本文提出了一個基于網(wǎng)頁內(nèi)容和時間的改進算法PageRank算法——STRP。

1 PageRank算法

PageRank 算法簡單描述如下：將Web 對應成有向圖：G=（V，E），其中V是節(jié)點（網(wǎng)頁）集，E是邊（當且僅當從頁面i到頁面j存在鏈接時）Ni是頁面i指向的所有頁面的集合，Bi是指向頁面i的所有頁面的集合。則頁面i的等級PageRank 值PR（i）的計算公式如公式（1-1）所示。

公式（1-1）有一個很大的缺陷，它是基于互聯(lián)網(wǎng)上網(wǎng)頁處于連通的狀態(tài)，即從任一個網(wǎng)頁出發(fā)都能到達任一個網(wǎng)頁，然而實際上并不是所有的網(wǎng)頁都有向外鏈接，總有一些網(wǎng)頁是處于孤立的狀態(tài)。

為了解決這個問題學者對對其進行了改進， 引入E（u） （等級源）來不斷的補充每個網(wǎng)頁的PageRank值，E（u）對應網(wǎng)頁集的某一向量。則改進的PageRank算法如公式（1-2）所示。

2 基于內(nèi)容改進

PageRank算法一個很大的缺點是主題漂移。所謂的主題漂移，即所查詢結(jié)果與查詢期望不一致。主題漂移使得查詢的相關性造成很大的破壞。PageRank只是基于超鏈接分析排序算法，沒有基于內(nèi)容考慮。PageRank算法解決了權(quán)威性的問題，這反而使得主題漂移現(xiàn)象更為加重。一般情況下如果一個網(wǎng)頁的鏈出網(wǎng)頁與本網(wǎng)頁內(nèi)容是同一個主題，那么該鏈出鏈接應該更具有價值。相反如果是垃圾鏈接，即兩個網(wǎng)頁是毫不相關的，那么該鏈接對權(quán)重的影響應該是很小的。所以在這里引入了兩個網(wǎng)頁內(nèi)容相似性來改進PageRank算法。這樣可以進一步的杜絕網(wǎng)頁作弊者通過不相關的網(wǎng)頁鏈接來提高網(wǎng)頁的排名。算法的改進公式如下：

公式（1-4）中W（v，u）表示網(wǎng)頁v與u的相似度。其中網(wǎng)頁u與v的相似性可以用VSM模型來求得。假設網(wǎng)頁u與v的文檔向量空間為u=（u1， u2， u3…un）， v=（ v1， v2， v3… vn），根據(jù)前面介紹的求文檔之間的相似性知識可知：

3 基于時間改進

在以上基于網(wǎng)頁內(nèi)容和結(jié)構(gòu)的基礎上，考慮網(wǎng)頁的更新時間。一般情況下一個非常重要的信息會在12小時以內(nèi)被廣泛傳播。假定隨著時間推移12小時后，網(wǎng)頁鏈接達到峰值。改進的公式如下：

4 結(jié)論

通過對pageRank算法的研究，基于其存在漂移的問題，進行了內(nèi)容的改進，利用VSM模型解決了相似性問題。針對新上網(wǎng)頁對鏈接解構(gòu)影響，根據(jù)網(wǎng)頁時間對網(wǎng)頁pagerank值進行了權(quán)重系數(shù)。

參考文獻

[1]原福永，張園園.基于鏈接分析的相關排序方法的研究和改進[J].計算機工程與設計，2007，07（28）：1630-1662.

[2]黃德刁，戚華春.PageRank算法研究.計算機工程，2006，32（4）：145-162.

[3]楊炳儒，李巖，陳新中等.Web結(jié)構(gòu)挖掘.計算機工程，2003，29（20）：28-30.

[4]Xing Wenpu，Ghorbani A. Weighted PageRank algorithm[C].Communication Networks and Services Research，Proceedingsof Second Annual Conference，2004：305-314.

作者簡介

李宜兵（1985-），男，安徽省桐城市人。碩士學位?，F(xiàn)為合肥師范學院助教。研究方向為信息檢索和數(shù)據(jù)挖掘。

郭玉堂（1962-），男，安徽省安慶市人。博士學位?，F(xiàn)為合肥師范學院教授、碩士生導師。主要研究方向為人工智能和圖形處理。

作者單位

合肥師范學院計算機學院 安徽省合肥市 230601endprint

摘 要 PageRank算法是一種基于網(wǎng)頁結(jié)構(gòu)的排序算法。充分考慮了網(wǎng)頁的權(quán)威性質(zhì)，但是沒有考慮內(nèi)容的相關性，與此同時，對權(quán)威性的側(cè)重，導致主題漂移現(xiàn)象更為突出。同時PageRank算法沒有考慮時間對網(wǎng)頁鏈接的影響，在一定的時間范圍內(nèi)，隨后時間推移，網(wǎng)頁的鏈接數(shù)應該越多。本文基于網(wǎng)頁內(nèi)容和網(wǎng)頁的時間對PageRank算法進行了改進，提出了改進算法STPR。

【關鍵詞】PageRank 排序 相關性 時間

PageRank算法首先應用于Google搜索引擎，并且取得了巨大的商業(yè)成功。是一種典型的基于web結(jié)構(gòu)的算法。統(tǒng)計每個頁面web圖的出度和入度，然后通過迭代的方法計算出每個頁面的PageRank值，PageRank值越大，表明網(wǎng)頁的權(quán)重越高。然而，PageRank算法，只注意了網(wǎng)頁的權(quán)威性，沒有考慮相關性。很有可能計算出的結(jié)果與用戶所需要的信息不大。另外PageRank算法對于網(wǎng)頁權(quán)威性計算也有缺陷。沒有考慮到時間對于網(wǎng)頁權(quán)威性的影響，例如一個很重要的網(wǎng)頁，信息發(fā)布之初也很少有其他網(wǎng)頁鏈接指向它。針對以上缺點，本文提出了一個基于網(wǎng)頁內(nèi)容和時間的改進算法PageRank算法——STRP。

1 PageRank算法

PageRank 算法簡單描述如下：將Web 對應成有向圖：G=（V，E），其中V是節(jié)點（網(wǎng)頁）集，E是邊（當且僅當從頁面i到頁面j存在鏈接時）Ni是頁面i指向的所有頁面的集合，Bi是指向頁面i的所有頁面的集合。則頁面i的等級PageRank 值PR（i）的計算公式如公式（1-1）所示。

公式（1-1）有一個很大的缺陷，它是基于互聯(lián)網(wǎng)上網(wǎng)頁處于連通的狀態(tài)，即從任一個網(wǎng)頁出發(fā)都能到達任一個網(wǎng)頁，然而實際上并不是所有的網(wǎng)頁都有向外鏈接，總有一些網(wǎng)頁是處于孤立的狀態(tài)。

為了解決這個問題學者對對其進行了改進， 引入E（u） （等級源）來不斷的補充每個網(wǎng)頁的PageRank值，E（u）對應網(wǎng)頁集的某一向量。則改進的PageRank算法如公式（1-2）所示。

2 基于內(nèi)容改進

PageRank算法一個很大的缺點是主題漂移。所謂的主題漂移，即所查詢結(jié)果與查詢期望不一致。主題漂移使得查詢的相關性造成很大的破壞。PageRank只是基于超鏈接分析排序算法，沒有基于內(nèi)容考慮。PageRank算法解決了權(quán)威性的問題，這反而使得主題漂移現(xiàn)象更為加重。一般情況下如果一個網(wǎng)頁的鏈出網(wǎng)頁與本網(wǎng)頁內(nèi)容是同一個主題，那么該鏈出鏈接應該更具有價值。相反如果是垃圾鏈接，即兩個網(wǎng)頁是毫不相關的，那么該鏈接對權(quán)重的影響應該是很小的。所以在這里引入了兩個網(wǎng)頁內(nèi)容相似性來改進PageRank算法。這樣可以進一步的杜絕網(wǎng)頁作弊者通過不相關的網(wǎng)頁鏈接來提高網(wǎng)頁的排名。算法的改進公式如下：

公式（1-4）中W（v，u）表示網(wǎng)頁v與u的相似度。其中網(wǎng)頁u與v的相似性可以用VSM模型來求得。假設網(wǎng)頁u與v的文檔向量空間為u=（u1， u2， u3…un）， v=（ v1， v2， v3… vn），根據(jù)前面介紹的求文檔之間的相似性知識可知：

3 基于時間改進

在以上基于網(wǎng)頁內(nèi)容和結(jié)構(gòu)的基礎上，考慮網(wǎng)頁的更新時間。一般情況下一個非常重要的信息會在12小時以內(nèi)被廣泛傳播。假定隨著時間推移12小時后，網(wǎng)頁鏈接達到峰值。改進的公式如下：

4 結(jié)論

通過對pageRank算法的研究，基于其存在漂移的問題，進行了內(nèi)容的改進，利用VSM模型解決了相似性問題。針對新上網(wǎng)頁對鏈接解構(gòu)影響，根據(jù)網(wǎng)頁時間對網(wǎng)頁pagerank值進行了權(quán)重系數(shù)。

參考文獻

[1]原福永，張園園.基于鏈接分析的相關排序方法的研究和改進[J].計算機工程與設計，2007，07（28）：1630-1662.

[2]黃德刁，戚華春.PageRank算法研究.計算機工程，2006，32（4）：145-162.

[3]楊炳儒，李巖，陳新中等.Web結(jié)構(gòu)挖掘.計算機工程，2003，29（20）：28-30.

[4]Xing Wenpu，Ghorbani A. Weighted PageRank algorithm[C].Communication Networks and Services Research，Proceedingsof Second Annual Conference，2004：305-314.

作者簡介

李宜兵（1985-），男，安徽省桐城市人。碩士學位?，F(xiàn)為合肥師范學院助教。研究方向為信息檢索和數(shù)據(jù)挖掘。

郭玉堂（1962-），男，安徽省安慶市人。博士學位。現(xiàn)為合肥師范學院教授、碩士生導師。主要研究方向為人工智能和圖形處理。

作者單位

合肥師范學院計算機學院 安徽省合肥市 230601endprint