一種改進的PageRank算法—STPR

李宜兵　郭玉堂　潘潔珠

摘 要 PageRank算法是一種基于網頁結構的排序算法。充分考慮了網頁的權威性質，但是沒有考慮內容的相關性，與此同時，對權威性的側重，導致主題漂移現象更為突出。同時PageRank算法沒有考慮時間對網頁鏈接的影響，在一定的時間范圍內，隨后時間推移，網頁的鏈接數應該越多。本文基于網頁內容和網頁的時間對PageRank算法進行了改進，提出了改進算法STPR。

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

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

1 PageRank算法

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

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

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

2 基于內容改進

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

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

3 基于時間改進

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

4 結論

通過對pageRank算法的研究，基于其存在漂移的問題，進行了內容的改進，利用VSM模型解決了相似性問題。針對新上網頁對鏈接解構影響，根據網頁時間對網頁pagerank值進行了權重系數。

參考文獻

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

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

[3]楊炳儒，李巖，陳新中等.Web結構挖掘.計算機工程，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-），男，安徽省桐城市人。碩士學位。現為合肥師范學院助教。研究方向為信息檢索和數據挖掘。

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

作者單位

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

摘 要 PageRank算法是一種基于網頁結構的排序算法。充分考慮了網頁的權威性質，但是沒有考慮內容的相關性，與此同時，對權威性的側重，導致主題漂移現象更為突出。同時PageRank算法沒有考慮時間對網頁鏈接的影響，在一定的時間范圍內，隨后時間推移，網頁的鏈接數應該越多。本文基于網頁內容和網頁的時間對PageRank算法進行了改進，提出了改進算法STPR。

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

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

1 PageRank算法

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

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

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

2 基于內容改進

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

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

3 基于時間改進

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

4 結論

通過對pageRank算法的研究，基于其存在漂移的問題，進行了內容的改進，利用VSM模型解決了相似性問題。針對新上網頁對鏈接解構影響，根據網頁時間對網頁pagerank值進行了權重系數。

參考文獻

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

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

[3]楊炳儒，李巖，陳新中等.Web結構挖掘.計算機工程，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為合肥師范學院助教。研究方向為信息檢索和數據挖掘。

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

作者單位

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

摘 要 PageRank算法是一種基于網頁結構的排序算法。充分考慮了網頁的權威性質，但是沒有考慮內容的相關性，與此同時，對權威性的側重，導致主題漂移現象更為突出。同時PageRank算法沒有考慮時間對網頁鏈接的影響，在一定的時間范圍內，隨后時間推移，網頁的鏈接數應該越多。本文基于網頁內容和網頁的時間對PageRank算法進行了改進，提出了改進算法STPR。

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

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

1 PageRank算法

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

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

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

2 基于內容改進

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

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

3 基于時間改進

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

4 結論

通過對pageRank算法的研究，基于其存在漂移的問題，進行了內容的改進，利用VSM模型解決了相似性問題。針對新上網頁對鏈接解構影響，根據網頁時間對網頁pagerank值進行了權重系數。

參考文獻

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

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

[3]楊炳儒，李巖，陳新中等.Web結構挖掘.計算機工程，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為合肥師范學院助教。研究方向為信息檢索和數據挖掘。

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

作者單位

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