PageRank算法核心思想及数学支撑

佩奇排名（PageRank），又称网页排名、谷歌左侧排名，是一种由搜索引擎根据网页之间相互的超链接计算的技术，而作为网页排名的要素之一，以Google公司创办人拉里·佩奇（Larry Page）之姓来命名。Google用它来体现网页的相关性和重要性，在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。[来该段自于Wikipedia对PageRank的权威诠释]

自从Google在商业上获得巨大成功后，它大力推行的PageRank也成为企业界和学术界十分关注的计算模型。Google将糅合入Title标识、Keywords关键字标识等因素的PageRank结果来调整搜索结果，使得“更加重要/等级更高”的网站呈现在检索结果中，从而提高搜索结果的相关度、质量。PageRank的结果从0到10，10级为满分。PR值越高说明网页越重要/受欢迎。例如PR值为1的网站不太重要，而PR值为7~10的网站可以说是非常重要了。一般到4，就能说是一个不错的网站。Google将自身PR值定为10.

在PageRank算法之前，曾经有人提出利用网页的入链数量作为依据进行链接分析，即认为入链越多，则该网页重要度越高。早期搜索引擎也采用该方法作为搜索引擎检索方法，对于检索结果亦起到较明显提升。而PageRank不单考虑到入链数量，也考虑到网页质量因素，两者结合后网页重要性评价则更为准确。

1、基本思想：

即对于某个网页A而言，该网页PageRank值的计算基于以下两个假设：

1：数量假设，如果越多的网页指向A，即A的入链数量越多，则该网页越重要；

2：质量假设，如果指向A的网页质量越高，则A越重要，即权重因素不同。

现实中一个具体的假设案例是：一篇论文被诺贝尔奖得主所引用， 显然要比被普通研究者所引用更说明其价值；一篇论文被100位学者引用，显然要比只有一位普通学者引用之更有价值。

初始阶段，网页通过链接关系构建起Web图，每个页面设置相同的PageRank值(原因在稍后阐述)，通过若干轮的计算，会得到每个页面所获得的最终PageRank值。随着每一轮的计算进行，网页当前的PageRank值会不断得到更新。

在每一轮更新页面PageRank得分的计算中，每个页面将其当前的PageRank值平均分配到本页面包含的出链上，这样每个链接即获得了相应的权值。而每个页面将所有指向本页面的入链所传入的权值求和，即可得到新的PageRank得分。当每个页面都获得了更新后的PageRank值，就完成了一轮PageRank计算。

用公式来表示，若网页T存在一个指向网页A的链接，则表明T的所有者认为A是重要的，从而把T的一部分重要性得分赋予A。

这个重要性得分值为：PR（T）/C(T) ，其中PR（T）为T的PageRank值，C(T)为T的出链数。

对于A而言，A的PageRank值为一系列类似于T的页面重要性得分总和。一个页面的PageRank是由所有链向它的页面（链入页面）的重要性经过递归算法得到的。

2、PageRank的简单计算

3、PageRank的修正公式

现实网络中，由于存在出链度数为0，即不链接到任何网页的页面，但是很多网页可以访问它。鉴于这类情况，PageRank公式需要进行修正，修正的方法是，在简单公式的基础上增加阻尼系数d(damping factor):

该公式是计算网页A的PR值公式。Ti是存在到A的链接的网页。C(Ti)是网页Ti中存在的链接的数量。d是阻尼系数，一般定义为用户随机点击链接的概率，根据工程经验一般取0.85。而(1-d)代表着不考虑入站链接的情况下随机进入一个页面的概率。

还有一种修正方式与第一种相似，公式如下：

其中p(i)是第i个页面，N是页面总数，q是阻尼系数，(1-q)代表着不考虑入站链接的情况下随机进入一个页面的概率，L(pi)是Pi链出页面的数量。所有页面的PageRank值可以组成一个特征向量，这个特征向量矩阵为：

R是如下矩阵方程式的一个解：

其中 L(Pi,Pj) 表示网页 j 指向网页 i 的链路权重，并且若网页i存在指向网页j的一个链接，则

否则，L(Pi,Pj) = 0.

关于R矩阵方程式的含义，按照矩阵相乘规则，实际上是所有网页节点的方程式聚合组：

以第一行为例，分拆开来实际上是：

PR(P1) = (1-q)/N + a*(L(p1,p1)*PR(P1) + L(p1,p2)*PR(P2) + ... + L(p1,pn)*PR(Pn) )

其余行数以此类推。遂构成上述矩阵方程式。

到现在为止，我们把PageRank的计算方式和原理都阐述了，但是仍然有一个问题：先有鸡还是先有蛋？我们要知道一个网页 Wi的排序， 不仅要知道有多少网页链接了它， 而且还得知道那些网页各自的排序——因为来自排序靠前网页的链接更有分量。 而但作为互联网大家庭的一员， Wi本身对其它网页的排序也是有贡献的， 而且基于来自排序靠前网页的链接更有分量的原则， 这种贡献与 Wi本身的排序也有关。简而言之，链接到Wi的网页们影响了Wi的重要性排名，而Wi也有可能反向影响其余网页的排名，想要知道其余网页的排名，那么首先又要知道Wi的排名。这就是先有鸡还是先有蛋的意思。

为了打破这个死循环，佩奇和布林采用了一个奇妙的思路，分析一个虚拟用户在互联网的漫游过程。他们做了这样的假定：该虚拟用户访问了一个网页后，下一步将有相同的几率访问被该网页链接的任何一个其他网页。初看之下这一假设不合情理，用户都会存在自己的偏好，不可能以相同几率访问一个网页所有链接。但是在PageRank中，考虑到我们这一虚拟用户实际上是对所有互联网漫游者所做的平均意义上的代表，这样一来这条假设就不像初看之下那么不合理了。实际上就也是PR（T）/C(T) 的来源。最终的网页排序，则由用户在网络上漫游了很长时间---理论上是无限时间后---访问各网页的几率分布来决定，访问几率越大的网页排序则越靠前。(细心的读者可以发现，在该核心思想下，网页排序与搜索关键词并无关系！这意味着排序计算可以单独进行，而无需在用户输入keywords后再临时进行，这是Google搜索速度迅即的重要原因！)

所以综上，一个页面的PageRank值是由其他页面的PR值计算得到的。Google不断的重复计算每个页面的PR值。给每个页面一个初始的非零随机PR值，那么经过不断地迭代计算，最终每个页面的PR值将趋于稳定。这是PageRank的奇妙所在以及为何搜索引擎使用它的原因。