Google之Page Rank分析（转）

本文来源为：http://hi.baidu.com/alphahunters/blog/item/e0e8a92d1b2820321f3089a0.html

 

首先申明，本博文自原创，部分数据来源于网络。

在google的搜索结果中，PR值越高的网页排在越前面。

网页权重的算法有很多种，为何我唯独选择了page rank来讨论，不仅因为它是Google搜索引擎采用的搜索结果排名算法之核心，且它把整个互联网当做一个整体来对待且最终依靠经典的数学模型精准地得到web上网页的权重。

虽然今天的搜索引擎的排名系统远远要比这个算法复杂。域名数据，内容质量，用户数据，建站时间等都可能被考虑进去，但是page rank算法仍然是核心的技术之一，使得Google名声大噪。关于page rank的介绍性文章，在Google黑板报里的” 谈 Page Rank – Google 的民主表决式网页排名技术”。关于其更详细的论述，可以参照Google 的两个创始人拉里•佩奇 （Larry Page ）和谢尔盖•布林 (Sergey Brin)的论文”The PageRank Citation Ranking: Bringing Order to the Web”。

首先，page rank基于以下的假设：”一个网页被引用 (即反向链接)的次数越多，则说明越重要; 一个网页虽然没有被多次引用，但是被重要的网页引用，则它也可能是很重要的；一个网页的重要性被平均的传递到它所引用的网页。”所以，为了说明问题的方便，就引出了下面这个简化了的Page Rank算法。简化版一：R(u) = cR(1)/N(1) + ……+cR(v)/N(v)。(v∈Bu)。其中R(v)是网页v的PR值，N(v)是网页v的正向链接数，B(u)是页面u的反向链接的集合。c是阻尼系数(Damping Factor)，它的值在0到1之间。因此，阻尼系数的使用，减少了其它页面对当前页面A的排序贡献。那么这个式子如何用数学的方法解答呢？首先可以认为整个互联网是一个大的有向图G=(V,E)。V是所有页面的集合，E是有向边的集合，(i,j)表示页i有指向页j的超链接。由于有向图和矩阵在本质上是可以互相转换的，下面举例是如何互转的：

此有向连通图模拟网页间的超链接

链接源I D 链接目标 ID

1          2,3 ,4,5, 7

2          1

3          1,2

4          2,3,5

5          1,3,4,6

6          1,5

7          5

如果我们假设Aij＝1 ,if (从页面 i 向页面 j 「有 」 链接的情况) ；Aij＝0, if (从页面 i 向页面 j 「没有」链接的情况) 。则根据以上我们可以构造如下矩阵

A = [

   0, 1, 1, 1, 1, 0, 1;

   1, 0, 0, 0, 0, 0, 0;

   1, 1, 0, 0, 0, 0, 0;

   0, 1, 1, 0, 1, 0, 0;

   1, 0, 1, 1, 0, 1, 0;

   1, 0, 0, 0, 1, 0, 0;

   0, 0, 0, 0, 1, 0, 0;

]

接下来再来看看公式一中的PR值求法，即

PR(1) = c[1*PR(2) + (1/2)*PR(3) + (1/4)*PR(5) +(1/2)*PR(6)];

PR(2) = c[(1/5)*PR(1) + (1/2)*PR(3) + 0.25*PR(5) + 0.5*PR(5)];

............

PR(7) = c[(1/5)*PR(1) + 0+ 0......];

则，可以得出P^{T =} cMP^T，其中M的方阵如下，

M = [

    0,    1,   1/2,    0,     1/4,    1/2,    0;

    1/5,    0, 1/2,    1/3,    0,     0,     0;

    1/5,    0, 0,     1/3,    1/4,    0,     0;

    1/5,    0, 0,      0,     1/4,    0,     0;

    1/5,    0, 0,     1/3,    0,     1/2,    1;

    0,      0, 0,      0,     1/4,    0,     0;

    1/5,    0, 0,     0,     0,     0,     0;

]

所以，P^T为M的特征根为c的特征向量。只需求出最大特征根的特征向量，就是网页集对应的最终PageRank值，这可以用迭代方法计算。如何迭代呢？如果我们给定初始向量P^T1’做第一次迭代，就相当于用初始向量乘以上面的矩阵。第二次迭代就相当于用第一迭代的结果再乘以上面的矩阵……实际上，在随机过程的理论中，上述矩阵被称为“转移概率矩阵”。这种离散状态按照离散时间的随机转移过程称为马尔可夫链(Markov chain)。设转移概率矩阵为P，若存在正整数N，使得P_N>0(每一个元素大于0)，这种链被称作正则链，它存在唯一的极限状态概率，并且与初始状态无关。这篇”Google搜索与Inter网中的数学”文章里，描述了马氏链与page rank的关系。

最后可以看到，从最开始的矩阵A到矩阵M可以很容易转化得到(将A倒置后将各个数值除以各自的非零要素)。

现在考虑有一个页面（比如是页面7），它不含有任何的超链接，即它的前向链接或者说出度为0，很显然，方阵M的最后一行为全零，这样，特征向量P^T也为全零。我们也可以从图论的角度来阐述这个问题。我们可以这样定义一个有向图：图G的顶点集合为V={V1,V2,…,Vn}，边的集合为E={E_ij}。我们把有向图G的每个顶点都给定一个权值P(Vi)，即为它的PR值。有向边AB的权值定义为A为B贡献的PageRank，也即网站A链接到网站B的概率。这样，对于一个顶点，若它的出度大于0，则从它出去的权值和为1（这一点可以从上述的方阵M中的列可以看出，满足了全概率）。显然，如果图中有一个顶点X的出度是0，那么经过有限次迭代后所有顶点的PR值都将变为0。这是因为由于X不对外贡献任何PR，所以整体的PR总和在不断减少，最终减为0。这个被拉里•佩奇和谢尔盖•布林称为rank sink。为了克服这个问题，就有了下面这个公式：Rank算法简化版二：R(u) = （1-c）+ cR(1)/N(1) + ……+cR(v)/N(v)。(v∈Bu)。 ……公式二

(1-c)实际上为了服从概率分布。这样可以推导出P = (1-c)e + cMP，即

P = [(1-c)ee^T/n + cM]P (e^TP=n)。关于用矩阵方法来推导的更详细的文章，可以参考这篇"The $25,000,000,000 Eigenvector: The Linear Algebra Behind Google".

   现在可以想象一下整个web中有250亿不止的网页，收敛速度是至关重要的。所以为什么作者拉里•佩奇 （Larry Page ）和谢尔盖•布林 (Sergey Brin)要取c为0.85,在这篇文章”How Google Finds Your Needle in the Web's Haystack”的最后部分讨论到。

Pagerank算法除了对搜索结果进行排序外，还可以应用到其它方面，如估算网络流量，向后链接的预测器，为用户导航等。这篇文章PageRank sculpting.讲述了当前Google的一些改进.

    后记，2001年9月，PageRank被授予美国专利，专利被正式颁发给斯坦福大学，佩奇作为发明人列于文件中。最后要说的一点，分析PR算法，用到了离散数学，线性代数，概率论，数值计算甚至随机过程，所以看来数学确实很好很强大需要认真学习啊。