搜索引擎的网页排名.doc
《搜索引擎的网页排名.doc》由会员分享，可在线阅读，更多相关《搜索引擎的网页排名.doc（15页珍藏版）》请在冰点文库上搜索。
[实验七]搜索引擎的网页排名问题
姓名：
蒋芬
学号：
1012211139
一、实验目的
本实验涉及线性代数的一些知识，通过搜索引擎的排名算法介绍了正矩阵，列随机矩阵的一些性质，特征值与特征向量的关系以及用于计算矩阵特征值的幂迭代法.
二、问题的提法
今天，如果你打算了解某种信息，多半会利用互联网.在google首页搜索栏输入一些关键词，跟此有关的网页会很快迅速显示出来，也许只用不到一秒钟.而且这些网页会依照某些次序排列，通常是越靠前的越重要（也许是关注的人越多）.那么google的搜索引擎是如何做到这一点的呢？
三、背景介绍
随着互联网的高速发展，网络已经成为现代人生活的一个重要组成部分.从网络上搜索信息已成为继电子邮件后的第二大互联网应用.Google搜索引擎是世界上最大的免费搜索引擎.目前，它对超过80多亿个网页进行整理，每天需提供的查询服务超过2亿次.
当我们在Google搜索引擎中输入一些关键词后，Google会在很短的时间内从数以亿计的网页中搜索与关键词匹配的网页，并给网页的显示顺序.事实上，Google会定期地对互联网上所用的网页进行搜索，并将结果保存在自己的数据库中.所以，表面上看是我们通过Google进行网上搜索，而实际是在Google网站的数据库里进行搜索.
那么Google又是如何给出网页的排名情况的呢？
这就要从搜索引擎排名算法说起.GooglePageRank是Google独有的搜索引擎排名算法,作用是衡量特定网页相对于搜索引擎索引中的其他网页而言的重要程度.它是由LarryPage和SergeyBrin在20世纪90年代后期发明的.PageRank实现了将链接价值概念作为排名因素.
我们知道Google工具条上有一个绿色的PageRank标尺，就是用来指示网站的链接广泛度的。
PageRank值从0到10.这里的链接包括网站内部链接、导出链接和导入链接，其中最重要的是导入链接.Google通过统计这些链接的质量和数量来给网站确定PageRank值，值越高排名也就越高.
如果你想查看自己站点的PR值，可以访问：
，下载Google的工具栏，就可以看到自己网站的PR值.
GooglePageRank现在还在使用中，不过已经是一个更大的系统中的一部分.其他部分还包括语言模块，查询模块，时间模块，个性化模块等.
PageRank算法主要用到了线性代数的一些知识，包括正矩阵，列随机矩阵的一些性质，特征值与特征向量的关系以及用于计算矩阵特征值的幂迭代法.
四、数学模型
Ⅰ．有向图的定义
数学中所谓的“图”是指某类具体事物和这些事物之间的联系.如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象.
记这些点为，而它们的连线用表示，记为，那么一个图是指一个二元组，其中:
1）是非空有限集，称为顶点集，其中元素称为图的顶点.
2）2）是顶点集中的无序或有序的元素对组成的集合，称为边集,其中的元素称为边.若图G中的边均为无序对，称G为无向图，若图G中的边均为有序对，称G为有向图.
1
2
3
4
5
图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，则该方阵称为列随机矩阵.
由上述定义可知，若某个网络的每个网页都有导出链接，则其链接矩阵必为列随机矩阵.
定理1：
列随机矩阵一定存在特征根1.
证明：
记A是一个n阶的列随机矩阵，e是一个n维的元素全为1的列向量。
由定义1，易知，即1是矩阵的特征根。
又因为A与有相同的特征根，所以A一定存在特征根1。
例如，由图7.1所示的小型网络，可得：
利用MATLAB：
在命令窗口键入:
A=[00.5000;0.50100;0.5000.50.5;00.5000.5;0000.50];
[V,D]=eig（A）;
diag（D）
就得到矩阵A的所有特征值，包括特征值1.再键入
abs（V（:
1））/norm（V（:
1）,1）
则可以得到A对应于特征根1的归一化特征向量.
这说明按照上述方法的网页排名为：
。
然而，上述方法仍然存在以下不足：
（1）若网络中存在导出链接数为0的网页，则链接矩阵A中必存在某列全为0.此时，可验证A的所有特征值的模都小于等于1，且1不一定是A的特征值.
解决这个问题的方法是采用所谓的Perron特征向量来进行排名，即A中一定存在一个正的特征值，其对应的正的归一化特征向量称为Perron特征向量.我们在这里不讨论这种方法的理论依据，而通过例子来说明算法.
我们来考察由图7.2所示的小型网络，易见网页3无导出链接
1
3
2
4
图7.2
其对应的链接矩阵为：
利用MATLAB:
A=[0000.5;1/3000;1/30.500.5;1/30.500];
[V,D]=eig（A）;
diag（D）
输出的四个特征值的模都小于1，且1不是A的特征值。
所以，无法利用特征值1对应的特征向量对网页进行排名。
（2）存在无法确定排名的情况.
考察由图7.3所示的小型网络
1
2
3
4
5
图7.3
该网络由两个互不相连的子网络构成，其对应的链接矩阵A为：
利用MATLAB计算可得这个矩阵有1和－1两个二重特征根，还有一个单重特征根0，特征根1对应的两个线性无关的归一化特征向量为：
，。
显然，利用上述特征向量无法对网页进行排名.
Ⅱ.改进的PageRank算法
只要对（7.2）式稍作改动，就可以解决由于网页重要性相等而无法确定排名的问题。
令n表示网络中包含的网页数，p称为加权因子其取值在0和1之间。
则网页k的重要性可以由下式给出：
（7.4）
上式亦可以用如下形式的矩阵方程来表示：
（7.5）
其中s是一个元素全为的列向量.若规定并记S是一个元素全为的n阶方阵，则由可得：
（7.6）
关于矩阵方程（7.6），可以证明：
若A是列随机矩阵，则M亦是列随机矩阵.在的约束条件下，上述方程有唯一解.其解为矩阵M特征根1所对应的归一化特征向量.这样我们就可以解决这类网络的网页排名问题。
回到图7.3所示的小型网络，n=5，p=0.85，利用MATLAB：
p=0.85;
A=[00000;0.50100;0.51000;00001;00010];
S=ones（5,5）/5;
M=p*A+（1-p）*S;
[V,D]=eig（M）;
diag（D）
可以得到M的最大正特征根为1，进而可得其对应的归一化特征向量为
，
利用该特征向量就可以对不同子网络中的网页进行排名.其对应的网页排名为：
.
若矩阵A中存在某列全为0，即存在j,aij=0,任意i,则规定矩阵M对应该列的元素均为1/n，这样，M就仍然是列随机矩阵。
以图7.2所示的小型网络为例，，通常取p=0.85，那么用MATLAB，易得
（7.7）
而M的模最大的正特征值为1，对应的归一化特征向量为
这样我们得到
.
Ⅲ.PageRank算法-幂法
值得注意的是，前面的作为例子的小型网络的规模微小，用数学软件直接求解矩阵方程x=Ax或求A的特征根和特征向量都无困难.当问题的规模很大，甚至A的阶数可能达到上万甚至上亿时，就必须寻找合适的数值计算方法.下面我们介绍用于计算矩阵特征值的幂迭代算法。
假设矩阵A的特征值满足条件，其中是特征方程的实根，相应的特征向量可以取成实向量，对于任意给定的非零初始向量，迭代格式
（7.8）
称为计算矩阵特征值的幂法.假设A有n个线性无关的特征向量，则初值可以用它们线性表示，即
（7.9）
从而幂法的迭代由下式给出
（7.10）
若对所有的，均有.所以只要，当k足够大时，由（7.9）式可得
（7.11）
（7.12）
即有
（7.13）
而，故有
（7.14）
这意味着，最终会趋于.但是，直接采用幂法往往会导致迭代序列趋向于无穷大（而的绝对值小于1时则会趋于零）.故在每次迭代是应当对进行归一化处理，所以上述算法可以改写为
（7.15）
其中（7.16）
例如再次考察图7.2所示的小型网络，相应的矩阵M如（7.7）式所示.那么给定初始向量，利用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:
20
y（:
k）=M*x（:
k-1）;
x（:
k）=y（:
k）/norm（y（:
k）,1）;
end
经计算得到幂法的迭代20次的序列如下：
表7.1
k
k
0
7
1
10
2
13
3
15
4
16
5
17
（后两次的迭代结果完全相同，故未列出），从上表中可以看到，经过不足20步迭代，就可以得到与前面方法同样的排名结论.
注意在网页数量很大时，迭代运算需要更多有效数字，迭代次数一般也会更多，才能使得归一化特征向量的各分量有序从而确定网页排名.
六、实验任务
1.在改进的PageRank算法讨论图7.2所示的小型网络时，我们取p=0.85，请依次改取p=0.75，p=0.8或p=0.9，然后观察网页排名结果的变化情况.
建立m文件：
functionm7_1（p）
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）
（abs（V（:
1））/norm（V（:
1）,1））'
取p=0.85时运行结果为：
m7_1（0.85）
ans=
0.6618
-0.2427+0.2257i
-0.2427-0.2257i
-0.0264
ans=
0.21230.14750.39790.2423
所以网页排名为：
取p=0.75时运行结果为：
m7_1（0.75）
ans=
0.7184
-0.2166+0.1999i
-0.2166-0.1999i
-0.0352
ans=
0.21580.16210.37550.2467
取p=0.8时运行结果为：
m7_1（0.8）
ans=
0.6909
-0.2297+0.2128i
-0.2297-0.2128i
-0.0315
ans=
0.21400.15500.38630.2447
取p=0.9时运行结果为：
m7_1（0.9）
ans=
0.6307
-0.2555+0.2385i
-0.2555-0.2385i
-0.0197
ans=
0.21050.13980.41030.2395
由上面当p取0.85；0.75；0.8；0.9时得到的网页排名任然为：
2.计算图7.4所示小型网络的排名，分析其排名与图7.2所示小型网络排名发生变化的原因.
1
3
2
4
图7.4
图7.4的衔接矩阵为
x=[0011/2;1/3000;1/31/201/2;1/31/200]
x=
001.00000.5000
0.3333000
0.33330.500000.5000
0.33330.500000
使用MATLAB建立m文件有助于分析其网页排名，m文件如下：
functionm7_2（p）
A=[0011/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）
（abs（V（:
1））/norm（V（:
1）,1））'
取p=0.85，运行得到结果为：
m7_2（0.85）
ans=
1.0000
-0.3065+0.3493i
-0.3065-0.3493i
-0.2369
ans=
0.36820.14180.28800.2021
所以网页排名为：
3.利用幂法计算图7.5所示网络的排名.
1
3
2
4
10
7
8
5
6
9
图7.5
图7.5的衔接矩阵为：
利用MATLAB建立m文件：
functionm7_3（p）
A=[0000001/2001/2;1/20000001/300;1/21/200000000;
001/30000000;01/2010001/31/20;001/30100001/2;
001/30000000;0000001/2000;00000001/300;
000000001/20;];
S=ones（10,10）/10;
M=p*A+（1-p）*S;
x（:
1）=[0000000001]';
y（:
1）=[0000000001]';
fork=2:
35
y（:
k）=M*x（:
k-1）;
x（:
k）=y（:
k）/norm（y（:
k）,1）;
end
x'
运行m7_3（0.85）得到结果：
m7_3（0.85）
ans=
0000000001.0000
0.44000.01500.01500.01500.01500.44000.01500.01500.01500.0150
0.04430.32950.33290.03080.07150.06130.03080.03410.03080.0341
0.04490.04590.18340.11530.21510.19470.11530.02960.02600.0296
0.09180.05090.06420.08030.18210.31450.08030.07670.02800.0312
0.08510.10340.10320.04530.18900.27470.04530.06700.05010.0367
0.06510.09160.12410.05770.17970.28770.05770.04470.04430.0474
0.07900.07320.10800.06640.17800.29520.06640.05230.03660.0448
0.08310.08460.10640.06090.17750.28830.06090.05770.03980.0408
0.07710.08830.11430.05980.18010.28260.05980.05410.04150.0423
0.07680.08310.11230.06240.17950.28750.06240.05320.03990.0430
0.07910.08300.10980.06200.17910.28800.06200.05490.03980.0423
0.07850.08500.11110.06110.17930.28650.06110.05470.04050.0423
0.07790.08440.11170.06140.17940.28670.06140.05410.04030.0426
0.07830.08390.11100.06170.17930.28720.06170.05440.04010.0425
0.07840.08420.11100.06150.17930.28700.06150.05450.04020.0424
0.07820.08440.11130.06140.17930.28680.06140.05440.04030.0424
0.07820.08420.11120.06150.17930.28700.06150.05440.04020.0425
0.07830.08420.11110.06150.17930.28700.06150.05440.04020.0424
0.07830.08420.11120.06150.17930.28690.06150.05440.04020.0424
0.07830.08420.11120.06150.17930.28690.06150.05440.04020.0425
0.07830.08420.11120.06150.17930.28700.06150.05440.04020.0425
0.07830.08420.11120.06150.17930.28690.06150.05440.04020.0424
0.07830.08420.11120.06150.17930.28690.06150.05440.04020.04
升级会员 