2021SC@SDUSC

Google是如今全球最成功的互联网搜索引擎，但在Google出现之前，也曾出现过很多 通用或专业领域的搜索引擎。Google最终能击败所有竞争对手，有一部分原因是因为它解 决了搜素引擎的最大难题：对搜索结果按重要性排序。解决这个问题的算法就是PageRanko PageRank算法计算每一个网页的PageRank值.然后根据这个值的大小对网页的重要性进行 排序。它的思想是模拟一个悠闲的上网者，上网者首先随机选择一个网页打开，然后在这个 网页上待了几分钟后，跳转到该网页所指向的链接，这样无所事事、漫无目的地在网页上跳 来跳去，PageRank就是估计这个悠闲的上网者分布在各个网页上的概率。

1. PageRank 算法

要理解PageRank算法需要有基本的高等代数基础。为了 降低理解门槛，先从简单的PageRank问题入手。假设当前网页 中共有A、B、C、D四个网页，每个网页都可以作为一个顶点。如果网页A有链接可以跳转到B,那么存在一 条有向边A— B。

定义1 ：如果一个顶点有力条出边，那么跳转到任意一个出 边的目的顶点的概率为/ko

根据定义1,可以看出顶点A的出度是3,分别有3条有向边到达B、C、D, 所以从顶点A跳转到B、C、D的概率都是1/3。同理，顶点B跳转到A、D的概率都是1/2, 顶点C跳转到A的概率是1,顶点D跳转到B、C的概率都是1/20

定义2：如果网页数目是N,它们之间的跳转概率可以用的二维矩阵M表示。其中 表示从第J个顶点到第i个顶点的跳转概率。

定义3：如果网页数目是N,则跳转至其中任一网页的概率是I/N。

根据定义3,则跳转至图10-32中任一网页的概率是1/4.

现在计算跳转到各个页面的概率.用矩阵M乘以矩阵Fo可以得到新的4X 1矩阵:

	—()	1/2	1	0	1/4		9/24
	1/3	0	0	1/2	1/4		5/24
= M'o =	1/3	0	0	1/2	1/4		5/24
	J/3	1/2	0	0__	_1/4_		5/24

得到F,后，接着迭代运算灼=A/K、人=M灼，最终会收敛为V= [3/9,2/9,2/9, 2/9]：

"1/4"	9/24	一15/48一	11/32-		一3/9 —
1/4	5/24	11/48	7/32		2/9
1/4	5/24	11/48	7/32		2/9
_1/4_	5/24	11/48	7/32		_2/9_

(1 )终止点问题

上述例子中的顶点间都是强连通的，即从任意顶点可以到达其 他顶点。真实情况下的很多网页是不满足强连通的，当用户访问一 个没有任何外链的网页时，他可能放弃继续浏览，也可能重新输入 一个网址访问。我们将图10-32中C到A的有向边去掉，那么整个 图就变为不是强连通的，如图10-33所示。

图10-33的二维矩阵如下：

'0	1/2	0
1/3	0	0
1/3	0	0
1/3	1/2	0

M =

0一

1/2

1/2

按照之前的迭代过程，最终所有元素都会是0：

一1/4一	一3/24一	~5/48-	一21/288「		「0~
1/4	5/24	7/48	31/288		0
1/4	5/24	7/48	31/288		0
_1/4_	_5/24_	_7/48_	_31/288_		0.

(2 )陷阱问题

有些情况下，某些网页不存在指向其他网页的链接，但却存在指向自己的链接。给 图10-33中的顶点C增加指向自己的有向边，如图10-34所示。

图10-34的二维矩阵如下：

为了克服以上出现的这些影响结果不正确的问题，需要考虑这样一种情况：每个用户无 论在任何页面，随时都有可能以一个较小概率跳转至其他页面。如果用户访问A、B、C、D 页面的概率为1-人那么跳出这些页面访问其他页面的平均概率是@4, N个顶点跳出的概率 分别为 m 假设e代表N各顶点的单位访问概率：

那么所有页面跳出的总概率是eg,最终得出如下公式：

V' = (-P)MV+e^

假设月等于0.2,则图10-33的二维矩阵使用公式计算得到的结果如下：

■ 0	2/5	0	0_		一 1/20 一
4/15	0	0	2/5	JZ _1_	1/20
4/15	0	0	2/5	V十	1/20
_4/15	2/5	0	0_		_1/20_

V'=

夕等于0.2,则图10-34的二维矩阵使用公式计算得到的结果如下:

一 0	2/5	0	0 —		"1/20-
4/15	0	0	2/5		1/20
4/15	0	4/15	2/5	V +	1/20
J/15	2/5	0	0_		_1/20_

按照最终的这两个公式持续迭代会发现终止点问题和陷阱问题都不存在了。