搜索引擎的网页排名问题数学实验报告

[实验七]搜索引擎的网页排名问题姓名：蒋芬学号：1012211139一、实验目的本实验涉及线性代数的一些知识，通过搜索引擎的排名算法介绍了正矩阵，列随机矩阵的一些性质，特征值与特征向量的关系以及用于计算矩阵特征值的幂迭代法.二、问题的提法今天，如果你打算了解某种信息，多半会利用互联网.在google首页搜索栏输入一些关键词，跟此有关的网页会很快迅速显示出来，也许只用不到一秒钟.而且这些网页会依照某些次序排列，通常是越靠前的越重要(也许是关注的人越多).那么google的搜索引擎是如何做到这一点的呢？三、背景介绍随着互联网的高速发展，网络已经成为现代人生活的一个重要组成部分.从网络上搜索信息已成为继电子邮件后的第二大互联网应用.Google搜索引擎是世界上最大的免费搜索引擎.目前，它对超过80多亿个网页进行整理，每天需提供的查询服务超过2亿次.当我们在Google搜索引擎中输入一些关键词后，Google会在很短的时间内从数以亿计的网页中搜索与关键词匹配的网页，并给网页的显示顺序.事实上，Google会定期地对互联网上所用的网页进行搜索，并将结果保存在自己的数据库中.所以，表面上看是我们通过Google进行网上搜索，而实际是在Google网站的数据库里进行搜索.那么Google又是如何给出网页的排名情况的呢？这就要从搜索引擎排名算法说起.GooglePageRank是Google独有的搜索引擎排名算法,作用是衡量特定网页相对于搜索引擎索引中的其他网页而言的重要程度.它是由LarryPage和SergeyBrin在20世纪90年代后期发明的.PageRank实现了将链接价值概念作为排名因素.我们知道Google工具条上有一个绿色的PageRank标尺，就是用来指示网站的链接广泛度的。PageRank值从0到10.这里的链接包括网站内部链接、导出链接和导入链接，其中最重要的是导入链接.Google通过统计这些链接的质量和数量来给网站确定PageRank值，值越高排名也就越高.如果你想查看自己站点的PR值，可以访问：，下载Google的工具栏，就可以看到自己网站的PR值.GooglePageRank现在还在使用中，不过已经是一个更大的系统中的一部分.其他部分还包括语言模块，查询模块，时间模块，个性化模块等.PageRank算法主要用到了线性代数的一些知识，包括正矩阵，列随机矩阵的一些性质，特征值与特征向量的关系以及用于计算矩阵特征值的幂迭代法.四、数学模型Ⅰ．有向图的定义数学中所谓的“图”是指某类具体事物和这些事物之间的联系.如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象.记这些点为)2,1(nivi，而它们的连线用),(jivv表示，记为ke，那么一个图G是指一个二元组))(),((GEGV，其中:1)nvvvGV,,,21是非空有限集，称为顶点集，其中元素称为图G的顶点.2）},,,{)(21meeeGE是顶点集)(GV中的无序或有序的元素对),(jivv组成的集合，称为边集,其中的元素称为边.若图G中的边均为无序对，称G为无向图，若图G中的边均为有序对，称G为有向图.图7.1这样，假定某个网络包含n个网页，每个网页用一个数字k标记，1kn。则该网络可以用一个有向图来表示，其中每个顶点看成是一个网页，边(箭头)表示从一个网页到另一个网页的链接.当网页j上有连到网页i的链接，则称网页j为网页i的导入链接，而称网页i为网页j的导出链接.比如，图7.1就可以看成是一个包含5个网页8个链接的小型网络，其中网页3有3个导入链接.12345Ⅱ邻接矩阵有向图G的邻接矩阵为Gijg，其中.01的连线到若不存在元素从的连线，到元素若存在从ijijgij（7.1）对于图7.1所示的有向图，其邻接矩阵为0100010100G100110100100010我们用kx表示某个网络中第k个网页的重要性，kx是一个非负的正数，若ijxx则表示第i个网页的重要性大于第j个网页的重要性.五、排名问题的算法Ⅰ.简化的PageRank算法一种简单的衡量某个网页重要性的方法是看谁的导入链接最多.由图7.1可得：11x，22x，33x，42x，51x.从而得到第3个网页的重要性最大，第2，4个网页的重要性其次，而第1，5个网页的重要性最小.然而上述排名算法显然不能令人满意，它不能区分第2，第4两个网页和第1，第5两个网页哪个更重要.一种改进的做法是除了考虑导入链接的数量外，还应考虑导入链接的质量，即来自一个重要性相对较高网页的链接可以增加该网页的重要性.用数学语言可表达如下：若网页j包含jn个导出链接，其中的某个链接到了网页k(即第k个网页)，则该链接赋给网页k的重要性为jjnx，即网页j的重要性被平分到其每个导出链接上.令1,2,,kLn(注意这里的数字是表示网页的标记)为链接到网页k的那些网页的集合，则网页k的重要性可以由下式得到kjkjLjxxn（7.2）如果引进矩阵A称为链接矩阵，其元素..01其他，链接到网页若从网页ijnajij那么(7.2)式等价于jnjkjkxax1，也即等价于矩阵方程xAx（7.3）其中12xTnx,x,x.不难验证：A=GD其中G为邻接矩阵，}1,,1,1{diagD21nnnn为对角矩阵.注意方程(7.3)的解就是矩阵A对应于特征根1的特征向量，若规定11niix，则对应的解就是矩阵A对应于特征根1的归一化特征向量.定义1：若一个方阵的所有元素均非负，且每列的和均为1，则该方阵称为列随机矩阵.由上述定义可知，若某个网络的每个网页都有导出链接，则其链接矩阵必为列随机矩阵.定理1：列随机矩阵一定存在特征根1.证明：记A是一个n阶的列随机矩阵，e是一个n维的元素全为1的列向量。由定义1，易知eeAT，即1是矩阵TA的特征根。又因为A与TA有相同的特征根，所以A一定存在特征根1。例如，由图7.1所示的小型网络，可得：021000210021021210021001021000210A利用MATLAB：在命令窗口键入:A=[00.5000;0.50100;0.5000.50.5;00.5000.5;0000.50];[V,D]=eig(A);diag(D)就得到矩阵A的所有特征值，包括特征值1.再键入abs(V(:,1))/norm(V(:,1),1)则可以得到A对应于特征根1的归一化特征向量.x0153803077023080205101026T.,.,.,.,.这说明按照上述方法的网页排名为：23415xxxxx。然而，上述方法仍然存在以下不足：（1）若网络中存在导出链接数为0的网页，则链接矩阵A中必存在某列全为0.此时，可验证A的所有特征值的模都小于等于1，且1不一定是A的特征值.解决这个问题的方法是采用所谓的Perron特征向量来进行排名，即A中一定存在一个正的特征值1，其对应的正的归一化特征向量称为Perron特征向量.我们在这里不讨论这种方法的理论依据，而通过例子来说明算法.我们来考察由图7.2所示的小型网络，易见网页3无导出链接图7.2其对应的链接矩阵A为：00213121021310003121000A利用MATLAB:A=[0000.5;1/3000;1/30.500.5;1/30.500];1324[V,D]=eig(A);diag(D)输出的四个特征值的模都小于1，且1不是A的特征值。所以，无法利用特征值1对应的特征向量对网页进行排名。（2）存在无法确定排名的情况.考察由图7.3所示的小型网络图7.3该网络由两个互不相连的子网络构成，其对应的链接矩阵A为：00000101002A=1100020000100010利用MATLAB计算可得这个矩阵有1和－1两个二重特征根，还有一个单重特征根0，特征根1对应的两个线性无关的归一化特征向量为：1x0000505T,,,.,.，2x0050500T,.,.,,。显然，利用上述特征向量无法对网页进行排名.Ⅱ.改进的PageRank算法只要对（7.2）式稍作改动，就可以解决由于网页重要性相等而无法确定排名的问题。令n表示网络中包含的网页数，p称为加权因子其取值在0和1之间。则网页k的重要性可以由下式给出：11kjkjLjxxppnn（7.4）12345上式亦可以用如下形式的矩阵方程来表示：xAx+1pps（7.5）其中s是一个元素全为n1的列向量.若规定11niix并记S是一个元素全为n1的n阶方阵，则由Sxs可得：xA+1Sx=Mxpp（7.6）关于矩阵方程(7.6)，可以证明：若A是列随机矩阵，则M亦是列随机矩阵.在11niix的约束条件下，上述方程有唯一解.其解为矩阵M特征根1所对应的归一化特征向量.这样我们就可以解决这类网络的网页排名问题。回到图7.3所示的小型网络，n=5，p=0.85，利用MATLAB：p=0.85;A=[00000;0.50100;0.51000;00001;00010];S=ones(5,5)/5;M=p*A+(1-p)*S;[V,D]=eig(M);diag(D)可以得到M的最大正特征根为1，进而可得其对应的归一化特征向量为Tx)2000.0,2000.0,2850.0,2850.0,0300.0(，利用该特征向量就可以对不同子网络中的网页进行排名.其对应的网页排名为：12345xxxxx.若矩阵A中存在某列全为0，即存在j,aij=0,任意i,则规定矩阵M对应该列的元素均为1/n，这样，M就仍然是列随机矩阵。以图7.2所示的小型网络为例，4n，通常取p=0.85，那么用MATLAB，易得0.03750.03750.25000.46250.32080.03750.25000.0375M0.32080.46250.25000.46250.32080.46250.25000.0375(7.7)而M的模最大的正特征值为1，对应的归一化特征向量为(0.2192,0.1752,0.3558,0.2497)Tx这样我们得到3412xxxx.Ⅲ.PageRank算法-幂法值得注意的是，前面的作为例子的小型网络的规模微小，用数学软件直接求解矩阵方程x=Ax或求A的特征根和特征向量都无困难.当问题的规模很大，甚至A的阶数可能达到上万甚至上亿时，就必须寻找合适的数值计算方法.下面我们介绍用于计算矩阵特征值的幂迭代算法。假设矩阵A的特征值满足条件123n，其中1是特征方程的实根，相应的特征向量1v可以取成实向量，对于任意给定的非零初始向量0x，迭代格式1kkAxx（7.8）称为计算矩阵特征值的幂法.假设A有n个线性无关的特征向量iv),,2,1(ni，则初值0x可以用它们线性表示，即0xiniiv1（7.9）从而幂法的迭代由下式给出0221xAxAAxxkkkk))((211111niiikikniiikivvv（7.10）若对所有的1i，均有11i.所以只要10，当k足够大时，由(7.9）式可得kx111vk,（7.11）1kx1111vk（7.12）即有kkxx11（7.13）而kkAxx1，故有kkxAx1(7.14)这意味着，kx最终会趋于1v.但是，直接采用幂法往往会导致迭代序列趋向于无穷大（而1的绝对值小于1时则会趋于零）.故在每次迭代是应当对kx进行归一化处理，所