一种改进的PageRank算法―STPR.doc

一种改进的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小时后,网页