２.２.２HITS的问题
HITS算法有以下几个问题：
1．实际应用中，由S生成T的时间开销是很昂贵的，需要下载和分析S中每个网页包含的所有链接，并且排除重复的链接。一般T比S大很多，由T生成有向图也很耗时。需要分别计算网页的A/H值，计算量比PageRank算法大。
2．有些时候，一主机A上的很多文档可能指向另外一台主机B上的某个文档，这就增加了A上文档的Hub值和B上文档的Authority，相反的情况也如此。HITS是假定某一文档的权威值是由不同的单个组织或者个人决定的，上述情况影响了A和B上文档的Hub和Authority值[7]。
3．网页中一些无关的链接影响A，H值的计算。在制作网页的时候，有些开发工具会自动的在网页上加入一些链接，这些链接大多是与查询主题无关的。同一个站点内的链接目的是为用户提供导航帮助，也与查询主题不甚无关，还有一些商业广告，赞助商和用于友情交换的链接，也会降低HITS算法的精度[8]。
4．HITS算法只计算主特征向量，也就是只能发现T集合中的主社区（Community），忽略了其它重要的社区[12]。事实上，其它社区可能也非常重要。
5．HITS算法最大的弱点是处理不好主题漂移问题（topicdrift）[7,8]，也就是紧密链接TKC（Tightly-KnitCommunityEffect）现象[8]。如果在集合T中有少数与查询主题无关的网页，但是他们是紧密链接的，HITS算法的结果可能就是这些网页，因为HITS只能发现主社区，从而偏离了原来的查询主题。下面讨论的SALSA算法中解决了TKC问题。
6．用HITS进行窄主题查询时，可能产生主题泛化问题[5,9]，即扩展以后引入了比原来主题更重要的新的主题，新的主题可能与原始查询无关。泛化的原因是因为网页中包含不同主题的向外链接，而且新主题的链接具有更加的重要性。
２.２.３HITS的变种
HITS算法遇到的问题，大多是因为HITS是纯粹的基于链接分析的算法，没有考虑文本内容，继J.Kleinberg提出HITS算法以后，很多研究者对HITS进行了改进，提出了许多HITS的变种算法，主要有：
２.２.３.１MonikaR.Henzinger和KrishnaBharat对HITS的改进
对于上述提到的HITS遇到的第2个问题，MonikaR.Henzinger和KrishnaBharat在[7]中进行了改进。假定主机A上有k个网页指向主机B上的某个文档d，则A上的k个文档对B的Authority贡献值总共为1,每个文档贡献1/k，而不是HITS中的每个文档贡献1，总共贡献k。类似的，对于Hub值，假定主机A上某个文档t指向主机B上的m个文档，则B上m个文档对t的Hub值总共贡献1，每个文档贡献1/m。I，O操作改为如下
I操作：
O操作：
调整后的算法有效的解决了问题2，称之为imp算法。
在这基础上，MonikaR.Henzinger和KrishnaBharat还引入了传统信息检索的内容分析技术来解决4和5，实际上也同时解决了问题3。具体方法如下，提取根集S中的每个文档的前1000个词语，串连起来作为查询主题Q，文档Dj和主题Q的相似度按如下公式计算：
，，＝项i在查询Q中的出现次数，
＝项i在文档Dj中的出现次数，IDFi是WWW上包含项i的文档数目的估计值。
在S扩展到T后，计算每个文档的主题相似度，根据不同的阈值（threshold）进行刷选，可以选择所有文档相似度的中值，根集文档相似度的中值，最大文档相似度的分数，如1/10，作为阈值。根据不同阈值进行处理，删除不满足条件的文档，再运行imp算法计算文档的A/H值，这些算法分别称为med，startmed，maxby10。
在此改进的算法中，计算文档的相似度时间开销会很大。
２.２.３.２ARC算法
IBMAlmaden研究中心的Clever工程组提出了ARC（AutomaticResourceCompilation）算法，对原始的HITS做了改进，赋予网页集对应的连结矩阵初值时结合了链接的锚（anchor）文本，适应了不同的链接具有不同的权值的情况。
ARC算法与HITS的不同主要有以下3点：
１．由根集S扩展为T时，HITS只扩展与根集中网页链接路径长度为1的网页，也就是只扩展直接与S相邻的网页，而ARC中把扩展的链接长度增加到2，扩展后的网页集称为增集（AugmentSet）。
２．HITS算法中，每个链接对应的矩阵值设为1，实际上每个链接的重要性是不同的，ARC算法考虑了链接周围的文本来确定链接的重要性。考虑链接p－q，p中有若干链接标记，文本1ahref=”q”锚文本/a文本2，设查询项t在文本1，锚文本，文本2，出现的次数为n（t），则w（p，q）＝1+n（t）。文本1和文本2的长度经过试验设为50字节[10]。构造矩阵W，如果有网页i－j，Wi,j＝w（i，j），否则Wi,j＝0，H值设为1，Z为W的转置矩阵，迭代执行下面3个的操作：
（1）A＝WH（2）H＝ZA（3）规范化A，H
３．ARC算法的目标是找到前15个最重要的网页，只需要A/H的前15个值相对大小保持稳定即可，不需要A/H整个收敛，这样2中迭代次数很小就能满足，[10]中指出迭代5次就可以，所以ARC算法有很高的计算效率，开销主要是在扩展根集上。
２.２.３.３Hub平均（Hub－Averaging－Kleinberg）算法
AllanBorodin等在[11]指出了一种现象，设有M＋1个Hub网页，M＋1个权威网页，前M个Hub指向第一个权威网页，第M＋1个Hub网页指向了所有M＋1个权威网页。显然根据HITS算法，第一个权威网页最重要，有最高的Authority值，这是我们希望的。但是，根据HITS，第M＋1个Hub网页有最高的Hub值，事实上，第M＋1个Hub网页既指向了权威值很高的第一个权威网页，同时也指向了其它权威值不高的网页，它的Hub值不应该比前M个网页的Hub值高。因此，AllanBorodin修改了HITS的O操作：
O操作：，n是(v,u)的个数
调整以后，仅指向权威值高的网页的Hub值比既指向权威值高又指向权威值低的网页的Hub值高，此算法称为Hub平均（Hub－Averaging－Kleinberg）算法。
２.２.３.４阈值（Threshhold—Kleinberg）算法
AllanBorodin等在[11]中同时提出了3种阈值控制的算法，分别是Hub阈值算法，Authority阈值算法，以及结合2者的全阈值算法。
计算网页p的Authority时候，不考虑指向它的所有网页Hub值对它的贡献，只考虑Hub值超过平均值的网页的贡献，这就是Hub阈值方法。
Authority阈值算法和Hub阈值方法类似，不考虑所有p指向的网页的Authority对p的Hub值贡献，只计算前K个权威网页对它Hub值的贡献，这是基于算法的目标是查找最重要的K个权威网页的前提。
同时使用Authority阈值算法和Hub阈值方法的算法，就是全阈值算法
２.３SALSA算法
PageRank算法是基于用户随机的向前浏览网页的直觉知识，HITS算法考虑的是Authoritive网页和Hub网页之间的加强关系。实际应用中，用户大多数情况下是向前浏览网页，但是很多时候也会回退浏览网页。基于上述直觉知识，R.Lempel和S.Moran提出了SALSA（StochasticApproachforLink-StructureAnalysis）算法[8]，考虑了用户回退浏览网页的情况，保留了PageRank的随机漫游和HITS中把网页分为Authoritive和Hub的思想，取消了Authoritive和Hub之间的相互加强关系。
具体算法如下：
１．和HITS算法的第一步一样，得到根集并且扩展为网页集合T，并除去孤立节点。
２．从集合T构造无向图G’＝（Vh，Va，E）
Vh={sh|s∈Candout-degree(s)0}(G’的Hub边).
Va={sa|s∈Candin-degree(s)0}(G’的Authority边).
E={(sh,ra)|s－rinT}
这就定义了2条链，Authority链和Hub链。
３．定义2条马尔可夫链的变化矩阵，也是随机矩阵，分别是Hub矩阵H，Authority矩阵A。
４．求出矩阵H，A的主特征向量，就是对应的马尔可夫链的静态分布。
５．A中值大的对应的网页就是所要找的重要网页。
SALSA算法没有HITS中相互加强的迭代过程，计算量远小于HITS。SALSA算法只考虑直接相邻的网页对自身A/H的影响，而HITS是计算整个网页集合T对自身AH的影响。
实际应用中，SALSA在扩展根集时忽略了很多无关的链接，比如
１．同一站点内的链接，因为这些链接大多只起导航作用。
２．CGI脚本链接。
３．广告和赞助商链接。
试验结果表明，对于单主题查询java，SALSA有比HITS更精确的结果，对于多主题查询abortion，HITS的结果集中于主题的某个方面，而SALSA算法的结果覆盖了多个方面，也就是说，对于TKC现象，SALSA算法比HITS算法有更高的健壮性。
２.３.１BFS（BackwordForwardStep）算法
SALSA算法计算网页的Authority值时，只考虑网页在直接相邻网页集中的受欢迎程度，忽略其它网页对它的影响。HITS算法考虑的是整个图的结构，特别的，经过n步以后，网页i的Authority的权重是，为离开网页i的的路径的数目，也就是说网页ji，对i的权值贡献等于从i到j的路径的数量。如果从i到j包含有一个回路，那么j对i的贡献将会呈指数级增加，这并不是算法所希望的，因为回路可能不是与查询相关的。
因此，AllanBorodin等[11]提出了BFS（BackwardForwardStep）算法，既是SALSA的扩展情况，也是HITS的限制情况。基本思想是，SALSA只考虑直接相邻网页的影响，BFS扩展到考虑路径长度为n的相邻网页的影响。在BFS中，被指定表示能通过路径到达i的结点的集合，这样j对i的贡献依赖就与j到i的距离。BFS采用指数级降低权值的方式，结点i的权值计算公式如下：
＝|B(i)|+|BF(i)|+|BFB(i)|+……+||
算法从结点i开始，第一步向后访问，然后继续向前或者向后访问邻居，每一步遇到新的结点加入权值计算，结点只有在第一次被访问时加入进去计算。
２.４PHITS
D.CohnandH.Chang提出了计算Hub和Authority的统计算法PHITS（ProbabilisticanalogueoftheHITS）[12]。他们提出了一个概率模型，在这个模型里面一个潜在的因子或者主题z影响了文档d到文档c的一个链接，他们进一步假定，给定因子z，文档c的条件分布P(c|z)存在，并且给定文档d，因子z的条件分布P（z|d）也存在。
P(d)P(z|d)P(c|z)，其中
根据这些条件分布，提出了一个可能性函数（likelihoodfunction）L,
，M是对应的连结矩阵
然后，PHITS算法使用Dempster等提出的EM算法[20]分配未知的条件概率使得L最大化，也就是最好的解释了网页之间的链接关系。算法要求因子z的数目事先给定。AllanBorodin指出，PHITS中使用的EM算法可能会收敛于局部的最大化，而不是真正的全局最大化[11]。D.Cohn和T.Hofmann还提出了结合文档内容和超链接的概率模型[13]。
２.５贝叶斯算法
AllanBorodin等提出了完全的贝叶斯统计方法来确定Hub和Authoritive网页[11]。假定有M个Hub网页和N个Authority网页，可以是相同的集合。每个Hub网页有一个未知的实数参数，表示拥有超链的一般趋势，一个未知的非负参数，表示拥有指向Authority网页的链接的趋势。每个Authoritive网页j，有一个未知的非负参数，表示j的Authority的级别。
统计模型如下，Hub网页i到Authority网页j的链接的先验概率如下给定：
P（i，j）＝Exp（＋）/（1＋Exp（＋））
Hub网页i到Authority网页j没有链接时，P（i，j）＝1/（1＋Exp（＋））
从以上公式可以看出，如果很大（表示Hub网页i有很高的趋势指向任何一个网页），或者和都很大（表示i是个高质量Hub，j是个高质量的Authority网页），那么i－j的链接的概率就比较大。
为了符合贝叶斯统计模型的规范，要给2M＋N个未知参数（，，）指定先验分布，这些分布应该是一般化的，不提供信息的，不依赖于被观察数据的，对结果只能产生很小影响的。AllanBorodin等在中指定满足正太分布N（μ，）,均值μ＝0，标准方差δ＝10，指定和满足Exp（1）分布，即x=0，P(=x)＝P(=x)＝Exp（－x）。
接下来就是标准的贝叶斯方法处理和HITS中求矩阵特征根的运算。
２.５.１简化的贝叶斯算法
AllanBorodin同时提出了简化的上述贝叶斯算法，完全除去了参数，也就不再需要正太分布的参数μ，δ了。计算公式变为：P（i，j）＝/（1＋），Hub网页到Authority网页j没有链接时，P（i，j）＝1/(1＋)。
AllanBorodin指出简化的贝叶斯产生的效果与SALSA算法的结果非常类似。
２.６Reputation
上面的所有算法，都是从查询项或者主题出发，经过算法处理，得到结果网页。多伦多大学计算机系AlbertoMendelzon,DavoodRafiei提出了一种反向的算法，输入为某个网页的URL地址，输出为一组主题，网页在这些主题上有声望（repution）[16]。比如输入，www.gamelan.com，可能的输出结果是“java”，具体的系统可以访问htpp://www.cs.toronto.edu/db/topic。
给定一个网页p，计算在主题t上的声望，首先定义2个参数，渗透率和聚焦率，简单起见，网页p包含主题项t，就认为p在主题t上。
是指向p而且包含t的网页数目，是指向p的网页数目，是包含t的网页数目。结合非条件概率，引入，，是WEB上网页的数目。P在t上的声望计算如下：
指定是既指向p有包含t的概率，即，显然有
我们可以从搜索引擎（如Altavista）的结果得到，,,WEB上网页的总数估计值某些组织会经常公布，在计算中是个常量不影响RM的排序，RM最后如此计算：
给定网页p和主题t，RM可以如上计算，但是多数的情况的只给定网页p，需要提取主题后计算。算法的目标是找到一组t，使得RM（p，t）有较大的值。TOPIC系统中是抽取指向p的网页中的锚文本的单词作为主题（上面已经讨论过锚文本能很好描述目标网页，精度很高），避免了下载所有指向p的网页，而且RM（p，t）的计算很简单，算法的效率较高。主题抽取时，还忽略了用于导航、重复的链接的文本，同时也过滤了停止字（stopword），如“a”，“the”，“for”，“in”等。
Reputation算法也是基于随机漫游模型的（randomwalk），可以说是PageRank和SALSA算法的结合体。这对SEO对PR的理解很有意思。
３.链接算法的分类及其评价
链接分析算法可以用来提高搜索引擎的查询效果，可以发现WWW上的重要的社区，可以分析某个网站的拓扑结构，声望，分类等，可以用来实现文档的自动分类等。归根结底，能够帮助用户在WWW海量的信息里面准确找到需要的信息。这是一个正在迅速发展的研究领域。
上面我们从历史的角度总结了链接分析算法的发展历程，较为详细的介绍了算法的基本思想和具体实现，对算法的存在的问题也做了讨论。这些算法有的处于研究阶段，有的已经在具体的系统实现了。这些算法大体可以分为3类，基于随机漫游模型的，比如PageRank，Repution算法，基于Hub和Authority相互加强模型的，如HITS及其变种，基于概率模型的，如SALSA，PHITS，基于贝叶斯模型的，如贝叶斯算法及其简化版本。所有的算法在实际应用中都结合传统的内容分析技术进行了优化。一些实际的系统实现了某些算法，并且获得了很好的效果，Google实现了PageRank算法，IBMAlmadenResearchCenter的CleverProject实现了ARC算法，多伦多大学计算机系实现了一个原型系统TOPIC，来计算指定网页有声望的主题。
ATT香农实验室的BrianAmento在指出，用权威性来评价网页的质量和人类专家评价的结果是一致的，并且各种链接分析算法的结果在大多数的情况下差别很小[15]。但是，AllanBorodin也指出没有一种算法是完美的，在某些查询下，结果可能很好，在另外的查询下，结果可能很差[11]。所以应该根据不同查询的情况，选择不同的合适的算法。
基于链接分析的算法，提供了一种衡量网页质量的客观方法，独立于语言，独立于内容，不需人工干预就能自动发现WEB上重要的资源，挖掘出WEB上重要的社区，自动实现文档分类。但是也有一些共同的问题影响着算法的精度。
１．根集的质量。根集质量应该是很高的，否则，扩展后的网页集会增加很多无关的网页，产生主题漂移，主题泛化等一系列的问题，计算量也增加很多。算法再好，也无法在低质量网页集找出很多高质量的网页。
２．噪音链接。WEB上不是每个链接都包含了有用的信息，比如广告，站点导航，赞助商，用于友情交换的链接，对于链接分析不仅没有帮助，而且还影响结果。如何有效的去除这些无关链接，也是算法的一个关键点。
３．锚文本的利用。锚文本有很高的精度，对链接和目标网页的描述比较精确。上述算法在具体的实现中利用了锚文本来优化算法。如何准确充分的利用锚文本，对算法的精度影响很大。
４．查询的分类。每种算法都有自身的适用情况，对于不同的查询，应该采用不同的算法，以求获得最好的结果。因此，对于查询的分类也显得非常重要。
当然，这些问题带有很大的主观性，比如，质量不能精确的定义，链接是否包含重要的信息也没有有效的方法能准确的判定，分析锚文本又涉及到语义问题，查询的分类也没有明确界限。如果算法要取得更好的效果，在这几个方面需要继续做深入的研究，相信在不久的将来会有更多的有趣和有用的成果出现。 |
