常见的web网站超链接分析算法.doc

传统的WEB搜索引擎大多数是基于关键字匹配的，返回的结果是包含查询项的文档，也有基于目录分类的搜索引擎。这些搜索引擎的结果并不令人满意。有些站点有意提高关键字出现的频率来提高自身在搜索引擎中的重要性，破坏搜索引擎结果的客观性和准确性。另外，有些重要的网页并不包含查询项。搜索引擎的分类目录也不可能把所有的分类考虑全面，并且目录大多靠人工维护，主观性强，费用高，更新速度慢[2]。

最近几年，许多研究者发现，WWW上超链结构是个非常丰富和重要的资源，如果能够充分利用的话，可以极大的提高检索结果的质量。基于这种超链分析的思想，SergeyBrin和LawrencePage在1998年提出了PageRank算法[1]，同年J.Kleinberg提出了HITS算法[5]，其它一些学者也相继提出了另外的链接分析算法，如SALSA，PHITS，Bayesian等算法。这些算法有的已经在实际的系统中实现和使用，并且取得了良好的效果。

文章的第2部分按照时间顺序详细剖析了各种链接分析算法，对不同的算法进行了比较。第3部分对这些算法做了评价和总结，指出了存在的问题和改进方向。

一、WEB超链分析算法

1Google和PageRank算法

搜索引擎Google最初是斯坦福大学的博士研究生SergeyBrin和LawrencePage实现的一个原型系统[2]，现在已经发展成为WWW上最好的搜索引擎之一。Google的体系结构类似于传统的搜索引擎，它与传统的搜索引擎最大的不同处在于对网页进行了基于权威值的排序处理，使最重要的网页出现在结果的最前面。Google通过PageRank元算法计算出网页的PageRank值，从而决定网页在结果集中的出现位置，PageRank值越高的网页，在结果中出现的位置越前。

1.1PageRank算法

PageRank算法基于下面2个前提：

前提1：一个网页被多次引用，则它可能是很重要的；一个网页虽然没有被多次引用，但是被重要的网页引用，则它也可能是很重要的；一个网页的重要性被平均的传递到它所引用的网页。这种重要的网页称为权威（Authoritive）网页。
前提2：假定用户一开始随机的访问网页集合中的一个网页，以后跟随网页的向外链接向前浏览网页，不回退浏览，浏览下一个网页的概率就是被浏览网页的PageRank值。
简单PageRank算法描述如下：u是一个网页，F(u)是u指向的网页集合，B(u)是指向u的网页集合，N(u)是u指向外的链接数，显然N(u)=|F(u)|，c是一个用于规范化的因子（Google通常取0.85），（这种表示法也适用于以后介绍的算法）则u的Rank值计算如下：

这就是算法的形式化描述，也可以用矩阵来描述此算法，设A为一个方阵，行和列对应网页集的网页。如果网页i有指向网页j的一个链接，则Ai,j=1/Ni，否则Ai,j＝0。设V是对应网页集的一个向量，有V=cAV，V为A的特征根为c的特征向量。实际上，只需要求出最大特征根的特征向量，就是网页集对应的最终PageRank值，这可以用迭代方法计算。

如果有2个相互指向的网页a，b,他们不指向其它任何网页，另外有某个网页c，指向a，b中的某一个，比如a，那么在迭代计算中，a，b的rank值不分布出去而不断的累计。如下图：

为了解决这个问题，SergeyBrin和LawrencePage改进了算法，引入了衰退因子E(u)，E(U)是对应网页集的某一向量，对应rank的初始值，算法改进如下：

其中，对应的矩阵形式为V’=c(AV’+E)。

另外还有一些特殊的链接，指向的网页没有向外的链接。PageRank计算时，把这种链接首先除去，等计算完以后再加入，这对原来计算出的网页的rank值影响是很小的。

Pagerank算法除了对搜索结果进行排序外，还可以应用到其它方面，如估算网络流量，向后链接的预测器，为用户导航等[2]。

1.2算法的一些问题

Google是结合文本的方法来实现PageRank算法的[2]，所以只返回包含查询项的网页，然后根据网页的rank值对搜索到的结果进行排序，把rank值最高的网页放置到最前面，但是如果最重要的网页不在结果网页集中，PageRank算法就无能为力了，比如在Google中查询searchengines，像Google，Yahoo，Altivisa等都是很重要的，但是Google返回的结果中这些网页并没有出现。同样的查询例子也可以说明另外一个问题，Google，Yahoo是WWW上最受欢迎的网页，如果出现在查询项car的结果集中，一定会有很多网页指向它们，就会得到较高的rank值，事实上他们与car不太相关。

在PageRank算法的基础上，其它的研究者提出了改进的PageRan