还原谷歌PageRank算法真相

之前写了七篇博客详细介绍了搜索引擎的工作原理。彼时的搜索引擎主要讲查询和网页的相关性匹配,是动态的、在线的、实时的。相关性匹配有一个问题,网页很容易作弊,比如可以在一个网页中写满诸如“免费”、“美容”之类的垃圾关键词,进而提升查询相关性。但是用户在查询时,一定希望返回的网页比较权威可信,比如同样搜索“苹果电脑”,排名第一的应该是Apple的官网,而不应该是中关村在线之类的第三方网站。

权威性是一个静态的(或者说变化较慢的)衡量网页重要性的指标。但是应该怎样度量权威性呢,HITS算法使用authority来度量,即指向自身的网页数量越多,则自身的authority值越大。谷歌的PageRank算法是用PageRank值来衡量权威性的。HITS和PageRank一个比较大的区别是HITS和查询有关,而PageRank和查询无关,所以PageRank可以离线计算。下面主要介绍PageRank算法。

PageRank’s thesis is that a webpage is important if it is pointed to by other important pages.

我先不加解释的给出PageRank的公式,然后带领大家一步步推导出这个公式。

\pi^T=\pi^T(\alpha S+(1-\alpha)E)

我们首先明确目标:PageRank计算的是网页的静态权威度(PR值),也就是如果给定了一个网络结构,则每个网页的PR值就可以通过PageRank算法计算出。假设网页$P_i$的PR值为$r(P_i)$,则$r(P_i)$等于所有指向$P_i$的网页的PR值之和,即

\begin{equation}r(P_i)=\sum\limits_{P_j\in B_{P_i}}\frac{r(P_j)}{|P_j|}\end{equation}

其中$B_{P_i}$为指向$P_i$的网页集合,$|P_j|$为$P_j$的出边的数量。这个式子很好理解,包括两方面内容:1)$\sum\limits_{P_j\in B_{P_i}}$表示如果指向$P_i$的网页数量越多,说明网页$P_i$越重要;2)$\frac{r(P_j)}{|P_j|}$表示如果$P_j$指向的页面数量越少,但有一个指向了$P_i$,说明网页$P_i$越重要(如果一个大牛写了很多推荐信($|P_j|$大),则这些推荐信的效力就下降了,如果大牛只给你写了推荐信($|P_j|=1$),则这封推荐信的效力一定很高)。

(1)式有一个问题,初始给定一个网络结构时,并不知道$r(P_i), r(P_j)$,如何计算呢?Brin和Page利用递归的思想求解,初始假设所有网页的PR值相等,都为$\frac{1}{n}$,其中$n$为网络中网页的数量。则第$k+1$轮的PR计算公式为:

\begin{equation}r_{k+1}(P_i)=\sum\limits_{P_j\in B_{P_i}}\frac{r_k(P_j)}{|P_j|}\end{equation}

初始对所有网页$P_i$有$r_0(P_i)=\frac{1}{n}$,迭代$k$步之后,可以计算出所有网页的PR值,然后按PR值从大到小排序,就可以知道每个网页的重要性了。

pr-1

对于上图的小网络,我们可以计算出其每一步的PR值:

pr-2

可以看到经过2次迭代之后,节点4的PR值最大,从图中也可以看出,节点4的出入边较多,它可能比较重要。

注意到对于(2)式,当$i,j$之间有边时,$\frac{1}{|P_j|}$相当于对$P_j$出度的归一化,设矩阵$H$为图的邻接矩阵的行归一化矩阵,对于上图,为

pr-3

设行向量$\pi^{(k)T}$为第$k$轮迭代时所有网页的PR值,则式(2)可以转换为如下的矩阵形式:

\begin{equation}\pi^{(k+1)T}=\pi^{(k)T}H\end{equation}

初始有$\pi^{(0)T}=\frac{1}{n}e^T$,$e^T$为全1的行向量。我们可以从(3)式观测出几点信息:

  • (3)式的每一轮计算涉及到向量和矩阵的乘法,复杂度为$O(n^2)$,$n$为矩阵$H$的大小
  • $H$是一个稀疏矩阵,因为大部分网页只和很少的网页有链接关系,所以上述向量和矩阵的乘法复杂度还可以降低
  • $H$有点像马尔科夫链中的随机转移矩阵,但又不完全是,因为如果有dangling nodes,则这一行就是全0,所以$H$被称为substochastic matrix
pr-4

上图中的节点3就是一个dangling node,它只有入边,没有出边,也就是说,每一轮迭代,PR值只会流入3号节点,不会从3号节点流出,久而久之,3就像一个水槽(sink)一样,吸走了大部分的PR,导致PR值虚高。

所以问题随之而来,怎样保证(3)式一定能够收敛到一个平稳概率分布$\pi^T$,$\pi^T$和$\pi^{(0)T}$有关吗,怎样解决dangling nodes问题,等等。此时需要引入一点马尔科夫链理论的知识。

在马尔科夫理论呢中,如果一个矩阵$P$是随机的(stochastic)、不可约的(irreducible)和非周期的(aperiodic),则对于任意的起始向量,都能收敛到一个唯一的平稳正向量。所以如果PageRank矩阵$H$满足上述三个条件,则可以用幂法(Power Method)找到一个平稳概率分布$\pi^T$。幂法是用来计算最大特征值的特征向量。因为$H$的最大特征值为1,所以可以用幂法找到稳态时($\pi^T=\pi^TH$)的概率分布$\pi^T$。

下面我们就将矩阵$H$调整为随机的(stochastic)、不可约的(irreducible)和非周期的(aperiodic)。

行随机矩阵是指行和为1的非负矩阵。如果图中含有dangling nodes,则$H$不是随机的,比如上面的例子,第二行为全0。所以第一个调整是对于所有dangling nodes,都加上一个随机跳转向量$e^T/n$,含义就是如果进入死胡同(dangling nodes),则随机跳转到网络中的任意一个网页。定义向量$a$:

\begin{equation}a_i=\begin{cases}1\quad\text{if page}~i\text{ is a dangling node}\\0\quad\text{otherwise}\end{cases}\end{equation}

则新的Google矩阵为:

\begin{equation}S=H+a\frac{1}{n}e^T\end{equation}

新矩阵$S$就是一个行随机矩阵了。对于上图的例子,有

pr-5

为了保证矩阵$S$满足不可约性(irreducible)非周期性(aperiodic),必须使$S$对应的图是强连通的且每个节点有子回路。所以再次调整为:

\begin{equation}G=\alpha S+(1-\alpha)\frac{1}{n}ee^T\end{equation}

\begin{equation}E=\frac{1}{n}ee^T\end{equation}

则得到本博客开头的Google矩阵公式:

\begin{equation}G=\alpha S+(1-\alpha)E\end{equation}

$E$即为随机平均游走矩阵。矩阵$G$也很好解释,大家上网的时候以$\alpha$的概率沿着某个网页里面的链接一步步深入进去($S$),当沿着链接走累的时候,以$1-\alpha$的概率在地址栏输入一个新地址,随机跳走了($E$)。

此时的矩阵$G$满足随机性(stochastic)、不可约性(irreducible)和非周期性(aperiodic),所以可以根据幂法(Power Method)找到一个平稳概率分布$\pi^T$,$\pi^T_i$就衡量了网页$P_i$的重要性或者权威性。

此时只剩下参数$\alpha$了,$\alpha$平衡了网络结构和随机游走。如果$\alpha$很小,则$1-\alpha$大,$G$就退化成一个人造随机网络,不能很好的反应真实的网络结构。如果$\alpha$很大,则有可能不能得到一个稳态分布,或者幂法会失效。当$\alpha\approx 1$时,幂法失效,且$\pi^T(\alpha)$对$H$的微小扰动很敏感。Google的选择是$\alpha=0.85$。

将(5)式带入(6)式,得到

\begin{equation}G=\alpha H+(\alpha a+(1-\alpha)e)\frac{1}{n}e^T\end{equation}

(9)式就非常好计算了,只涉及到向量和矩阵的乘法,而且矩阵$H$还是稀疏矩阵,复杂度还可以降低。

幂法(Power Method)求解PageRank稳态分布就是不断计算下面的等式:

\begin{equation}\pi^{(k+1)T}=\pi^{(k)T}G=\alpha \pi^{(k)T}H+(\alpha\pi^{(k)T}a+1-\alpha)e^T/n\end{equation}

当前后两次的$\pi^{(k+1)T}$和$\pi^{(k)T}$变化小于某个阈值时,算法收敛,所以算法实现是非常容易的。Brin and Page在他们1998年的论文中提到,只需要50-100次迭代运算就可以收敛了。

对于上图的例子,令$\alpha=0.9$,解得

pr-6

利用幂法解得稳态分布为

pr-7

所以这6个网页的排名为4>6>5>2>3>1。

真正的搜索引擎应该综合了网页的静态权威性(如PageRank值)和查询的相关性,每个网站都有一个PR值,具体可以点此查询

本博客主要内容参考Google’s PageRank and Beyond: The Science of Search Engine Rankings[1],插图即为该书封面;如果想快速了解PageRank,可以参考[2];[3]的讲解也很详细。

  1. http://geza.kzoo.edu/~erdi/patent/langvillebook.pdf
  2. http://www.cs.cmu.edu/~elaw/pagerank.pdf
  3. http://www.ams.org/samplings/feature-column/fcarc-pagerank

3 thoughts on “还原谷歌PageRank算法真相

  1. Pingback: 随机矩阵及其特征值 | bitJoy

  2. nce3xin

    写的太好了!!!!!!!!!逻辑清晰,按照文章所述(我没有找到书中的代码[笑cry]),实现了一遍,用文中的小网络做测试,结果完美匹配~!Thanks a lot !

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *