第6章链接分析搜索引擎在查找能够满足用户请求的网页时，主要考虑两方面的因素：一方面是用户发出的查询与网页内容的内容相似性得分，即网页和查询的相关性。另一方面就是通过链接分析方法计算获得的得分，即网页的重要性。搜索引擎融合了两者，共同草拟出相似性评分函数，来对搜索结果进行排序。6.1Web图对于某个单独的网页A来说，在其内容部分往往会包含指向其他网页的链接，这些连接一般称为页面A的出链。其他网页指向A，那么这些指向A的链接称为网页A的入链。锚文字也是网页中一个比较常见且fiche有用的信息。所谓锚文字，就是页面内某个出链附近的一些描述文字。之所以锚文字比较重要，是因为锚文字往往是对目标网页的一种概括性描述，所以在很多技术方法里都会利用这个信息来代表目标网页的含义。6.2两个概念模型及算法之间的关系6.2.1随机游走模型（RandomSurferModel）互联网用户在上网时，往往有类似的网络行为：输入网址，浏览页面，然后顺着页面的链接不断打开新的网页。随机游走模型就是针对浏览器网页的用户行为建立的抽象概念模型。之所以要建立这个抽象概念模型，是因为包括pagerank算法在内的很多链接分析算法都是建立在随机游走模型的基础上。如果对于某个网页包含的所有的链接，用户都没兴趣继续浏览，则可能会在浏览器中输入另外一个网址，直接到达该网页，这个行为成为远程跳转。假设互联网中有m个页面，则用户远程跳转到任意一个页面的概率也是相等的，即为1/m。随机游走模型就是一个对直接跳转和远程跳2种用户浏览行为进行抽象的概念模型。6.2.2子集传播模型子集传播模型是从诸多链接分析算法中抽象出来的概念模型。其基本思想是在做算法设计时，把互联网网页按照一定规则划分，分为两个甚至是多个子集合。其中某个子集合具有特殊性质，很多算法往往从这个具有特殊性质的子集合触发，给与子集合内网页初始权值，之后根据这个特殊自子集合内网页和其他网页的链接关系，按照一定方式将权值传递到其他网页。6.2.3链接分析算法之间的关系PageRank 算法，HITS 算法，SALSA 算法，主体敏感PageRank算法和 Hilltop 算法。尽管链接算法很多，但是从其概念模型来说，基本遵循上述的随机游走模型和子集传播模型。而从图中可以看出，在众多算法中，PageRank 和 HITS 算法可以说是最重要的两个具有代表性的链接分析算法，后续的很多链接分析算法都是在这2个算法的基础上衍生出来的改进算法。6.3PageRank算法6.3.1从入链数量到PageRank对于某个互联网网页A来说，该网页PageRank的计算基于以下两个基本假设:1.数量假设在web图模型中，如果一个页面节点接收到的其他网页指向的入链数量越多，那么这个页面就越重要。2.质量假设指向页面A的入链质量不同，质量搞的页面会通过链接向其他页面传递更多的权重。所以越是高质量的页面指向页面A，则页面A越重要。通过利用以上两个假设，pagerank算法刚开始赋予每个网页相同的重要性得分，通过递归迭代计算来更新每个页面节点的pagerank得分，直到得分稳定为止。PageRank计算得出的结果是网页的重要性评价，这和用户输入的查询是没有任何关系的，即算法是与主题无关的。假设有一个搜索引擎，其相似度计算函数不考虑内容相似性因素，完全采用PageRank算法进行排序，那么这个搜索引擎的表现是什么样的呢？这个搜索引擎对于任意不同的查询请求，返回的结果都是相同的，即返回PageRank值最高的页面。6.3.2PageRank计算网页通过链接关系构建起web图，在初始阶段，每个页面设置相同的PageRank值，通过若干轮的计算，会的得到每个页面所获得的的最终PageRank值。随着每一轮的计算进行，网页当前的PageRank值会不断的更新。在一轮更新页面PageRank得分的计算中，每个页面将其当前的PageRank值平均分配到本页面包含的出链上，这样每个链接获得了响应的权值。而每个页面将所有指向本页面的入链所传入的权值求和，即可得到新的PageRank得分。当每个页面都获得了更新后的PageRank，就完成了一轮PageRank计算。6.3.3链接陷阱（LinkSink）与远程跳转（Teleporting）例子，包含了3个网页，互相有链接指向，形成了一个环形结构。这种结构类似于天体中的黑洞，在计算PageRank的时候，giant结构将导致系统只会吸收传入的分值，而不能将获得的分值传导出去，随着PageRank一轮一轮的连续运算，链接陷阱内的页面的PageRank得分越来越高，这与PageRank的设计初衷相违背。远程跳转是解决链接陷阱的通用方式，所谓的远程跳转，即在网页向外传递分值的时候，不限于向出链所指网页传递，也可以以一定的概率向任意其他网页跳转。对于链接陷阱内的网页来说，增加了远程跳转措施后，就像为每个页面增加了指向互联网任意其他页面的虚边界，权值可以通过这种虚边界向外传递，以此来避免陷阱导致的问题。6.4HITS算法（HypertextInducedTopicSelection）6.4.1Hub页面与Authority页面Hub页面与Authority页面 是 HITS 算法最基本的两个定义。所谓 Authority页面，是指与某个领域或者某个话题相关的高质量网页。比如搜索引擎领域，google和百度首页即该领域的高质量网页；所谓 Hub 页面，指的是包含了很多指向高质量 Authority 页面的链接网页，比如hao123首页这种。6.4.2相互增强关系很多算法都是建立在一些假设之上的，HITS 算法也不例外。HITS 算法隐含并利用了两个基本的假设:1.基本假设1一个好的Authority 页面会被很多 Hub页面指向。2.基本假设2一个好的Hub页面会指向很多好的 Authority页面。6.4.3HITS算法HITS 算法与 PageRank 算法的一个显著差异是：HITS 算法与用户输入的查询请求密切相关，而PageRank算法是与查询无关的全局算法。HITS后续计算步骤都是在接收到用户查询后展开的，即是与查询相关的链接分析算法。HITS 算法接收到了用户查询之后，将查询提交给某个现有的搜索引擎，并在返回的搜索结果中，提取排名靠前的网页，得到一组与用户查询高度相关的初始网页集合，这个集合被称作根集。在根集的基础上，HITS算法对网页集合进行扩充，扩充的原则是：凡是与根集内网页有直接链接指向关系的网页都会被扩充进来，无论是有链接指向根集内页面也好，或者是根集页面有链接指向其他的页面也好，都被扩充进扩展网页集合。HITS算法在这个扩展页集合内寻找好的Hub页面与好的Authority页面。对于扩展网页集合来说，我们并不知道哪些页面是好的Hub页面或者好的Authority页面，每个网页都有潜在的可能，所以对于每个页面都设立两个权值，分别来记载这个页面是好的Hub页面或者Authority页面的可能性。在初始情况下，在没有更多可利用信息前，每个页面的这2个权值都是相同的，可以设置为1.之后，即可利用上面提到的两个基本假设，以及互相增强关系等原则进行多伦迭代计算，每轮迭代计算更新每个页面的两个权值，直到权值稳定不再发生明显变化为止。6.4.4HITS算法存在的问题1.计算效率比较低2.主题漂移问题3.易被作弊者操纵4.结构不稳定6.4.5HITS算法与PageRank算法比较1.HITS 算法是与用户输入的查询请求密切相关的，而pagerank与查询请求无关。所以，HITS算法可以单独作为相似性计算评价标准，而pagerank必须结合内容相似性计算才可以用来对网页相似性进行评价2.hits 算法因为与用户查询密切相关，所以必须在接收到用户查询后进行实时计算，计算效率比较低；而pagerank则可以在爬虫抓取完成后离线计算，在线直接使用计算结果，计算效率比较高。3.hits 算法的计算对象数量比较少，只需计算扩展集合内网页之间的链接关系；而pagerank是全局性算法，对所有互联网页面节点进行处理。4.从两者的计算效率和处理对象集合大小来比较，pagerank更适合部署在服务器端，而hits 算法更适合部署在客户端5.hits 算法存在主题泛化问题，所以更适合处理具体的用户查询；而pagerank算法在处理宽泛的用户查询时更有优势6.hits 算法在计算时，对于每个页面需要计算两个分值，而pagerank算法只需要计算一个分值即可；在搜索领域，更重视hits 算法计算出的authority 权值，但是在很多应用hits算法的其他领域，Hub分值也有很重要的作用。7.从链接反作弊的角度来说，pagerank从机制上优于hits算法，而hits算法更容易遭受链接作弊的影响8.hits算法结构不稳定，当对扩展网页集合内链接关系作出很小改变，则对最终排名有很大影响；而pagerank算法对hits而言表现稳定，其根本原因在于pagerank计算时的远程跳转6.5SALSA算法SALSA 算法的初衷希望能够结合两者的主要特点，既可以利用HITS算法与查询相关的特点，也可以采纳pagerank的随机游走模型，这是SALSA算法提出的背景。从整体来说，可以将SALSA划分为2个阶段：首先是确定计算对象集合的阶段，这一阶段与hits算法基本相同；第2个阶段是链接关系传播过程，在这一阶段采纳了随机游走模型。6.5.1确定计算对象集合pagerank 的计算对象是互联网所有网页，SALSA算法与此不同，在本阶段，其与hits算法思路大致相同，也是先得到扩展网页集合，之后将网页关系转换为方向二分图形式。1.扩展网页结合2.转换为无向二分图6.5.2链接关系传播在链接关系传播阶段，SALSA算法放弃了 hits 算法的Hub节点和 Authority节点互相增强的假设，转而采纳 pagerank 的随机游走模型。1.链接关系传播概念模型2.Authority 节点关系图3.节点关系图中边的建立4.节点之间的转移概率6.5.3Authority权值计算6.6主题敏感PageRank（TopicSensitivePageRank）主题敏感pagerank 是 pagerank 算法的改进版本。6.6.1主题敏感PageRank与PageRank的差异pagerank 算法基本遵循随机游走模型，即用户在浏览某个网页时，如果希望跳转到其他页面，则随机选择本网页包含的某个链接，进入另外一个页面。主题敏感pagerank则对该概念模型做出改进，引入了更符合现实的假设。一般来说用户会对某些领域感兴趣，同时当浏览某个页面时，这个页面也是与某个主题相关的，所以当用户看完当前页面时，希望跳转时，更倾向于点击和当前页面主题类似的链接。这符合用户真实的浏览过程。pagerank 是全局性的网页重要性衡量标准，每个网页会根据链接情况，被赋予一个唯一的pagerank分值。主题敏感pagerank在此点有所不同，该算法引入了16种主题类型，对于某个网页来说，对应某个主题都有相应的pagerank分值，即每个网页会被赋予16个主题相关的pagerank分值。6.6.2主题敏感PageRank计算流程主题敏感pagerank计算主要由2个步骤组成，第一步是离线分类主题pagerank数值计算；第二步是在线利用算好的主题pagerank分值，来评估网页和用户查询的相似度，以按照相似度排序提供给用户搜索结果。1.分类主题pagerank计算2.在线相似度计算6.6.3利用主题敏感PageRank构造个性化搜索6.7Hilltop 算法Hilltop 算法融合了 hits 和 pagerank 两个算法的基本思想。一方面，Hilltop是与用户查询请求相关的链接分析算法，吸收了hits算法根据用户查询获得最高质量相关网页子集的思想，符合子集的思想，符合子集传播模型，是该模型的一个具体实例；同时，在权值传播过程中，Hilltop 算法也采纳了pagerank 的基本指导思想，即通过页面入链的数量和质量来确定搜索结果的排序权重。6.7.1Hilltop 算法的一些基本定义非从属组织页面是 Hilltop 算法的一个很重要的定义。要了解什么是非从属组织页面，先要搞明白什么是从属组织网站，所谓的从属组织网站，即不同的网站属于同一机构或者拥有密切关联。具体而言，满足如下任一一条判断规则的网站会被认为是从属网站。1.条件1：主机ip地址的前3个子网段相同，比如:ip地址分别为159.226.138.127 和 159.226.138.234 的两个网站会被认为是从属网站2.如果网站域名中的主域名相同，比如 和 会被认为是从属网站非从属网站页面的含义是：如果两个页面不属于从属网站，则为非从属网站。专家页面是 Hilltop 算法的另外一个重要定义。所谓专家页面，即与某个主题相关的高质量页面，同时需要满足以下要求：这些页面的链接所指向的页面互相之间都是非从属组织页面，且这些被指向的页面大多数是与专家页面主题相近的。Hilltop 算法将互联网页面划分为两类子集合，最重要的子集合是由专家页面构成的互联网页面子集，不在这个子集合里的剩下的互联网页面作为另外一个集合，这个集合被称为目标页面集合。6.7.2Hilltop算法6.8其他改进算法6.8.1智能游走模型（IntelligentSurferModel）6.8.2偏置游走模型（BiasedSurferModel）6.8.3PHITS算法（ProbabilityAnalogyofHITS）6.8.4BFS算法（BackwardForwardStep）
