PDF《一种改进的 PageRank 算法》

除非最后厌烦了才 随机选择另一个页面,随机网页浏览者访问某个页面 的随机概率就是该页面的 PageRank 值;

阻尼系数 d 就是随机浏览者在某个页面会厌烦,然后选择一个新 页面的概率, 取值为 0~1, 一般取 0.85,页面的 PageRank 值越高,则网页浏览者发现它的概率也越高,PageRank 算法的优点:它是与查询无关的静态算法,所有网页 的PageRank 值均可以通过离线计算获得, 加速了查询 相应时间[3] .

2 PageRank算法分析 由于 PageRank 算法是离线计算网络的 PR 值,在 用户查询时仅仅根据关键字匹配获得网页集合,然后 排序推荐给用户,因此具有很高的相应速度,并且搜 索引擎 Google 的成功也验证该算法是合理、高效的. 但是,只有网络的链接结果的使用,此算法也有 不小的缺点:1)PageRank 算法更注重.com 结尾的网 站,.com 结尾的网站一般是综合性的网站,自然能比 其他类型的网站获得更多的联系,但实际上一些对这 个问题的论述更具有权威性的专业网站也许更有权威 性;

2)PageRank 算法不会区分网页和网络链接相关或 不相关的主题,那就是无法确定网页内容的相似性, 所以很容易造成主题漂移的问题.谷歌,雅虎作为互 联网上最受欢迎的网站,自然具有较高的 PR 值.因此,如果用户输入一个查询关键词,这样网页通常会 出现在查询结果集中,并将占据相当靠前的位置.但是事实上有时会与用户查询的主题不太相关;

3)PageRank 算法是偏重于旧的网页,因为其他网页上 的旧链接的可能性会更大,而事实上,在新网站上会 找到更多的有信息价值的资料[4] .

3 对PageRank改进的算法算法 从PageRank 算法以及随机漫游模型中, 可以看出 在迭代过程中权值是按当前网页的出度平均分配的, 但实际上,从链接结构上看网页按入度和出度的不同 是具有相对重要性的,入度和出度较大的网页比较重 要, 因此应该分得较高的权重. 基于此方面考虑 Xing[5] 提出加权 PageRank 算法, 其中网页的重要性和网页的 入度、出度成正比. 网页间的链接反应的是一种认可关系,网页 A 中 有链接指向网页 B,说明网页 B 的内容与 A 相关或者 具有一定的价值,同一网页中不同链接指向的网页的 内容与当前网页内容的相关程度是有差别的.基于此 思想,Ingongngam 等人[6] 提出了以主题为中心的 PageRank 算法,算法指出网页权值的分配应用和网页 的内容的相似度成正比,被链接的网页内容与当前网 页的内容越相似分配到的权值比重就越大.

4 本文改进PageRank算法 目前国内外对 PageRank 算法改进最多的就是 基于超链接的算法改进,主要是对链接的链入和链 出的改进,并且在链接的权重上做出的一些研究. 使一个网页的链接对另一个网页的权重影响更合 理.在大量研究中,都是通过链接分析来如何准确 分析该网页的权值,但是具有权威性的网页不一定 是我们要查找的网页,这称作 主题漂移 .所谓主 题漂移就是已经查找的网页和用户所要查找的主题 相关性不大. 加权 PageRank 算法在分配权值时以网 页重要性为比例,因此知名网站会获得更高的权重, 所以在一定程度上加剧了主题漂移的发生.在以主 题为中心的 PageRank 算法中根据网页的相关性来 分配权值可以有效解决主题漂移现象,但确忽略了 排序中对权威性的需求. 本文综合上述两方面的思想,从链接分析的角度 解决权威性的问题,从内容相关性分析的角度解决相 关性问题,对PageRank 算法进行改进.本文改进的 PageRank 算法(Extended PageRank)算法公式如下: ( ) ( ) ( ) ( ) (1 ) ( )( ) a v r v v B u ER u d d ER v W W ? = - + ? ? (3) 其中:Wa(v), Wr(v)分别表示网页 V 对U的权威性和 相关性.Wa(v) ?Wr(v)表示不同权威网页上内容的相 计算机系统应用http://www.c-s-a.org.cn