pageRank详细解析具体例子

PageRank解释方法1.PageRank的核心思想尺⑴二VR(j)Z為 (1) R(x)表示x的PageRank,B(x)表示所有指向x的网页。公式(1)的意思是一个网页的重要性等于指向它的所有网页的重要性相加之和。粗看之下， 公式(1)将核心思想准确地表达岀来了。但仔细观察就会发现，公式 (1)有一个缺陷：无论J有多少个超链接，只要J指向I,I都将得到与J一样的重要性。当J有多个超链接时，这个思想就会造成不合理的情况。例如：一个新开的网站 N只有两个指向它的超链接，一个来自著名并且历史悠久的门户网站F,另一个来自不为人知的网站 U。根据公式(1)，就会得到N比F更优质的结论。这个结论显然不符合人们的常识。弥补这个缺陷的一个简单方法是当 J有多个超链接(假设个数为N)，每个链接得到的重要性为R(j)/N。于是公式(1)就变成公式(2):从图2可以看岀，如果要得到N比F更优质的结论，就要求N得到很多重要网站的超链接或者海量不知名网站的超链接。而这是可接受的。因此可以认为公式 (2)将核心思想准确地表达岀来了。为了得到标准化的计算结果，在公式 (2)的基础上增加一个常数C，得到公式(3):2.计算，实例由公式⑶可知，PageRank是递归定义的。换句话就是要得到一个页面的 PageRank,就要先知道另一些页面的PageRank。因此需要设置合理的 PageRank初始值。不过，如果有办法得到合理的PageRank初始值，还需要这个算法吗或者说，这个严重依赖于初始值的算法有什么意义吗依赖于合理初始值的 PageRank算法是没意义的，那么不依赖于初始值的 PageRank算法就是有意义的了。也就是说，如果存在一种计算方法， 使得无论怎样设置初始值， 最后都会收敛到同一个值就行了。要做到这样，就要换一个角度看问题，从线性代数的角度看问题。将页面看作节点，超链接看作有向边，整个互联网就变成一个有向图了。此时，用邻接矩阵 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}

观察矩阵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,0,1,0,0}将R看作是一个N行1列的矩阵，公式（3）变为公式（4）R=CMR （4）在公式⑷中，R可以看作MT的特征向量，其对应的特征值为 1/C（看不明白这句话，可以回忆下线性代数中对特征向量的定义 一一对于矩阵A,若存在着列向量X和一个数c,使得AX=cX,则X称为A的特征向量，c称为A的特征值）。幕法（powermethod）计算主特征向量与初始值无关，因此只要把R看作主特征向量计算，就可以解决初始值的合理设置问题。幕法得到的结果与初始值无关， 是因为最终都会收敛到某个值。 因此使用幕法之前，要确保能够收敛。但是，在互联网的超链接结构中，一旦岀现封闭的情况，就会使得幕法不能收敛。所谓的封闭是指若干个网页互相指向对方，但不指向别的网页，具体的例子如图 4所示：ff--41—If~—1

厂nu\图4来自SoumyaSanyal的PPT上图4个绿色网页就是封闭情况。这种情况会使得这些网页的 PageRank在计算的时候不断地累加，从而使得结果不能收敛。仔细研究就会发现红色网页的 PageRank给了绿色网页后，绿色网页就将这些PageRank吞掉了。LarryPage将这种情况称为RankSink。如果沿着网页的链接一直点下去， 发现老是在同样的几个网页中徘徊， 怎么办没错，把当前页面关掉，再开一个新的网页。上述情况正好与 RankSink类似，也就意味着可以借鉴这个思想解决RankSink。因此，在公式(3)中的基础上加一个逃脱因子 E,得到：R(i)=CV+CE(e)(5)E(i)表示第i个网页的逃脱因子将(5)变成矩阵形式，可得：R=CMR+CE=C(MR+E)其中列向量R的1范数(即R的全部矩阵元素相加)为1将上式重写为R=C(Mt+E*1)R(6)1是指一行N列的行向量，且每个元素都是 1在公式⑹中，只要将R看作(Mt+E*1)的特征向量，就可以同时解决初始值设置问题和封闭的情况。3.资料共享找资料是简单的事，但要找到好资料就不那么容易了。 因此，这一小节是分享我找到的一些比较好的资料。1.PageRank之父的文章：ThePageRankCitationRankingBringingOrdertotheWeb一个对PageRank进行解释的PPT，讲解得很好：ThePageRankCitationRanking-Redone不错的PageRank科普文：Google的秘密Rank彻底解说中文版本文所用到的线性代数相关知识基本思想:如果网页T存在一个指向网页A的连接，则表明T的所有者认为A比较重要，从而把T的一部分重要性得分赋予A。这个重要性得分值为： PR(T)/L(T)其中PR(T)为T的PageRank值，L(T)为T的出链数则A的PageRank值为一系列类似于T的页面重要性得分值的累加。即一个页面的得票数由所有链向它的页面的重要性来决定， 到一个页面的超链接相当于对该页投一票。一个页面的 PageRank是由所有链向它的页面(链入页面)的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级， 相反如果一个页面没有任何链入页面，那么它没有等级。PageRank简单计算:假设一个由只有4个页面组成的集合：A，B,C和D。如果所有页面都链向A,那么A的PR(PageRank值将是B，C及D的和。PH(A)=PR(B)+PR(C)+PR(D)继续假设B也有链接到C，并且D也有链接到包括A的3个页面。一个页面不能投票2次。所以B给每个页面半票。以同样的逻辑，D投出的票只有三分之一算到了A的PageRanl上。叫)=警+竽+警换句话说，根据链出总数平分一个页面的 PR值。PR(X)=PR(B)PR(C),PR[D)

+L(C)+L(D)PR(X)=例子:如图1所示的例子来说明PageRank的具体计算过程。BE1铳摆蜡构中的郁分网审及JCF标阳山值修正PageRank计算公式：由于存在一些出链为o，也就是那些不链接任何其他网页的网， 也称为孤立网页，使得很多网页能被访问到。因此需要对 PageRank公式进行修正，即在简单公式的基础上增加了阻尼系数(dampingfactor)q,q一般取值q=。其意义是，在任意时刻，用户到达某页面后并继续向后浏览的概率。 1-q=就是用户停止点击，随机跳到新URL的概率)的算法被用到了所有页面上，估算页面可能被上网者放入书签的概率。最后，即所有这些被换算为一个百分比再乘上一个系数 q。由于下面的算法，没有页面的PageRank会是0。所以，Google通过数学系统给了每个页面一个最小值。PR(A)=fPR[B)PR(C)PR(D)[L(B)+L(C)+1(D)PR(A)=这个公式就是.SBrin和L.Page在《TheAnatomyofaLarge-scaleHypertextualWebSearchEngineComputerNetworksandISDNSystems》定义的公式。所以一个页面的PageRank是由其他页面的PageRank计算得到。Google不断的重复计算每个页面的PageRank。如果给每个页面一个随机PageRank值（非0），那么经过不断的重复计算，这些页面的PR值会趋向于正常和稳定。这就是搜索引擎使用它的原因。4.PageRank幕法计算（线性代数应用）完整公式：关于这节内容，可以查阅： 谷歌背后的数学首先求完整的公式：ArvindArasu在《JunghooChoHectorGarcia-Molina.AndreasPaepcke,SriramRaghavan.SearchingtheWeb》更加准确的表达为：p吗曲叫r〒+略氏鬻如节是被研究的页面，二「是，链入页面的数量，口巧）是卩」链出页面的数量，而N是所有页面的数量。PageRank值是一个特殊矩阵中的特征向量。这个特征向量为:PageRank(pi)PageRank(p2)■aPageRank(p沖)为n为n维的全11.R是如下等式的一个解：「卩-啊飞(P1,P1)i(PuP2)…R=■+坯伽卩1) ■■-a: 仏对如果网页i有指向网页j的一个链接，则N£氏為巧）=；=1否则E（加巧）=0。使用幕法求PageRank那我们PageRank公式可以转换为求解飓护*的值，其中矩阵为A=qXP+一1q）*肿/N。P为概率转移矩阵，占行.则Ef?1=88TOC\o"1-5"\h\z1 ・・・ 1: 1 :1 … 1幕法计算过程如下：X设任意一个初始向量,即设置初始每个网页的 PageRank值均。一般为R=AX;while(1)(if(lX[RI<)—―—=-1{D.05D・0弓0-9i1.3d!/I=o.sa=氏AX-0.0&0.06O.5S=0.45S=R1-a0.4-5a0521.109--直到最后两次的结果近似或者相同，即 R最终收敛，R约等于X,此时计算停止。最终的R就是各个页面的PageRank值。用幕法计算PageRank值总是收敛的，即计算的次数是有限的。LarryPage和SergeyBrin两人从理论上证明了不论初始值如何选取，这种算法都保证了网页排名的估计值能收敛到他们的真实值。由于互联网上网页的数量是巨大的，上面提到的二维矩阵从理论上讲有网页数目平方之多个元素。如果我们假定有十亿个网页，那么这个矩阵 就有一百亿亿个元素。这样大的矩阵相乘，计算量是非常大的。