0%

从谱中心度到PageRank算法

图中心度表示方法

介数中心度

距离中心度

谱中心度

其中,主特征值对应特征向量的所有元素均非负

PageRank算法

PageRank的直观解释

$PageRank$ 的直观解释,被很多重要页面指向的页面是重要的页面。

即如果一个网页被很多其他网页链接到的话,说明这个网页比较重要,如果一个 $PageRank$ 值很高的网页链接到一个其他的网页,那么被链接到的网页的 $PageRank$ 值会相应地因此而提高。

$PageRank$ 的物理意义,对一个网页来说,当浏览者沿着网页中的超链接进行浏览时,访问到该网页的概率。

谱中心度与PageRank

证明:

转移概率矩阵是一个行和为 $1$ 的矩阵,所以也被称作行随机矩阵,如下图所示:

$$ P=\begin{bmatrix} 0 & 1/3 & 1/3 & 1/3\\ 1/2 & 0 & 1/2 & 0\\ 0 & 0 & 0 & 1\\ 1/2 & 1/2 & 0 & 0 \end{bmatrix} $$

主特征值是 $P$ 的所有特征值最大的那个,所以转移概率矩阵的主特征值为 $1$ 的证明可以转化为证明转移概率矩阵 $P$ 的特征值都小于等于 $1$,且最大特征值为 $1$ 的问题。

由于 $P$ 的每个行和都为 $1$,于是有:

$$ P[\frac{1}{n},\frac{1}{n},\cdots,\frac{1}{n}]^T=[\frac{1}{n},\frac{1}{n},\cdots,\frac{1}{n}]^T $$

因为 $P$ 的第 $i$ 行的元素和为 $1$, 所以 $P_{i·}[\frac{1}{n},\frac{1}{n},\cdots,\frac{1}{n}]^T =\sum_{j=1}^{n}\frac{1}{n}P_{ij}=\frac{1}{n}\sum_{j=1}^{n}P_{ij}=\frac{1}{n}$。于是上式得证,即 $[\frac{1}{n},\frac{1}{n},\cdots,\frac{1}{n}]^T$ 是转移概率矩阵 $P$ 特征值为 $1$ 对应的特征向量。

方法一:
令 $x_k$ 为 $\bf x$ 中最大的元素,又因为 $P$ 中的元素非负,且行和为 $1$,所以 $\lambda \bf x$ 中的每个元素都是 $\bf x$ 中元素的凸组合,假设 $\lambda \bf x$ 中的每个元素都小于等于 $x_k$ 。根据 $P \bf x = \lambda \bf x$,对 $P$ 的任意一行元素 $P_{i·}$, 有:
$$P_{i,1}x_1+P_{i,2}x_2+…+P_{i,n}x_n=\lambda x_i\leq x_k $$

此时若有 $\lambda \gt 1$,则会有 $\lambda x_k \gt x_k$,与假设矛盾。所以 $\lambda \le 1$,问题得证。

方法二:
取 $P$ 的任一特征向量 $x$ ,构造矩阵 $M = [x, 0, \cdots ,0]$ 。根据 $P \bf x = \lambda \bf x$ 有 $\lambda M = PM$ ,即 $|\lambda| ||M|| = ||PM||$ ,由矩阵范数的三角不等式得,$ ||PM|| \le ||P||||M||$。于是有 $|\lambda| \le ||P|| \le 1$。

$||M||$ 表示矩阵 $M$ 的一阶范数。

PageRank的算法原理

相关概念

$PageRank$ 算法总的来说就是预先给每个网页一个 $PR$ 值,由于 $PR$ 值物理意义上为一个网页被访问概率,所以一般情况下,所有网页的 $PR$ 值的总和为 $1$ 。如果不为 $1$ 的话最后算出来的不同网页之间 $PR$ 值的大小关系仍然是正确的,只是不能直接地反映概率。预先初始化给定 $PR$ 值后,通过不断迭代,直至达到平稳分布收敛为止。

互联网中的众多网页可以看作一个有向图。下图是一个简单的例子:

$PageRank$ 计算的是网页的静态权威度,也就是如果给定了一个网络结构,则每个网页的 $PR$ 值就可以通过算法计算出。记网页 $j$ 的 $PR$ 值为 $x_j$,则:$$ x_ j = \sum_{i \in IN(j)} \frac {A_{ij}} {d_j} x_i $$其中,$IN(j)$ 是指向网页 $j$ 的集合,$d_i$ 是网页 $i$ 的出度,$d_i = \sum_j A_{ij}$ , $ A_{ij}$ 表示的是邻接矩阵,有边为 $1$,否则为 $0$ 。所以对上图,$PR(A) =\frac {PR(B)} 2 + \frac {PR(C)} 1$。

迭代算法

在算法收敛后,有 $x_{t+1} = x_t$,根据 $x_{t+1}^T = x_t^TP$,可以得到 $x_t^T = x_t^TP$,也就是说 $x_t^T$ 是 $P$ 特征值为 $1$ 对应的特征向量,即转移概率矩阵的主特征向量。

收敛情况

使用最原始的 $PageRank$ 算法,则对于以下两种特殊网络,则会面临着算法不可收敛的问题

对于悬挂点来说,节点只有入度没有出度,此时 $P$ 中属于 $C$ 的那一行都是 $0$,假设权重向量初始化为 $[5,5,5]^T$,状态转移矩阵是$\begin{bmatrix} 0 & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & 0 \\ \end{bmatrix}$,则迭代过程如下所示:
$$[5,5,5]\begin{bmatrix} 0 & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & 0 \\ \end{bmatrix}^2=[\frac{5}{2},\frac{5}{2},5]\begin{bmatrix} 0 & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & 0 \\ \end{bmatrix}=[\frac{5}{4},\frac{5}{4},\frac{5}{2}]$$

对于循环指代,两个节点互相指向且不与其他节点相连,假设权重向量初始化为 $[5, 10]^T$ ,状态转移矩阵是每轮迭代都会交换 $PR$ 值 $[5,10]\to[10,5]\to[5,10]$,不会收敛。

保证收敛

对于悬挂点,将转移概率矩阵 $P$ 中悬挂点所在的行替换为 $ \frac {e^\top}{n} $,其中 $e^\top$ 是全 $1$ 的行向量,$n$ 是当前网络中网页的总数,即矩阵的维度。

对于循环指代,我们假定用户不会完全受当前网页所限,死板地只访问当前网页提供的链接。假定用户在每一步都有一个概率 $c$ 去访问当前网页所提供的链接,同时也有 $1-c$ 的概率随机访问互联网上的任何一个节点。这样就得到了如图所示的新矩阵 $G$ ,其中 $c$ 一般取 $0.85$ 。

PageRank的收敛证明

收敛证明

通过对悬挂点和循环指代点的处理,我们得到新的转移概率矩阵 $G$:
$$G=cS+(1-c)\frac{1}{n}ee^T\tag{1}$$

在 $PageRank$ 的迭代过程中,有:
$$ x_{t+1}^T = x_t^T G \tag{2}$$

于是计算 $PR$ 值的过程就变成了一个 $Markov$ 过程,那么 $PageRank$ 算法的证明也就转为证明 $Markov$ 过程的收敛性证明:如果这个 $Markov$ 过程收敛,那么$lim_{t\rightarrow \infty}x_t$存在,且与 $x_0$ 的选取无关。

若一个 $Markov$ 过程收敛,那么它的状态转移矩阵 $G$ 需要满足:

  1. $G$ 为随机矩阵
  2. $G$ 是不可约的
  3. $G$ 是非周期的

对于第一点,矩阵 $G$ 所有元素都大于等于 $0$,并且每一行的元素和都为 $1$,显然为一个随机矩阵。
对于第二点,方阵 $G$ 是不可约的当且仅当与 $G$ 对应的有向图是强联通的,有向图 $G=(V,E)$ 是强联通的当且仅当对每一对节点对 $u,v\in V$,存在从 $u$ 到 $v$ 的路径,因为我们在之前增加了随机跳转,所以矩阵 $G$ 同样满足不可约的要求。
对于第三点,所谓周期性,体现在 $Markov$ 链的周期性上。即若 $G$ 是周期性的,那么这个 $Markov$ 链的状态就是周期性变化的。因为 $G$ 是素矩阵(素矩阵指自身的某个次幂为正矩阵的矩阵),所以 $G$ 是非周期的。

收敛速度

通过对悬挂点和循环指代点的处理,我们得到了新的概率转移矩阵 $G$,所以有:
$${x_{t+1}^T}={x_t^T}G=cx_t^TS+(1-c)\frac{1}{n}x_t^Tee^T \tag{3}$$

因为 $x_i$ 代表节点 $i$ 的 $PR$ 值,所有 $PR$ 值的和为 $1$,于是就有 $x_t^Te=1$,所以可以得到:

$${x_{t+1}^T}=c{x_t^T}S+(1-c)\frac{1}{n}e^T$$

(图中最下面一行应该是 $x_t$ 而非 $x_t^T$,这里 $x$ 和特征向量 $v$ 都应该是一个列向量)

证明:

由 $ x_{t+1}^T = x_t^T G $ 可以得到 $ x_{t+1} = G^Tx_t $。

因为 $G$ 是一个满秩矩阵,所以 $G$ 和 $G^T$ 有相同的 $n$ 个线性无关的特征向量,记为 $v_0, v_1, \cdots, v_n$,所以 $x_0$ 必然可以用这些特征向量表示:
$$ x_0=\beta_1v_1+\beta_2v_2+\cdots+\beta_nv_n$$$$ x_1=x_0G ^T=\beta_1G^Tv_1+\cdots+\beta_nG^Tv_n=\beta_1\lambda_1v_1+\cdots+\beta_n\lambda_nv_n$$$$\vdots$$$$x_t=x_0(G^T)^t =\beta_1\lambda_1^tv_1+\beta_1\lambda_2^tv_2+\cdots+\beta_n\lambda_n^tv_n$$

其中 $\lambda_i$ 是 $v_i$ 对应的特征值,上文已经证明了 $\lambda_i$ 是小于等于 $1$ 的正数,所以当 $t\rightarrow \infty$时,$\lambda_i^t \rightarrow 0$,此时有 $|{x_{t+1}}-{x_{t}}|<\epsilon$,所以 $PageRank$ 终会收敛,收敛速度取决于次主特征值的大小。

此外, $0.85^{100}=0.87\times10^{-7}$,所以通常意义上说 $PageRank$ 算法在迭代 $100$ 次后就会收敛。

收敛顺序

拓展

PageRank的缺点

  1. 没有区分站内导航链接。很多网站的首页都有很多对站内其他页面的链接,称为站内导航链接。这些链接与不同网站之间的链接相比,肯定是后者更能体现 $PageRank$ 值的传递关系。
  2. 没有过滤广告链接和功能链接(例如常见的“分享到微博”)。这些链接通常没有什么实际价值,前者链接到广告页面,后者常常链接到某个社交网站首页。
  3. 对新网页不友好。一个新网页的一般入链相对较少,即使它的内容的质量很高,要成为一个高PR值的页面仍需要很长时间的推广。

LeaderRank

个性化PageRank


HITS

$HITS$ 算法的目的是:当用户查询时,返回给用户高质量的 $Authority$ 页面。其中一个页面扮演两种角色,$Hub$(枢纽节点)表示导出链接,$Authority$(权威节点)表示导入链接



参考文献:
[1] 沈华伟,《网络数据挖掘》,中国科学院大学2017年秋季研究生课程