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

[实验七] 搜索引擎的网页排名问题 姓名：蒋芬 学号：1012211139 实验目的 本实验涉及线性代数的一些知识，通过搜索引擎的排名算法介绍了正矩阵，列随机矩阵的一些性质，特征值与特征向量的关系以及用于计算矩阵特征值的幂迭代法. 问题的提法 今天，如果你打算了解某种信息，多半会利用互联网.在google首页搜索栏输入一些关键词，跟此有关的网页会很快迅速显示出来，也许只用不到一秒钟.而且这些网页会依照某些次序排列，通常是越靠前的越重要(也许是关注的人越多).那么google的搜索引擎是如何做到这一点的呢？ 背景介绍 随着互联网的高速发展，网络已经成为现代人生活的一个重要组成部分. 从网络上搜索信息已成为继电子邮件后的第二大互联网应用. Google搜索引擎是世界上最大的免费搜索引擎. 目前，它对超过80多亿个网页进行整理，每天需提供的查询服务超过2亿次. 当我们在Google搜索引擎中输入一些关键词后，Google会在很短的时间内从数以亿计的网页中，显示顺序Google PageRank是Google独有的搜索引擎排名算法, 作用是衡量特定网页相对于搜索引擎索引中的其他网页而言的重要程度. 它是由Larry Page和Sergey Brin在20世纪90年代后期发明的. Page Rank实现了将链接价值概念作为排名因素. 我们知道Google 工具条上有一个绿色的PageRank标尺，就是用来指示网站的链接广泛度的。 PageRank值从0到10.这里的链接包括网站内部链接、导出链接和导入链接，其中最重要的是导入链接. Google通过统计这些链接的质量和数量来给网站确定PageRank值，值越高排名也就越高. 如果你想查看自己站点的PR值，可以访问：/T5/intl/zh-CN/index.html ，下载Google的工具栏，就可以看到自己网站的PR值. Google PageRank现在还在使用中，不过已经是一个更大的系统中的一部分其他部分还包括语言模块，查询模块，时间模块，个性化模块. 数学模型 Ⅰ．有向图的定义 数学中所谓的“图”是指某类具体事物和这些事物之间的联系.如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象. 记这些点为，而它们的连线用表示，记为，那么一个图是指一个二元组，其中: 1) 是非空有限集，称为顶点集，其中元素称为图的顶点. 2）2）是顶点集中的无序或有序的元素对组成的集合，称为边集,其中的元素称为边. 若图G中的边均为无序对，称G为无向图，若图G中的边均为有序对，称G为有向图. 图7.1 这样，假定某个网络包含n个网页，每个网页用一个数字k标记，。则该网络可以用一个有向图来表示，其中每个顶点看成是一个网页，边(箭头)表示从一个网页到另一个网页的链接. 当网页j 上有连到网页i的链接，则称网页j为网页i的导入链接，而称网页i为网页j 的导出链接. 比如，图7.1就可以看成是一个包含5个网页8个链接的小型网络，其中网页3有3个导入链接. Ⅱ 邻接矩阵 有向图的邻接矩阵为，其中 （7.1） 对于图7.1所示的有向图，其邻接矩阵为 我们用表示某个网络中第k个网页的重要性，是一个非负的正数，若则表示第i个网页的重要性大于第j个网页的重要性. 排名问题的算法 Ⅰ. 简化的PageRank算法 一种简单的衡量某个网页重要性的方法是看谁的导入链接最多. 由图7.1可得：，，，，. 从而得到第3个网页的重要性最大，第2，4个网页的重要性其次，而第1，5个网页的重要性最小. 然而上述排名算法显然不能令人满意，它不能区分第2，第4两个网页和第1，第5两个网页哪个更重要. 一种改进的做法是除了考虑导入链接的数量外，还应考虑导入链接的质量，即来自一个重要性相对较高网页的链接可以增加该网页的重要性. 用数学语言可表达如下： 若网页j包含个导出链接，其中的某个链接到了网页k (即第k个网页)，则该链接赋给网页k的重要性为，即网页j的重要性被平分到其每个导出链接上. 令(注意这里的数字是表示网页的标记)为链接到网页k的那些网页的集合，则网页k的重要性可以由下式得到 （7.2） 如果引进矩阵A称为链接矩阵，其元素 那么(7.2)式等价于，也即等价于矩阵方程 （7.3） 其中. 不难验证： 其中为邻接矩阵，为对角矩阵. 注意方程(7.3)的解就是矩阵A对应于特征根1的特征向量，若规定，则对应的解就是矩阵A对应于特征根1的归一化特征向量. 定义1：若一个方阵的所有元素均非负，且每列的和均为1，