资源描述：
《pagerank 详细解析(具体例子)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、PageRank解释方法一1.PageRank的核心思想 (1)R(x)表示x的PageRank，B(x)表示所有指向x的网页。 公式(1)的意思是一个网页的重要性等于指向它的所有网页的重要性相加之和。粗看之下，公式(1)将核心思想准确地表达出来了。但仔细观察就会发现，公式(1)有一个缺陷：无论J有多少个超链接，只要J指向I，
2、I都将得到与J一样的重要性。当J有多个超链接时，这个思想就会造成不合理的情况。例如：一个新开的网站N只有两个指向它的超链接，一个来自著名并且历史悠久的门户网站F，另一个来自不为人知的网站U。根据公式(1)，就会得到N比F更优质的结论。这个结论显然不符合人们的常识。弥补这个缺陷的一个简单方法是当J有多个超链接（假设个数为N），每个链接得到的重要性为R(j)/N。于是公式(1)就变成公式（2）： （2）N(j)表示j页面的超
3、链接数 图2来自LawrencePage的文章 从图2可以看出，如果要得到N比F更优质的结论，就要求N得到很多重要网站的超链接或者海量不知名网站的超链接。而这是可接受的。因此可以认为公式(2)将核心思想准确地表达出来了。为了得到标准化的计算结果，在公式(2)的基础上增加一个常数C，得到公式(3)： (3) 2. 计算，实例由公式(3)可知，PageRank是递归定义的。换句话就是要得到一个页面的PageRank
4、，就要先知道另一些页面的PageRank。因此需要设置合理的PageRank初始值。不过，如果有办法得到合理的PageRank初始值，还需要这个算法吗？或者说，这个严重依赖于初始值的算法有什么意义吗？依赖于合理初始值的PageRank算法是没意义的，那么不依赖于初始值的PageRank算法就是有意义的了。也就是说，如果存在一种计算方法，使得无论怎样设置初始值，最后都会收敛到同一个值就行了。要做到这样，就要换一个角度看问题，从线性代数的角度看问题。将页面看作节点，超链接看作有向边，整个互联网就变成一个有向图了。此时，
5、用邻接矩阵M表示整个互联网，若第I个页面有存在到第J个页面的超链接，那么矩阵元素m[i][j]=1，否则m[i][j]=0。对于图3有矩形M={0,1,1,0, 0,0,0,1, 1,0,0,0, 1,1,1,0} 图3观察矩阵M可发现，M的第I行表示第I个网页指向的网页，M的第J列表示指向J的网页。如果将M的每个元素都除于所在行的全部元素之和，然后再将M转置（交换行和列），得到MT。MT的每一行的
6、全部元素之和不就正好是公式(3)中的吗？例如图3可以得到这样的矩阵：MT={0, 0, 1,1/3, 1/2,0, 0,1/3, 1/2, 0, 0,1/3, 0, 1, 0, 0 }将R看作是一个N行1列的矩阵，公式(3)变为公式（4）R=CMT R (4)在公式(4)中，R可以看作MT的特征向量，其对应的特征值为1/C（看不明白这句话，可以回忆下线性代数中对特征向量的定义——对于矩阵A，若存在着列向量X和一个数c，使得AX=cX，则X称为A的特征向量，c称为A的特征值）。幂法(powermet
7、hod）计算主特征向量与初始值无关，因此只要把R看作主特征向量计算，就可以解决初始值的合理设置问题。幂法得到的结果与初始值无关，是因为最终都会收敛到某个值。因此使用幂法之前，要确保能够收敛。但是，在互联网的超链接结构中，一旦出现封闭的情况，就会使得幂法不能收敛。所谓的封闭是指若干个网页互相指向对方，但不指向别的网页，具体的例子如图4所示： 图4来自SoumyaSanyal的PPT上图4个绿色网页就是封闭情况。这种情况会使得这些网页的PageRank在计算的时候不断地累加，从而使
8、得结果不能收敛。仔细研究就会发现红色网页的PageRank给了绿色网页后，绿色网页就将这些PageRank吞掉了。LarryPage将这种情况称为RankSink。如果沿着网页的链接一直点下去，发现老是在同样的几个网页中徘徊，怎么办？没错，把当前页面关掉，再开一个新的网页。上述情况正好与RankSink类似，也就意味着可以借鉴这个思想解决RankSink。因
