PageRank算法详解

主要内容
- PageRank算法简介
- PageRank算法详解
  - 基本PageRank模型
  - 终止点问题
  - 陷阱问题
  - 解决终止点问题和陷阱问题

1、PageRank算法简介
PageRank，网页排名，又称网页级别或佩奇排名，是一种根据网页间相互超链接进行网页排名的技术，以Google公司创办人拉里·佩奇（Larry Page）之姓来命名。Google用它来体现网页的相关性和重要性，在搜索引擎优化操作中是评估网页优化的有效指标之一。Google的创始人拉里·佩奇和谢尔盖·布林于1998年在斯坦福大学发明了这项技术。
PageRank通过网络浩瀚的超链接关系来确定一个页面的等级。Google把从A页面到B页面的链接解释为A页面给B页面投票，Google根据投票来源（甚至来源的来源）和投票目标的等级来决定新的等级。简单的说，一个高等级的页面可以使其他低等级页面的等级提升。

2、PageRank算法详解
2.1 基本PageRank模型
互联网中的网页可以看成是一个有向图，其中网页是结点，如果网页 $A$ 有链接到网页 $B$ ，则存在一条有向边 $A \rightarrow B$ ，下面是一个简单的示例：

这个例子中只有四个网页，如果当前在

A $A$ 网页，那么悠闲的上网者将会各以

1/3
$1/3$ 的概率跳转到

B、C、D $B、C、D$ ，这里的

3 $3$ 表示

A
$A$ 有

3 $3$ 条出链，如果一个网页有

k
$k$ 条出链，那么跳转任意一个出链上的概率是

1/k $1/k$ ，同理

D $D$ 到

B、C
$B、C$ 的概率各为

1/2 $1/2$ ，而

B $B$ 到

C
$C$ 的概率为

0 $0$ 。一般用转移矩阵表示上网者的跳转概率，如果用

n
$n$ 表示网页的数目，则转移矩阵

M $M$ 是一个

n×n
$n \times n$ 的方阵；如果网页

j $j$ 有

k
$k$ 个出链，那么对每一个出链指向的网页

i $i$ ，有

M[i][j]=1/k
$M[i][j]=1/k$ ，而其他网页的

M[i][j]=0 $M[i][j]=0$ ；上面示例图对应的转移矩阵如下：

这里写图片描述

初试时，假设上网者在每一个网页的概率都是相等的，即

1/n $1/n$ ，于是初试的概率分布就是一个所有值都为

1/n $1/n$ 的

n $n$ 维列向量

V0
$V_{0}$ ，用

M $M$ 乘以

V0
$V_{0}$ ，就得到了第一步之后上网者的概率分布向量

V1 $V_{1}$ ，

(n×n)×(n×1) $(n\times n)\times (n\times 1)$ 依然得到一个

n×1 $n\times 1$ 的矩阵。下面是

V1 $V_{1}$ 的计算过程：

这里写图片描述

注意矩阵

M $M$ 中

M[i][j]
$M[i][j]$ 不为

0 $0$ 表示用一个链接从

j
$j$ 指向

i $i$ ，

M
$M$ 的第一行乘以

V0 $V_{0}$ ，表示累加所有网页到网页

A $A$ 的概率即得到

9/24
$9/24$ 。得到了

V1 $V_{1}$ 后，再用

M $M$ 乘以

V1
$V_{1}$ 得到

V2 $V_{2}$ ，一直下去，最终

V $V$ 会收敛，即

Vn=M×Vn−1
$V_{n}=M\times V_{n-1}$ ，上面的图示例，不断的迭代，最终得到

V=[3/9,2/9,2/9,2/9] $V=[3/9,2/9,2/9,2/9]$ ：

这里写图片描述

2.2 终止点问题
上述上网者的行为是一个马尔科夫过程的实例，要满足收敛性，需要具备一个条件：

图是强连通的，即从任意网页可以到达其他任意网页

互联网上的网页不满足强连通的特性，因为有一些网页不指向任何网页，如果按照上面的计算，上网者到达这样的网页后便走投无路、四顾茫然，导致前面累计得到的转移概率被清零，这样下去，最终的得到的概率分布向量所有元素几乎都为 $0$ 。假设我们把上面图中 $C$ 到 $A$ 的链接丢掉， $C$ 变成了一个终止点，得到下面这个图：

对应的转移矩阵为：

连续迭代下去，最终所有元素都为

0 $0$ ：

2.3 陷阱问题
另外一个问题就是陷阱问题，即有些网页不存在指向其他网页的链接，但存在指向自己的链接。比如下面这个图：

上网者跑到

C
$C$ 网页后，就像跳进了陷阱，陷入了漩涡，再也不能从

C $C$ 中出来，将最终导致概率分布值全部转移到

C
$C$ 上来，这使得其他网页的概率分布值为

0 $0$ ，从而整个网页排名就失去了意义。如果按照上面图对应的转移矩阵为：

这里写图片描述

不断的迭代下去，就变成了这样：

这里写图片描述

2.4 解决终止点问题和陷阱问题
上面过程，我们忽略了一个问题，那就是上网者是一个悠闲的上网者，而不是一个愚蠢的上网者，我们的上网者是聪明而悠闲，他悠闲，漫无目的，总是随机的选择网页，他聪明在走到一个终结网页或者一个陷阱网页（比如两个示例中的 $C$ ），不会傻傻的干着急，他会在浏览器的地址随机输入一个地址，当然这个地址可能又是原来的网页，但这里给了他一个逃离的机会，让他离开这万丈深渊。模拟聪明而又悠闲的上网者，对算法进行改进，每一步，上网者可能都不想看当前网页了，不看当前网页也就不会点击上面的连接，而上悄悄地在地址栏输入另外一个地址，而在地址栏输入而跳转到各个网页的概率是 $1/n$ 。假设上网者每一步查看当前网页的概率为 $\alpha$ ，那么他从浏览器地址栏跳转的概率为 $(1-\alpha)$ ，于是原来的迭代公式转化为：