Google搜索引擎的数学模型及其应用

1、第卷第期一。西南民族大学学报。自然苎学版文章编号：（）搜索引擎的数学模型及其应用赵国，宋建成（西南民族大学计算机科学与技术学院，四川成都）摘要：该文在阐明搜索引擎中关键的页面等级算法（）原理的基础上，分析了算法的随机冲浪模型，并着重讨论相应的数学模型在足球队排名问题（年全国大学生数学建模竞赛题）中的应用具体做法是综合考虑各队的比赛成绩，为每支球队计算相应的等级分（），然后根据各队的等级分高低来确定名次考虑到竞技比赛结果的不确定性，最后建立了等级分的随机冲浪模型分析表明等级分排名结果具有良好的参数稳定性，并且可以成功地处理数据缺损方面的困难关键词：搜索引擎；算法；随机冲浪模型；足球队排名问题中图

2、分类号：文献标识码：引言据统计，在短短多年的时间里，中产生的信息量相当于人类过去年产生的信息总量，而且上的信息量正以几何级数递增搜索引擎已经成为人们进行信息资源搜索必不可少的工具在众多的搜索引擎中，搜索引擎以其雄厚的技术为支撑，凭借其强大的检索功能和高质量的检索服务，逐渐脱颖而出搜索引擎是由斯坦福大学和共同设计的，它是目前功能最强的搜索引擎通过对亿网页进行整理，可为世界各地的用户提供所需的搜索结果，而且搜索速度极快，通常不到半秒，每天可提供约亿次查询服务图搜索引擎的工作原理示意图图网络的拓扑结构的优势在于掌握的信息量以及检索模型和检索速度传统的搜索引擎在很大程度上取决于文字在网页上出现的频率使

3、用技术检查整个网络链接结构，并确定哪些网页重要性最高然后进行超文本匹配分析（），以确定哪些网页与正在执行的特定搜索相关在综合考虑整体收稿日期：作者简介：赵国（），男，硕士，西南民族大学计算机科学与技术学院讲师，主要研究方向为金融数学、数学模型 基金项目：西南民族大学青年项目第期赵国等：搜索引擎的数学模型及其应用重要性以及与特定查询的相关性之后，可以将最相关最可靠的搜索结果放在最前面搜索引擎的数学模型拥有多项专利技术，其中算法是关键技术之一，它奠定了强大的检索功能及提供各种特色功能的基础虽然每天有很多工程师负责全面改进系统，但是仍把算法作为所有网络搜索工具的基础结构【原理算法是搜索引擎对检索结果

4、的一种排序算法它的基本思想主要是来自传统文献计量学中的文献引文分析，即一篇文献的质量和重要性可以通过其它文献对其引用的数量和引文质量来衡量，也就是说，一篇文献被其它文献引用越多，并且引用它的文献的质量越高，则该文献本身就越重要在给出页面排序时也有两条标准：一是看有多少超级链接指向它；二是要看超级链接指向它的那个页面重要不重要这两条直观的想法就是算法的数学基础，也是搜索引擎最基本的工作原理算法利用了互联网独特的超链接结构在庞大的超链接资源中，提取出上亿个超级链接页面进行分析，制作出一个巨大的网络地图具体的讲，就是把所有的网页看作图里面相应的顶点，如果网页有个指向网页的链接，则认为一条从顶点到顶点

5、的有向边这样就可以利用图论来研究网络的拓扑结构算法正是利用网络的拓扑结构来判断网页的重要性具体来说，假如网页有个指向网页的超链接，就认为网页投了网页一票，说明网页认为网页有链接价值，因而可能是个重要的网页根据指向网页的超链接数及其重要性来判断页面的重要性，并赋予相应的页面等级值（）网页的页面等级值被平均分画己给网页所链接指向的网页，从而当网页的页面等级值比较高时，则网页可从网页到它的超链接分得一定的重要性根据这样的分析，得到了高评价的重要页面会被赋予较高的网页等级，在检索结果内的排名也会较高页面等级值（）是表示网页重要性的综合性指标，而且不会受到不同搜索引擎的影响当然，重要性高的页面如果和检索

6、关键词无关同样也没有任何意义为此，使用了完善的超文本匹配分析技术，使得能够检索出重要而且正确的网页算法算法的具体实现可以利用网页所对应的图的邻接矩阵来表达超链接关系为此，首先写出所对应图的邻接矩阵为了能将网页的页面等级值平均分配给该网页所链接指向的网页，对各个行向量进行归一化一一一处理，得矩阵算法的矩阵是将归一化矩阵转置所得矩阵这样形成的矩阵肜被称为转移概率矩阵，它的各个列向量之和为全概率，各个行矢量表示状态之间的转移概率转移概率矩阵与过程有着密切的联系【】转置的理由是，算法并非重视链接到多少页面，而是重视被多少页面链接各个网页的页面等级值的计算，就是求这个转移概率矩阵的最大特征值所属的特征向

7、量现在以前面给出的三个页面之间的超链接关系为例，说明算法如何计算给定网页的页面等级值，从而定量地知道哪些网页是最重要的为利用网页所对应的图的邻接矩阵来表达链接关系，首先写出所对应图的邻接矩阵为了能将网页的页面等级值平均分配给该网页所链接指向的网页，对各个行向量进行归一化处理，得西南民族大学学报自然科学版第卷彳将归一化所得的矩阵彳转置，所得到的转移概率矩阵（口）为形一现给每个页面尸一个值，这些值应该由链接到该页面的那些页面的值确定，即指向的那些页面的页面等级值之和应该与尸的页面等级值。成正比设共同的比例系数为，则有下面的线性方程组土：，。（）令（而，）为页面等级值组成的列向量，则由矩阵乘法，等式

8、（）可以写成触由此求出转移概率矩阵的最大正特征值五，相应非负特征向量（，），由此可以确定网页的排序为，其中页面，的排序无显著差别，之所以将排在前面是因为指向的超链接数更多一些随机冲浪模型（）算法原理中有个重要的假设：所有的网页形成一个闭合的链接图，除了这些文档以外没有其他任何链接的出入，并且每个网页能从其他网页通过超链接达到但是在现实的网络中，并不完全是这样的情况当一个页面没有出链的时候，它的值就不能被分配给其它的页面同样道理，只有出链接而没有入链接的页面也是存在的但并不考虑这样的页面，因为没有流入的而只流出的，从对称性角度来考虑是很奇怪的吲时，有时候也有链接只在一个集合内部旋转而不向外界链接

9、的现象在现实中的页面，无论怎样顺着链接前进，仅仅顺着链接是绝对不能进入的页面群总归是存在的技术为了解决这样的问题，提出用户的随机冲浪模型：用户虽然在大多数场合都顺着当前页面中的链接前进，但有时会突然重新打开浏览器随机进入到完全无关的页面认为：用户在的情况下沿着链接前进，但在的情况下会跳跃到无关的页面中用公式表示相应的转移概率矩阵为一：！型门。其中，为分量全为的胛维列向量，从而为全矩阵，（，）为权重因子（），在实际中取也就是说，在随机冲浪模型中，求各个页面等级值的问题变成了求正矩阵形的最大特征值所属的特征向量问题还是考虑前面给出的三个网页、之间的超链接关系，在随机冲浪模型下为方便计算令，相应的转

10、移概率矩阵为一：螋，）根据著名的定理【】，转移概率矩阵的最大正特征值是，相应的特征向量为（，）由此可以确定网页的排序为，可见随机冲浪模型下的排序结果更合理一些第期赵国等：搜索引擎的数学模型及其应用页面等级算法的应用首先我们从图论的角度解释算法的原理：一是看这个页面对应顶点的入度；二是要给指向该顶点的边赋予权重，表明这个超级链接的重要性具体的讲，就是把所有的页面看作图里面的点，然后给每个页面一个数量，用这个数量来刻画页面的重要性，这样网页的重要性就脱离了它的具体内容我们只需从网络拓扑结构出发研究网页的重要性，这样就可以用图论来研究向互联网这样的随机复杂网络而且按照这个原理对网页排序具有三个优点：

11、第一，排序与特定搜索关键词无关；第二，网页排序与网页的具体内容无关；第三，只需要知道网页所对应的图的结构算法的这个特点使得它可以被应用于社会领域的其他问题例如体育比赛的排名问题下面针对年全国大学生数学建模竞赛题，利用算法讨论足球队排名次问题，我们发现随机冲浪模型可以有效克服数据缺损等方面的凼难足球队排名次问题要求我们建立一个客观的评估方法，只依据过去一段时间（几个赛季或几年）内每个球队的战绩给出各个球队的名次，具有很强的实际背景【通过分析题中支足球队在联赛中的成绩，不难发现表中的数据残缺不全，队与队之间的比赛场数相差很大，直接根据比赛成绩来排名次比较困难下面我们利用算法的随机冲浪模型来求解类比

12、算法，我们可以综合考虑各队的比赛成绩为每支球队计算相应的等级分（），然后根据各队的等级分高低来确定名次直观上看，给定球队的等级分应该由它所战胜和战平的球队的数量以及被战胜或战平的球队的实力共同决定具体来说，确定球队的等级分的依据应为：一是看它战胜和战平了多少支球队；二要看它所战胜或战平球队的等级分的高低这两条就是我们确定排名的基本原理在实际中，若出现等级分相同的情况，可以进一步根据净胜球的多少来确定排名由于表中包含的数据量庞大，我们先在不计平局，只考虑获胜局的情形下计算出各队的等级分，以说明算法原理然后我们综合考虑获胜局和平局，加权后得到各队的等级分，并据此进行排名考虑到竞技比赛的结果的不确定

13、性，我们最后建立了等级分的随机冲浪模型，分析表明等级分排名结果具有良好的参数稳定性获胜局的等级分首先利用有向赋权图的权重矩阵来表达出各队之间的胜负关系用图的顶点表示相应球队，用连接两个顶点与丁，的有向边表示两队的比赛结果，同时给该边赋予相应的权重，表明战胜丁，的次数由此，可以写出表中支球队所对应的有向赋权图的权重矩阵例如，表中五与瓦比赛了两场，各胜一场，故瓦。，瓦，同理，互。表明正曾次战胜正注意到被战胜球队的等级分应该平均分配给各个获胜球队，将权重矩阵的各个列向量向量进行归一化，得转移概率矩阵。）为西南民族大学学报自然科学版第卷铷；仉现设每个队的等级分，这些等级分应由被战胜的那些队的等级分确定

14、，即谤，“一，（）其中五为比例系数令（，一，），则由矩阵乘法，等式（）可以写成缸即各个队的等级分的计算，转化求这个转移概率矩阵的最大正特征值旯所属的正特征向量直接利用软件计算得五，相应等级分为（，）由此可以确定只算获胜局的情况下各队的排名为，。，加权等级分在实际中，平局也会队双方的排名产生影响，因此也有必要考虑平局对等级分的贡献因为平局是相互的，所以可以利用无向赋权图的权重矩阵来表达出各队之间的平局关系，即，注意平局的权重矩阵尸是对称的同时注意到被战平球队的等级分也应该平均分配给各个与之战平的球队，故将权重矩阵的各个列向量向量进行归一化处理，得转移概率矩阵第期 赵国等：搜索引擎的数学模型及其应

15、用 根据常识，在一场比赛中平局出现的概率为三同时，考虑到通常平局与获胜局的得分比为：，我们可以 对平局和获胜局的转移概率矩阵进行加权处理，得到下面的加权权重矩阵 形二××二×× 同样，被战胜或战平球队的等级分也应该平均分配给各个获胜队或与之战平的球队，故将加权权重矩阵的各个 列向量向量进行归一化，得转移概率矩阵形（）为 现设每个队的等级分为，这些等级分应由所战胜或战平的那些队的等级分确定，即 佗一 帚 ，。， （） 万方数据 西南民族大学学报自然科学版 第卷 其中五为比例系数令（，一，），则由矩阵乘法，等式（）可以写成 即各个队的等级分的计算，转化求平局

16、的转移概率矩阵矩阵的最大正特征值名所属的非负特征向量直 接利用软件计算得力，相应等级分为 （ ， ， ， ， ， ， ） 由此可以确定在综合考虑获胜局和平局的情况下各队的排名为 ，：，。，：，。 等级分的随机冲浪模型 在大多数时候，竞技比赛的结果都是两队之间实力的客观反映但是，竞技比赛的结果有时具有一定的不 确定性，它很容易受到某些偶然或人为因素的影响为了消除这些不确定因素的影响，我们需要建立等级分的 随机冲浪模型 设球队的实力能确定比赛的结果的概率为，即强队因为不确定因素输掉给任意一支球队的概率为一 则可得下面的转移概率矩阵 矿：木万坐幸 疗 其中，为分量全为的疗维列向量，从而丁为全矩阵；（，）为权重因子，在实际中可以根据历史数据 确定同样，各个队的等级分的计算，转化求转移概率矩阵形最大正特征值所属的正特征向量 下面着重分析权重因子（，）的变化对排名的影响为此，我们利用软件计算出权重因子取不 同的值时的排智隋况如表 表权重因子取不同的值时的排名情况 取值范围 球队排名 ，：，。，：，。 ，：，。，：， ，：，。，：，。 ，：，。，：，。，