PageRank算法教程及Python实现

PageRank算法是Google公司用于标识网页影响力的方法，即是一种判断网页好坏的算法。每个网页都具有自己的重要性，PageRank给每个链入网页赋予不同权值，每个网页的重要性由其链入网页的权值和重要性计算得到。网页初始重要性由Title、Keywords等因素决定，再通过PageRank调整结果，在使用Google进行网页搜索时，具有高重要性/影响力的网页将会在搜索结果中排名较高，提高了搜索结果的相关性和质量。

若某个网页链入网页数量越多，则该网页影响力越大。PageRank相比于前人的研究，还参考了网页本身的内容，二者结合得到了算法中的评价标准。
PageRank算法有两个基本假设：
数量假设：若网页的链入网页越多，则这个页面越重要。
质量假设：链入网页质量有区别，链入网页的质量越高，对被链入的网页影响力也有影响。
      PageRank算法为每个网页赋予相同的初始影响力得分，通过迭代递归更新每个网页的得分，即PageRank得分，直至得分稳定。但PageRank的重要性计算与搜索主题无关，即不管我们搜索什么，得到的都是影响力最高的网页。
     PageRank得到的结果为0-10，10为满分。得分在4以上的网页，就已经表明这是一个比较优秀的网页了。
PageRank算法原理

1.基本假设

      PageRank将互联网视作一张有向图，网页作为网络节点，链接作为有向边；每个网页有一个PageRank得分；每个网页的PageRank得分等于其所有链入网页的PageRank得分的加权和，权值等于链接数量的倒数。

      PageRank得分的计算步骤为：首先给每个网站设置一个初始PageRank得分，第一次迭代将网站PageRank得分更新，第二次迭代按照公式得到一组新的PageRank得分，不断迭代直至PageRank得分收敛。

迭代结束条件有很多设置方法：

页面的PageRank得分与上一次相等。

设置一个差值指标，当若有页面与上一次计算的PageRank得分小于差值指标时，结束迭代。

设置一个百分比，当大于百分比的页面与上一次计算的PageRank得分相等时，结束迭代。

设置最大迭代次数。

2.基本思想

      如果网页T链入网页A，则表明网页T认为网页A很重要，于是将自己的一部分PageRank得分赋给网页A，赋予的分值为：

PR(T)为T的PageRank得分，L(T)为T的出链数。即一个页面的PageRank得分由其链入网页经过迭代递归计算得到。若网页的链入页面较多，则它的重要性较高；若网页没有链入页面，则该网页没有重要性。

3.简化算法

     假设有一个4个网页（A、B、C、D）组成的集合。若所有网页都只链入A，则A的PageRank得分为：

若B链入至A和C，C链入A，D链入A、B、C。此时A网页的PageRank得分为

用公式表示为

最后得到的PageRank得分会换算成百分比形式乘上修正系数d。由于无链入的网页计算得到的PageRank得分为0，使得其传向链出网页的PageRank得分也为0，所以需要给每个页面赋予一个最小PageRank得分：

最后每个网页的PageRank得分都会趋于某个定值。

4. 完整算法

      完整的方程引入了随机游走理论，即假设某人打开了一个网页，随机浏览其他网页直到网页没有链出。引入修正系数d，定义为用户访问某网页后继续访问下个网页的概率，一般由上网者使用书签频率的平均值估算得到。所以网页的PageRank得分为：

其中，所有链入网页的PageRank得分可以由一个特殊的邻接矩阵的特征向量R表示：

同时，R是以下方程组的解：

其中邻接函数表示网页j指向网页i的链接数与网页j含有链接总数的比值。

      这样邻接矩阵产生的巨大eigengap值在经过几次迭代后就可以在高精确度下估计PageRank算法特征向量R的值。

5.注意事项

(1)   初始系数的确定

根据Page和Brin的文章，不论初始值如何选取，PageRank算法都能保证网页收敛于真实值，且每个网页级别收敛于整个网络中网页数量，故设置初始网页PageRank得分为1，阻尼系数为0.85。

(2)   时间复杂度

由于使用了稀疏矩阵的技巧，大大简化了计算量。



PageRank算法优缺点

1.优缺点

优点：PageRank是一个与查询无关的静态算法，即每个网页的PageRank得分可以通过离线计算获得，降低了查询响应时间。

缺点：PageRank算法忽略了搜索内容与网页的相关性，且旧的页面会比新页面的影响力高。

2.改进算法

(1)主题敏感的PageRank（Topic-Sensitive PageRank）

     算法首先计算网页的PageRank得分，然后给每个网页计算多个PageRank得分对应不同的主题，查询时把初始PageRank得分与特定主题下的PageRank得分综合在一起形成一个复合PageRank得分。

(2)二次方程推断法（Quadratic Extra polation）

     该算法可以加快PageRank的运算速度。通过周期性削减当前矩阵乘幂迭代的非主要特征向量的方法，大大加快了收敛速度。当计算一个包含8kW个节点的网络时，相比于PageRank算法，该方法计算速度提高了20%-30%。

(3)分块矩阵排序算法（BlockRank Algorithm）

     该算法也能加快PageRank的运算速度，该算法将网络根据领域划分成块，为每个领域计算PageRank得分；估计它们的BlockRank得分（相对影响力），用BlockRank得分给每个区域的BlockRank赋予权重。再把加权的局部PageRank得分看作全局PageRank向量，作为PageRank算法的开始向量。

以上就是“PageRank算法教程及Python实现”的详细内容，想要了解更多Python教程欢迎持续关注编程学习网。