基于超链接分析的排序算法

基于超链接分析的排序算法洪赛2015.1.42023/10/61WME小组:洪赛小组:洪赛搜索引擎排序算法概述超链接分析排序算法概述PageRank算法PageRank算法概述从入链数量到PageRankPageRank算法原理PageRank幂法计算PageRank优缺点CONTENTHITS算法Hub页面与Authority页面算法基本思想：相互增强关系HITS算法HITS算法存在的问题HITS算法与PageRank算法比较2023/10/62WME小组:洪赛小组:洪赛搜索引擎排序算法，主要经历了三个阶段的发展历程：第一阶段，主要考虑关键词因素，统计关键词在文档中出现的频率和关键词在文档中出现的位置信息。词频位置加权算法应用广泛，发展也相对比较成熟，目前这种算法仍然是许多搜索引擎的核心排序算法。这类算法的代表为TF-IDF。第二阶段，考虑网页权重因素，网页本身的级别越高，在检索结果排序中越靠前。利用超链接分析，有效地计算网页的相关度与重要度，代表的算法有PageRank，HITS等。第三阶段，有效利用用户日志数据与统计学习方法，使网页相关度与重要度计算的精度有了进一步的提升，代表的方法包括排序学习、网页重要度学习、匹配学习、话题模型学习、查询语句转化学习。搜索引擎排序算法概述2023/10/63WME小组:洪赛小组:洪赛超链接分析排序算法的思想起源于文献引文索引机制：一篇文章若被其他文章引用的次数越多或者被权威的论文引用，则该文章被认为很有价值。超链接分析的思想与上述思想极为相似，一个网页被其他网页引用的次数越多，或者被某一权威的网页所引用，该网页就显得越重要。超链接分析排序算法概述2023/10/64WME小组:洪赛小组:洪赛大部分链接分析算法建立在两个概念模型上：随机漫游模型：针对浏览网页用户行为建立的抽象概念模型，用户上网过程中会不断打开链接，在相互有链接指向的网页之间跳转，这是直接跳转，如果某个页面包含的所有链接用户都不感兴趣则可能会在浏览器中输入另外的网址，这是远程跳转。该模型就是对一个直接跳转和远程跳转两种用户浏览行为进行抽象的概念模型；典型的使用该模型的算法是PageRank；子集传播模型：基本思想是把互联网网页按照一定规则划分，分为两个甚至是多个子集合。其中某个子集合具有特殊性质，很多算法从这个具有特殊性质的子集合出发，给予子集合内网页初始权值，之后根据这个特殊子集合内网页和其他网页的链接关系，按照一定方式将权值传递到其他网页。典型的使用该模型的算法有HITS和Hilltop算法。2023/10/65WME小组:洪赛小组:洪赛链接算法很多，从其概念模型来说，基本遵循上述介绍的随机游走模型和子集传播模型。而从图中可看出，在众多算法中，PageRank和HITS算法可以说是最重要的两个具有代表性的链接分析算法，后续的很多链接分析算法都是在这两个算法基础上衍生出来的改进算法。链接分析算法之间的关系2023/10/66WME小组:洪赛小组:洪赛PageRank，即网页排名，又称网页级别、Google左侧排名或佩奇排名。Google创始人拉里·佩奇和谢尔盖·布林于1997年构建早期搜索系统原型时提出的链接分析算法。目前很多重要的链接分析算法都是在PageRank算法基础上衍生出来的。PageRank是Google用于用来标识网页的等级/重要性的一种方法。PageRank算法概述2023/10/67WME小组:洪赛小组:洪赛PageRank的级别从0到10级，10级为满分。PR值越高说明该网页越受欢迎（越重要）。PR值为7到10则表明这个网站非常受欢迎（或者说极其重要）。一般PR值达到4，就算是一个不错的网站了。Google把自己的网站的PR值定到10。2023/10/68WME小组:洪赛小组:洪赛早期的很多搜索引擎也采纳了入链数量作为链接分析方法，对于搜索引擎效果提升也有较明显的效果。PageRank除了考虑到入链数量的影响，还参考了网页质量因素，两者相结合获得了更好的网页重要性评价标准。从入链数量到PageRank2023/10/69WME小组:洪赛小组:洪赛对于某个互联网网页A来说，该网页PageRank的计算基于以下两个基本假设：

数量假设：在Web图模型中，如果一个页面节点接收到的其他网页指向的入链数量越多，那么这个页面越重要。质量假设：指向页面A的入链质量不同，质量高的页面会通过链接向其他页面传递更多的权重。所以越是质量高的页面指向页面A，则页面A越重要。从入链数量到PageRank2023/10/610WME小组:洪赛小组:洪赛PageRank的计算充分利用了数量假设和质量假设。步骤如下：1）在初始阶段：网页通过链接关系构建起Web图，每个页面设置相同的PageRank值，通过若干轮的计算，会得到每个页面所获得的最终PageRank值。随着每一轮的计算进行，网页当前的PageRank值会不断得到更新。2）在一轮中更新页面PageRank得分的计算方法：在一轮更新页面PageRank得分的计算中，每个页面将其当前的PageRank值平均分配到本页面包含的出链上，这样每个链接即获得了相应的权值。而每个页面将所有指向本页面的入链所传入的权值求和，即可得到新的PageRank得分。当每个页面都获得了更新后的PageRank值，就完成了一轮PageRank计算。PageRank算法原理2023/10/611WME小组:洪赛小组:洪赛基本思想：如果网页T存在一个指向网页A的连接，则表明T的所有者认为A比较重要，从而把T的一部分重要性得分赋予A。这个重要性得分值为：PR（T）/L(T)其中PR（T）为T的PageRank值，L(T)为T的出链数;则A的PageRank值为一系列类似于T的页面重要性得分值的累加。即一个页面的得票数由所有链向它的页面的重要性来决定，到一个页面的超链接相当于对该页投一票。一个页面的PageRank是由所有链向它的页面（链入页面）的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级，相反如果一个页面没有任何链入页面，那么它没有等级。PageRank算法原理2023/10/612WME小组:洪赛小组:洪赛

PageRank算法原理2023/10/613WME小组:洪赛小组:洪赛例子：如图所示的例子来说明PageRank的具体计算过程。

PageRank算法原理2023/10/614WME小组:洪赛小组:洪赛修正PageRank计算公式:由于存在一些出链为0，也就是那些不链接任何其他网页的网，也称为孤立网页，使得很多网页能被访问到。对PageRank公式进行修正，即在简单公式的基础上增加了阻尼系数（dampingfactor）q，q一般取值q=0.85。其意义是，在任意时刻，用户到达某页面后并继续向后浏览的概率。1-q=0.15就是用户停止点击，随机跳到新URL的概率的。

PageRank算法原理2023/10/615WME小组:洪赛小组:洪赛ArvindArasu在《JunghooChoHectorGarcia-Molina,AndreasPaepcke,SriramRaghavan.SearchingtheWeb》更加准确的表达为：p_1,p_2,...,p_N是被研究的页面，L(p_j)是p_j链出页面的数量，而N是所有页面的数量。PageRank算法原理2023/10/616WME小组:洪赛小组:洪赛一个页面的PageRank是由其他页面的PageRank计算得到。Google不断的重复计算每个页面的PageRank。如果给每个页面一个随机PageRank值（非0），那么经过不断的重复计算，这些页面的PR值会趋向于正常和稳定。要得到一个页面的PageRank，得先知道另一些页面的PageRank。因此需要设置合理的PageRank初始值。不过，如果有办法得到合理的PageRank初始值，还需要这个算法吗？那么有没有不依赖于初始值的PageRank算法？也就是说，如果存在一种计算方法，使得无论怎样设置初始值，最后都会收敛到同一个值就行了。要做到这样，就要换一个角度看问题，从线性代数的角度看问题。PageRank算法原理2023/10/617WME小组:洪赛小组:洪赛

PageRank幂法计算2023/10/618WME小组:洪赛小组:洪赛

PageRank幂法计算2023/10/619WME小组:洪赛小组:洪赛PageRank值是一个P’T中的特征向量。这个特征向量为：

R是如下等式的一个解：如果网页i有指向网页j的一个链接，则否则PageRank幂法计算2023/10/620WME小组:洪赛小组:洪赛

PageRank幂法计算幂法计算过程如下：

X设任意一个初始向量,

即设置初始每个网页的

PageRank值均。一般为1.R=AX;while

(1){ if

(l

X-

RI

<

Ɛ){//如果最后两次的结果近似或者相同，返回R returnR;

}

else

{ X=R; R=AX;}}2023/10/621WME小组:洪赛小组:洪赛用幂法计算PageRank值总是收敛的，即计算的次数是有限的。不论初始值如何选取，这种算法都保证了网页排名的估计值能收敛到他们的真实值。PageRank幂法计算2023/10/622WME小组:洪赛小组:洪赛优点：是一个与查询无关的静态算法，所有网页的PageRank值通过离线计算获得；有效减少在线查询时的计算量，极大降低了查询响应时间。缺点：1）人们的查询具有主题特征，PageRank忽略了主题相关性，导致结果的相关性和主题性降低2）旧的页面等级会比新页面高。因为即使是非常好的新页面也不会有很多上游链接，除非它是某个站点的子站点。PageRank需要多项算法结合应用PageRank优缺点2023/10/623WME小组:洪赛小组:洪赛HITS(Hyperlink-InducedTopicSearch)算法是由康奈尔大学(CornellUniversity)的JonKleinberg博士于1997年首先提出的,为IBM公司阿尔马登研究中心(IBMAlmadenResearchCenter)的名为“CLEVER”的研究项目中的一部分。HITS算法是链接分析中非常基础且重要的算法，目前已被Teoma搜索引擎（）作为链接分析算法在实际中使用。HITS算法2023/10/624WME小组:洪赛小组:洪赛Hub页面（枢纽页面）和Authority页面（权威页面）是HITS算法最基本的两个定义。所谓“Authority”页面，是指与某个领域或者某个话题相关的高质量网页，比如搜索引擎领域，Google和百度首页即该领域的高质量网页，比如视频领域，优酷和土豆首页即该领域的高质量网页。所谓“Hub”页面，指的是包含了很多指向高质量“Authority”页面链接的网页，比如hao123首页可以认为是一个典型的高质量“Hub”网页。

HITS算法的目的即是通过一定的技术手段，在海量网页中找到与用户查询主题相关的高质量“Authority”页面和“Hub”页面，尤其是“Authority”页面，因为这些页面代表了能够满足用户查询的高质量内容，搜索引擎以此作为搜索结果返回给用户。Hub页面与Authority页面2023/10/625WME小组:洪赛小组:洪赛基本假设1：一个好的Authority页面会被很多好的Hub页面指向；基本假设2：一个好的Hub页面会指向很多好的Authority页面；具体算法：利用这两个基本假设，以及相互增强关系等原则进行多轮迭代计算，每轮迭代计