搜索引擎的网页排名[32页].ppt

搜索引擎的网页排名内容提要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可解此方程