PageRank算法

作者: 飞翔的哈土奇 | 来源:发表于2018-12-08 22:30 被阅读0次

Pagerank算法
大数据实例 | 你想知道搜索引擎排名怎么来的嘛---PageRa
PageRank算法
TextRank学习笔记
统计学习方法——修炼学习笔记21：PageRank算法
大数据Hadoop生态圈技术之浅析PageRank计算原理
常用图算法实现--Spark
关键词和摘要
文章摘要的自动生成（2）textTank的应用
自然语言处理-PageRank（上）

算法部分首先通过对理想情况的分析，阐述了PageRank算法的流程以及如何利用幂迭代法求解平稳向量，然后指出可能遇到的一些问题以及相应的解决方案。

证明部分主要涉及平稳向量存在性和正确性的证明以及利用幂迭代法求解平稳向量收敛性的证明。

PageRank算法
1. 简介
2. 算法
2.1 理想情况
2.2 幂迭代法
2.3 存在的问题
2.3.1 悬空结点
问题描述
解决方案
2.3.2 幂迭代法不收敛
问题描述
解决方案
3. 证明

1. 简介

PageRank算法是谷歌提出的，用于计算网页的重要性，当使用搜索引擎搜索网页的时候，越重要的网页越靠前显示。其基本思想是将网页抽象为图结点，网页之间的链接关系抽象为有向边，通过定义在这个有向图上的矩阵来计算各个网页之间的相对重要性。这里之所以说相对，是因为重要性的数值并没有实际意义，我们不能说网页 $A$ 的重要性是 $2$ 或者网页 $B$ 的重要性是 $1$ ，但可以说网页 $A$ 比网页 $B$ 重要或者网页 $A$ 的重要性是网页 $B$ 的两倍。

2. 算法

2.1 理想情况

如上图，假设图中 $3$ 个点 $A$ ， $B$ ， $C$ 分别表示 $3$ 个网页，图中的有向边表示网页的链接关系，点 $A$ 到点 $B$ 有一条有向边，其含义是网页 $A$ 中有一条链接可以跳转到网页 $B$ 。记某网页，比如网页 $A$ ，的重要性为 $I(A)$ ，则各个网页的重要性

$I(A)=\frac{I(C)}{2}$

$I(B)=\frac{I(A)}{2} + \frac{I(C)}{2}$

$I(C)=\frac{I(A)}{2} + \frac{I(B)}{1}$

可以看出，某网页的重要性是由链接到该网页的网页所决定的。网页 $B$ 可以由网页 $A$ 或网页 $C$ 跳转过来，所以网页 $B$ 的重要性由网页 $A$ 和网页 $C$ 决定。网页 $C$ 可以跳转到网页 $A$ 或网页 $B$ ，相当于网页 $C$ 将其重要性平均分给了网页 $A$ 和网页 $B$ 。上面三个式子可以写成矩阵乘法的形式，如下式所示

$\begin{bmatrix} I(A) \\ I(B) \\ I(C) \end{bmatrix} = \begin{bmatrix} 0 & 0 & \tfrac{1}{2} \\ \tfrac{1}{2} & 0 & \tfrac{1}{2} \\ \tfrac{1}{2} & 1 & 0 \\ \end{bmatrix} \begin{bmatrix} I(A) \\ I(B) \\ I(C) \end{bmatrix} \tag{1}$

式 $(1)$ 形如 $H\vec{x}=1\vec{x}$ ，其解为 $H$ 矩阵特征值为 $1$ 时候的特征向量 $\vec{v}=(v_1, \cdots, v_n)^T$ ，称其为平稳向量(stationary vector)。所以各网页的重要性可以用相应的 $v_i, i \in \{1, 2, \cdots, n \}$ 来衡量。这里需要注意的一点是，我们不加以证明地假设 $v_i \ge 0, \forall i \in \{1, 2, \cdots, n \}$ 成立，因为一个网页的重要性为负值没有实际意义，若 $\vec{v}$ 为平稳向量，令 $\lambda > 0$ ，则 $\lambda \vec{v}$ 也是平稳向量，也可以用来衡量网页的重要性。所以网页重要性的数值没有什么意义，真正有意义的是各网页之间的相对重要性，这种关系不会因为乘了一个常数而改变，所以方便起见，一般令 $\begin{matrix} \sum_{i=1}^n v_i = 1 \end{matrix}$ 。

综上，PageRank算法大致分为两步，首先根据网页之间的链接关系得到 $H$ 矩阵，然后计算 $H$ 矩阵的平稳向量。

2.2 幂迭代法

如前文所述，我们需要计算 $H_{n \times n}$ 矩阵的平稳向量来得到网页的重要性，实际中， $n$ 的值可能非常大，如何快速得到平稳向量呢，我们可以利用幂迭代法解决这个问题。这部分内容主要讲计算流程，关于幂迭代法的相关证明，可见证明部分。

幂迭代法首先选取一个初始向量 $\vec{v}^{(0)}$ ，通过计算 $\vec{v}^{(1)}=H\vec{v}^{(0)}$ ， $\vec{v}^{(2)}=H\vec{v}^{(1)}$ ，……， $\vec{v}^{(k)}=H\vec{v}^{(k-1)}$ ，得到一个序列 $\vec{v}^{(0)}$ ， $\vec{v}^{(1)}$ ， $\vec{v}^{(2)}$ ，……， $\vec{v}^{(k)}$ ，当 $k \rightarrow +\infty$ ， $\vec{v}^{(k)}$ 会收敛到平稳向量。如图所示，该图的 $H$ 矩阵

$H = \begin{bmatrix} 0 & 0 & \tfrac{1}{2} \\ \tfrac{1}{2} & 0 & \tfrac{1}{2} \\ \tfrac{1}{2} & 1 & 0 \\ \end{bmatrix}$

直接计算可得 $H$ 矩阵的平稳向量为 $\vec{v}=(0.22, 0.33, 0.44)^T$ ，令 $\vec{v}^{(0)}=(0.33, 0.33, 0.33)^T$ ，即最开始每个网页具有相同的重要性，记录幂迭代法的计算过程，可以得到下面的表格

$\vec{v}^{(0)}$	$\vec{v}^{(1)}$	$\vec{v}^{(2)}$	$\vec{v}^{(3)}$	$\vec{v}^{(4)}$	$\vec{v}^{(5)}$	$\vec{v}^{(6)}$	$\vec{v}^{(7)}$	$\cdots$	$\vec{v}^{(100)}$
$\begin{pmatrix} 0.33 \\ 0.33 \\ 0.33 \end{pmatrix}$	$\begin{pmatrix} 0.17 \\ 0.33 \\ 0.50 \end{pmatrix}$	$\begin{pmatrix} 0.25 \\ 0.33 \\ 0.42 \end{pmatrix}$	$\begin{pmatrix} 0.21 \\ 0.33 \\ 0.46 \end{pmatrix}$	$\begin{pmatrix} 0.23 \\ 0.33 \\ 0.44 \end{pmatrix}$	$\begin{pmatrix} 0.22 \\ 0.33 \\ 0.45 \end{pmatrix}$	$\begin{pmatrix} 0.22 \\ 0.33 \\ 0.44 \end{pmatrix}$	$\begin{pmatrix} 0.22 \\ 0.33 \\ 0.44 \end{pmatrix}$	$\ldots$	$\begin{pmatrix} 0.22 \\ 0.33 \\ 0.44 \end{pmatrix}$

可以看到，该向量序列逐渐向 $\vec{v}$ 靠拢。

2.3 存在的问题

前面讨论的是理想情况下的PageRank算法，这部分讨论可能存在的问题。

2.3.1 悬空结点

问题描述

悬空结点指的是没有出度的结点，也就是说该网页没有链接到其他网页。如下图，网页 $D$ 就是一个悬空结点，这时如果采用幂迭代法计算平稳向量就会出现问题。

上图的 $H$ 矩阵

$H= \begin{bmatrix} 0 & 0 & \tfrac{1}{2} & 0 \\ \tfrac{1}{3} & 0 & \tfrac{1}{2} & 0 \\ \tfrac{1}{3} & \tfrac{1}{2} & 0 & 0 \\ \tfrac{1}{3} & \tfrac{1}{2} & 0 & 0 \\ \end{bmatrix}$

取 $\vec{v}^{(0)}=(0.25, 0.25, 0.25, 0.25)^T$ ，迭代过程如下

$\vec{v}^{(0)}$	$\vec{v}^{(1)}$	$\vec{v}^{(2)}$	$\cdots$	$\vec{v}^{(5)}$	$\cdots$	$\vec{v}^{(10)}$	$\cdots$	$\vec{v}^{(100)}$
$\begin{pmatrix} 0.250 \\ 0.250 \\ 0.250 \\ 0.250 \end{pmatrix}$	$\begin{pmatrix} 0.125 \\ 0.208 \\ 0.208 \\ 0.208 \end{pmatrix}$	$\begin{pmatrix} 0.104 \\ 0.146 \\ 0.146 \\ 0.146 \end{pmatrix}$	$\cdots$	$\begin{pmatrix} 0.039 \\ 0.057 \\ 0.057 \\ 0.057 \end{pmatrix}$	$\cdots$	$\begin{pmatrix} 0.008 \\ 0.012 \\ 0.012 \\ 0.012 \end{pmatrix}$	$\cdots$	$\begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}$

可以看到，向量序列收敛到 $(0, 0, 0, 0)^T$ ，这显然是不正确的。原因是在每一次的迭代过程中，网页 $D$ 都会“吸收”一部分重要性，从而使得每一次迭代后，网页整体的重要性都会减少，最后网页整体的重要性会变成 $0$ ，从而每个网页的重要性都为 $0$ 。

如果给 $D$ 结点添加一条边，指向其自身，如下图所示，其 $H$ 矩阵

$H= \begin{bmatrix} 0 & 0 & \tfrac{1}{2} & 0 \\ \tfrac{1}{3} & 0 & \tfrac{1}{2} & 0 \\ \tfrac{1}{3} & \tfrac{1}{2} & 0 & 0 \\ \tfrac{1}{3} & \tfrac{1}{2} & 0 & 1 \\ \end{bmatrix}$

重复上述的迭代过程，会有一个很有意思的结果，向量序列收敛到 $(0, 0, 0, 1)^T$ 。直观来讲，在每一次的迭代过程中，其他网页的重要性会流向网页 $D$ ，而网页 $D$ 的重要性则只流向其自身，最后所有的重要性都会集中在网页 $D$ 上。

解决方案

如上图所示，其 $H$ 矩阵

$H= \begin{bmatrix} 0 & 0 & \tfrac{1}{2} & 0 \\ \tfrac{1}{3} & 0 & \tfrac{1}{2} & 0 \\ \tfrac{1}{3} & \tfrac{1}{2} & 0 & 0 \\ \tfrac{1}{3} & \tfrac{1}{2} & 0 & 0 \\ \end{bmatrix}$

从概率的角度来看 $H$ 矩阵，其元素 $H_{ji}$ 表示从网页 $i$ 跳转到网页 $j$ 的概率，以第一列为例， $H_{21}=H_{31}=H_{41}=\tfrac{1}{3}$ ，说明在浏览网页 $A$ 的时候，等可能地会跳转到网页 $B$ ， $C$ 或者 $D$ ，这也和图相符。对于悬空结点，其不能跳转到任何网页，所以 $H$ 矩阵第四列元素全部为 $0$ 。所以 $H$ 矩阵有个性质，非悬空结点对应的列所有元素加起来等于 $1$ 。

问题在于，假如进入了网页 $D$ ，则不会再跳转到其他网页了，在这实际中是不可能的。所以，对于悬空节点，假定其可以跳转到任意网页，包括自身，并且跳转到这些网页的概率是相等的，则这一列元素可以全部用 $\tfrac{1}{n}$ 代替，那么修正后的矩阵

$S=H+A= \begin{bmatrix} 0 & 0 & \tfrac{1}{2} & \tfrac{1}{4} \\ \tfrac{1}{3} & 0 & \tfrac{1}{2} & \tfrac{1}{4} \\ \tfrac{1}{3} & \tfrac{1}{2} & 0 & \tfrac{1}{4} \\ \tfrac{1}{3} & \tfrac{1}{2} & 0 & \tfrac{1}{4} \\ \end{bmatrix}$

其中

$A= \begin{bmatrix} 0 & 0 & 0 & \tfrac{1}{4} \\ 0 & 0 & 0 & \tfrac{1}{4} \\ 0 & 0 & 0 & \tfrac{1}{4} \\ 0 & 0 & 0 & \tfrac{1}{4} \\ \end{bmatrix}$

我们这样定义 $A$ 矩阵，悬空结点对应的那一列，矩阵元素全部为 $\tfrac{1}{n}$ ，其余结点对应的列元素全部为 $0$ 。这样得到的 $S$ 矩阵是一个列随机矩阵，即 $\sum_i S_{ij} = 1, \forall j$ 。

2.3.2 幂迭代法不收敛

问题描述

上图的 $H$ 矩阵

$H= \begin{bmatrix} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \end{bmatrix}$

取 $\vec{v}^{(0)}=(0.1, 0.2, 0.3, 0.4)^T$ ，迭代过程如下，可以看出，向量序列并不收敛，其呈现一种周期性。

$\vec{v}^{(0)}$	$\vec{v}^{(1)}$	$\vec{v}^{(2)}$	$\vec{v}^{(3)}$	$\vec{v}^{(4)}$
$\begin{pmatrix} 0.1 \\ 0.2 \\ 0.3 \\ 0.4 \end{pmatrix}$	$\begin{pmatrix} 0.4 \\ 0.1 \\ 0.2 \\ 0.3 \end{pmatrix}$	$\begin{pmatrix} 0.3 \\ 0.4 \\ 0.1 \\ 0.2 \end{pmatrix}$	$\begin{pmatrix} 0.2 \\ 0.3 \\ 0.4 \\ 0.1 \end{pmatrix}$	$\begin{pmatrix} 0.1 \\ 0.2 \\ 0.3 \\ 0.4 \end{pmatrix}$

解决方案

假设现在有 $\alpha$ 的概率以 $S_{n \times n}$ 矩阵进行网页之间的跳转，有 $1-\alpha$ 的概率随机选择一个网页进行浏览，则修正后的矩阵为

$M_{n \times n}= \alpha S_{n \times n} + (1 - \alpha) \tfrac{1}{n}1$

其中 $\alpha \in [0,1)$ ，一般取 $\alpha=0.85$ 。我们可以证明，对 $M$ 矩阵采用幂迭代法一定能收敛到其平稳向量。

3. 证明

未完待续

Pagerank算法
一. Pagerank介绍PageRank算法以前就是Google的网页排序算法。PageRank算法，对每个目标...
大数据实例 | 你想知道搜索引擎排名怎么来的嘛---PageRa
目录什么是PageRank算法算法原理（1）算法原理（2）看论文推荐 1. 什么是PageRank算法 P...
PageRank算法
算法部分首先通过对理想情况的分析，阐述了PageRank算法的流程以及如何利用幂迭代法求解平稳向量，然后指出可能遇...
TextRank学习笔记
TextRank起源与PageRank TextRank的灵感来源于大名鼎鼎的PageRank算法，这是一个用作网...
统计学习方法——修炼学习笔记21：PageRank算法
PageRank算法是图的链接分享的代表性算法，属于图数据上的无监督学习方法。PageRank可以定义在任意有向图...
大数据Hadoop生态圈技术之浅析PageRank计算原理
一、什么是PageRank？ —— PageRank是Google提出的算法，用于衡量特定网页相对于搜索引擎索引中...
常用图算法实现--Spark
使用Spark实现PageRank，强连通分量等图算法 PageRank 数据准备边：网页：将这两个文件放入...
关键词和摘要
1、TextRank算法 https://zh.wikipedia.org/wiki/PageRank http:...
文章摘要的自动生成（2）textTank的应用
TextRank算法基于PageRank，用于为文本生成关键字和摘要。PageRank的原理已经在（1）里面总结了...
自然语言处理-PageRank（上）
PageRank 是什么 PageRank 一种是用来进行网页排序的算法，由Google的创始人拉里·佩奇和谢尔盖...