PageRank 问题

PageRank 算法旨在评估网页重要性，如可以在搜索网页时将网页按重要程度依次排列所谓重要程度，在该模型的抽象简化中用网页间的超链接所衡量
将海量用户点击链接的过程视为随机过程，在这样的情形下，网站的点击概率全权取决于网页间的超链接。
直观而言，通向该网页的超链接越多，其流量越大，浏览概率越多。

在该问题的研究中：
将网页看作图的顶点
将网页之间的超链接看作顶点之间的有向边

现在需要从某个顶点开始移动，在随机的各顶点间移动，用得到的到各顶点的频率视作其重要程度，将移动进行无数次，即取极限得到的概率视作最终得到的结果，这便适合：
随机游走模型:
一个物体或者系统在一系列时间步长中随机地移动。每一步移动都是基于随机因素而不是预定的规则 .

在该问题中，在单独的一步中，终点实际上仅取决于该步的起点，是什么意思呢，就是说比如在某一步，准备从 $A$ 出发，到达 $A_1,A_2,...,A_s$ 所有可能的终点中的一个，$P(A\rightarrow A_i)$ 是确定的 $(i=1,...,s)$ ，与在 $A$ 之前经过了哪些点是完全无关的，这种过程称为Markov链
数学一点的语言来讲，即：

(离散时间)Markov链:
一组随机变量 $\mathbf X=\{X_n:n\in N\}$ , 其中 $X_k$ 的取值在可数集内,
条件概率满足 $P(X_{t+1}|X_t,...,X_1)=P(X_t)$ .

我们设 $t$ 为该随机过程中的时间, 作为"步数"
$V=\{v_1,v_2,...,v_n\}$ 为所有的顶点,
$E=\bigcup_{i=1,j=1}^nE_{ij}$ , $E_{ij}$ 为从$v_i$ 到 $v_j$ 的所有有向边的集合, 即有 $\varphi(E_{ij})=\{(v_i,v_j)\}$ , ( $\varphi$ 为该图的关联函数 )
如果从 $v_i$ 到 $v_j$ 有 $a_{ij}$ 条有向边, $|E_{ij}|=a_{ij}$
$P_t(v_i)$ 为 $t$ 时刻正处于顶点 $v_i$ 处的概率, $\sum_{i=1}^nP_t(v_i)=1$ , $P_t(v_i)\geq0$

现在考虑这个过程,
在起点, 即 $t=0$ 时, $P_0(v_i)$ 为初值
接下来, 动点的每一步从 $v_i$ 到 $v_j$ 的移动实际上会且仅会来源于两种操作:
$(\mathrm{I})$ 从 $v_i$ 到 $v_j$ 的超链接集 $E_{ij}$ 中选择一个
随机过程意味着每条边的权重都是相同的, 由于顶点间的有向边(的条数)都是已知的, 因此从 $v_i$ 出发通过有向边到达 $v_j$ 的概率是可求得的
$(\mathrm{II})$ 从 $v_i$ 随机的(直接输入网址)到达 $V$ 中的任意一个顶点(包括它自身), 由于各顶点权重也是相等的, 实际上到达各顶点的概率也是相同的, 因此实际上最后可得到结果是与该步骤无关的, 但为考虑它的实际意义, 下面计算中会考虑到它

上面提到, 单独的一步从 $v_i$ 通过有向边到达 $v_j$ 的概率是可求得的, 取决于给的数据条件, 我们先假设已知, 这里记为

\[ p_{ij} \]

由概率的性质应满足

\[ p_{ij}>0,\qquad\sum_{j=1}^np_{ij}=1,\qquad(i,j=1,2,...,n) \]

事实上有

$$ p_{ij}=\frac{a_{ij}}{a_{i1}+a_{i2}+\cdots+a_{in}} $$ 假设在 $t=k$ 时刻, 已知了 $P_k(v_i)$ $(i=1,2,...,n)$ , 那么 $t=k+1$ 时, 出现在所有顶点的概率都是可求的, 事实上, 出现在顶点 $v_j$ 的概率为

\[ P_{k+1}(v_j)=\sum_{i=1}^nP_{k}(v_i)\cdot(d\cdot p_{ij}+(1-d)\cdot\frac{1}{n}) \]

理由是: 在 $k$ 时刻, 可能从 $v_1,v_2,...,v_n$ 处到达 $k+1$ 时刻的 $v_j$
若从 $v_i$ 处开始, 有两种方式进行下一步, 它们是由经验决定的, 概率分别为 $d$ 和 $1-d$
如果选择超链接, 那么跟起点有关, 先乘 $P_k(v_i)$ 再乘 $p_{ij}$ ; 如果选择直接输入, 与起点无关, 直接乘 $\frac{1}{n}$
那么有

\[ P_{k+1}(v_j)=d\cdot\sum_{i=1}^nP_{k}(v_i)\cdot p_{ij}+\frac{1-d}{n}=d\cdot\begin{bmatrix}p_{1j}&p_{2j}&\cdots&p_{nj}\end{bmatrix}\begin{bmatrix}P_k(v_1)\\P_k(v_2)\\\vdots\\P_k(v_n)\end{bmatrix}+\frac{1-d}{n} \]

可得到

\[ \underbrace{\begin{bmatrix}P_{k+1}(v_1)\\P_{k+1}(v_2)\\\vdots\\P_{k+1}(v_n)\end{bmatrix}}_{x_{k+1}}=d\cdot\underbrace{\begin{bmatrix}p_{11}&p_{21}&\cdots&p_{n1}\\p_{12}&p_{22}&\cdots&p_{n2}\\\vdots&\vdots&\ddots&\vdots\\p_{1n}&p_{2n}&\cdots&p_{nn}\end{bmatrix}}_P\underbrace{\begin{bmatrix}P_k(v_1)\\P_k(v_2)\\\vdots\\P_k(v_n)\end{bmatrix}}_{x_k}+\frac{1-d}{n}\beta,\qquad\qquad(\beta=\sum_{i=1}^n\varepsilon_i) \]

也即

\[ x_{k+1}=dPx_{k}+\frac{1-d}{n}\beta,\qquad\qquad\qquad(*) \]

$P$ 称作随机邻接矩阵

$(\mathrm I)$ 当 $d=1$ 时

\[ x_{k+1}=Px_{k} \]

如若各顶点的出现概率, 即Pagerank, 出现平稳分布, 即极限存在, 那么令 $k\to\infty$ , 记 $x$ 为收敛后的概率向量, 应有

\[ x=Px \]

指出了 $x$ 应为 $P$ 的特征值 $1$ 下的特征向量