当前位置：文档库 › 搜索引擎的网页排名问题数学实验报告

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

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

姓名：蒋芬

学号：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 值，可以访问：

https://www.wendangku.net/doc/ed2558835.html,/T5/intl/zh-CN/index.html ，下载Google 的工具栏，就可以看到自己网站的PR 值.

Google PageRank 现在还在使用中，不过已经是一个更大的系统中的一部分. 其他部分还包括语言模块，查询模块，时间模块，个性化模块等.

PageRank 算法主要用到了线性代数的一些知识，包括正矩阵，列随机矩阵的一些性质，特征值与特征向量的关系以及用于计算矩阵特征值的幂迭代法. 四、数学模型

Ⅰ．有向图的定义

数学中所谓的“图”是指某类具体事物和这些事物之间的联系.如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象.

记这些点为)2,1(n i v i =，而它们的连线用),(j i v v 表示，记为k e ，那么一个图G 是指一个二元组))(),((G E G V ，其中:

1) (){}n v v v G V ,,,21 =是非空有限集，称为顶点集，其中元素称为图G 的顶点.

2）},,,{)(21m e e e G E =是顶点集)(G V 中的无序或有序的元素对),(j i v v 组成的集合，称为边集,其中的元素称为边. 若图G 中的边均为无序对，称G 为无向图，若图G 中的边均为有序对，称G 为有向图.

图7.1

这样，假定某个网络包含n 个网页，每个网页用一个数字k 标记，

1k n ≤≤。则该网络可以用一个有向图来表示，其中每个顶点看成是一个网页，边(箭头)表示从一个网页到另一个网页的链接. 当网页j 上有连到网页i 的链接，则称网页j 为网页i 的导入链接，而称网页i 为网页j 的导出链接. 比如，图7.1就可以看成是一个包含5个网页8个链接的小型网络，其中网页3有3个导入链接.

4 5

Ⅱ 邻接矩阵

有向图G 的邻接矩阵为{}

G ij g =，其中

??=.01的连线到若不存在元素从的连线，到元素若存在从i j i j g ij （7.1）

对于图7.1所示的有向图，其邻接矩阵为

00010100G 1

0011010010

001

0????????=????????

我们用k x 表示某个网络中第k 个网页的重要性，k x 是一个非负的正数，若

i j x x >则表示第i 个网页的重要性大于第j 个网页的重要性.

五、排名问题的算法

Ⅰ. 简化的PageRank 算法

一种简单的衡量某个网页重要性的方法是看谁的导入链接最多. 由图7.1可得：11x =，22x =，33x =，42x =，51x =. 从而得到第3个网页的重要性最大，第2，4个网页的重要性其次，而第1，5个网页的重要性最小.

然而上述排名算法显然不能令人满意，它不能区分第2，第4两个网页和第1，第5两个网页哪个更重要. 一种改进的做法是除了考虑导入链接的数量外，还应考虑导入链接的质量，即来自一个重要性相对较高网页的链接可以增加该网页的重要性. 用数学语言可表达如下：

若网页j 包含j n 个导出链接，其中的某个链接到了网页k (即第k 个网页)，则该链接赋给网页k 的重要性为

j n x ，即网页j 的重要性被平分到其每个导出链接

上. 令{}1,2,,k L n ? (注意这里的数字是表示网页的标记)为链接到网页k 的那些网页的集合，则网页k 的重要性可以由下式得到

k j L j

x x n

∈=

∑ （7.2）

如果引进矩阵A 称为链接矩阵，其元素

?????=..

1其他，

链接到网页若从网页i j n a j

那么(7.2)式等价于j n

j kj k x a x ∑==1

，也即等价于矩阵方程

x Ax = （7.3）

其中()12x T

n x ,x ,x = .

不难验证：

A=GD

其中G 为邻接矩阵，}1

,,1,1{diag D 21n

n n n =为对角矩阵.

注意方程(7.3)的解就是矩阵A 对应于特征根1的特征向量，若规定1

i x

==∑，

则对应的解就是矩阵A 对应于特征根1的归一化特征向量.

定义1：若一个方阵的所有元素均非负，且每列的和均为1，则该方阵称为列随机矩阵.

由上述定义可知，若某个网络的每个网页都有导出链接，则其链接矩阵必为列随机矩阵.

定理1：列随机矩阵一定存在特征根1.

证明：记A 是一个n 阶的列随机矩阵，e 是一个n 维的元素全为1的列向量。由定义1，易知e e A =T ，即1是矩阵T A 的特征根。又因为A 与T A 有相同的特征根，所以A 一定存在特征根1。

例如，由图7.1所示的小型网络，可得：

????????????

?=02

0210021021210021001021000210A 利用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的归一化特征向量.

()x 0153803077023080205101026T

.,.,.,.,.=

这说明按照上述方法的网页排名为：23415x x x x x >>>>。

然而，上述方法仍然存在以下不足：

（1）若网络中存在导出链接数为0的网页，则链接矩阵A 中必存在某列全为0. 此时，可验证A 的所有特征值的模都小于等于1，且1不一定是A 的特征值.

解决这个问题的方法是采用所谓的Perron 特征向量来进行排名，即A 中一定存在一个正的特征值1λ≤，其对应的正的归一化特征向量称为Perron 特征向量. 我们在这里不讨论这种方法的理论依据，而通过例子来说明算法.

我们来考察由图7.2所示的小型网络，易见网页3无导出链接

图7.2

其对应的链接矩阵A 为：

??????????

? ??

=00

121021310003

121000A 利用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];

[V,D]=eig(A); diag(D)

输出的四个特征值的模都小于1，且1不是A 的特征值。所以，无

法利用特征值1对应的特征向量对网页进行排名。

（2）存在无法确定排名的情况. 考察由图7.3所示的小型网络

图7.3

该网络由两个互不相连的子网络构成，其对应的链接矩阵A 为：

00000101002A=1

10002000010

0?? ? ? ? ? ? ? ? ???

利用MATLAB 计算可得这个矩阵有1和－1两个二重特征根，还有一个单重特征根0，特征根1对应的两个线性无关的归一化特征向量为：

()1x 0000505T ,,,.,.=，()2x 0050500T

,.,.,,=。

显然，利用上述特征向量无法对网页进行排名.

Ⅱ. 改进的PageRank 算法

只要对（7.2）式稍作改动，就可以解决由于网页重要性相等而无法确定排名的问题。

令n 表示网络中包含的网页数，p 称为加权因子其取值在0和1之间。则网页k 的重要性可以由下式给出：

()1

k j L j x x p p n n

∈=+-∑

（7.4） 1

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

()x Ax+1p p s =- （7.5）

其中s 是一个元素全为n

的列向量. 若规定

i i x ==∑并记S 是一个元素全为n

1的

n 阶方阵，则由Sx s =可得：

()x A+1S x=Mx p p =?-??? （7.6）

关于矩阵方程(7.6)，可以证明：若A 是列随机矩阵，则M 亦是列随机矩阵.在

i x

==∑的约束条件下，

上述方程有唯一解. 其解为矩阵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，进而可得其对应的归一化特征向量为

T x )2000.0,2000.0,2850.0,2850.0,0300.0(=，

利用该特征向量就可以对不同子网络中的网页进行排名. 其对应的网页排名为：

12345x x x x x >=>=.

若矩阵A 中存在某列全为0，即存在j,a ij =0,任意i ,则规定矩阵M 对应该列的元素均为1/n ，这样，M 就仍然是列随机矩阵。

以图7.2所示的小型网络为例，4=n ，通常取p =0.85，那么用MATLAB ，易得

0.0375

0.03750.25000.46250.32080.03750.25000.0375M 0.32080.46250.25000.46250.3208

0.46250.2500

0.0375??

= ?

???

(7.7)

而M 的模最大的正特征值为1，对应的归一化特征向量为

(0.2192,0.1752,0.3558,0.2497)T =x

这样我们得到

3412x x x x >>>.

Ⅲ. PageRank 算法-幂法

值得注意的是，前面的作为例子的小型网络的规模微小，用数学软件直接求解矩阵方程x =Ax 或求A 的特征根和特征向量都无困难. 当问题的规模很大，甚至A 的阶数可能达到上万甚至上亿时，就必须寻找合适的数值计算方法. 下面我们介绍用于计算矩阵特征值的幂迭代算法。

假设矩阵A 的特征值满足条件123n λλλλ>≥≥≥ ，其中1λ是特征方程的实根，相应的特征向量1v 可以取成实向量，对于任意给定的非零初始向量

0x ，迭代格式

1-=k k Ax x （7.8）

称为计算矩阵特征值的幂法. 假设A 有n 个线性无关的特征向量i v ),,2,1(n i =，则初值0x 可以用它们线性表示，即

0x i n

i i v ∑==1

α （7.9）

从而幂法的迭代由下式给出

0221x A x A Ax x k k k k ====--

))((2

111

∑∑==+==n

i i i k i k n i i i k

v v v αλλαλαλ （7.10）

若对所有的1i >，均有

<λλi

. 所以只要10α≠，当k 足够大时，由(7.9）式可得 k x 111v αλk

≈ , （7.11） 1+k x 111

1v αλ+≈k （7.12）

即有

k k x x 11λ≈+ （7.13）

而k k Ax x =+1，故有

k k x Ax 1λ≈ (7.14)

这意味着，k x 最终会趋于1v . 但是，直接采用幂法往往会导致迭代序列趋向于无

穷大（而1λ的绝对值小于1时则会趋于零）.故在每次迭代是应当对k x 进行归一化处理，所以上述算法可以改写为

1-=k k Ax y （7.15）

k k

k y y x =, 其中∑==n

j kj k y 1

y （7.16）例如再次考察图7.2所示的小型网络，相应的矩阵M 如(7.7)式所示.那么给定初始向量T )1,0,0,0(0=x ，利用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]'; for k=2:20

y(:,k)=M*x(:,k-1);

x(:,k)=y(:,k)/norm(y(:,k),1); end

经计算得到幂法的迭代20次的序列如下：表7.1 k

k x

0 )0000.1,0000.0,0000.0,0000

.0( 7 )2422.0,3957.0,1517.0,2104.0( 1 )0375.0,4625.0,0375.0,4625

.0( 10 )2426.0,3977.0,1480.0,2117.0( 2 )3040.0,3302.0,2777.0,0881

.0( 13 )2423.0,3980.0,1473.0,2124.0( 3 )2509.0,4305.0,0868.0,2317

.0( 15 )2423.0,3979.0,1476.0,2123.0( 4 )2209.0,3891.0,1627.0,2273

.0( 16 )2423.0,3979.0,1475.0,2123.0( 5 )2556.0,3959.0,1523.0,1963

.0( 17 )2423.0,3979.0,1475.0,2123.0(

(后两次的迭代结果完全相同，故未列出)，从上表中可以看到，经过不足20步迭代，就可以得到与前面方法同样的排名结论.

注意在网页数量很大时，迭代运算需要更多有效数字，迭代次数一般也会更多，才能使得归一化特征向量的各分量有序从而确定网页排名.

六、实验任务

1. 在改进的PageRank 算法讨论图7.2所示的小型网络时，我们取p =0.85，请依次改取p =0.75，p =0.8或p =0.9，然后观察网页排名结果的变化情况.

建立m 文件：

function m7_1(p)

A=[0 0 0 1/2;1/3 0 0 0;1/3 1/2 0 1/2;1/3 1/2 0 0]; 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.2123 0.1475 0.3979 0.2423 所以网页排名为： x x x x 2

>>>

取p=0.75时运行结果为： m7_1(0.75) ans =

0.7184 -0.2166 + 0.1999i -0.2166 - 0.1999i -0.0352 ans =

0.2158 0.1621 0.3755 0.2467 取p=0.8时运行结果为： m7_1(0.8)

ans =

0.6909 -0.2297 + 0.2128i -0.2297 - 0.2128i -0.0315 ans =

0.2140 0.1550 0.3863 0.2447 取p=0.9时运行结果为： m7_1(0.9) ans =

0.6307 -0.2555 + 0.2385i -0.2555 - 0.2385i -0.0197 ans =

0.2105 0.1398 0.4103 0.2395

由上面当p 取0.85；0.75；0.8；0.9时得到的网页排名任然为：

x x x x 2

>>>

2. 计算图7.4所示小型网络的排名，分析其排名与图7.2所示小型网络排名发生变化的原因.

图7.4

图7.4的衔接矩阵为

2 4

x=[0 0 1 1/2;1/3 0 0 0 ;1/3 1/2 0 1/2;1/3 1/2 0 0] x =

0 0 1.0000 0.5000 0.3333 0 0 0 0.3333 0.5000 0 0.5000 0.3333 0.5000 0 0

使用MATLAB 建立m 文件有助于分析其网页排名，m 文件如下：

function m7_2(p)

A=[0 0 1 1/2;1/3 0 0 0;1/3 1/2 0 1/2;1/3 1/2 0 0]; 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.3682 0.1418 0.2880 0.2021 所以网页排名为：

x x x x 2

>>>

3. 利用幂法计算图7.5 所示网络的排名.

图7.5

图7.5的衔接矩阵为：

???

????

?02/1000

00000003/10000000

0002/100000000000003/100

2/10000103/10002/13/1000102/1000000003/100

000000002/12/1003/1000000

2/12/10

02/1000000

利用MATLAB 建立m 文件：

function m7_3(p)

A=[0 0 0 0 0 0 1/2 0 0 1/2;1/2 0 0 0 0 0 0 1/3 0 0;1/2 1/2 0 0 0 0 0 0 0 0;

0 0 1/3 0 0 0 0 0 0 0;0 1/2 0 1 0 0 0 1/3 1/2 0;0 0 1/3 0 1 0 0 0 0 1/2; 0 0 1/3 0 0 0 0 0 0 0;0 0 0 0 0 0 1/2 0 0 0;0 0 0 0 0 0 0 1/3 0 0; 0 0 0 0 0 0 0 0 1/2 0;];

S=ones(10,10)/10; M=p*A+(1-p)*S;

x(:,1)=[0 0 0 0 0 0 0 0 0 1]'; y(:,1)=[0 0 0 0 0 0 0 0 0 1]'; for k=2:35

y(:,k)=M*x(:,k-1);

4 10

8 5

x(:,k)=y(:,k)/norm(y(:,k),1);

end

运行m7_3(0.85)得到结果：

m7_3(0.85)

ans =

0 0 0 0 0 0 0 0 0 1.0000

0.4400 0.0150 0.0150 0.0150 0.0150 0.4400 0.0150 0.0150 0.0150 0.0150

0.0443 0.3295 0.3329 0.0308 0.0715 0.0613 0.0308 0.0341 0.0308 0.0341

0.0449 0.0459 0.1834 0.1153 0.2151 0.1947 0.1153 0.0296 0.0260 0.0296

0.0918 0.0509 0.0642 0.0803 0.1821 0.3145 0.0803 0.0767 0.0280 0.0312

0.0851 0.1034 0.1032 0.0453 0.1890 0.2747 0.0453 0.0670 0.0501 0.0367

0.0651 0.0916 0.1241 0.0577 0.1797 0.2877 0.0577 0.0447 0.0443 0.0474

0.0790 0.0732 0.1080 0.0664 0.1780 0.2952 0.0664 0.0523 0.0366 0.0448

0.0831 0.0846 0.1064 0.0609 0.1775 0.2883 0.0609 0.0577 0.0398 0.0408

0.0771 0.0883 0.1143 0.0598 0.1801 0.2826 0.0598 0.0541 0.0415 0.0423

0.0768 0.0831 0.1123 0.0624 0.1795 0.2875 0.0624 0.0532 0.0399 0.0430

0.0791 0.0830 0.1098 0.0620 0.1791 0.2880 0.0620 0.0549 0.0398 0.0423

0.0785 0.0850 0.1111 0.0611 0.1793 0.2865 0.0611 0.0547 0.0405 0.0423

0.0779 0.0844 0.1117 0.0614 0.1794 0.2867 0.0614 0.0541 0.0403 0.0426

0.0783 0.0839 0.1110 0.0617 0.1793 0.2872 0.0617 0.0544 0.0401 0.0425

0.0784 0.0842 0.1110 0.0615 0.1793 0.2870 0.0615 0.0545 0.0402 0.0424

0.0782 0.0844 0.1113 0.0614 0.1793 0.2868 0.0614 0.0544 0.0403 0.0424

0.0782 0.0842 0.1112 0.0615 0.1793 0.2870 0.0615 0.0544 0.0402 0.0425

0.0783 0.0842 0.1111 0.0615 0.1793 0.2870 0.0615 0.0544 0.0402 0.0424

0.0783 0.0842 0.1112 0.0615 0.1793 0.2869 0.0615 0.0544 0.0402 0.0424

0.0783 0.0842 0.1112 0.0615 0.1793 0.2869 0.0615 0.0544 0.0402 0.0425

0.0783 0.0842 0.1112 0.0615 0.1793 0.2870 0.0615 0.0544 0.0402 0.0425

0.0783 0.0842 0.1112 0.0615 0.1793 0.2869 0.0615 0.0544 0.0402 0.0424

0.0783 0.0842 0.1112 0.0615 0.1793 0.2869 0.0615 0.0544 0.0402 0.0425

0.0783 0.0842 0.1112 0.0615 0.1793 0.2869 0.0615 0.0544 0.0402 0.0424

0.0783 0.0842 0.1112 0.0615 0.1793 0.2869 0.0615 0.0544 0.0402 0.0425

0.0783 0.0842 0.1112 0.0615 0.1793 0.2869 0.0615 0.0544 0.0402 0.0424

由上述结果可以得到网页排名为：

x x

x x x x x x x x 910

>>>=>>>>>

总结：

通过对这个实验的学习让我能更好的用MATLAB 进行矩阵运算，和认识到计算矩阵特征值的幂迭代法。在学习的过程中老师教会我如何通过有向图求解衔接矩阵，知道了关于矩阵的一系列算法。

还有我明白了我们通常上网搜索的结果是通过什么原理出现的，以前以为排在前面的网页就是最精准的搜索结果，然而通过对本实验的学习知道事实并非这样。

通过这个实验可以解决犹如有向图一样的实际问题，比如食物链问题，每个生物在食物链中都存在作用，需要我们考察那种生物更重要一点，通过有向图找出衔接矩阵，用MATLAB 实现，就可以知道那种生物更重要。

搜索引擎-第二次实验报告

实验二：实验一、实验目的：根据网络爬虫的基本原理，实现一个简易网络爬虫，需要达到以下指标： 1、种子URL为https://www.wendangku.net/doc/ed2558835.html,； 2、至少抓取10000个页面； 3、至少完成3轮抓取，每轮给出更新的URL及其数量； 4、实现ＵＲＬ判重，列出每轮爬去时重复的URL数量； 5、数据存放到数据库中，能抽取出网页中的标题、页面生成日期（http协议中的时间），至少包含标题、时间、url、抓取时间、网页正文这几个字段。二、实验方案： 1.爬虫分析与设计我们组应用的是java来写爬虫，我们应用SSM框架将数据库和应用程序连接起来，可以在程序中更简单的进行数据库插入、查询等操作。在对url处理的时候我们用的是Java的URL类，通过这个类可以获得请求头的一些信息，例如编码方式。如何获取url，我们一开始遇到了一些问题，直接解析网页中的ref 标签的时候得到的不全是网页链接，所以转换思路，我们先得到页面中的标签，然后再得到标签里边href中的url，然后再对url进行处理。在处理url的时候，因为网页中的url并不是全部以http开头的，所以在url获取部分，对url的格式进行判断，如果通常格式就进行修改，例如，有的链接是”#”，我们就把开始搜索的url加到它的前边，形成一个正确的url。

图1：应用URL类获取网页内容图2：利用url请求头获取编码信息图3：获取a标签

图4-1：获取url 图4-2：获取url

图5：url判重 2.数据库分析与设计我们设计了两个表，一个是未爬取url表，两一个是已经爬取url表。未爬取的表中村的是搜索判重之后，还没有爬取的url，已爬取的存储爬取到的信息。图6：判重后需要爬取的url表图7：爬取后url信息存储表