一种基于网页质量的PageRank算法改进分析

赵亚娟　闫娜

摘要：互联网信息的海量性一方面带给人们无穷的信息，另一方面也给人们的信息获取工作带来一定的困难。因而能够快捷高效地提供高质量的查询结果的互联网搜索引擎将受到大众的青睐。在网页搜索中，PageRank和hits是重要的基于链接的排序算法，在百度、谷歌等商业引擎中使用广泛。但在PageRank算法中也极存在一些问题，导致其容易受垃圾网页的攻击，不利于人们高质量地从互联网上获取信息，因此，有必要对PageRank算法进行改进，从而改善网页质量，提高信息获取的高效准确性。该文基于这样的背景对PageRank算法改进进行分析，以更好地实现信息的有效流通，让高质量的网页得到更多关注。

关键词：PageRank算法改进；网页质量

中图分类号：TP37 文献标识码：A 文章编号：1009-3044（2014）27-6365-02

Abstract： The huge amount of Internet information on one hand brings people endless information， on the other hand also give people access to information work to bring certain difficulty. The Internet search engine so it can efficiently provide high quality results will be favored by the public. In Webpage search， PageRank and hits are important link based ranking algorithms， widely used in Baidu， Google commercial engine. But in the PageRank algorithm also has some problems， resulting in the waste Webpage vulnerable to attack， is not conducive to high quality people to obtain information from the Internet， therefore， it is necessary to improve PageRank algorithm， so as to improve the quality of Webpage， improve the efficiency and accuracy of information acquisition. This paper analyzes the improvement of PageRank algorithm based on this background， the effective circulation to achieve better information， make high quality Webpage get more attention.

Key words： improved PageRank algorithm Webpage quality

1 PageRank算法原理

PageRank算法是一种针对链接进行分析并计算网页在互联网中的等级和重要性的算法，网页等级越高、重要性越大则其在搜索引擎中的排位就会越靠前，在信息搜索时被访问的次数就越多。PageRank算法的使用基于两个前提，一个前提指向一个网页的超链接数量越多，网页被引用或搜索的次数越多，表明这个网页越重要，权威网页往往被传递和引用的次数更多。另一个前提是同一链接中用户选择的随机冲浪性原理，可以简单地理解为用户随机点击一个链接进入该链接所指向的一个网页，然后从打开的这个网页中再随机点击一个链接进入下一个页面，直到用户不再点击进入为止。网页的重要性是基于其在这种随机可能性中被选择的概率，如果它被访问的次数越多，尤其是当该网页被重要的网页如百度、谷歌等引用，表明该网页的重要程度越高。换言之，网页的PageRank值越高，则认为其在互联网中越重要，被访问的次数就越多。

为了更形象地说明PageRank算法的原理，可以将互联网看成一个巨大的有向图，有向图中的一个结点表示一个网页，连接结点和结点之间的线表示网页间的超链接，结点间的边是有方向的，既可以表示该网页中包括的超链接又可以表明指向该网页的超链接。如图1所示，表示互联网中一个简单的网络结构。A-E表示网页，它们之间通过超链接互相联系，箭头表示超链接，有指入和指出的区别。

2 PageRank算法的现状分析

PageRank算法对网页重要性的计算虽具有一定的代表性，但其目前存在的缺点也不断突显出来。首先，PageRank算法对新网页的存在偏见，由其计算公式（2） 可知，一个网页的重要性是由该网页的链入超链接数决定的，而新的网页在链入数方面明显吃亏，其被搜索的可能性降低相反，用户对新网页往往抱有好奇。其次，PageRank算法主题偏移。PageRank算法是没有考虑大多数用户访问网页所查询内容，忽略了网页间内容的关联度，在现实网络中又存在许多垃圾网页，它们指向的内容与用户查询的内容无关，从而导致用户在查询时产生主题的偏移，网页链接与用户查询的内容及目的性直接相关，PageRank算法是直接依据网络的链接结构计算出的PR值来评价网页的重要性，而实际网络的重要性与用户的查询关键词不具有依赖性。此外，PageRank算法忽略了不同链接的重要程度，PageRank算法对于某一个网页的链出的超链接所占的权重是平均分配的，但是网络中一部分链接具有注释性，另一些链接只是起导航或广告的作用，它们相当于噪音信息，而PageRank算法计算的只是具有注释性的链接。

3 PageRank算法的改进

针对上述PageRank算法存在的问题，研究PageRank算法的专家学者提出了一些改进算法，如国内学者提出的结合分类、相似度及时间反馈因子的PageRank算法，国外学者提出的主题敏感的PageRank算法等。该文主要从提高网页质量的角度出发，对PageRank算法进行质量衡量值的算法改进。因为当前的网络中存在大量的垃圾网页和噪链，使网页质量出现明显的分化，这样传统的PageRank算法中平均分配权重的算法变得不再合适。在后来改进中，虽然通过多次迭代后仍可以得到较为客观的PR值来反映网页的质量，但是这个过程中需要进行多次的迭代，并且对噪链没有起到有效的过滤作用。

为了解决这些问题，笔者对基于网页质量的PageRank算法进行改进分析。在算法改进中引入了相对质量的概念，在迭代中利用每次迭代后所得的网页质量PR值与网页链接结构来计算中该网页相对质量Q（p），并将所得结果分配到PR值中。相对质量作为衡量网页质量的参数，它用来帮助分配PR值，网页的排序依然按照PR值来定。

由上述分析可以看出，改进之后的算法利用了每一轮迭代后得到的PR值，这样网页高的PR值可以得到更快的累积，最终减少了总的迭代次数。另外，相对质量Q（p）及网页q分配给p的PR值在迭代过程中都只要计算一次，且它们的计算过程简单，因此，总体而言，改进后的PageRank算法—相对质量算法虽然算法稍微复杂一些，但瑕不掩瑜，对网页质量的PR值计算更准确。

参考文献：

[1] 乔少杰，彭京，李天瑞，等.基于中心性和PageRank的网页综合评分方法[J].西南交通大学学报，2011，46（3）.

[2] 秦拯，张玲，李娜，等.改进的PageRank在Web信息搜集中的应用[J].计算机研究与发展，2006，43（6）.

[3] ZHANG Yong，YIN Chuan-ye，WU Chong-zheng，等.基于MapReduce的PageRank算法优化研究[J].计算机应用研究，2014，31（2）.