基于超链接分析搜索引擎页面排序算法的剖析

张书江

(安徽理工大学计算机科学与工程学院，安徽淮南232001)

摘要： 对搜索结果的排序是搜索引擎中至关重要的一项技术，算法的好坏直接关系到用户输 入关键词后能不能迅速查看到要查找的信息。系统的介绍超链接分析技术及基于超链接分析 的搜索引擎页面排序算法。对两种最基本的页面排序算法PageRank和HITS的算法思想和实现 原理进行详细阐述。通过分析对比，总结出它们各自存在的优点和不足进而指出适合其应用 的条件领域。最后指出搜素引擎应用超链接分析时应注意的一些影响因素。

关键词：搜索引擎；超链接分析；页面排序；PageRank；HITS

中图分类号：TP301文献标识码：A[WT]文章编号：16721098(2008)02007305

Analysis of Two Kinds of Search Engine Pageranking

Algorithm Based on Hyperlink Analysis

ZHANG Shujiang

(School of Computer Science and Engineering, Anhui University of Science and Tec hnology, Huainan Anhui 232001, China) Abstract: Search results sorting is a key technology in search engine, the algo rithmhas a direct influence on whether users can quickly find their expected i nformation afterkeywords are entered or not. The technology used for hyperlinkanalysis andpageranking algorithms based on hyperlink analysis were system ic ally presented. The ideas and principles of two of the most fundamental pager an king algorithms, PageRank and HITS, were expatiated. After analysis and comparis on, their respective advantages and disadvantages were summed up, and the condit ions and fields suitable for their application given. Finally some factors to benoted when search engine uses hyperlink analysis were pointed out.

Key words:search engine; hyperlink analysis; pageranking;PageRank; HITS

在互联网发展初期，网站相对较少，信息查找也比较容易。然而伴随互联网爆炸性的发展， 从1994年万维网（World Wide Web，WWW或Web）出现到现在短短十几年的发展，由于其开放 性和其上信息广泛的可访问性极大的鼓舞了人们创作的积极性使其日益发展成为一个最为丰 富庞大的信息资源库。对于一个普通互联网用户要想在这个硕大的信息库中找到自己所需的 资料简直如同大海捞针，这时为满足大众信息检索需求的专业搜索网站便应运而生了。

这些专业搜索网站的核心就是搜索引擎技术。而搜索引擎技术中搜索结果页面的排序算法在 搜索引擎中处于举足轻重的地位，因为排序算法决定了系统索引的网页与用户查询意图的相 关程度，同时也决定了网页在查询结果中出现的次序。它的好坏直接关系到用户输入关键词 后能不能得到要查找的信息。因此搜索引擎页面排序算法越来越受到众多研究学者的青睐， 尤其是基于超链接分析的排序算法更是层出不穷。

1超链接分析技术简介

传统的Web搜索引擎大多数是基于关键字匹配的，返回的结果是包含查询项的文档。也有基 于目录分类的搜索引擎，比如早期的Yahoo、新浪的搜索服务。但这些搜索引擎的搜索结果 并不令人满意。因为有些网站拥有者为了使自己的网站在搜索结果中能排在较为前端的位置 故意提高某些关键字的出现频率从而破坏了搜索结果的客观性和准确性。此外，有些重要网 页可能并没有包含查询项因而也就不可能被搜索引擎检索到。

然而，一些研究学者们逐渐发现，Web上超链结构是个非常丰富和重要的资源，如果能够充 分利用的话，可以极大的提高检索结果的质量［1］189。进而提出了基于超链接分析 的搜索结果排序算法。文献［2］78提出的PageRank算法开启了超链接分析研究的热 潮 。超链接分析的基本原理是：在某次搜索的所有结果中（大型商业搜索引擎通常会有数十万 甚至上百万个搜索结果），被其它网页用超链指向越多的页面，其价值就越高，在输出排序 中就应该排得越靠前［3］。即一个网页的重要性取决于该网页被其它网页链接的数 量，特别是被一些已经被认定为“重要”网页链接的数量。

超链接分析其实是一种引用投票机制，也就说如果一个网页被另外一个网页链接一次就相当 于另一网页对其投了一票，其重要性被肯定一次。对于静态网页或网站主页，这种机制具有 一定的合理性。因为这样的网页容易根据其在互联网上受到的评价而产生超链接指向的数量 ，超链分析的结果可以从很大程度上反映该网页的实际重要程度，能够为搜索用户返回接近 其搜索意图且很有价值的搜索结果。事实上，超链分析技术除了分析网页本身的文字外，还 分析所有指向该网页的链接URL、链接文字、甚至链接周围的文字。这样，有时候即使某个 网页html1中并没有包含某个词，比如“下载”，但如果有别的网页html2用链接文字“下载 ”指向这个网页html1，那么用户在搜索“下载”这个关键词时也能找到网页html1。而且， 如果有越多网页（html2、html3、html4、html5…）用“下载”链接指向这个网页html1 ，或者给出这个链接的源网页（html2、html3、html4、html5…）越优秀，那么网页html 1在用户搜索“下载”时就会被认为越相关，在搜索结果中的排名也就会越靠前。

由此看见，所谓链接分析主要基于如下两个重要假设:①超文本链接包含了用户对一个网站 的判断信息;②对一个网站而言，如果其他网站链接到该网站的链接数（即入链数）越多， 则该网站越重要。这两个假设在各种基于链接分析的算法中均以某种方式体现出来［2 ］78。

基于这种超链分析思想，一些学者提出了许多页面排序算法。目前有：PageRank算法、HITS算法、SALSA（Stochastic Approach for LinkStructure Analysis）算法、PHITS算法（Probabilistic analogue of the HITS）；贝叶斯算法、Reputation算法［3］6。还有在各自的基础上进行改进而产生的算法变种。这些算法 有的已经在实际的系统中实现和使用，并且取得了良好的效果。在这些算法中，PageRank和 HITS是最著名也是最基本的页面排序算法，其它算法是在两者基础之上进行某种程度的改进 版。下面对这两个基本算法作个详细的介绍与分析以为以后的研究工作做好基础准备工作。

2基于超链接分析的算法

2．1PageRank算法

2.1.1基本思想在基于超链接分析的排序算法中，PageRank算法是最有名的一种。它最初是Sergey Brin和L awrence Page在1998年提出的，后来被用在世界上最著名的搜索引擎Google中一直到今天。 Google通过PageRank元算法计算出网页的PageRank值，从而决定网页在搜索结果集中的出现 位置，PageRank值越高的网页，在结果中出现的位置越靠前。

其基本思想是:如果某一网页玊存在一个指向网页A的链接，则表明网页T的所有者认为网页 A是比较重要的，从而把T重要性得分值（即网页T的PageRank值）的一部分赋予獳。A 得到的分值大小由玊的PageRank值玃R(T)和T的出链(从T链出的链接)数C(T)决定。用公 式表示为:PR(T)/C(T)。因而对于页面A，其PageRank值玃R(A)就是从所有指向它的页 面分得的重要性分值的总和。可用以下公式计算オPR(A)=PR(T1)/C(T1)+…+

PR(Tn)/C(Tn)(1)

其中：玊1、T2、T3…Tn为含有指向A的链接的页面。

由于互联网上也存在一些页面没有入链或出链那么就无法计算其PageRank值。为避免这个问 题（即所谓的LinkSink问题）一些研究学者对其进行改进，为式（1）添加一个阻尼系数 玠使其变为

PR(A)=(1-d)+d［PR(T1)/C(T1)+…+PR(Tn)/C(Tn)］(2)

玠为阻尼系数，Google常指定为0.85［4］。这样在整个网络内的页面经过多次递 归迭代计算，直到PR值达到收敛即求得页面的PageRank值。

2.1.2优缺点分析从以上PageRank的计算公式中也以看出，一个页面会将自己的PageRank值均匀的分配给它所 引用的页面，它引用的页面越多，每个被它引用的页面所分得的PageRank值越少。因而一个 页面会因为别的页面对自己的引用而增加自己的PageRank值，但并不会因为自己对别的页面 的引用而提高自己的PageRank值。这样，对于一个网页来说要想获得较为靠前的排名就要获 得较大的PageRank值，而要获得较大的PageRank值就要被较多重要的网站所引用，因为只有 那些重要网站才有较大的PageRank值。而如果两个页面各自本身的PageRank值都很低，则它 们互相链接后也增加不多，重复链接对两者更是有害无益。由于页面的链接数越多，被链接 页面得到的PageRank值就会越低因此高级别的网站也不会与质量不高的网站互换链接。一个 网站要想获得较高级别的PageRank值就只有一个办法那就是要求网站拥有者老老实实地做好 自己的每一个网页，提高整个网站的质量水平才能换得高级别网站的链接。所以PageRank技 术可以很有效的避免某些网站为获得较高排名来欺骗搜索引擎。

PageRank技术的另外一个优点在于它是一个与查询无关的静态算法。尽管所有网页的PageRa nk值都要通过进行递归迭代计算以求得收敛值，这一过程中计算量很大，但这些计算不要求 实时性，可以离线计算获得结果后保存起来。这样能有效的减少在线查询时的运算量极大的 缩短查询响应时间。

然而，PageRank技术的缺点也是显而易见的。因为PageRank仅仅依靠计算网页的外部链接数 量来决定该网页的排名，而完全忽略了页面的主题内容与用户查询意图的相关性从而影响搜 索结果的相关性和准确性。另外，有一些Hub页本身并不突出，除了链接外也没有多少内容 也没有多少链接指向它，但它却指向了某个话题最突出的页面链接。可以说一个好的页面由 多个好的Hub页面所指向，一个好的Hub页面指向多个好的页面。这应该是一种互动关系，但 在PageRank中并没有考虑到［5］。再者，对于一些较新的网页由于还没有被发现故 被引用的次数很少因而即使质量很高也不会获得很高的PageRank值。也就是说PageRank会对 新网页表现很大的歧视性。

2．2HITS算法

2.2.1基本思想HITS（Hyperlink Induced Topic Search）算法是Kleinberg在1998年提出的，是基于超链 接分析排序算法中另一个最著名的算法之一。在该算法中,按照超链接的方向,将网页分成两 种类型的页面：Authority页面（权威页）和Hub页面（目录页）。二者是HITS算法中两个十 分重要的概念。Authority页面是指与某个查询关键词和组合最相近的页面；Hub页面是指它 的出链中包含了很多的Authority页面的页面，它的主要功能就是把这些Authority页面联合 在一起［6］。

HITS基本思想是：将查询玵提交给传统的基于关键字匹配的搜索引擎，搜索引擎返回很 多网页，从中取前玭个网页作为根集(Root Set)，用玆表示。R一般满足如下三个条件 ：① R中网页数量相对较小；② R中网页大多数是与查询q相关的网页；③ R中包 含 较多的权威网页。然后根据这个集合R在整个网页有向图中的位置来扩展这个根集合。即通 过向R加入被R引用的网页和引用R的网页将R扩展成一个更大的集合称为基集T。在得到这 个集合后，就开始计算集合中每个网页的目录型权值和权威型权值。利用Authority页面和H ub页面互相增强属性,对集合玊进行链接分析,通过迭代的计算方法为玊中的每个页面 计算一个Authority值和一个Hub值,作为结果页面排名的依据。

假定基集玊中的页面分别为 1，2，3，…玴 。每个页面玴有一个Authority值玜 p和Hub值玥p；页面玴的入链页面集表示为Bp(m），出链页面集表示为獸p（n ）。则ap和hp用如下公式进行计算

ap=∑[DD(]m[]i=1[DD)]hi(i∈Bp(m))

hp=∑[DD(]n[]i=1[DD)]ai(i∈Fp(n))

这样的递归式很容易用矩阵方法表示。令所有选出来的网页都进行标号，得到所有网页的编 号集｛1,2,…,玭｝。令相邻矩阵A为一个n×n的矩阵，如果存在一个从 网页i 链接到网页j 的超链，就令矩阵中A的第（i, j）个元素置为1，否 则置为0。同时，将所有网页的权威型 权值x和目录型权值y都分别表示成向量x=(x1,x2,x3,…,xn),y=(y1,y2,y3, …,yn)。由此可以得到计算x和y的简单矩阵公式：y=A•x,x=A 琓•y其中A琓是A的转置矩阵。进一 步，我们有：

x=A琓•y=A琓•Ax=( A琓A)•x

y=A琓•x=AA琓y=(AA琓)• y

因此向量玿,y均可经过多次迭代而得。经过一定次数的递归运算后，会得到集合中每个网 页的权威型权值和目录型权值。按照这两个不同的权值，分别取出前k个页面输出返回给 用户。根据线性代数的理论,迭代序列经过标准化最终将收敛于矩阵A的 特征向量,即上文计 算的Hub权值和Authority权值是页面集合的固有特征,不是由初始向量和参数的选择决定的 。

2.2.2优缺点分析由HITS的计算过程我们可以看出这种算法是一种依赖于查询关键字的算法。每得到一个检索 ，它都要从数据库中找到相应的网页，同时提取出这些网页和链接构成的有向子图，再通过 运算获得各个网页的相应链接权值。实际应用中，由R生成T的时间开销是很昂贵的 ，需要下 载和分析R中每个网页包含的所有链接，并且排除重复的链接。一般玊比R大很 多，由T生 成有向图也很耗时。需要分别计算网页的A/H值，计算量比PageRan k算法大。已有实验数据 表明，这种算法获得的排名准确性高于PageRank算法。但在用户检索时进行如此大量的运算 ，检索效率显然不高。

HITS算法最大的弱点是处理不好主题漂移问题（topic drift），也就是紧密链接TKC（Tigh tlyKnit Community Effect）现象［7］。由于HITS只计算主特征向量，也就是只 能发现玊集合中的主社区（Community），忽略了其它重要的社区。如果在集合玊中 有少数与查询主题无关的网页，但是他们是紧密链接的，HITS算法的结果可能就是这些网页 ，从而偏离了原来的查询主题。因此，HITS更适合于宽主题的查询。

另外，HITS算法不能有效的识别网站制作者对搜索引擎的欺骗。Web页面中有许多链接是为 其他目的而创建的,例如付费广告、网站本身导航等等,因此单凭链接数目来判断页面的Auth ority值和Hub值,是不合理的。

用HITS进行窄主题查询时，还可能产生主题泛化问题，即由根集到基集的扩展后引人了比原 来主题更重要的新主题，新主题可能与原始查询无关。泛化的原因是因为网页中包含不同主 题的向外链接，而且新主题的链接更加具有重要性。

3超链接分析应注意的问题

基于超链接分析的算法，提供了一种衡量网页质量的客观方法，独立于语言，独立于内容， 不需人工干预就能自动发现Web上重要的资源，挖掘出Web上重要的社区，自动实现文档分类 ［3］4。但由于互联网的开放性和自由性使得Web页面上的超链接也呈现鱼龙混杂状 态，给超链分析工作带来一定的干扰和欺骗。避害趋利，力求算法做到最大程度的精确 有效。有一些共同的问题影响着算法的精度我们必须给与重视。

(1) 根集的质量根集质量应该是很高的，否则，扩展后的网页集会增加很多无关的网页， 产生主题漂移，主题泛化等一系列的问题，计算量也增加很多。算法再好，也无法在低质量 网页集找出很多高质量的网页。

(2) 噪音链接Wed上不是每个链接都包含了有用的信息，比如广告，站点导航，赞助商， 用于友情交换的链接，对于链接分析不仅没有帮助，而且还影响结果［1］196。如何 有效的去除这些无关链接，也是算法的一个关键点。

(3) 锚文本的利用锚文本有很高的精度，对链接和目标网页的描述比较精确。在具体的实 现中我们应大加利用锚文本来优化算法。如何准确充分的利用锚文本，对算法的精度影响很 大。

(4) 查询的分类每种算法都有自身的适用情况，对于不同的查询，应该采用不同的算法， 以求获得最好的结果。因此，对于查询的分类也显得非常重要。

4结束语

随着Internet上信息量的爆炸式增长，人们越来越依赖于搜索引擎获取所需信息。虽然目前 的商用搜索引擎取得了很大的成功，但还有许多方便需要进一步完善。本文主要对基于超链 接分析的两种最基本的搜索结果排序算法PageRank和HITS进行了详细介绍和分析对比。希望 为将来在这两种算法思想的基础上进行改进，提出更精确更完善的排序算法打下基础。搜索 引擎的研究是一个热点,要能真正的研究并有所创新,对现有基础技术理论的学习和深入理解 是基础。

参考文献：

［1］李晓明，闫宏飞，王继民.搜索引擎——原理、技术与系统［M］.北京：科 学出版社,2004：189，196.

［2］吴江.使用超链分析技术的搜索引擎［J］.图书情报工作，2004，48(7)：78 81.

［3］李绍华，高文宇.搜索引擎页面排序算法研究综述［J］. 计算机应用研究，2007,24(6):47.

［4］刘琨，郑有才.搜索引擎剖析［J］.微机发展，2004,14(3):1922.

［5］徐宝文,张卫丰.搜索引擎与信息获取技术［M］. 北京:清华大学出版社,200 3：109110.

［6］张娜，张化祥.基于超链接和内容相关度的检索算法［J］. 计算机应用，2 006,26(5):1 1711 173.

［7］郑煜,钱榕.一个基于链接分析的相关度排序算法及其在专题搜索引擎中应用 ［J］.计算机应用与软件，2007，24（7）：5455.

(责任编辑：李丽)