网页排序算法 PageRank

PageRank——Google网页搜索核心技术东北大学数学系王琪[e-mail]简介1998年由斯坦福大学计算机系的博士研究生LarryPage和SergeyBrin创办。现在：未来：Google搜索核心算法网页级别（PageRank）按网页链接广泛程度判断网页重要性，是Google中表示网页重要性的综合性指标。页面分析（PageAnalysis）按页面标题是否出现关键词、网页内关键词出现的频率及关键词出现的位置确定哪些网页与正在执行的搜索密切相关。PageRank对搜索结果的影响结合了所有网页重要性和相关性指标，Google将最相关和最可靠的结果放在搜索结果的顶端。一般而言，PageRank对于排名的影响比页面分析还高。PageRank算法思想简介•基本依据：•PageRank基于假设关系——“许多优质的网页链接的网页，必定是优质网页”，判定所有网页的重要性。PageRank要点大致有3个:•链入链接数单纯意义上的受欢迎度指标•链入链接是否来自受欢迎程度高的页面有根据的受欢迎指标•链入链接源页面的链出链接数被选中的概率指标PageRank计算•互联网是一个有向图•每一个网页是图的一个顶点•网页间的每一个超链接是图的一个有向边•用邻接矩阵来表示图，即：定义邻接矩阵为G，若网页j到网页i有超链接，则；反之，。•显然，如果网页有N个，则矩阵为N×N的0、1方阵。1ijg0ijg多个网页相互链接的图对应的邻接矩阵（这里将0,1值用二值图像显示，黑色代表0，白色代表1）PageRank的计算•定义邻接矩阵为G，若网页j到网页i有超链接，则；反之，。•记矩阵G的列和、行和分别是•它们分别给出了页面j的链出链接数目和链入链接数目iijjgcjijigr1ijg0ijgPageRank的计算•假设我们在上网的时侯浏览页面并选择下一个页面，这个过程与过去浏览过哪些页面无关，而仅依赖于当前所在的页面，那么这一选择过程可以认为是一个有限状态、离散时间的随机过程，其状态转移规律用Markov链描述。•定义转移概率矩阵)(ijaAjijijcganji...1,PageRank的计算•根据Markov链的基本性质，对于正则Markov链，存在平稳分布，满足•表示在极限状态（转移次数趋于无限）下各网页被访问的概率分布。•定义为网页的PageRank向量，表示第i个网页的PageRank值TNxxx),,(21Aiix1ix某7个网页之间的链接关系图网页链接图的邻接矩阵0110110101100010011001000100100101100001001000000G=PageRank的计算011/201/41/201/501/21/30001/5001/31/4001/50001/4001/5001/301/2100001/4001/5000000A=状态转移概率矩阵APageRank的计算0.6994565338373890.3828604185215180.3239588156720540.2429691117540400.4123112199462510.1030778049865630.1398913067674780.3035143769968050.1661341853035140.1405750798722040.1054313099041530.1789137380191690.04472843450479230.0607028753993610求特征值1对应的特征向量归一化7个网页的PageRank值PageRank结果的评价•将PageRank的评价按顺序排列(PageRank小数点3位四舍五入):页面之间相互关系及状态转移图PageRank结果的评价•首先应该关注的是，PageRank的名次和链入链接的数目是基本一致的。无论链接多少链出链接都几乎不会影响PageRank，相反地有多少链入链接却是从根本上决定PageRank的大小。•但是，仅仅这些并不能说明第1位和第2位之间的显著差别，在链入链接相同的情况下，链出链接数也影响PageRank的大小。(同样地、第3位和第4位，第6位和第7位之间的差别)。•总之，绝妙之处在于PageRank并不只是通过链入链接数来决定的。PageRank结果的评价•让我们详细地看一下。ID=1的页面的PageRank是0.304，占据全体的三分之一，成为了第1位。特别需要说明的是，起到相当大效果的是从排在第3位的ID=2页面中得到了所有的PageRank(0.166)数。ID=2页面有从3个地方过来的链入链接，而只有面向ID=1页面的一个链接，因此(面向ID=1页面的)链接就得到了所有的PageRank数。不过，就因为ID=1页面是链出链接和链入链接最多的页面，也可以理解它是最受欢迎的页面。PageRank结果的评价•反过来，最后一名的ID=6页面只有ID=1的15％的微弱评价，这可以理解为是因为没有来自PageRank很高的ID=1的链接而使其有很大地影响。总之，即使有同样的链入链接的数目，链接源页面评价的高低也影响PageRank的高低。•实际地试着计算一下PageRank的收支。因为λ=1所以计算很简单，只要将自各页的流入量单纯相加即可。譬如ID=1的流入量=(ID=2发出的Rank)+(ID=3发出的Rank)+(ID=5发出的Rank)+(ID=6发出的Rank)=0.166+0.141/2+0.179/4+0.045/2=0.30375页面之间状态转移图的验证PageRank算法实际应用的困难1.现实世界和假想模型不同；2.实际计算上，80亿的网页数量，计算非常困难。现实世界和假想模型的不同现实世界：•1.顺着链接前进的话，有时会走到完全没有链出链接的网页；•2.同样道理，只有链出的链接而没有链入的链接的页面也是存在的。（不考虑）•3.有时候也有链接只在一个集合内部旋转而不向外界链接的现象。假想的理论模型：•正则链（或称回归类，无吸收状态）现实世界和假想模型的不同实际问题可能出现的情况•最大特征值不唯一，导致特征向量不唯一，无法对网页进行排序问题的解决方法•为了解决这样的问题，PageRank考虑了这样一种浏览模型——用户虽然在许多场合都顺着当前页面中的链接前进,但时常会跳跃到完全无关的页面。•将「时常」这个概率固定为15％来计算。则用户在85％的情况下沿着链接前进,但在15％的情况下会突然跳跃到无关的页面中去。(注:PageRank的原始参数是87％(＝1/1.15)和13％(＝0.15/1.15)。)问题的解决方法•即A'=c*A+(1-c)*[1/N]•其中，[1/N]是所有要素为1/N的N次正方行列，c=0.85(=1-0.15)。A’是新的状态转移矩阵。•也就是说，根据PageRank的变形，原先求矩阵A的特征值问题变成了求矩阵A’的最大特征值对应特征向量的问题了。方法的数学解释•从数学角度看，把非正则链的状态转移矩阵正则化，就是把不是强联通的图变成强联通的，是一种变换操作。•对全部的要素都考虑0.15的转移概率，意味着将原本非正则的状态转移矩阵转换为正则的状态转移矩阵，将原本并非强连通的图变成了强联通的。•相对于原来的状态转移矩阵，这样的变换操作能保证最大特性值的次数为1，也就保证了PageRank的存在。PageRank数值计算难点PageRank数值计算难点（一）•计算机容量限制•假设N是104的order。通常，数值计算程序内部行列和矢量是用双精度记录的，N次正方行列A的记忆领域为sizeof(double)*N*N=8*104*104＝800MB。N如果变成105或106的话，就变成80GB,8TB。这样的话不用说内存就连硬盘也已经很困难了。目前，Google处理着80亿以上的页面，很显然，已知的这种做法已经完全不适用了。PageRank数值计算难点（二）•收敛问题•特征向量的求解，就是求解方程，是N元一次方程组，一般地不能得到分析解，所以只能解其数值。•然而，常用的迭代求解方法会导致收敛速度很慢。A思考•PageRank算法还可以应用在什么问题上？