搜索引擎核心技术详解6—链接分析

• 链接分析在搜索引擎搜索结果排序中起到非常重要的作用。绝大部分链接分析算法建立在随机游走模型和子集传播模型基础之上。

• PageRank和HTS算法是最重要且基础的两种链接分析算法，很多链接分析算法是对这两种方法的改进。

• SALSA算法是目前效果最好的链接分析算法之一，其融合了HTs算法与查询相关的特点，以及 PageRank算法的随机游走模型。

• 主题敏感 PageRank是对 PageRank算法的改进，可以应用于个性化搜索中。

• Hilltop算法除了可以用来改善搜索系统的精确性，还可以用来当做网页反作弊的技术手段

搜索引擎在查找能够满足用户请求的网页时，主要考虑两方面的因素：一方面是用户发出的查询与网页内容的内容相似性得分，即网页和查询的相关；另一方面就是通过链接分析方法计算获得的得分，即网页的重要性。

搜索引擎融合两者，共同拟合出相似性评分函数，来对搜索结果进行排序。

1、Web图

互联网包含了海量网页，而网页和一般文本的一个重要区别是在页面内容中包含相互引用的链接（Link)，如果将一个网页抽象成一个节点，而将网页之间的链接理解为一条有向边，则可以把整个互联网抽象为一个包含页面节点和节点之间联系边的有向图，称之为Web图。

Web图是对互联网的一种宏观抽象，其微观构成元素是一个个单独的网页。对于某个单独的网页A来说，在其内容部分往往会包含指向其他网页的链接，这些链接一般称为页面A的出链（Out Link)。因为网页A是在一个网状结构中，所以不仅网页A会指向其他页面，也会有很多其他页面有链接指向网页A，那么这些指向网页A的链接称为网页A的入链（In Link)。

锚文字也是网页中一种常见且非常有用的信息。所谓锚文字，就是页面内某个出链附近的一些描述文字。之所以锚文字会比较重要，是因为锚文字往往是对目标网页的一种概括性描述，所以在很多技术方法里都会利用这个信息来代表目标网页的含义。

2、两个概念模型及算法之间的关系

在介绍具体链接分析算法之前，首先介绍两个概念模型，并对各个链接分析算法之间的关系进行说明，这样有助于从宏观角度理解各个算法的基本思路与传承关系。

1）随机游走模型（Random Surfer Model)

互联网用户在上网时，往往有类似的网络行为：输入网址，浏览页面，然后顺着页面的链接不断打开新的网页。随机游走模型就是针对浏览网页的用户行为建立的抽象概念模型。之所以要建立这个抽象概念模型，是因为包括PageRank算法在内的很多链接分析算法都是建立在随机游走模型基础上的。

在最初阶段，用户打开浏览器浏览第1个网页，假设我们有一个虚拟时钟用来计时，此时可以设定时间为1，用户在看完网页后，对网页内某个链接指向的页面感兴趣，于是点击该链接，进入第2个页面，此时虚拟时钟再次计时，时钟走向数字2，如果网页包含了k个出链，则用户从当前页面跳转到任意一个链接所指向页面的概率是相等的。用户不断重复以上过程，在相互有链接指向的页面之间跳转。如果对于某个页面所包含的所有链接，用户都没有兴趣继续浏览，则可能会在浏览器中输入另外一个网址，直接到达该网页，这个行为称为远程跳转（Teleporting)。假设互联网中共有m个页面，则用户远程跳转到任意一个页面的概率也是相等的，即为1/m。随机游走模型就是一个对直接跳转和远程跳转两种用户浏览行为进行抽象的概念模型。

假设互联网由A、B、C3个网页构成，其相互链接关系如图中页面节点之间的有向边所示。根据链接关系，即可计算页面节点之间的转移概率，比如对于节点A来说，只有唯一一个出链指向节点B，所以从节点A跳转到节点B的概率为1，对于节点C来说，其对节点A和B都有链接指向，所以转向任意一个其他节点的概率为1/2。

假设在时刻1，用户浏览页面A，之后经由链接进入页面B，然后进入页面C，此时面临两种可能选择，跳转进入页面A或者页面B皆可，两者概率相同，都为1/2。

假设例子中的互联网包含不止3个页面，而是由10个页面构成，此时用户既不想跳回页面A，也不想跳回页面B，则可以按照1/10的概率跳入其他任意一个页面，即进行远程跳转。

2）子集传播模型

子集传播模型是从诸多链接分析算法中抽象出来的概念模型。其基本思想是在做算法设计时，把互联网网页按照一定规则划分，分为两个甚至是多个子集合。其中某个子集合具有特殊性质，很多算法往往从这个具有特殊性质的子集合出发，给予子集合内网页初始权值，之后根据这个特殊子集合内网页和其他网页的链接关系，按照一定方式将权值传递到其他网页。

一些链接分析算法符合子集传播模型，比如HITS算法和Hiltop算法及其衍生算法，在“网页反作弊”中会看到更多符合此模型的链接分析算法。

子集传播模型是个高度抽象的算法框架，很多算法可以认为是属于此框架的具体实例，即整体思路如上面所描述的流程，通常在以下几个方面各自存在不同。

• 如何定义特殊子集合，即在确定子集合内的网页应该有哪些特殊性质，具体算法规则不同。

• 在确定了特殊子集合所具有的性质后，如何对这个特殊子集合内网页给予一定的初始分值？不同算法打分方式各异。

• 从特殊子集合将其分值传播到其他网页时，采取何种传播方式？可传播的距离有多远？不同算法在此阶段也大都有差异。

注意：子集传播模型是本书作者从具体链接分析算法中归纳出的抽象模型，未见有文献明确提出，请读者阅读时谨慎参考。

3）链接分析算法之间的关系

到目前为止，学术界已经提出了很多链接分析算法，列出了其中影响力较大的一些算法及其相互关系，图中不同算法之间的箭头连接代表算法之间的改进关系，比如SALSA算法即融合了PageRank和HITS算法的基本思路。其他算法所代表的关系与此类似，可在图中明显看出算法间的传承关系。

尽管链接算法很多，但是从其概念模型来说，基本遵循上述介绍的随机游走模型和子集传播模型。而从图中可看出，在众多算法中，PageRank和HITS算法可以说是最重要的两个具有代表性的链接分析算法，后续的很多链接分析算法都是在这两个算法基础上衍生出来的改进算法。

3、PageRank算法

PageRank是Google创始人于1997年构建早期的搜索系统原型时提出的链接分析算法，自从Google在商业上获得空前的成功后，该算法也成为其他搜索引擎和学术界十分关注的计算模型。目前很多重要的链接分析算法都是在PageRank 算法基础上衍生出来的。

1）从入链数量到PageRank

在PageRank提出之前，已经有研究者提出利用网页的入链数量来进行链接分析计算，这种入链方法假设一个网页的入链越多，则该网页越重要。早期的很多搜索引擎也采纳了入链数量作为链接分析方法，对于搜索引擎效果提升也有较明显的效果。

PageRank除了考虑到入链数量的影响，还参考了网页质量因素，两者相结合获得了更好的网页重要性评价标准。

对于某个互联网网页A来说，该网页PageRank的计算基于以下两个基本假设：

• 数量假设：在Web图模型中，如果一个页面节点接收到的其他网页指向的入链数量越多，那么这个页面越重要。

• 质量假设：指向页面A的入链质量不同，质量高的页面会通过链接向其他页面传递更多的权重。所以越是质量高的页面指向页面A，则页面A越重要。

通过利用以上两个假设，PageRank算法刚开始赋予每个网页相同的重要性得分，通过迭代递归计算来更新每个页面节点的PageRank得分，直到得分稳定为止。

PageRank计算得出的结果是网页的重要性评价，这和用户输入的查询是没有任何关系的，即算法是主题无关的。假设有一个搜索引擎，其相似度计算函数不考虑内容相似因素，完全采用PageRank来进行排序，那么这个搜索引擎的表现是什么样子的呢?？这个搜索引擎对于任意不同的查询请求，返回的结果都是相同的，即返回PageRank值最高的页面。

2）PageRank计算

网页通过链接关系构建起Web图，在初始阶段，每个页面设置相同的PageRank值，通过若干轮的计算，会得到每个页面所获得的最终PageRank值。随着每一轮的计算进行，网页当前的PageRank值会不断得到更新。

在一轮更新页面PageRank得分的计算中，每个页面将其当前的PageRank值平均分配到本页面包含的出链上，这样每个链接即获得了相应的权值。而每个页面将所有指向本页面的入链所传入的权值求和，即可得到新的PageRank得分。当每个页面都获得了更新后的PageRank值，就完成了一轮PageRank计算。

如果在新的一轮PageRank计算之后，发现总体而言，页面节点的PageRank值基本稳定，不再发生较大变化，即可结束PageRank的计算，以此时得到的得分，作为最后排序时可以利用的PageRank得分。

3）链接陷阱（Link Sink）与远程跳转（Teleporting）

环形结构链接。这种结构类似于天体中的黑洞，在计算PageRank的时候，该结构将导致系统只会吸收传入的分值，而不能将获得的分值传播出去，随着PageRank一轮轮地连续运算，链接陷阱内的页面PageRank得分越来越高，这与PageRank的设计初衷相违背。

远程跳转是解决链接陷阱的通用方式，所谓的远程跳转，即在网页向外传递分值的时候，不限于向出链所指网页传递，也可以以一定的概率向任意其他网页跳转。对于链接陷阱内的网页来说，增加了远程跳转措施后，就像为每个页面增加了指向互联网任意其他页面的虚拟边，权值可以通过这种虚拟边向外传递，以此来避免链接陷阱导致的问题。

4、HITS 算法

（Hypertext Induced Topic Selection)

HITS算法也是链接分析中非常基础且重要的算法

1）Hub 页面与Authority页面

Hub页面和Authority页面是HITS算法最基本的两个定义。

Authority页面，是指与某个领域或者某个话题相关的高质量网页。比如搜索引擎领域，Google和百度首页即该领域的高质量网页；比如视频领域，优酷和土豆首页即该领域的高质量网页。

Hub页面，指的是包含了很多指向高质量Authority页面链接的网页，比如hao123首页可以认为是一个典型的高质量Hub网页。

HITS算法的目的是通过一定的技术手段，在海量网页中找到与用户查询主题相关的高质量Authority页面和Hub页面，尤其是Authority页面，因为这些页面代表了能够满足用户查询的高质量内容，搜索引擎以此作为搜索结果返回给用户。

2）相互增强关系

很多算法都是建立在一些假设之上的，HITS算法也不例外。HITS算法隐含并利用了两个基本假设：

• 基本假设1：一个好的Authority页面会被很多好的Hub页面指向。

• 基本假设2：一个好的Hub页面会指向很多好的Authority页面。

模糊的描述，即“高质量”或者“好的”，那么什么是“好的”Hub页面？什么是“好的”Authority页面?两个基本假设给出了所谓“好”的定义。

基本假设1说明了什么是“好的”Authority页面，即被很多好的Hub页面指向的页面是好的Authority页面，这里两个修饰语非常重要：“很多”和“好的”，所谓“很多”，即被越多的Hub页面指向越好，所谓“好的”，意味着指向该页面的Hub页面质量越高，则页面越好。这综合了指向本页面的所有Hub节点的数量和质量因素。

基本假设2则给出了什么是“好的”Hub页面的说明，即指向很多好的Authority页面的网页是好的Hub页面。同样地，“很多”和“好的”两个修饰语很重要，所谓“很多”，即指向的Authority页面数量越多越好；所谓“好的”，即指向的Authority页面质量越高，则该页面越是好的Hub页面。这也综合考虑了该页面有链接指向的所有页面的数量和质量因素。

从以上两个基本假设可以推导出Hub页面和Authority页面之间的相互增强关系，通过这种相互增强关系不断迭代计算，即可找出哪些页面是高质量的Hub页面，哪些页面是高质量的Authority页面。

3）HITS 算法

HITS算法与PageRank算法一个显著的差异是：HITS算法与用户输入的查询请求密切相关，而PageRank算法是与查询无关的全局算法。HITS后续计算步骤都是在接收到用户查询后展开的，即是与查询相关的链接分析算法。

HTS算法接收到了用户查询之后，将查询提交给某个现有的搜索引擎（或者是自己构造的检索系统），并在返回的搜索结果中，提取排名靠前的网页，得到一组与用户查询高度相关的初始网页集合，这个集合被称做根集（Root Set)。

在根集的基础上，HITS算法对网页集合进行扩充，扩充原则是：凡是与根集内网页有直接链接指向关系的网页都被扩充进来，无论是指向根集内页面也好，或者是根集页面指向的页面也好，都被扩充进入扩展网页集合。HITS算法在这个扩展网页集合内寻找好的Hub页面与好的Authority页面。

对于扩展网页集合来说，我们并不知道哪些页面是好的Hub页面或者好的Authority页面，每个网页都有潜在的可能，所以对于每个页面都设立两个权值，分别来记载这个页面是好的Hub页面或者Authority页面的可能性。在初始情况下，在没有更多可利用信息前，每个页面的这两个权值都是相同的，可以都设置为1。

之后，即可利用上面提到的两个基本假设，以及相互增强关系等原则进行多轮迭代计算，每轮迭代计算更新每个页面的两个权值，直到权值稳定不再发生明显的变化为止。

4）HITS 算法问题

HITS算法整体而言是个效果很好的算法，目前不仅在搜索引擎领域应用，而且被自然语言处理及社交分析等很多其他计算机领域借鉴使用，并取得了很好的应用效果。尽管如此，最初版本的HITS算法仍然存在一些问题，而后续很多基于HITS算法的链接分析方法，也是立足于改进HITS算法存在的这些问题而提出的。

• 计算效率较低：因为HITS算法是与查询相关的算法，所以必须在接收到用户查询后实时进行计算，而HITS算法本身需要进行很多轮迭代计算才能获得最终结果，这导致其计算效率较低，这是实际应用时必须慎重考虑的问题。

• 主题漂移问题：如果在扩展网页集合里包含部分与查询主题无关的页面，而且这些页面之间有较多的相互链接指向，那么使用HITS算法很可能会给予这些无关网页很高的排名，导致搜索结果发生主题漂移，这种现象被称为紧密链接社区现象（Tightly-Knit Community Effect)。

• 易被作弊者操纵结果：HITS算法从机制上很容易被作弊者操纵，比如作弊者可以建立一个网页，页面内容增加很多指向高质量网页或者著名网站的网址，这就是一个很好的Hub页面，之后作弊者再将这个网页链接指向作弊网页，于是可以提升作弊网页的Authority得分。

• 结构不稳定：所谓结构不稳定，就是说在原有的扩展网页集合内，如果添加删除个别网页或者改变少数链接关系，则HITS算法的排名结果就会有非常大的改变。

5）HITS算法与PageRank 算法比较

HITS算法和PageRank算法可以说是搜索引擎链接分析的两个最基础且最重要的算法。

从以上对两个算法的介绍可以看出，两者无论是在基本概念模型，还是计算思路及技术实现细节都有很大的不同，下面对两者之间的差异进行逐一说明。

• HITS算法是与用户输入的查询请求密切相关的，而PageRank与查询请求无关。所以，HITS算法可以单独作为相似性计算评价标准，而PageRank必须结合内容相似性计算才可以用来对网页相关性进行评价。

• HITS算法因为与用户查询密切相关，所以必须在接收到用户查询后进行实时计算，计算效率较低；而PageRank则可以在爬虫抓取完成后离线计算，在线直接使用计算结果，计算效率较高。

• HITS算法的计算对象数量较少，只需计算扩展集合内网页之间的链接关系；而PageRank是全局性算法，对所有互联网页面节点进行处理。

• 从两者的计算效率和处理对象集合大小来比较，PageRank更适合部署在服务器端，而HITS算法更适合部署在客户端。

• HITS算法存在主题泛化问题，所以更适合处理具体的用户查询；而PageRank算法在处理宽泛的用户查询时更有优势。

• HITS算法在计算时，对于每个页面需要计算两个分值，而PageRank算法只需计算一个分值即可：在搜索引擎领域，更重视HITS算法计算出的Authority权值，但是在很多应用HITS算法的其他领域，Hub分值也有很重要的作用。

• 从链接反作弊的角度来说，PageRank从机制上优于HITS算法，而HITS算法更易遭受链接作弊的影响。

• HITS算法结构不稳定，当对扩展网页集合内链接关系做出很小改变，则对最终排名有很大影响：而PageRank算法相对HITS而言表现稳定，其根本原因在于PageRank 计算时的远程跳转。

5、SALSA算法

SALSA算法的初衷希望能够结合两者的主要特点，既可以利用HITS算法与查询相关的特点，也可以采纳PageRank的随机游走模型，这是SALSA算法提出的背景。由此可见，SALSA算法融合了PageRank和HITS算法的基本思想，从实际效果来说，很多实验数据表明，SALSA的搜索效果也都优于前两个算法，是目前效果最好的链接分析算法之一。

从整体计算流程来说，可以将SALSA划分为两个大的阶段：首先是确定计算对象集合的阶段，这一阶段与HITS算法基本相同；第2个阶段是链接关系传播过程，在这一阶段则采纳了随机游走模型。

1）确定计算对象集合

PageRank的计算对象是互联网所有网页，SALSA算法与此不同，在本阶段，其与HITS算法思路大致相同，也是先得到扩展网页集合，之后将网页关系转换为方向二分图形式。

扩展网页集合

SALSA算法在接收到用户查询请求后，利用现有搜索引擎或者检索系统，获得一批与用户查询在内容上高度相关的网页，以此作为根集。并在此基础上，将与根集内网页有直接链接关系的网页纳入，形成扩展网页集合。之后会在扩展网页集合内根据一定的链接分析方法获得最终搜索结果排名。

转换为无向二分图

在获得了扩展网页集合之后，SALSA根据集合内的网页链接关系，将网页集合转换为一个二分图。即将网页划分到两个子集合中，一个子集合是Hub集合，另一个子集合是Authority集合。划分网页节点属于哪个集合，则根据如下规则：

• 如果一个网页包含出链，这些出链指向扩展网页集合内其他节点，则这个网页可被归入Hub集合。

• 如果一个网页包含扩展网页集合内其他节点指向的入链，则可被归入Authority集合。

由以上规则可以看出，如果某个网页同时包含入链和出链，则可以同时归入两个集合。同时，Hub集合内网页的出链组成了二分图内的边，根据以上法则，将扩展网页集合转换为二分图。

扩展网页集合示例 二分图

假设扩展网页集合如图所示，由6个网页构成，其链接关系如图所示，同时为了便于说明，每个网页给予一个唯一编号。以网页6为例，因为其有出链指向网页节点3和网页节点5，所以可以放入Hub集合，也因为编号为1、3、10的网页节点有链接指向网页节点6，所以也可以放入Authority集合中。网页节点6的两个出链保留，作为二分图的边，但是这里需要注意的是，在转换为二分图后，原先的有向边不再保留方向，转换为无向边，而HITS算法仍然保留为有向边，这点与SALSA略有不同。

到这一步骤为止，除了SALSA算法将扩展网页集合转换为无向二分图，而 HITS仍然是有向二分图外，其他步骤和流程，SALSA算法与HITS算法完全相同，因此，SALSA算法保证是与用户查询相关的链接分析算法。

2）链接关系传播

在链接关系传播阶段，SALSA算法放弃了HITS算法的Hub节点和Authority节点相互增强的假设，转而采纳PageRank的随机游走模型。

链接关系传播概念模型

假设存在某个浏览者，从某个子集合中随机选择一个节点出发（为方便说明，图中所示为从Hub子集合的节点1出发，实际计算往往是从Authority子集合出发的），如果节点包含多条边，则以相等概率随机选择一条边，从Hub子集合跳到Authority集合内节点，图中所示为由节点1转移到节点3之后从Authority子集合再次跳回Hub子集合，即由节点3跳到节点6。如此不断在两个子集之间转移，形成了SALSA自身的链接关系传播模式。

尽管看上去与PageRank的链接传播模式不同，但其实两者是一样的，关键点在于：其从某个节点跳到另外一个节点的时候，如果包含多个可供选择的链接，则以等概率随机选择一条路径，即在权值传播过程中，权值是被所有链接平均分配的。而HITS算法不同，HITS算法属于权值广播模式，即将节点本身的权值完全传播给有链接指向的节点，并不根据链接多少进行分配。

SALSA的上述权值传播模型与HITS模型关注重点不同，HITS模型关注的是Hub和Authority之间的节点相互增强关系，而SALSA实际上关注的是Hub-Hub及Authority-Authority之间的节点关系，而另一个子集合节点只是充当中转桥梁的作用。所以，上述权值传播模型可以转化为两个相似的子模型，即Hub节点关系图和Authority节点关系图。

Authority 节点关系图

Authority节点关系图，Hub节点关系图与此类似，两者转化过程是相似的，我们以Authority节点关系图为例来看如何从二分图转化为节点关系图。

Authority集合内从某个节点 i 转移到另一个节点 j 的概率，与从节点 j 转移到节点 i 的概率是不同的，即非对称的，所以转换后的Authority节点关系图是个有向图，以此来表示其转移概率之间的差异。

图中包含的节点就是二分图中属于Authority子集合的节点，关键在于节点之间的边如何建立及节点之间转移概率如何计算。

节点关系图中边的建立

之所以在Authority节点图中，节点3有边指向节点5，是因为在二分图中，由节点3通过Hub子集合的节点6中转，可以通达节点5，所以两者之间有边建立。

这里需要注意的是：在二分图中，对于Authority集合内的某个节点来说，一定可以通过Hub子集合的节点中转后再次返回本身，所以一定包含一条指向自身的有向边。节点1因为只有中转节点2使得其返回Authority子集合中的自身节点，所以只有指向自身的一条边，和其他节点没有边联系，所以例子中的Authority节点关系图由两个连通子图构成，一个只有节点1，另外一个连通子图由剩余几个节点构成。

节点之间的转移概率

至于为何Authority节点关系图中，节点3到节点5的转移概率为0.25，是因为前面介绍过，SALSA的权值传播模型遵循随机游走模型。在二分图中，从节点3转移到节点5的过程中，节点3有两条边可做选择来跳转到Hub子集合，所以每条边的选择概率为1/2，可以选择其中一条边到达节点6，同样，从节点6跳回到Authority子集合时，节点6也有两条边可选，选中每条边的概率为1/2。所以从节点3出发，经由节点6跳转到节点5的概率为两条边权值的乘积，即为1/4。

对于指向自身的有向边，其权重计算过程是类似的，我们仍然以节点3为例，指向自身的有向边代表从Authority子集合中的节点3出发，经由Hub子集合的节点再次返回节点3的概率。从二分图可以看出，完成这个过程有两条路径可走，一条是从节点3到节点1返回；另外一条是从节点3经由节点6后返回；每一条路径的概率与上面所述计算方法一样，因为两条路径各自的概率为0.25，所以节点3返回自身的概率为两条路径概率之和，即为0.5。图中其他边的转移概率计算方式也是类此。

建立好Authority节点关系图后，即可在图上利用随机游走模型来计算每个节点的Authority权值。在实际计算过程中，SALSA将搜索结果排序问题进一步转换为求Authority节点矩阵的主秩问题，矩阵的主秩即为每个节点的相应Authority得分，按照Authority得分由高到低排列，即可得到最终的搜索排序结果。

3）Authority权值计算

经过数学推导，可以得出SALSA与求矩阵主秩等价的Authority权值计算公式。示意图表明了SALSA算法中某个网页节点的Authority权值是如何计算的。如图右上角公式所示，决定某个网页i的Authority权值涉及4个因子。

• Authority子集合中包含的节点总数 |A|。其实这个因子对于Authority集合中任意节点来说都是相同的，所以对于最终的根据节点Authority权值进行的排序没有影响，只是起到保证权值得分在0到1之间，能够以概率形式表示权值的作用。    

• 网页 i 所在连通图中包含的节点个数|A_{j}|。网页所在的连通图包含的节点个数越多，则网页的Authority权值越大。

• 网页 i 所在连通图中包含的入链总数|E_{j}|。网页所在的连通图包含的入链总数越少，则网页的Authority权值越大。

• 网页 i 的入链个数|B_{i}|。节点入链越多，则Authority权值越大，这个因子是唯一—个和节点本身属性相关的。由此可见，SALSA权值计算和节点入链个数成正比。

我们以节点3为例，看其对应的4个计算因素取值。

• Authority子集共包括4个节点。

• 节点3所在连通图包含3个节点。

• 节点3所在连通图共有6个入链。

• 节点3的入链个数为2。

所以，节点3的Authority权值为：（3/4）×（2/6）=0.25。其他节点权值的计算过程与此类似。SALSA根据节点的Authority权值由高到低排序输出，即为搜索结果。

由上述权值计算公式可以推出：如果整个Authority子集合所有节点形成一个完整的连通图，那么在计算Authority权值的过程中，对于任意两个节点，4个因子中除了节点入链个数外，其他3个因子总是相同的，即只有入链个数起作用，此时，SALSA算法退化为根据节点入链个数决定排序顺序的算法。

从SALSA计算Authority得分过程中可看出，SALSA算法不需要像HITS算法一样进行不断的迭代计算，所以从计算效率角度看要快于HITS算法。另外，SALSA算法解决了HITS算法的计算结果主题漂移问题，所以搜索质量也优于HITS算法。SALSA算法是目前效果最好的链接算法之一。

6、主题敏感PageRank

（Topic Sensitive PageRank)

主题敏感PageRank是PageRank算法的改进版本，该算法已被Google使用在个性化搜索服务中。

1）主题敏感PageRank与PageRank的差异

PageRank算法基本遵循前面章节提到的随机游走模型，即用户在浏览某个网页时，如果希望跳转到其他页面，则随机选择本网页包含的某个链接，进入另一个页面。主题敏感PageRank则对该概念模型做出改进，引入了更符合现实的假设。一般来说用户会对某些领域感兴趣，同时当浏览某个页面时，这个页面也是与某个主题相关的（比如体育报道或者娱乐新闻），所以当用户看完当前页面，希望跳转时，更倾向于点击和当前页面主题类似的链接，即主题敏感PageRank 是将用户兴趣、页面主题及链接所指向网页与当前网页主题的相似程度综合考虑而建立的模型。很明显，这更符合真实用户的浏览过程。

PageRank是全局性的网页重要性衡量标准，每个网页会根据链接情况，被赋予一个唯一的PageRank分值。主题敏感PageRank在此点有所不同，该算法引入了16种主题类型，对于某个网页来说，对应某个主题类型都有相应的PageRank分值，即每个网页会被赋予16个主题相关PageRank分值。

在接收到用户查询后，两个算法在处理方式上也有较大差异。PageRank算法与查询无关，只能作为相似度计算的一个计算因子体现作用，无法独立使用。而主题敏感PageRank是查询相关的，可单独作为相似度计算公式使用。而且，在接收到用户查询后，主题敏感PageRank还需要利用分类器，计算该查询隶属于事先定义好的16个主题的隶属度，并在相似度计算时的排序公式中利用此信息。

2）主题敏感PageRank 计算流程

主题敏感PageRank 计算主要由两个步骤构成，第1步是离线的分类主题PageRank数值计算；第2步是在线利用算好的主题PageRank分值，来评估网页和用户查询的相似度，以按照相似度排序提供给用户搜索结果。下面以具体示例来了解主题敏感PageRank的计算流程。

分类主题PageRank 计算

主题敏感 PageRank 参考ODP网站（www.dmoz.org)，定义了16个大的主题类别，包括体育、商业、科技等。ODP（Open Directory Project)是人工整理的多层级网页分类导航站点，在顶级的16个大分类下还有更细致的小粒度分类结构，在最底层目录下，人工收集了符合该目录主题的精选高质量网页地址，以供互联网用户导航寻址。主题敏感PageRank采用了ODP最高级别的16个分类类别作为事先定义的主题类型。

主题敏感PageRank对16个类别的主题，依次计算该类别的PageRank分值，图显示了其计算流程和基本思路，为了简化说明，示意图只表现出了3个分类类别。在计算某个类别的PageRank分值时，将所有网页划分为两个集合，一个集合是ODP对应分类主题下所包括的所有网页，即人工精选的高质量网页，可以称之为集合S，剩下的网页放入另一个集合内，可称之为集合T。在计算PageRank时，由于集合S内的网页能够很好地表征分类主题，所以赋予较大的跳转概率值。通过这种设定，集合S内的网页根据链接关系向集合T中网页传递权值，因为直接有链接指向的往往主题类似，这样就将与该分类主题内容相似的网页赋予较高的PageRank值，而无关的网页则赋予较低权重的PageRank分值，以此方式达到对网页所包含主题的判断。

网页的分类主题pr计算方式

假设有个编号为1的网页，其被列到ODP目录中的艺术类别中，在对艺术类别进行PageRank 计算时，1号网页在集合S内，计算结束后，该网页获得的PageRank分值为0.5。当计算体育和商业类别的主题PageRank分值时，1号网页在集合T中，获得了相应的集合S中网页传递的权值，分别为0.02和0.01。在所有类别计算结束后，1号网页获得了3个不同主题对应的PageRank分值，组成一个主题PageRank向量。通过类似的方式，互联网内任意网页也可以获得相应的主题相关PageRank向量。通过以上过程可以看出，主题相关的PageRank分值向量其实代表了某个网页所讲述内容所属类别的概率。

在上述计算主题PageRank过程中，从集合S和集合了的划分及其权值传播方式中可以看出，该步骤计算过程也符合子集传播模型。但是由于本算法主框架及其出发点都是为了改进PageRank，所以将其归入随机游走模型的衍生算法类别中。

在线相似度计算

图中给出了主题敏感PageRank在线计算用户查询与网页相似度的示意图。假设用户输入了查询请求“乔丹”，搜索系统首先利用用户查询分类器对查询进行分类，计算用户查询隶属于定义好的各个类别的概率分别是多少，在我们给出的例子里，“乔丹”隶属于体育类别的概率为0.6，娱乐类别的概率为0.1.商业类别的概率为0.3。

在线相似度计算

在进行上述用户查询分类计算的同时，搜索系统读取索引，找出包含了用户查询“乔丹”的所有网页，并获得上一步骤离线计算好的各个分类主题的PageRank值，假设某个网页A的各个主题PageRank值分别为体育0.2、娱乐0.3及商业0.1。

得到用户查询的类别向量和某个网页的主题PageRank向量后，即可计算这个网页和查询的相似度。通过计算两个向量的乘积就可以得出两者之间的相关性。网页A和用户查询“乔丹”的相似度为：

对包含“乔丹”这个关键词的网页，都根据以上方法计算，得出其与用户查询的相似度后，就可以按照相似度由高到低排序输出，作为本次搜索的搜索结果返回给用户。

3）利用主题敏感PageRank构造个性化搜索

以上内容介绍的是主题敏感PageRank的基本思想和计算流程，从其内在机制来说，这个算法非常适合作为个性化搜索的技术方案。

计算相似度使用的只有用户当前输入的查询词“乔丹”，如果能够对此进行扩展，即不仅使用当前查询词，也考虑利用用户过去的搜索记录等个性化信息。比如用户之前搜索过“耐克”，则可以推断用户输入“乔丹”是想购买运动服饰，而如果之前搜索过“姚明”，则很可能用户希望获得体育方面的信息。通过这种方式，可以将用户的个性化信息和当前查询相融合来构造搜索系统，以此达到个性化搜索的目的，更精准地提供搜索服务。

7、Hiltop算法

Hilltop算法是Torono大学研发的链接分析算法，在2003年被Google公司收购，而Google在之后的排序算法大改版中引入了Hilltop算法。

Hilltop算法融合了HITS和PageRank两个算法的基本思想。一方面，Hilltop是与用户查询请求相关的链接分析算法，吸收了HITS算法根据用户查询获得高质量相关网页子集的思想，符合子集传播模型，是该模型的一个具体实例；同时，在权值传播过程中，Hiltop算法也采纳了PageRank的基本指导思想，即通过页面入链的数量和质量来确定搜索结果的排序权重。

1）Hilltop算法的一些基本定义

非从属组织页面（Non-affiliated Pages)是Hiltop算法的一个很重要的定义。要了解什么是非从属组织页面，先要搞明白什么是从属组织网站，所谓的从属组织网站，即不同的网站属于同一机构或者其拥有者有密切关联。具体而言，满足如下任意一条判断规则的网站会被认为是从属网站。

• 条件1：主机IP地址的前3个子网段相同，比如：IP地址分别为159.226.138.127和159.226.138.234的两个网站会被认为是从属网站。

• 条件2：如果网站域名中的主域名相同，比如www.ibm.com和www.ibm.com.cn会被认为是从属组织网站。

非从属组织页面的含义是：如果两个页面不属于从属网站，则为非从属组织页面。

专家页面（Export Sources)是Hiltop算法的另外一个重要定义。所谓专家页面，即与某个主题相关的高质量页面，同时需要满足以下要求：这些页面的链接所指向的页面相互之间都是非从属组织页面，且这些被指向的页面大多数是与专家页面主题相近的。

Hilltop算法将互联网页面划分为两类子集合，最重要的子集合是由专家页面构成的互联网页面子集，不在这个子集合里的剩下的互联网页面作为另外一个集合，这个集合称做目标页面集合（Target Web Servers）。

2）Hilltop算法

上图是Hilltop算法的整体流程示意。首先从海量的互联网网页中通过一定规则筛选出专家页面子集合，并单独为这个页面集合建立索引。Hilltop在接收到用户发出的某个查询请求时，首先根据用户查询的主题，从专家页面子集合中找出部分相关性最强的专家页面，并对每个专家页面计算相关性得分，然后根据目标页面和这些专家页面的链接关系来对目标页面进行排序。基本思路遵循PageRank算法的链接数量假设和质量原则，将专家页面的得分通过链接关系传递给目标页面，并以此分数作为目标页面与用户查询相关性的排序得分。最后系统整合相关专家页面和得分较高的目标页面作为搜索结果返回给用户。

若在上述过程中，Hiltop算法无法得到一个足够大的专家页面集合，则返回搜索结果为空。由此可以看出，Hilltop算法更注重搜索结果的精度和准确性，不太考虑搜索结果是否足够多或者对大多数用户查询是否都有相应的搜索结果，所以很多用户发出的查询的搜索结果为空。这意味着Hilltop算法可以与某个排序算法相结合，以提高排序准确性，但并不适合作为一个独立的网页排序算法来使用。

Hillop算法主要包含两个步骤：专家页面搜索及目标页面排序。

步骤一：专家页面搜索

Hiltop算法从1亿4千万网页中，通过计算筛选出250万规模的互联网页面作为专家页面集合。专家页面的选择标准相对宽松，同时满足以下两个条件的页面即可进入专家页面集合。

• 条件1：页面至少包含k个出链，这里的数量k可人为指定。

• 条件2：k个出链指向的所有页面相互之间的关系都符合非从属组织页面的要求。

当然，在此基础上，可以设定更严格的筛选条件，比如要求这些专家页面所包含链接指向的页面中，大部分涉及的主题和专家页面的主题必须是一致或近似的。

根据以上条件筛选出专家页面后，即可对专家页面单独建索引，在此过程中，索引系统只对页面中的关键片段（Key Phrase)进行索引。所谓关键片段，在Hiltop算法里包含了网页的3类信息：网页标题、H1标签内文字和URL锚文字。

网页的关键片段可以支配（Qualify)某个区域内包含的所有链接，支配关系代表了一种管辖范围，不同的关键片段支配链接的区域范围不同，具体而言，页面标题可以支配页面内所有出现的链接，H1标签可以支配包围在<H1>和</H1>内的所有链接，而 URL锚文字只能支配本身唯一的链接。

图中给出了关键片段对链接支配关系的示意图，在以“奥巴马访问中国”为标题的网页页面中，标题支配了所有这个页面出现的链接，而H1标签的管辖范围仅限于标签范围内出现的两个链接，对于锚文字“中国领导人”来说，其唯一能够支配的就是本身的这个链接。之所以定义这种支配关系，对于第2阶段将专家页面的分值传递到目标页面时候会起作用。

系统接收到用户查询Q，假设用户查询包含了多个单词, Hilltop如何对专家页面进行打分呢?对专家页面进行打分主要参考以下3类信息。

• 关键片段包含了多少查询词，包含的查询词越多，则分值越高，如果不包含任何查询词，则该关键片段不计分。

• 关键片段本身的类型信息，网页标题权值最高，H1标签次之，再次是链接锚文字。

• 用户查询和关键片段的失配率，即关键片段中不属于查询词的单词个数占关键片段总单词个数，这个值越小越好，越大则得分衰减越多。

Hilltop综合考虑以上3类因素，拟合出打分函数来对专家页面是否与用户查询相关进行打分，选出相关性分值足够高的专家页面，以进行下一步骤操作，即对目标页面进行相关性计算。

步骤二：目标页面排序

Hilltop算法包含一个基本假设， 即认为一个目标页面如果是满足用户查询的高质量搜索结果，其充分必要条件是该目标页面有高质量专家页面链接指向。然而，这个假设并不总是成立，比如有的专家页面的链接所指向的目标页面可能与用户查询并非密切相关。所以， Hilltop算法在这个阶段需要对专家页面的出链仔细进行甄别，以保证选出那些和查询密切相关的目标页面。

Hilltop在本阶段是基于专家页面和目标页面之间的链接关系来进行的， 在此基础上，将专家页面的得分传递给有链接关系的目标页面。传递分值之前，首先需要对链接关系进行整理，能够获得专家页面分值的目标页面需要满足以下两点要求：

• 条件1：至少需要两个专家页面有链接指向目标页面，而且这两个专家页面不能是从属组织页面，即不能来自同一网站或相关网站。如果是从属组织页面，则只能保留一个链接，抛弃权值低的那个链接。

• 条件2：专家页面和所指向的目标页面也需要符合一定要求，即这两个页面也不能是从属组织页面。

在步骤一，给定用户查询， Hilltop算法已经获得相关的专家页面及其与查询的相关度得分，在此基础上，如何对目标页面的相关性打分？上面列出的条件1指出，能够获得传递分值的目标页面一定有多个专家页面链接指向，所以目标页面所获得的总传播分值是每个有链接指向的专家页面所传递分值之和。而计算其中某个专家页面传递给目标页面权值的时候是这么计算的：

1. 找到专家页面中那些能够支配目标页面的关键片段集合S。

2. 统计S中包含用户查询词的关键片段个数T，T越大传递的权值越大。

3. 专家页面传递给目标页面的分值为： E X T， E为专家页面本身在第一阶段计算得到的相关得分， T为b步骤计算的分值。

假设专家页面集合内存在一个网页P，其标题为“奥巴马访问中国”，网页内容由一段<H1>标签文字和另一个单独的链接锚文字组成。该页面包含3个出链，其中两个指向目标页面集合中的网页www.china.org，另外一个指向网页www.obama.org。出链对应的锚文字分别为“奥巴马”、“中国”和“中国领导人”。

从图示的链接关系可以看出，网页P中能够支配www.china.org这个目标页面的关键片段集合包括：（中国领导人，中国，<H1>奥巴马访问中国</H1>，标题：奥巴马访问中国）而能够支配www.obamba.org目标页面的关键片段集合包括：（奥巴马，<H1>奥巴马访问中国</H1>，标题：奥巴马访问中国）。

接下来我们分析专家页面P在接收到查询时，是怎样将分值传递给与其有链接关系的目标页面的。假设系统接收到的查询请求为“奥巴马”，在接收到查询后，系统首先根据上述章节所述，找出专家页面并给予分值，而网页P作为专家页面中的一个页面，并获得了相应的分值S，我们重点关注分值传播步骤。

对于查询“奥巴马”来说，网页P中包含这个查询词的关键片段集合为： （奥巴马， <HI>奥巴马访问中国<HI>，标题：奥巴马访问中国），如上所述，这3个关键片段都能够支配www.obama.org页面，所以网页P传递给www.obamba.org的分值为Sx3。而对于目标页面www.china.org来说，这3个关键片段中只有（<HI>奥巴马访问中国</HI>，标题：奥巴马访问中国）这两个能够支配目标页面，所以网页P传递给www.china.org的分值为Sx2

对于包含多个查询词的用户请求，则每个查询词单独如上计算，将多个查询词的传递分值累加即可。

Hilltop算法存在与HITS算法类似的计算效率问题，因为根据查询主题从专家页面集合中选取主题相关的页面子集也是在线运行的，这与前面提到的HITS算法一样会影响查询响应时间。随着专家页面集合的增大，算法的可扩展性存在不足之处。

8、其他改进算法

学术界提出了很多改进方法

1、智能游走模型(IntelligentSurfer Model)

智能游走模型是对PageRank算法的改进，算法提出者认为PageRank所遵循的随机游走模型不符合真实情况，浏览者在浏览一个页面并选择下一步点击对象时，并非随机的，而是会对链接进行甄别，如果某个链接的网页内容能够表达浏览者向搜索引擎发出的查询词主题，则用户选择点击这个链接的概率会更大。智能游走模型即是对这种情况建立模型，会判断网页包含的链接所指向的网页内容和用户查询的相关性，以此来改善链接分析效果。

智能游走模型考虑到了网页内容和用户输入查询词的相关性，所以是查询相关的链接分析算法。但是需要在线计算某个查询和网页内容的相关性，所以计算速度较慢是其重要缺陷。

2、偏置游走模型(Biased Surfer Model)

偏置游走模型也是针对PageRank的随机游走模型的改进， 其基本思路和智能游走模型很接近，不同点在于：智能游走模型考虑的是网页内容和用户查询的相关性，而偏置游走模型考虑的是链接指向的网页内容和当前浏览网页内容之间的相似性，即认为如果链接指向网页内容和当前浏览网页内容越相似，则用户越可能点击这个链接。

偏置游走模型由于没有考虑查询，而只需要计算网页内容之间的相似性，可以离线进行计算，并在线使用，所以计算速度要优于智能游走模型。

3、PHITS算法(Probability Analogy of HITS)

PHITS算法是对HITS算法的直接改进。HITS算法在通过链接进行权值传递时，会将Hub或者Authority节点的权值全部传递给所有相连链接，而PHITS算法认为不同链接其传递权值的能力应该是不同的，这是其基本思想。基于此，PHITS需要计算两个页面S和T 之间链接的连接强度。

PHITS算法在页面S和页面T之间引入主题隐变量，而两个页面之间链接的强度取决于两个页面和这个隐变量的主题耦合关系，所以可以将这个算法看做PLSI算法的链接分析版本。虽然看上去复杂，但是PHITS算法的本质思想和偏置游走模型是一样的，即考虑的其实是页面S和页面T之间的内容相似性，内容越相似其链接强度越强，传递权值的能力越强。PHITS 算法和直接计算页面内容相似性的区别，仅仅是加入一个隐藏主题层，通过网页和隐藏层的关系来计算相似性。

4、BFS 算法(Backward Forward Step)

BFS算法作为SALSA算法的改进提出，而其本质既是对SALSA算法的扩展，也是对HITS算法的限制。 SALSA算法在计算网页的Authority分值时，仅仅考虑了通过Hub节点能够直接建立联系的网页之间的关系，而HITS算法考虑的是链接图的整个结构，任意两个网页S和T，如果网页S能够通过中间节点链接到网页T，则网页S就对网页T有影响，而影响的大小取决于从S到T的不同路径走法的个数，与S到T的距离远近没有关系。

BFS则是对两者的一个折中考虑，解除了SALSA算法只允许直接相邻网页才能有影响的限制，只要网页 S可以通达T，即可对网页 T施加影响，但是又对 HITS的网页影响方式做了限制，如果网页S距离网页 T距离越远，那么网页S的影响就随着距离增大而呈指数衰减，即距离越远，影响越小。通过这种折中，来实现对SALSA算法的扩充和对HITS 算法的限制。