-
PageRank
解释方法一
1.
PageRank
的核心思想
PageRank
，
B(x)
表示所有指向
x
的网页。
(1)
R(x)
表示
x
的
公式
(1)
的意思是一个网页的重要性等于指向它的所有网页的重要性相加之和。
粗看之下，
公
式
(1)
将核心思想准确地表达出来了。但仔细观察就会发现，公式
(1)
有一个缺陷：无论
J
有多少
个超链接，只要
J
指向
I
，
I
都将得到与
J
一样的重要性。当
J
有多个超链接时，这个思想
就会造
成不合理的情况。例如：一个新开的网站
N
只有两个指向它的超链接，一个来自著名并且历史
悠久的门户网站
F
，
另一个来自不为人知的网站
< br>U
。
根据公式
(1)
，
就会得到
N
比
F
更优质的结论。
这个结论显然不符合人们的常
识。
弥补这个缺陷的一个简单方法是当
J
有多个超链接（假设个数为
N
），
每个链接得到的重要性为
R(j)/N
。于是公式
(1)
就变成公式（
2
）：
（
2
）
N(j)
表示
j
页
面的超链接数
图
2
来自
Lawrence
Page
的文章
从图
2
可以看出，如果要得到
< br>N
比
F
更优质的结论，就要求<
/p>
N
得到很多重要网站的超链接或
者海量不
知名网站的超链接。而这是可接受的。因此可以认为公式
(2)
将核心思想准确地表达出
来了。为了得到标准化的计算结果，在公式
(2)
的基础上增加一个常数
C
，
得到公式
(3)
：
(3)
2.
计算，实例
由公式
< br>(3)
可知，
PageRank
是递归定义的。换句话就是要得到一个页面的
PageRank
，就要先知道
另一些页面的
PageRank
< br>。因此需要设置合理的
PageRank
初始值。不过，
如果有办法得到合理的
PageRank
初始值，还需要这个算
法吗或者说，这个严重依赖于初始值的算法有什么意义吗
依赖
于合理初始值的
PageRank
算法是没意义的，
那么不依赖于初始值的
PageRank
算法就是
有意
义的了。也就是说，如果存在一种计算方法，
使得无论怎样
设置初始值，
最后都会收敛到同一个
值就行了。要做到这样，就
要换一个角度看问题，从线性代数的角度看问题。
将页面看作
节点，超链接看作有向边，整个互联网就变成一个有向图了。此时，用邻接矩阵
M
表示整个互联网，若第
I
个页面有存在到第<
/p>
J
个页面的超链接，那么矩阵元素
m[i
][j]=1
，否则
m[i][j]=0
。对于图
3
有
矩形
M={ 0, 1, 1, 0,
0, 0, 0,
1,
1, 0, 0, 0,
1, 1, 1, 0}
图
3
观察矩
阵
M
可发现，
M
的第
I
行表示第
I
< br>个网页指向的网页，
M
的第
J<
/p>
列表示指向
J
的网页。如
果将
M
的每个元素都除于所在行的全部元素之和，然后
再将
M
转置（交换行和列），得到
M<
/p>
T
。
M
T
的每一行的全部元素之和不就正好是公式
(3)
中的
吗例如图
3
< br>可以得到这样的矩阵：
M
T
={ 0,
0,
1,
1/3,
1/2, 0,
0, 1/3,
1/2,
0,
0, 1/3,
0,
1,
0,
0
}
将<
/p>
R
看作是一个
N
行
1
列的矩阵，公式
(3)
变为公式（
4
）
R = C M
T
R
(4)
在公式
(4)
中，
R
可以看作
M
T
< br>的特征向量，其对应的特征值为
1 / C
（看不明白这
句话，可以回忆
下线性代数中对特征向量的定义
——
对于矩阵
A
，若存在着列向量
X
和一个数
c
，使得
AX=cX
，
则
X
称为
A
的特征向量，
c
称为
A
的特征值）。幂法
(power method
）计算主特征向量与初始值
无关，因此只要把
R
看作主特征向量计算，就可以解决初始
值的合理设置问题。
幂法得到的结果与初始值无关，
是因为最终都会收敛到某个值。
因此使用幂法之前，
要确保能够
收敛。但是，在互联网的超链接结构中，一旦出现封闭的情况，就会使得
幂法不能收敛。所谓的
封闭是指若干个网页互相指向对方，但不指向别的网页，具体的例
子如图
4
所示：
图
4
来自
Soumya
Sanyal
的
PPT
上图
4
个绿色网页就是封闭情况。这种情况会使得这
些网页的
PageRank
在计算的时候不断地累
加，从而使得结果不能收敛。仔细研究就会发现红色网页的
PageRank
给了绿色网页后，绿色网
页就将这些
P
ageRank
吞掉了。
Larry
Page
将这种情况称为
Rank
Sink
。
如果沿着网页的链接一直
点下去，
发现老是在同样的几个网页中徘徊，
怎么办没错，
把当前页面
关掉，再开一个新的网页。上述情况正好与
Rank
Sink
类似，也就意味着可以借鉴这个思想解决
Rank S
ink
。因此，在公式
(3)
中的基础
上加一个逃脱因子
E
，得到：
(5)
E(i)
< br>表示第
i
个网页的逃脱因子
将
(5)
变成矩阵形式，可得：
R = C
M
T
R + CE = C(
M
T
R + E )
其中列向量
R
的
1
范数
(
即
R
的全部矩阵元素相加
)
为
1
将上式重写为
R = C( M
T
+ E * 1
) R (6)
1
是指一行
N
列的行向量，且每个元素都是
1
在公式
(6)
中，
只要将
R
看作
(M
T
+ E * 1)
的特征向量，
就可以同时解决初始值设置问题和封闭的
情况。
3.
资料共享
找资料是简单的事，
但要找到好资料就不那么容易了。
因此
，
这一小节是分享我找到的一些比
较好的资料。
1.
PageRank
之父的文章
: The PageRank
Citation Ranking Bringing Order to the
Web
一个对
PageRank
进行解释的
PPT
，讲解得很好
: The PageRank Citation Ranking
–
Redone
不错的
PageRank
科普文
: Google
的秘密
- PageRank
彻底解说
中文版
本文所用到的线性代数相关知识