题目：请比较PageRank算法和HITS算法的优缺点，除此之外，请再介绍2种用于搜索引擎检索结果的排序算法，并举例说明。 答： 1998年，Sergey Brin和Lawrence Page[1]提出了PageRank算法。该算法基于“从许多优质的网页链接过来的网页，必定还是优质网页”的回归关系，来判定网页的重要性。该算法认为从网页A导向网页B的链接可以看作是页面A对页面B的支持投票，根据这个投票数来判断页面的重要性。当然，不仅仅只看投票数，还要对投票的页面进行重要性分析，越是重要的页面所投票的评价也就越高。根据这样的分析，得到了高评价的重要页面会被给予较高的PageRank值，在检索结果内的名次也会提高。PageRank是基于对“使用复杂的算法而得到的链接构造”的分析，从而得出的各网页本身的特性。 HITS 算法是由康奈尔大学( Cornell University ) 的JonKleinberg 博士于1998 年首先提出。Kleinberg认为既然搜索是开始于用户的检索提问，那么每个页面的重要性也就依赖于用户的检索提问。他将用户检索提问分为如下三种：特指主题检索提问（specific queries，也称窄主题检索提问）、泛指主题检索提问（Broad-topic queries，也称宽主题检索提问）和相似网页检索提问（Similar-page queries）。HITS 算法专注于改善泛指主题检索的结果。 Kleinberg将网页（或网站）分为两类，即hubs和authorities，而且每个页面也有两个级别，即hubs（中心级别）和authorities（权威级别）。Authorities 是具有较高价值的网页，依赖于指向它的页面；hubs为指向较多authorities的网页，依赖于它指向的页面。HITS算法的目标就是通过迭代计算得到针对某个检索提问的排名最高的authority的网页。 通常HITS算法是作用在一定范围的，例如一个以程序开发为主题的网页，指向另一个以程序开发为主题的网页，则另一个网页的重要性就可能比较高，但是指向另一个购物类的网页则不一定。在限定范围之后根据网页的出度和入度建立一个矩阵，通过矩阵的迭代运算和定义收敛的阈值不断对两个向量authority 和hub值进行更新直至收敛。 从上面的分析可见，PageRank算法和HITS算法都是基于链接分析的搜索引擎排序算法，并且在算法中两者都利用了特征向量作为理论基础和收敛性依据。
PageRank算法实验报告 一、算法介绍 PageRank是Google专有的算法，用于衡量特定网页相对于搜索引擎索引中的其他网页而言的重要程度。它由Larry Page 和Sergey Brin在20世纪90年代后期发明。PageRank实现了将链接价值概念作为排名因素。 PageRank的核心思想有2点： 1.如果一个网页被很多其他网页链接到的话说明这个网页比较重要，也就是pagerank值会相对较高； 2.如果一个pagerank值很高的网页链接到一个其他的网页，那么被链接到的网页的pagerank值会相应地因此而提高。 若页面表示有向图的顶点，有向边表示链接，w(i,j)=1表示页面i存在指向页面j的超链接，否则w(i,j)=0。如果页面A存在指向其他页面的超链接，就将A 的PageRank的份额平均地分给其所指向的所有页面，一次类推。虽然PageRank 会一直传递，但总的来说PageRank的计算是收敛的。 实际应用中可以采用幂法来计算PageRank，假如总共有m个页面，计算如公式所示： r=A*x 其中A=d*P+（1-d)*(e*e'/m) r表示当前迭代后的PageRank，它是一个m行的列向量,x是所有页面的PageRank初始值。 P由有向图的邻接矩阵变化而来，P'为邻接矩阵的每个元素除以每行元素之和得到。 e是m行的元素都为1的列向量。 二、算法代码实现
三、心得体会 在完成算法的过程中，我有以下几点体会： 1、在动手实现的过程中，先将算法的思想和思路理解清楚，对于后续动手实现 有很大帮助。 2、在实现之前，对于每步要做什么要有概念，然后对于不会实现的部分代码先 查找相应的用法，在进行整体编写。 3、在实现算法后，在寻找数据验证算法的过程中比较困难。作为初学者，对于 数据量大的数据的处理存在难度，但数据量的数据很难寻找，所以难以进行实例分析。
如何理解网页和网页之间的关系，特别是怎么从这些关系中提取网页中除文字以外的其他特性。这部分的一些核心算法曾是提高搜索引擎质量的重要推进力量。另外，我们这周要分享的算法也适用于其他能够把信息用结点与结点关系来表达的信息网络。 今天，我们先看一看用图来表达网页与网页之间的关系，并且计算网页重要性的经典算法：PageRank。 PageRank 的简要历史 时至今日，谢尔盖·布林（Sergey Brin）和拉里·佩奇（Larry Page）作为Google 这一雄厚科技帝国的创始人，已经耳熟能详。但在1995 年，他们两人还都是在斯坦福大学计算机系苦读的博士生。那个年代，互联网方兴未艾。雅虎作为信息时代的第一代巨人诞生了，布林和佩奇都希望能够创立属于自己的搜索引擎。1998 年夏天，两个人都暂时离开斯坦福大学的博士生项目，转而全职投入到Google 的研发工作中。他们把整个项目的一个总结发表在了1998 年的万维网国际会议上（WWW7，the seventh international conference on World Wide Web）（见参考文献[1]）。这是PageRank 算法的第一次完整表述。 PageRank 一经提出就在学术界引起了很大反响，各类变形以及对PageRank 的各种解释和分析层出不穷。在这之后很长的一段时间里，PageRank 几乎成了网页链接分析的代名词。给你推荐一篇参考文献[2]，作为进一步深入了解的阅读资料。
PageRank 的基本原理 我在这里先介绍一下PageRank 的最基本形式，这也是布林和佩奇最早发表PageRank 时的思路。 首先，我们来看一下每一个网页的周边结构。每一个网页都有一个“输出链接”（Outlink）的集合。这里，输出链接指的是从当前网页出发所指向的其他页面。比如，从页面A 有一个链接到页面B。那么B 就是A 的输出链接。根据这个定义，可以同样定义“输入链接”（Inlink），指的就是指向当前页面的其他页面。比如，页面C 指向页面A，那么C 就是A 的输入链接。 有了输入链接和输出链接的概念后，下面我们来定义一个页面的PageRank。我们假定每一个页面都有一个值，叫作PageRank，来衡量这个页面的重要程度。这个值是这么定义的，当前页面I 的PageRank 值，是I 的所有输入链接PageRank 值的加权和。 那么，权重是多少呢？对于I 的某一个输入链接J，假设其有N 个输出链接，那么这个权重就是N 分之一。也就是说，J 把自己的PageRank 的N 分之一分给I。从这个意义上来看，I 的PageRank，就是其所有输入链接把他们自身的PageRank 按照他们各自输出链接的比例分配给I。谁的输出链接多，谁分配的就少一些；反之，谁的输出链接少，谁分配的就多一些。这是一个非常形象直观的定义。