page page rank算法

《page page rank算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、PageRank算法摘要：本文较为详细地介绍怎样计算pagerank值的，主要通过入链网页的数量和质量综合计算出该网页的PR值，不过PR值是需要更新的，而且稳定的PR值才是最后的PR值。单纯地计算的PR值参考价值不是特别大，只有结合了概率矩阵和阻尼系数计算出来的PR值才有参考价值。关键词：入链数量；入链质量；阻尼系数；概率矩阵引言：pagerank算法是Google创始人拉里·佩奇和谢尔盖·布林于1997年构建早期的搜索系统原型时提出的链接分析算法。目前很多重要的链接分析算法都是在PageRank算法基础上衍生出来的。PageRank是Google用于用来标

2、识网页的重要性的一种方法，是Google用来衡量一个网站的好坏的唯一标准。在揉合了诸如Title标识和Keywords标识等所有其它因素之后，Google通过PageRank来调整结果，使那些更重要的网页的排名更靠前，方便人们的搜索。其级别从0到10级，10级为满分。PR值越高说明该网页越受欢迎（越重要）。例如：一个PR值为1的网站表明这个网站不太具有流行度，而PR值为7到10则表明这个网站非常受欢迎。2.从入链数量到PageRank在PageRank提出之前，已经有研究者提出利用网页的入链数量来进行链接分析计算，这种入链方法假设一个网页的入链越多，则该网页

3、越重要。早期的很多搜索引擎也采纳了入链数量作为链接分析方法，对于搜索引擎效果提升也有较明显的效果。PageRank除了考虑到入链数量的影响，还参考了网页质量因素，两者相结合获得了更好的网页重要性评价标准。对于某个互联网网页A来说，该网页PageRank的计算基于以下两个基本假设：l数量假设：在Web图模型中，如果一个页面节点接收到的其他网页指向的入链数量越多，那么这个页面越重要。l质量假设：指向页面A的入链质量不同，质量高的页面会通过链接向其他页面传递更多的权重。所以越是质量高的页面指向页面A，则页面A越重要。利用以上两个假设，PageRank算法刚开始赋予

4、每个网页相同的重要性得分，通过迭代递归计算来更新每个页面节点的PageRank得分，直到得分稳定为止。PageRank计算得出的结果是网页的重要性评价，这和用户输入的查询是没有任何关系的，即算法是主题无关的。假设有一个搜索引擎，其相似度计算函数不考虑内容相似因素，完全采用PageRank来进行排序，那么这个搜索引擎的表现是什么样子的呢？这个搜索引擎对于任意不同的查询请求，返回的结果都是相同的，即返回PageRank值最高的页面。3.PageRank算法原理PageRank的计算充分利用了两个假设：数量假设和质量假设。步骤如下：1）在初始阶段：网页通过链接关系

5、构建起Web图，每个页面设置相同的PageRank值，通过若干轮的计算，会得到每个页面所获得的最终PageRank值。随着每一轮的计算进行，网页当前的PageRank值会不断得到更新。2）在一轮中更新页面PageRank得分的计算方法：在一轮更新页面PageRank得分的计算中，每个页面将其当前的PageRank值平均分配到本页面包含的出链上，这样每个链接即获得了相应的权值。而每个页面将所有指向本页面的入链所传入的权值求和，即可得到新的PageRank得分。当每个页面都获得了更新后的PageRank值，就完成了一轮PageRank计算。3.2基本思想：如果网

6、页T存在一个指向网页A的连接，则表明T的所有者认为A比较重要，从而把T的一部分重要性得分赋予A。这个重要性得分值为：PR（T）/L(T)　其中PR（T）为T的PageRank值，L(T)为T的出链数则A的PageRank值为一系列类似于T的页面重要性得分值的累加。即一个页面的得票数由所有链向它的页面的重要性来决定，到一个页面的超链接相当于对该页投一票。一个页面的PageRank是由所有链向它的页面（链入页面）的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级，相反如果一个页面没有任何链入页面，那么它没有等级。3.3PageRank简单计算：假设一

7、个由只有4个页面组成的集合：A，B，C和D。如果所有页面都链向A，那么A的PR（PageRank）值将是B，C及D的和。继续假设B也有链接到C，并且D也有链接到包括A的3个页面。一个页面不能投票2次。所以B给每个页面半票。以同样的逻辑，D投出的票只有三分之一算到了A的PageRank上。换句话说，根据链出总数平分一个页面的PR值。例子：如图1所示的例子来说明PageRank的具体计算过程。3.4修正PageRank计算公式：由于存在一些出链为0，也就是那些不链接任何其他网页的网，也称为孤立网页，使得很多网页能被访问到。因此需要对PageRank公式进行修正，

8、即在简单公式的基础上增加了阻尼系数（dampingf