pagerank的理解和java实现

1. PageRank的发展

 1.1 Pagerank是如何牛逼起来的？

   首先简单介绍一下pagerank的发展背景。百度百科对pagerank的解释：PageRank是Google专有的算法，用于衡量特定网页相对于搜索引擎索引中的其他网页而言的重要程度。它由Larry Page 和 Sergey Brin在20世纪90年代后期发明。PageRank实现了将链接价值概念作为排名因素。

   PageRank其实不是Google用来衡量一个网站好坏的唯一标准，出名的原因是因为google在成立初期用来排名搜索结果的算法。google使用googlebot（google的web 抓取漫游器。它从web上收集文档，为Google搜索引擎建立可搜索的索引）发现新网页和更新的网页并将这些网页添加到 Google 索引中的过程。

   PageRank结合了很多其他其他因素，比如Title标识和Keywords标识等，之后通过PageRank来调整结果，使那些更具“等级/重要性”的网页在搜索结果中另网站排名获得提升，从而提高搜索结果的相关性和质量。它定义的级别是从0到10级，10级为满分。PR值越高说明该网页越受欢迎。

 1.2 如何查询Pagerank的值？

   如何查询各个网页的PageRank的值是多少呢？其实chrome浏览器有提供一个插件，供用户使用来查询不同页面的PR值。可以在工具-->扩展程序-->更多扩展程序-->PageRank Status 下载安装之后启用，在浏览不同网页的时候就可以看到PR值了。 截图是baidu的PR值为9。但是请注意，这里所指示的PageRank是个缓冲值，通常是过时的。因为PageRank值每年只发布几次，有时就得使用过时的信息，因此，PageRank并不是一个非常精确的度量。

 

2. PageRank的核心

   PageRank算法不仅考虑了网页的入链数量，同时考虑了网页质量，结合两者的分析获得更准确的网页重要性。

    对于互联网中某个网页A来说，该网页PageRank的计算基于以下两个基本假设（模拟整个互联网是一个有向带权图，每个网页都是一个节点，引用的链接是节点之间的关系）： 

     数量假设：如果一个页面节点接收到的其他网页指向的入链数量越多，那么这个页面越重要。
     质量假设：指向页面A的入链质量不同，质量高的页面会通过链接向其他页面传递更多的权重。所以越是质量高的页面指向页面A，则页面A越重要。
       通过以上两个假设，PageRank算法刚开始赋予每个网页相同的重要性得分，通过迭代递归计算来更新每个页面节点的PageRank得分，直到得分稳定为止。 PageRank计算得出的结果是网页的重要性，这和用户输入的查询是没有任何关系的，即算法是主题无关的。假设有一个搜索引擎，其相似度／匹配计算函数不考虑，完全采用PageRank来进行排序，那么这个搜索引擎的表现是什么样子的呢？这个搜索引擎对于任意不同的查询请求，返回的结果都是相同的，即返回PageRank值最高的页面。

基本思想

   其实pagerank的基本思想不难理解，就是用概率分布的形式来表示一个人随机点击链接到达任何页面的概率。最开始的时候为每个页面初始化一个相同的pagerank的值，经过若干轮迭代计算，结果回收敛于一个值，并趋于稳定。在每一次迭代过程中，每个页面将自己的权值平均分配到自己的出链中去，这样赋予了每个链接相应的权值，每个页面对所有指向自己的链接求和就是这轮迭代中该页面的pagerank的值。

   下面是wiki百科中给的简单的例子说明一下：

    假设一个由只有4个页面组成的集合：A，B，C和D。如果页面B，C，D都链向A，页面A的PR（PageRank）值是B，C及D的和：

          
   即初始化每个页面的PR是0.25，经过第一轮迭代，页面B，C，D的PR值为0，页面A的PR值为0.75。

    继续假设，B也有链接到C，D有链接到A，B，C的 3个页面，那么换句话说B有两个出链，A得到一半的权值，D有三个出链，A得到三分之一的权值，如下：
         

     所以得到

        
      一半情况下，就有如下的公式：

                  Bu是指向页面u的全部页面

 

 修正版的PageRank

       由于存在一些出链为0，也就是那些不链接任何其他网页的n网页， 使得很多网页能被访问到。因此需要对 PageRank公式进行修正，即在简单公式的基础上增加了阻尼系数（damping factor）q， q一般取值q=0.85。

      其意义是，在任意时刻，用户到达某页面后并继续向后浏览的概率。 1- q= 0.15就是用户停止点击，随机跳到新URL的概率）的算法被用到了所有页面上，估算页面可能被上网者放入书签的概率。

      最后，即所有这些被换算为一个百分比再乘上一个系数q。由于下面的算法，没有页面的PageRank会是0。所以，Google通过数学系统给了每个页面一个最小值。                                                                                                

 PageRank完整公式

            

       是被研究的页面，是链入页面的数量，是链出页面的数量，而N是所有页面的数量。

       PageRank值是一个特殊矩阵中的特征向量。这个特征向量为：

        

      R是如下等式的一个解：

       

      如果网页i有指向网页j的一个链接，则

       

      否则＝0。

      http://blog.csdn.net/hguisu/article/details/7996185

      有使用幂法求PageRank的值，写的不错，但是矩阵相乘时有错误，但不影响整体的思路。

      下面是java实现的pagerank算法。

 

      本文有参照wiki对pagerank的详细说明和  http://blog.csdn.net/hguisu/article/details/7996185部分翻译解释。