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

[实验七] 搜索引擎的网页排名问题

姓名：蒋芬

学号：1012211139

一、 实验目的

本实验涉及线性代数的一些知识，通过搜索引擎的排名算法介绍了正矩阵，列随机矩阵的一些性质，特征值与特征向量的关系以及用于计算矩阵特征值的幂迭代法.

二、 问题的提法

今天，如果你打算了解某种信息，多半会利用互联网.在google首页搜索栏输入一些关键词，跟此有关的网页会很快迅速显示出来，也许只用不到一秒钟.而且这些网页会依照某些次序排列，通常是越靠前的越重要(也许是关注的人越多).那么google的搜索引擎是如何做到这一点的呢？

三、 背景介绍

随着互联网的高速发展，网络已经成为现代人生活的一个重要组成部分. 从网络上搜索信息已成为继电子邮件后的第二大互联网应用. Google搜索引擎是世界上最大的免费搜索引擎. 目前，它对超过80多亿个网页进行整理，每天需提供的查询服务超过2亿次.

当我们在Google搜索引擎中输入一些关键词后，Google会在很短的时间内从数以亿计的网页中搜索与关键词匹配的网页，并给网页的显示顺序. 事实上，Google会定期地对互联网上所用的网页进行搜索，并将结果保存在自己的数据库中. 所以，表面上看是我们通过Google进行网上搜索，而实际是在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现在还在使用中，不过已经是一个更大的系统中的一部分.

其他部分还包括语言模块，查询模块，时间模块，个性化模块等.

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个导入链接. 1 2

3 4

5 Ⅱ 邻接矩阵

有向图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=[0 0.5 0 0 0;0.5 0 1 0 0;0.5 0 0 0.5 0.5;0 0.5 0 0 0.5;0 0 0 0.5

0];

[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=[0 0 0 0.5;1/3 0 0 0;1/3 0.5 0 0.5;1/3 0.5 0 0]; 1

3 2

4 [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） 1 2

3 4

5 上式亦可以用如下形式的矩阵方程来表示：

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=[0 0 0 0 0;0.5 0 1 0 0;0.5 1 0 0 0;0 0 0 0 1;0 0 0 1 0];

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)