搜索引擎的网页排名

搜索引擎的网页排名

内容提要Google

网页排名的数学原理图与网络回顾线性代数的相关内容某些有关矩阵特征值知识的介绍计算矩阵特征值的幂迭代法Matlab

中矩阵运算实际问题现今，若你打算了解某种信息，多半会利用互联网，在Google(或百度)搜索引擎中输入一些而且这些网址会依照某些次序排列，通常是越靠关键词后，与此有关的网页地址会很快显示出来，前的越重要(意味着关注的人越多).那么google的搜索引擎是如何做到这一点的呢？准备知识而数组称为边(或连线),在数组两个元素有次序时联系(用数组表示)称为图D

,元素称为顶点，非空集合以及其中元素间的图的表示是十分形象的，则图称为有向图例1:右图就表示了有4个顶点6条边的有向图1234邻接矩阵将有向图转化为代数形式表示则称矩阵G=｛gij｝为邻接矩阵例1的4个顶点6条连线的有向图的邻接矩阵为对于有向图D，定义1234设某个网络包含n个网页，每个网页用一个网络与有向图数字k(1≤k≤n)标记，则该网络可用一个有向则表示网页间链接，当有网页j上有连到网页i图表示，其中每个顶点看成是一个网页，而边的链接，称网页j为网页i的导入链接，而称网页i为网页j的导出链接例1的有向图可表示含4个网页的小网络,网页1、4各有一个导入链接,2、3各有2个导入链接1234简化的PageRank算法

最简方法看谁的导入链接更多

12345若用正数xk表示某网络中第k个网页的重要

性，那么xi>xj表示网页i比网页j更重要例2导入链接数：x3=3,x2=x4=2,x1=x5=1问题：1）未考虑导入链接网页的重要性2)并列数能否区分(例如2、4)

调整

增加考虑网页的质量因素设网页j包含nj个导出链接，则可认为网页j的重要性被平分赋予其导出链接的网页上，这些网页均获得重要性数值为,记Lk为链接到网页k

的那些网页标记的集合,那么引进链接矩阵A，其元素那么记，就有这方程的解就是矩阵A对应于特征根1的特征向量

这意味着我们要求的体现网页重要性的向量考虑特征向量构成线性空间，规定x为矩阵A对应于特征根1的归一化特征向量

注:将邻接矩阵的每列除以该列元素之和就得到A方程有解吗若一个方阵的所有元素非负，且每列的和均为1，则该方阵称为列随机矩阵定理1：列随机矩阵一定存在特征根1

若网络的链接矩阵A是列随机矩阵,方程可解例2网络的链接矩阵A可解此方程使用MatlabA=[00.5000;0.50100;0.5000.50.5;00.5000.5;0000.50];[V,D]=eig(A);diag(D)键入会得到A的特征值(第1个是1).再键入abs(V(:,1))/norm(V(:,1),1)得到对应1的特征向量依然有问题1）网络的链接矩阵有某列元素全为零(存在导出链接数为0的网页)可能特征值中不含1！1324例3Matlab求特征值A=[0000.5;1/3000;1/30.500.5;1/30.500];[V,D]=eig(A);diag(D)2）依然可能出现无法排名的情况12345例4A=[00000;1/20100;1/21000;00001;00010];[V,D]=eig(A);diag(D)利用Matlab

特征值1对应的归一特征向量(两个)，均无法排序改进的PageRank算法修改方程为其中P是加权因子(小于1的正数,常取0.85)，这的赋予，还有一个最低数据(即使无导出链接)意味着标志网页重要性的数据大部分来自各网页这样若以S表示所有元素均为的方阵，依然要求x是归一化的，则Sx就是元素均的列向量记M=[pA+(1-p)S],方程为x=Mx(*)情况讨论1)A是列随机矩阵易见M也是列随机矩阵，且此时(*)有唯一归一化解,也就是M的特征根1所对应的特征向量考虑原来方法未能解决的例4，n=5取p=0.85,利用M求特征值1和相应特征向量就可以解决排名问题p=0.85;A=[00000;1/20100;1/21000;00001;00010];S=ones(5,5)/5;M=p*A+(1-p)*S;[V,D]=eig(M);diag(D)使用

Matlab得到特征值1(第2个)，再由abs(V(:,2))/norm(V(:,2),1)说明x2=x3>x4=x5>x1（并列合理吗?）2)A有某列元素全为零M对应的列元素全为(1－p)/n,不是列随机矩阵解决方法是■可把这列元素都换成1/n，得到列随机矩阵去求特征根1所对应的归一化特征向量■

也可直接求M的最大的正特征根，同时求得对应的归一化特征向量得到的排名结果是相同的(理论：Perron-Frobnius定理)例3的排名实现-使用Matlabp=0.85;A=[0001/2;1/3000;1/31/201/2;1/31/200];S=ones(4,4)/4;M=p*A+(1-p)*S;[V,D]=eig(M);diag(D)M1=M;M1(:,3)=ones(1,4)/4[V1,D1]=eig(M1);diag(D1)直接对M修改MPageRank算法-幂法

当问题的规模很大，甚至A的阶数可能达到幂迭代算法上万甚至上亿时，必须寻找合适的数值计算方法设矩阵A的特征值满足λ1是特征方程的实根，相应的特征向量v1可以取实向量,则任给初始向量x0，幂法迭代格式为xk=Axk-1假设A有n个线性无关的特征向量vi,则初值可用它们线性表示，即x0依照幂法说明xk最终趋于v1正式迭代格式防止迭代使数据趋无穷大或无穷小其中对例3，取x0＝（0,0,0,1)T,只需迭代不足20次，就可以得到与前面方法同样的结果用Matlab可以容易实现这计算M=[0.0375,0.0375,0.0375,0.4625;0.32083,0.0375,0.0375,0.0375;0.32083,0.4625,0.0375,0.4625;0.32083,0.4625,0.0375,0.0375];x(:,1)=[0,0,0,1]';y(:,1)=[0,0,0,1]';fork=2:20y(:,k)=M*x(:,k-1);x(:,k)=y(:,k)/norm(y(:,k),1);endx使用Matlab实验任务见教材

补充说明本例所介绍的内容有多种应用再举一例实际问题－循环赛的名次若干球队进行两两交锋