图机器学习——3.1 PageRank 基础算法_pagerank算法习题

PageRank算法是一种由根据网页之间相互的超链接计算的技术，而作为网页排名的要素之一，以Google公司创办人拉里·佩奇（Larry Page）之姓来命名。实际的网页连接图是一个非常庞大的图结构，通常将节点表示一个一个的网页，节点之间相连接的边表示网页与网页之间的连接关系。PageRank算法就是衡量网页重要性的算法之一。

基础方法介绍

Page Rank算法是一种“流动”的模型，也可以理解成“投票”的想法，来自越重要网页的投票权重占比越高，我们以下图为例，算法有如下特点：

• 每个连接的投票与其来源页面的重要性成正比；
• 若页面$i$具有重要性$r_i$，并且有$d_i$条向外的有向连接，每一个连接将得到$r_i/d_i$票；
• 页面$j$所拥有的重要性$r_j$为连接到它的投票数之和。

由于重要节点（页面）的票数更多（因为重要性更高），因此，在Page Rank算法中如果一个页面被其他重要页面所指向，那么此页面也是重要的。

下面可以给出具体的定义，我们定义节点$j$重要性得分为“rank”：

$$r_j=\sum _{i\to j}\frac{r_i}{d_i}$$

其中，$d_i$为出度（一个节点向外连接的所有边的个数）。根据上述方程，可以写成矩阵的形式，

$$\mathbf{r}=\mathbf{M}\cdot \mathbf{r}$$

其中，$\mathbf{M}$为列随机邻接矩阵（列和为1），若$i\to j$, 则 ${\mathbf{M}}_{ji}=\frac{1}{d_i}$；$\mathbf{r}$的每个元素$r_i$为节点（页面）$i$的重要性得分，满足${\sum }_i{r}_i=1$。下图为一个具体的例子：

下面我们从随机游走的视角来考虑这个问题，将上面的重要性得分$r_i$理解成某一时刻浏览$i$网页的概率。$t$时刻的概率我们记为$p(t)$。因此迭代的公式可以记为：

$$\mathbf{p}(t+1)=\mathbf{M}\cdot \mathbf{p}(t)$$

当上式满足$\mathbf{M}\cdot \mathbf{p}(t)=\mathbf{p}(t)$，则称$\mathbf{p}(t)$为随机游走的平稳分布。

此时，我们可以将$\mathbf{M}$作为马尔科夫随机矩阵，根据方程：

$$1\cdot \mathbf{r}=\mathbf{M}\cdot \mathbf{r}$$

可知，矩阵$\mathbf{M}$一定有一个值为1的特征值。并且根据 Gershgorin circle theorem 可得，马尔科夫矩阵的任意一个特征值的绝对值都不大于1。因此1即为矩阵$\mathbf{M}$的主特征值（最大特征值），而幂迭代法便是通过迭代来计算矩阵的主特征值与其对应特征向量的方法。最终的特征向量就是我们所需要的稳定之后的重要性得分向量$\mathbf{r}$。

算法迭代过程如下（$N$为节点/网页个数）：

• 初始化: ${\mathbf{r}}^{(0)}=[1/N,\dots ,1/N{]}^T$
• 迭代: ${\mathbf{r}}^{(t+1)}=\mathbf{M}\cdot {\mathbf{r}}^{(t)}$
• 停止条件： ${\Vert {\mathbf{r}}^{(t+1)}-{\mathbf{r}}^{(t)}\Vert }_1<\epsilon$

下面为前面介绍的y-a-m图迭代示例：

( r y r a r m ) = ( 1 / 3 1 / 3 1 / 3 ) ( 1 / 3 3 / 6 1 / 6 ) ( 5 / 12 1 / 3 3 / 12 ) ( 9 / 24 11 / 24 1 / 6 ) … ( 6 / 15 6 / 15 3 / 15 ) \left(

$$\begin{array}{l} r_{y} \\ r_{a} \\ r_{m} \end{array}$$ \right)=\left( $$\begin{array}{l} 1 / 3 \\ 1 / 3 \\ 1 / 3 \end{array}$$ \right) \quad\left( $$\begin{array}{l} 1 / 3 \\ 3 / 6 \\ 1 / 6 \end{array}$$ \right) \quad\left( $$\begin{array}{l} 5 / 12 \\ 1 / 3 \\ 3 / 12 \end{array}$$ \right) \quad\left( $$\begin{array}{l} 9 / 24 \\ 11 / 24 \\ 1 / 6 \end{array}$$ \right) \quad \ldots \quad\left( $$\begin{array}{l} 6 / 15 \\ 6 / 15 \\ 3 / 15 \end{array}$$ \right) ⎝⎛​ry​ra​rm​​⎠⎞​=⎝⎛​1/31/31/3​⎠⎞​⎝⎛​1/33/61/6​⎠⎞​⎝⎛​5/121/33/12​⎠⎞​⎝⎛​9/2411/241/6​⎠⎞​…⎝⎛​6/156/153/15​⎠⎞​

下面考虑三个问题：

• 迭代算法是否收敛？
• 算法是否收敛到我们期望的值？
• 最终的结果是否合理？

关于这三个问题的回答，我们将在下个博客中进行阐述。

参考

• CS224W: Machine Learning with Graphs