pageRank 详细解析具体例子

1、PageRank解释方法一1. PageRank的核心思想                                             &

2、#160;                                                (1) R(x)表示x的

3、PageRank，B(x)表示所有指向x的网页。      公式(1)的意思是一个网页的重要性等于指向它的所有网页的重要性相加之和。粗看之下，公式(1)将核心思想准确地表达出来了。但仔细观察就会发现，公式(1)有一个缺陷：无论J有多少个超链接，只要J指向I，I都将得到与J一样的重要性。当J有多个超链接时，这个思想就会造成不合理的情况。例如：一个新开的网站N只有两个指向它的超链接，一个来自著名并且历史悠久的门户网站F，另一个来自不为人知的网站U。根据公式(1)，就会得到N比F更优质的结论。这个结论显然不符合人们的常识。弥补这个缺陷的一个简单方法是

4、当J有多个超链接（假设个数为N），每个链接得到的重要性为R(j)/N。于是公式(1)就变成公式（2）：                                                                      

5、0;                          （2） N(j)表示j页面的超链接数 图2 来自Lawrence Page的文章     从图2可以看出，如果要得到N比F更优质的结论，就要求N得到很多重要网站的超链接或者海量不知名网站的超链接。而这是可接受的。因此可以认为公式(2)将核心思想准确地表达出来了。为了得到标准化的计算结果，在公式(2)的基础上增加一个常数C，得到公式(3)：   

6、;                                                                                     

7、0;           (3) 2.  计算，实例由公式(3)可知，PageRank是递归定义的。换句话就是要得到一个页面的PageRank，就要先知道另一些页面的PageRank。因此需要设置合理的PageRank初始值。不过，如果有办法得到合理的PageRank初始值，还需要这个算法吗？或者说，这个严重依赖于初始值的算法有什么意义吗？依赖于合理初始值的PageRank算法是没意义的，那么不依赖于初始值的PageRank算法就是有意义的了。也就是说，如果存在一种计算方法，使得无论怎样设置初始值，最后都会收敛到同

8、一个值就行了。要做到这样，就要换一个角度看问题，从线性代数的角度看问题。将页面看作节点，超链接看作有向边，整个互联网就变成一个有向图了。此时，用邻接矩阵M表示整个互联网，若第I个页面有存在到第J个页面的超链接，那么矩阵元素mij=1，否则mij=0。对于图3有矩形M= 0, 1, 1, 0,             0, 0, 0, 1,            1, 0, 0, 0,           

9、1, 1, 1, 0                                                                                 

10、0;  图3观察矩阵M可发现，M的第I行表示第I个网页指向的网页，M的第J列表示指向J的网页。如果将M的每个元素都除于所在行的全部元素之和，然后再将M转置（交换行和列），得到MT。MT的每一行的全部元素之和不就正好是公式(3)中的 吗？例如图3可以得到这样的矩阵：MT= 0,   0,  1, 1/3,        1/2, 0,  0, 1/3,       1/2,  0,  0, 1/3,      

11、0; 0,   1,   0,  0   将R看作是一个N行1列的矩阵，公式(3)变为公式（4）R = C MT R  (4)在公式(4)中，R可以看作MT的特征向量，其对应的特征值为1 / C（看不明白这句话，可以回忆下线性代数中对特征向量的定义对于矩阵A，若存在着列向量X和一个数c，使得AX=cX，则X称为A的特征向量，c称为A的特征值）。幂法(power method）计算主特征向量与初始值无关，因此只要把R看作主特征向量计算，就可以解决初始值的合理设置问题。幂法得到的结果与初始值无关，是因为最终都会收敛到某个值。因此使用幂法之

12、前，要确保能够收敛。但是，在互联网的超链接结构中，一旦出现封闭的情况，就会使得幂法不能收敛。所谓的封闭是指若干个网页互相指向对方，但不指向别的网页，具体的例子如图4所示：                                     图4 来自Soumya Sanyal的PPT上图4个绿色网页就是封闭情况。这种情况会使得这些网页的PageRank在计算的时候不断地累加，从而使得结果不能收

13、敛。仔细研究就会发现红色网页的PageRank给了绿色网页后，绿色网页就将这些PageRank吞掉了。Larry Page将这种情况称为Rank Sink。如果沿着网页的链接一直点下去，发现老是在同样的几个网页中徘徊，怎么办？没错，把当前页面关掉，再开一个新的网页。上述情况正好与Rank Sink类似，也就意味着可以借鉴这个思想解决Rank Sink。因此，在公式(3)中的基础上加一个逃脱因子E，得到：                           

14、                                                                     (5)E(i)表示第i个网页的逃脱因子   将(5)变成矩阵形式，可得：R = C MT&#

15、160;R + CE = C( MT R + E )其中列向量R的1范数(即R的全部矩阵元素相加)为1将上式重写为R = C( MT + E * 1 ) R (6)1是指一行N列的行向量，且每个元素都是1   在公式(6)中，只要将R看作(MT + E * 1)的特征向量，就可以同时解决初始值设置问题和封闭的情况。 3.  资料共享   找资料是简单的事，但要找到好资料就不那么容易了。因此，这一小节是分享我找到的一些比较好的资料。1. PageRank之父的文章: The PageRank Citatio

16、n Ranking Bringing Order to the Web:8090/422/2. 一个对PageRank进行解释的PPT，讲解得很好: The PageRank Citation Ranking Redone3. 不错的PageRank科普文: Google 的秘密- PageRank 彻底解说 中文版4. 本文所用到的线性代数相关知识pageRank二1 基本思想：       如果网页T存在一个指向网页A的连接，则表明T的所有者认为A比较重要，从而把T的一部分重要性得

17、分赋予A。这个重要性得分值为：PR（T）/L(T)    其中PR（T）为T的PageRank值，L(T)为T的出链数        则A的PageRank值为一系列类似于T的页面重要性得分值的累加。        即一个页面的得票数由所有链向它的页面的重要性来决定，到一个页面的超链接相当于对该页投一票。一个页面的PageRank是由所有链向它的页面（链入页面）的重要性经过递归算法得到的。一个有较多链入的页面会有较高

18、的等级，相反如果一个页面没有任何链入页面，那么它没有等级。2 PageRank简单计算：       假设一个由只有4个页面组成的集合：A，B，C和D。如果所有页面都链向A，那么A的PR（PageRank）值将是B，C及D的和。              继续假设B也有链接到C，并且D也有链接到包括A的3个页面。一个页面不能投票2次。所以B给每个页面半票。以同样的逻辑，D投出的票只有三分之一算到了A的Pag

19、eRank上。             换句话说，根据链出总数平分一个页面的PR值。       例子：        如图1 所示的例子来说明PageRank的具体计算过程。             

20、;                        3  修正PageRank计算公式：         由于存在一些出链为0，也就是那些不链接任何其他网页的网， 也称为孤立网页，使得很多网页能被访问到。因此需要对 PageRank公式进行修正，即在简单公式的基

21、础上增加了阻尼系数（damping factor）q， q一般取值q=0.85。      其意义是，在任意时刻，用户到达某页面后并继续向后浏览的概率。 1- q= 0.15就是用户停止点击，随机跳到新URL的概率）的算法被用到了所有页面上，估算页面可能被上网者放入书签的概率。      最后，即所有这些被换算为一个百分比再乘上一个系数q。由于下面的算法，没有页面的PageRank会是0。所以，Google通过数学系统给了每个页面一个最小值。  

22、         这个公式就是.S Brin 和 L. Page 在The Anatomy of a Large- scale Hypertextual Web Search Engine Computer Networks and ISDN Systems 定义的公式。     所以一个页面的PageRank是由其他页面的PageRank计算得到。Google不断的重复计算每个页面的PageRank。如果给每个页面一个随机PageRank值（非0），那么经过不断的重复计算，

23、这些页面的PR值会趋向于正常和稳定。这就是搜索引擎使用它的原因。 4. PageRank幂法计算(线性代数应用)4.1 完整公式：关于这节内容，可以查阅：谷歌背后的数学首先求完整的公式：Arvind Arasu 在Junghoo Cho Hector Garcia - Molina, Andreas Paepcke, Sriram Raghavan. Searching the Web 更加准确的表达为： 是被研究的页面，是链入页面的数量，是链出页面的数量，而N是所有页面的数量。PageRank值是一个特殊矩阵中的特征向量。这个特征向量为： R是如下等式的一个解：

24、如果网页i有指向网页j的一个链接，则否则0。4.2 使用幂法求PageRank      那我们PageRank 公式可以转换为求解的值，      其中矩阵为 A = q  × P + ( 1 一 q) *  /N 。 P 为概率转移矩阵，为 n  维的全 1 行. 则 =           幂法计算过程

25、如下：      X  设任意一个初始向量, 即设置初始每个网页的 PageRank值均。一般为1.     R = AX;     while  (1 )(            if ( l X - R I  <  ) /如果最后两次的结果近似或者相

26、同，返回R                  return R;               else                  

27、X =R;               R = AX;             4.3 求解步骤：一、 P概率转移矩阵的计算过程:        先建立一个网页间的链接关系的模型,即我们需要合适的数据结构表示页面间的连接关系。    

28、60; 1) 首先我们使用图的形式来表述网页之间关系：       现在假设只有四张网页集合：A、B、C，其抽象结构如下图1：                                  

29、60;  图1 网页间的链接关系      显然这个图是强连通的（从任一节点出发都可以到达另外任何一个节点）。      2）我们用矩阵表示连通图：       用邻接矩阵 P表示这个图中顶点关系 ，如果顶（页面）i向顶点（页面）j有链接情况 ，则pij   =   1 ，否则pij   =   0 。如图2所示。如果

30、网页文件总数为N ， 那么这个网页链接矩阵就是一个N x N  的矩 阵 。       3）网页链接概率矩阵       然后将每一行除以该行非零数字之和，即（每行非0数之和就是链接网个数）则得到新矩阵P，如图3所示。 这个矩阵记录了 每个网页跳转到其他网页的概率，即其中i行j列的值表示用户从页面i 转到页面j的概率。图1 中A页面链向B、C，所以一个用户从A跳转到B、C的概率各为1/2。    

31、;  4）概率转移矩阵P       采用P 的转置矩 阵进行计算， 也就是上面提到的概率转移矩阵P 。  如图4所示：                    图2  网页链接矩阵：         

32、                             图3  网页链接概率矩阵：                   

33、;          图4  P 的转置矩 阵 二、 A矩阵计算过程。      1）P概率转移矩阵  :             2）/N 为：           3）A矩阵为：q  × P + ( 1 一 q) *  /N = 0.85  × P + 0.15  * /N           初始每个网页的 PageRank值均