PageRank算法的分析及其改进_王德广

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