比较PageRank算法和HITS算法的优缺点

题目：请比较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算法都是基于链接分析的搜索引擎排序算法，并且在算法中两者都利用了特征向量作为理论基础和收敛性依据。

虽然两种算法均为链接分析算法，但两者之间还是有明显的区别的。HITS算法计算的authority值只是相对于某个检索主题的权重，因此HITS算法也常被称为Query-dependent算法；而PageRank算法是独立于检索主题，因此也常被称为Query-independent算法。

PageRank算法的优点在于它对互联网上的网页给出了一个全局的重要性排序，并且算法的计算过程是可以离线完成的，这样有利于迅速响应用户的请求。不过，其缺点在于主题无关性，没有区分页面内的导航链接、广告链接和功能链接等，容易对广告页面有过高评价；另外，PageRank算法的另一弊端是，旧的页面等级会比新页面高，因为新页面，即使是非常好的页面，也不会有很多链接，除非他是一个站点的子站点。这就是PageRank需要多项算法结合的原因。

HITS算法的优点在于它能更好地描述互联网的组织特点，由于它只是对互联网中的很小的一个子集进行分析，所以它需要的迭代次数更少，收敛速度更快，减少了时间复杂度。但HITS算法也存在如下缺点：中心网页之间的相互引用以增加其网页评价，当一个网站上的多篇网页指向一个相同的链接，或者一个网页指向另一个网站上的多个文件时会引起评分的不正常增加，这会导致易受“垃圾链接”的影响；网页中存在自动生成的链接；主题漂移，在邻接图中经常包括一些和搜索主题无关的链接，如果这些链接自身也是中心网页或权威网页就会引起主题漂移：对于每个不同的查询算法都需要重新运行一次来获取结果。这使得它不可能用于实时系统，因为对于上千万次的并发查询这样的开销实在太大。

PageRank算法和HITS算法都是客观的描述了网页之间的本质特征，但是它们都很少考虑到用户浏览习惯时的主题相关性。

Hilltop算法：

HillTop，是一项搜索引擎结果排序的专利，是Google的一个工程师Bharat 在2001年获得的专利。HillTop算法的指导思想和PageRank是一致的，即都通过反向链接的数量和质量来确定搜索结果的排序权重。但HillTop认为只计算来自具有相同主题的相关文档链接对于搜索者的价值会更大，即主题相关网页之间的链接对于权重计算的贡献比主题不相关的链接价值要更高。在1999-2000年，当这个算法被Bharat与其他Google开发人员开发出来的时候，他们称这种对主题有影响的文档为“专家”文档，而只有从这些专家文档页面到目标文档的链接决定了被链接网页“权重得分”的主要部分。

Hilltop算法的过程：首先计算查询主题最相关的“专家”资源列表；其次在选中的“专家”集中识别相关的链接，并追踪它们以识别相关的网页目标；然后将目标根据非关联的指向它们的“专家”数量和相关性排序。由此，目标网页的得分反映了关于查询主题的最中立的专家的集体观点。如果这样的专家池不存在，Hilltop不会给出结果。

从Hilltop算法过程可见，该算法包括两个主要的方面：寻找专家；目标排序。通过对搜索引擎抓取的网页进行预处理，找出专家页面。对于一个关键词的查询，首先在专家中查找，并排序返回结果。

权威页面是对于一个查询主题来说最好的专家指向的页面。专家也有可能在更宽泛的领域或其它领域的主题上也是专家。在专家页面中只有一部分链接与主题相关。因此，把查询主题的专家中相关的外向链接合并，以找到查询主题相关页面高度认可的页面。

从排名在前的匹配专家页面和相联系的匹配信息中选择专家页面中一个超链接的子集。尤其选择那些与所有的查询相关的链接。基于这些选中的链接找出一个它们的目标子集作为查询主题最相关的网页。这个目标子集包含至少被两个非亲属的专家页面链接到的网页。目标集根据指向它们的专家的综合成绩来排序。

Hilltop在应用中还存在一些不足。专家页面的搜索和确定对算法起关键作用，专家页面的质量决定了算法的准确性；而专家页面的质量和公平性在一定程度上难以保证。Hiltop忽略了大多数非专家页面的影响。在Hiltop的原型系统中，专家页面只占到整个页面的1.79%，不能全面代表整个互联网。Hiltop算法在无法得到足够的专家页面子集时（少于两个专家页面），返回为空，即Hiltop适合于对查询排序进行求精，而不能覆盖。这意味着Hilltop可以与某个页面排序算法结合，提高精度，而不适合作为一个独立的页面排序算法。Hilltop中根据查询主题从专家页面集合中选取与主题相关的子集也是在线运行的，这与前面提到的HITS算法一样会影响查询响应时间。随着专家页面集合的增大，算法的可伸缩性存在不足之处。

Direct Hit 算法

与前面的算法相比，Ask Jeeves公司的Direct Hit算法是一种注重信息的质量和用户反馈的排序方法。它的基本思想是，搜索引擎将查询的结果返回给用户，

并跟踪用户在检索结果中的点击。如果返回结果中排名靠前的网页被用户点击后，浏览时间较短，用户又重新返回点击其它的检索结果，那么可以认为其相关度较差，系统将降低该网页的相关性。另一方面，如果网页被用户点击打开进行浏览，并且浏览的时间较长，那么该网页的受欢迎程度就高，相应地，系统将增加该网页的相关度。可以看出，在这种方法中，相关度在不停地变化，对于同一个词在不同的时间进行检索，得到结果集合的排序也有可能不同，它是一种动态排序。

该算法的优点是能够节省大量时间，因为用户阅读的是从搜索结果中筛选出来的更加符合要求的结果。同时，这种算法直接融入用户的反馈信息，能够保证页面的质量。然而，统计表明，Direct Hit算法只适合于检索关键词较少的情况，因为它实际上并没有进行排序，而是一种筛选和抽取，在检索数据库很大、关键词很多的时候，返回的搜索结果成千上万，用户不可能一一审阅。因此，这种方式也不能作为主要的排序算法来使用，而是一种很好的辅助排序算法，目前在许多搜索引擎当中仍然在使用。

参考文献

1. S. Brin, L. Page. Anatomy of a Large - Scale HypertextualWeb Search Engine. Proc. 7th International World Wide Web Conference, 1998

2. Jon M. Kleinberg. Authoritative Sources in a Hyperlinked Environment. Journal of the ACM, 1999; 46(5)

3. Krishna Bharat. Hilltop: A Search Engine based on Expert Documents. Department of Computer Science University of Toronto 2004

4. Gary Culliss. Method for organizing information. United States Patent. Patent number:6014665

比较PageRank算法和HITS算法的优缺点

题目：请比较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算法设计

算法设计： 假设一个有集合：A，B，C和D 是由4个网页组成的。在同一个页面之中，多个指向相同的链接，把它们看作是同一个链接，并且每个页面初始的PageRank值相同。因为要满足概率值位于0到1之间的需求，我们假设这个值是0.25。 在每一次的迭代中，给定页面的PR值（PageRank值）会被平均分配到此页面所链接到的页面上。 倘若全部页面仅链接到A，这样的话A的PR值就是B，C和D的PR值之和，即：PR（A）=PR（B）+PR（C）+PR（D）{\displaystyle PR(A)=PR(B)+PR(C)+PR(D)} 再次假设C链接到了A，B链接到了A和C，D链接到了A,B,C。最开始的时候一个页面仅仅只会有一票。正因为这样，所以的话B将会给A ,C这两个页面每一个页面半票。按照这样来类比推算，D所投出去的票将只会有三分之一的票会被添加到属于A 的PR值上： {\displaystyle PR(A)={\frac {PR(B)}{2}}+{\frac {PR(C)}{1}}+{\frac {PR(D)}{3}}} 换个方式表达的话，算法将会依据每一个页面链接出来的总数 {\displaystyle L(x)}平均的分配每一个页面的PR值，然后把它添加至它指向的页面：

最后，这些全部的PR值将会被变换计算成为百分比的形式然后会再乘上一个修正系数。因为“没有向外链接的网页”它传递出去的PR值将会是0，而且这将递归地差生影响从而使得指向它的页面的PR值的计算出来得到的结果同样是零，因此每一个页面要有预先设置好了的一个最小值： 需要注意的是，在Sergey Brin和Lawrence Page的1998年原版论文中给每一个页面设定的最小值是1-d，而不是这里的（1-d)/N，这将导致集合中所有网页的PR值之和为N（N为集合中网页的数目）而并不是所期待的1。 所以，一个页面的PR值直接取决于指向它的的页面。如果在最初给每个网页一个随机且非零的PR值，经过重复计算，这些页面的PR值将会逐渐接近于某一个固定 定值，也就是处于收敛的状态，即最终结果。这就是搜索引擎使用该算法的原因。【测试环境】 【测试数据】

Pagerank算法与网页排序方法的建模

Pagerank 算法与网页排序方法的建模 摘要 随着互联网的飞速发展,各种杂乱无章的信息充斥其中，如何对数以亿记的相关网页进行排序成为搜索引擎的核心问题。针对这个现象本文根据题目要求建立了两个模型： 模型一：结合Google 的Pagerank 算法，建立了网上冲浪模型，得到Pagerank 算法定义： n i i 1 i P R(T )P R(A )(1d )d C (T ) ==-+∑ 用迭代算法通过MATLAB 编程计算出网页的PR 值； 模型二：由于传统PR 值算法仅考虑网页的外链和内链数量，偏重于旧网页；另外，传统算法不能区分网页中的链接与网页的主题是否相关，容易产生主题漂移现象；考虑其算法存在的缺陷，在此基础上为给出对搜索网页进行排序的方法，着重考虑搜索出的网页以下几个方面：外链，内链，时间反馈因子和相关度，对PR 值进行改进，得到以下公式： Wt V VT sim VT V sim T PR d d p PR k i m j j i i P i +?+-=∑ ∑==1 1 , ,) () ()()1()( 以PR 值的高低来对搜索网页进行排序； 对于如何使新网站在搜索引擎中排名靠前，从影响网页的PR 值的因素：內链、外链、时间反馈因子和相关度出发对提高网页的PR 值以使其在搜索引擎中排名靠前给出了稳健的建议。 关键词 Pagerank 迭代算法 MATLAB 时间反馈因子 相关度 一、问题重述 随着互联网的发展，面对众多杂乱无章的信息，如何对数以亿计的相关网页进行排序成为搜索引擎算法的核心问题。一个搜索引擎的算法，要考虑很多的方面。主要是“域

名、密度、内链、外链、相关度、服务器稳定、内容更新、域名时间、内容数量”这些方面。不同的搜索引擎侧重点也不同，比如Google，它对收录的网站有一个重要性排名的指数，被称为Pagerank，作为对搜索网页排序的重要参数。 根据搜索引擎与Pagerank，考虑如下问题： 1.考察Google的Pagerank算法，建立数学模型，给出合理的Pagerank的计算方法； 2.如果你是搜索引擎的建设者，请考虑你会侧重考虑搜索网页的那些方面，给出你对搜索网页进行排序的方法； 3.如果你是某新网站的建设者，请考虑使你的网站在第2题中你建立的搜索引擎中排名靠前的方法。 二、问题分析 互联网的迅速发展，使现有的搜索引擎面临着巨大的挑战，面对众多杂乱无章的信息，如何对数以亿计的相关网页进行排序成为搜索引擎算法的核心问题，因此，搜索引擎排序算法也就称为众多搜索引擎关注的关键问题之一。 对于问题1，根据题目要求，结合Google的Pagerank算法，PageRank算法的基本思想是：页面的重要程度用PageRank值来衡量，PageRank值主要体现在两个方面：引用该页面的页面个数和引用该页面的页面重要程度。若B网页设置有连接A网页的链接(B为A的导入链接时)，说明B认为A有链接价值，是一个“重要”的网页。当B网页级别(重要性)比较高时，则A网页可从B网页这个导入链接分得一定的级别(重要性)，并平均分配给A网页上的导出链接，由此建立了网上冲浪模型，用迭代算法计算出网页的PR值。 对于问题2，经过对Google的Pagerank算法的分析，发现该算法仅考虑了搜索出的网页的外链和内链的数量，以此来确定网页的PR值偏重于旧网页，即越旧的网页排名越靠前；对一个刚放到网上不久的新网页，指向它的网页就很少，通过计算后的PR 值就很低，在搜索结果中也就被排在了靠后的位置。然而在有些时候，比如新闻类网页和商务性信息，用户当然是希望先看到新的网页，因此我们在计算PR值时考虑加入时间反馈因子，使得在网络上存在时间比较长的网页被沉下去，在搜索结果中被排在靠后的位置；存在时间短的网页就会浮上来，在搜索结果中被排在较靠前的位置，方便用户查看。时间反馈因子利用搜索引擎的搜索周期来表征，即如果一个网页存在时间较长，它将在每个搜索周期中都能被搜到，对网页采取在同一个周期里不管搜到该网页几次，都算一次处理的方法，网页的存在时间正比于搜索引擎搜到该网页的次数，时间反馈因子与网页的存在时间成反比关系。 另外，Google的Pagerank算法是基于网页链接结构进行分析的算法，不能区分网页中的链接与网页的主题是否相关，这样就容易出现搜索引擎排序结果中大量与查询主题无关的网页的现象，即产生主题漂移现象。为解决这个问题，引入主题相关度这个概念。主题相关度就是搜索出的网页与其链入和链出网页的相似度，可用余弦相似度来度量计算。 在加入了时间反馈因子和相关性因素后，改进网页的PR值的算法，以PR值高低的来对搜索的网页进行排序。 对于问题三，主要通过模型二的结果，加强有力的因素，避免不利的方面 三、模型假设与符号说明

pagerank算法实验报告

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。 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。谁的输出链接多，谁分配的就少一些；反之，谁的输出链接少，谁分配的就多一些。这是一个非常形象直观的定义。