Page rank

背景

page rank算法最初是用来计算网页重要度的算法，在1996年由Page和Brin提出，用于谷歌搜索引擎的网页排序。
其可以应用在任意的DAG中，后来被应用到社会影响力分析、文本摘要等多个问题。

网页重要度

搜索引擎中，首先需要将网页进入收录。而page rank就是定义在网页集合上的一个函数，对每个网页都输出一个表示重要程度的数字。

基本想法：
- 将所有网页看做一个有向图，在其上面定义随机游走模型(即一阶马尔可夫链)， 表示网页浏览者在互联网上随机浏览网页的过
- 假设浏览者在每个网页依照连接出去的超链接以等概率跳转到下一个网页，并在网上持续不断进行这样的随机跳转，这个过程形成一阶马尔可夫链
- PageRank表示这个马尔可夫链的平稳分布，每个网页的PageRank值就是平稳概率

1. pageRank定义

在进行pageRank的定义之前，先看几个基础概念的定义：

随机游走模型:
给定一个含有n个节点的有向图，在图上定义随机游走模型，从一个节点到其有向边相连的所有节点的转移概率相同。记其转移矩阵为M, t时刻访问各个节点的概率分布记录为t时刻的状态，则有
$R_{t+1}=MR_t$
其中M满足每个元素非负，且每列元素之和为1.

【定义】Page rank-基本定义
对于包含n个节点的强连通图，定义在其上的随机游走模型，则其极限$\lim_{t-> ∞} M^tR_0=R$ 存在，极限向量R表示马尔可夫链的平稳分布，满足
$<span class="arithmatex"><span class="MathJax_Preview">MR=R</span><script type="math/tex">MR=R$
平稳分布R称为这个有向图的PageRank

强连通图：对于有向图，如果从其中任何一个节点出发可以到达其他任何一个节点则称该图是强连通图

【定义】page rank 一般定义
实际情况下，很多节点并不一定会有出链或者入链，所以不会是强连通的。比如

在该图中节点C没有，转移矩阵M此时不是一个随机矩阵，因为存在某列和不是1。如果用前面说的方式，随着时间的推移，最终计算得到的各个节点的概率变为0

一般定义：
$<span class="arithmatex"><span class="MathJax_Preview">R=dMR + \frac{1-d}{n}1</span><script type="math/tex">R=dMR + \frac{1-d}{n}1$
- d: 阻尼因子
即对于每个节点不止考虑与其有连接的，还考虑与其没有连接的那些点。对于没有连接的那些点，其mij不是0，也赋予一个较小的数，做一个平滑处理。
- 后面那个1是取值都是1的向量
- 直观理解：浏览者可以概率d按照给定的超链做随机跳转，也可以以(1-d)做随机跳转。

2. PageRank的计算

(1) 直接根据迭代公式计算，直至收敛

$$R_{t+1} = dMR_{t} + \frac{1-d}{n}1$$

同样上面的例子，假设取d=0.8， R0=(¼, ¼, ¼, ¼), 进行迭代之后

(2) 幂法
通过近似计算矩阵的主特征值和主特征向量的方式，具体地。

首先看这么一个问你：假设矩阵A有n个特征值，按照绝对值大小排列:
$<span class="arithmatex"><span class="MathJax_Preview">|\lambda_1| \ge |\lambda_2| \ge ..|\lambda_n|</span><script type="math/tex">|\lambda_1| \ge |\lambda_2| \ge ..|\lambda_n|$
对应的n个线性无关的特征向量是u1,u2, ....un
则对于任意一个n维向量x0，其可以表示成基空间的线性组合，所以有
$<span class="arithmatex"><span class="MathJax_Preview">x_0=a_1u_1 + a_2u_2+...+a_nu_n</span><script type="math/tex">x_0=a_1u_1 + a_2u_2+...+a_nu_n$
$<span class="arithmatex"><span class="MathJax_Preview">x_1=Ax_0=a_1Au_1 + a_2Au_2+...+a_nAu_n</span><script type="math/tex">x_1=Ax_0=a_1Au_1 + a_2Au_2+...+a_nAu_n$
$<span class="arithmatex"><span class="MathJax_Preview">x_k=Ax_{k-1}=a_1A^ku_1 + a_2A^ku_2+...+a_nA^ku_n=a_1\lambda_1^ku_1 + ...+a_n\lambda_n^ku_n</span><script type="math/tex">x_k=Ax_{k-1}=a_1A^ku_1 + a_2A^ku_2+...+a_nA^ku_n=a_1\lambda_1^ku_1 + ...+a_n\lambda_n^ku_n$
所以有:

$<span class="arithmatex"><span class="MathJax_Preview">x_k -&gt; a_1\lambda_1^ku_1 (k-&gt;∞)</span><script type="math/tex">x_k -> a_1\lambda_1^ku_1 (k->∞)$
即当进行无数次迭代后，xk与其主特征向量u1之间只相差一个常数，所以有$\lambda_1≈\frac{x_{k+1,j}}{x_{k, j}}$，在实际计算时候为了避免出现绝对值过大或者过小，在每一次迭代后可以进行规范化操作。

回到pageRank的计算

(3) 代数算法
根据定义$<span class="arithmatex"><span class="MathJax_Preview">R=dMR + \frac{1-d}{n}1</span><script type="math/tex">R=dMR + \frac{1-d}{n}1$
所以有$<span class="arithmatex"><span class="MathJax_Preview">R=(I-dM)^{-1}\frac{1-d}{n}1</span><script type="math/tex">R=(I-dM)^{-1}\frac{1-d}{n}1$
当0<d<1时，方程组的解存在且唯一。