问题提出

PageRank的核心思想就是：

1. 如果一个网页被很多其他网页链接到的话说明这个网页比较重要，也就是PageRank值会相对较高
2. 如果一个PageRank值很高的网页链接到一个其他的网页，那么被链接到的网页的PageRank值会相应地因此而提高

因此，我们希望计算出每个网站的PR值，通过这个值来反映网站的重要程度，进而对网站排序。

这样，我们就可以对这个问题进行如下建模和猜想：

假设$n$是所有可访问网页的数目，此数值非常大，定义$n\times n$为网页链接矩阵$G = (g_{ij})\in R^{n\times n}$，若从网页$j$有一个链接到网页$i$，则$g_{ij} = 1$，否则为0。矩阵$G$有如下特点：

1. $G$是大规模系数矩阵；
2. 第$j$列非零向量的位置表示了从网页$j$链接出去的所有网页；
3. 第$i$行非零向量的位置表示了所有链接到网页$i$的网页；
4. $G$中非零向量的数目为整个网络中存在的超链接的数目；
5. $r_i = \sum _j g_{ij}$，表示第$i$个网站的入度；
6. $c_j = \sum_i g_ij$，表示第$j$个网站的出度；

建模

为了解决这个问题，我们想象一个随机浏览网页的人，当他到达C网页后：

1. 假定他有一定概率点击超链接（$p$）到达另一个网页。即，若网页$i$在网页$j$的链接上，概率可以表示为：

   • $p \cdot 1/c_i + (1 - p) \cdot 1/n$

2. 假定他有一个确定的概率会输入网址直接跳转到一个随机的网页，若网页$i$不在网页$j$的链接上，概率可以表示为：

   • $(1-p)\cdot 1/n$

由于网页$i$是否在网页$j$上由$g_{ij}$决定，因此网页$j$到$i$的转移概率为：

$a_{ij} = g_{ij }[p \cdot 1/c_i + (1 - p) \cdot 1/n] + (1 - g_{ij})[(1-p)\cdot 1/n]= \frac{pg_{ij}}{c_j} + \frac {1-p }{n}$

应该注意的是，若$C_j = 0$意味着$g_{ij} = 0$,则$a_{ij} = 1/n$。任意两个网页之间的转移概率形成了一个转移矩阵$A$，设$D$为各个网页出度的导数构成的$n$阶对角阵，$e$是全为1的$n$维向量，则：

$A = pGD + \frac {1-p}{n}ee^T$

设$x_i^{(k)}$表示时刻$k$浏览网页$i$的概率，其中$\sum x_i^{(k)} = 1$，那么下一刻浏览到网页$i$的概率为$\sum _{j = 1}^n x_i^{(k)}$,此时浏览整个网页的概率分布为$x^{(k+1)} = Ax^{(k)}$。

当这个过程无线进行下去，达到极限情况，即网页访问概率$x^{(k)}$收敛到一个极限值，这个极限向量$x^{(k)}$为网页的PageRank，满足$Ax = x$，且$\sum _{i = 1}^n x_i = 1$。

参考资料

1. PageRank算法--从原理到实现