链接分析
我们在最开始说过，搜索引擎在查找能够满足用户需求的网页时，主要会考虑两方面的因素，一方面是用户发出的查询与网页内容的相关性得分，另一点就是通过链接分析方法计算获得的得分，也即网页的重要性。
PageRank算法
PageRank算法是Google创始人于1997年构建早期搜索系统原型时提出的链接分析算法，目前很多重要的链接分析算法都是在PageRank算法基础上衍生出来的。
对于某个网页A来说，该网页的PageRank计算基于以下两个基本假设：
- 数量假设：在Web图模型中，如果一个页面节点接收到的其他网页指向的入链数量越多，那么这个页面越重要。
- 质量假设：指向页面A的入链质量不同，质量高的页面会通过链接向其他页面传递更多的权重。所以越是高质量的页面指向页面A，页面A越重要。
PageRank计算得出的结果是网页的重要性评价，这和用户输入的查询是没有任何关系的。也即如果有一个搜索引擎完全基于PageRank，那用户不论输入什么查询语句，返回的结果都是相同的，都是PageRank值最高的页面。
PageRank计算
初始阶段，每个页面设置相同的PageRank值，通过若干轮的计算，每个页面会收敛到最终的PageRank值。
在一轮PageRank得分的更新计算中，每个页面将其当前的PageRank值平均分配到本页包含的出链上，这样每个链接即获得了相应的权值。而每个页面将所有指向本页面的入链所传入的权值求和，即可得到新的PageRank得分。当每个页面都获得了更新后的PageRank值，就完成了一轮PageRank计算。
链接陷阱与远程跳转
如果仔细思考一下就会发现上面的PageRank算法存在问题。一个典型的例子就是链接陷阱，比如三个网页，相互链接指向，形成了一个环结构，这种结构在计算PageRank的时候，该结构将导致系统只会吸收传入的分支，而不能将获得的分值传播出去，随着PageRank一轮轮地连续计算，链接陷阱内的页面PageRank值将会越来越高。
远程跳转是解决链接陷阱的通用方式，所谓远程跳转，即在网页向外传递分值的时候，不限于向出链所指网页传递，也可以以一定的概率向任意其他网页跳转。权值通过这种虚拟边向外传递，以此来避免链接陷阱导致的问题。
HITS算法（Hypertext Induced Topic Selection）
Hub页面与Authority页面
Hub页面与Authority页面是HITS算法最基本的两个定义，所谓Authority页面是指与某个领域或某个话题相关的高质量网页；所谓Hub页面，指的是包含了很多指向高质量Authority页面链接的网页。
相互增强关系
HITS算法隐含并利用了两个基本假设：
- 一个好的Authority页面会被很多好的Hub页面指向
- 一个好的Hub页面会指向很多好的Authority页面
通过这种相互增强关系不断迭代计算，即可找出哪些页面是高质量的Hub页面和Authority页面。
HITS算法流程
HITS算法与PageRank一个显著的区别就是HITS算法与用户输入的查询请求密切相关，而PageRank算法是与查询无关的全局算法。
HITS算法接收到了用户查询之后，会将查询提交给某个现有的搜索引擎或是自己构建的检索模型，并在返回的搜索结果中，提取排名靠前的网页，得到一组与用户查询高度相关的初始网页集合，这个集合被称为根集。
在根集的基础上，凡是与根集网页有直接链接指向关系（指向根集内页面/根集页面有链接指向）的网页都被扩充进扩展网页集合。HITS算法在这个扩展网页集合内寻找好的Hub页面与Authority页面。
对于扩展网页集合，我们对每个页面都设置两个初始权值，一般将Hub权值和Authrity权值都初始化为1
之后可以根据前面的两条基本假设不断进行迭代，直到权值收敛。
HITS算法存在主题漂移问题，如果在扩展网页集合里包含部分与查询主题无关的页面，而且这些页面之间有较多的相互链接指向，那么HITS算法很可能给给予这些无关网页很高的排名，这种现象被称为紧密链接社区现象。
HITS算法计算效率较低，且较容易被作弊者操纵结果，而PageRank因为增加了远程跳转，机制上优于HITS算法。
SALSA算法
SALSA算法融合了PageRank与HITS算法的基本思想，是目前效果最好的链接分析算法之一。
SALSA算法有两个阶段，首先是确定计算对象集合的阶段，这一阶段与HITS算法基本相同；第二阶段是链接关系传播过程，这一阶段采纳了PageRank的随机游走模型。
