一种改进的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-），男，安徽省安庆市人。博士学位。现为合肥师范学院教授、硕士生导师。主要研究方向为人工智能和图形处理。

作者单位

合肥师范学院计算机学院 安徽省合肥市 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-），男，安徽省桐城市人。硕士学位。现为合肥师范学院助教。研究方向为信息检索和数据挖掘。

郭玉堂（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-），男，安徽省桐城市人。硕士学位。现为合肥师范学院助教。研究方向为信息检索和数据挖掘。

郭玉堂（1962-），男，安徽省安庆市人。博士学位。现为合肥师范学院教授、硕士生导师。主要研究方向为人工智能和图形处理。

作者单位

合肥师范学院计算机学院 安徽省合肥市 230601endprint