搜索引擎的PageRank模型¶

约 1329 个字预计阅读时间 4 分钟

网页重要度假设¶

利用有向图将网络进行链接由此计算网页重要度

网页\(v_i\)对其他网页的贡献度和为\(x_i\)
网页\(v_i\)对它链接的\(q_i\)个网页中的任一个的重要度贡献为\(\frac{x_i}{q_i}\)
若链接到网页\(v_i\)的网页有\(v_{j_1},v_{j_2},...,v_{j_k}\)，则有\(x_j=\frac{x_{j_1}}{q_{j_1}}+\frac{x_{j_2}}{q_{j_2}}+\dots+\frac{x_{j_k}}{q_{j_k}}\)

线性方程组

\(x_j=\frac{x_{j_1}}{q_{j_1}}+\frac{x_{j_2}}{q_{j_2}}+\dots+\frac{x_{j_k}}{q_{j_k}}=p_{i1}x_1+p_{i2}x_2+\dots+p_{in}x_n=\Sigma_{j=1}^np_{ij}x_j, j=1,\dots,n\)

我们使用矩阵来表示，其中\(\begin{equation} p_{ij}=\left\{ \begin{aligned} \frac{1}{q_j} & , 有链接自v_j链向v_i \\ 0 & , 其他 \end{aligned} \right. \end{equation}\)

由此，记矩阵\(\mathbf{P}=(p_{ij})_{n\times n}\)为初始链接矩阵，\(\mathbf{X}=(x_1,\dots,x_n)^T\)为网页重要度

亦可知，\(\mathbf{X}\)为线性方程组\(\mathbf{X}=\mathbf{PX}\)的解，有

任一随机矩阵的模最大特征值为 1

证明

设\(\lambda\)是行随机矩阵\(\mathbf{P}=(p_{ij})_{n\times n}\)的特征值，非零向量\(\mathbf{X}=(x_1,\dots ,x_n)^T\)为属于特征值\(\lambda\)的特征向量，取\(\left\lvert x_i\right\rvert =\max_{i\leq j\leq n} \left\lvert x_j\right\rvert >0\)
有\(\lambda x_i=\Sigma_{j=1}^n p_{ij}x_j\)，两边取模，有\(\left\lvert \lambda \right\rvert \left\lvert x_i\right\rvert =\left\lvert \Sigma_{j-1}^n p_{ij}x_j\right\rvert \leq \Sigma_{j-1}^n \left\lvert p_{ij}\right\rvert \left\lvert x_j\right\rvert\leq \left\lvert x_i\right\rvert \Sigma_{j-1}^n \left\lvert p_{ij}\right\rvert=\left\lvert x_i\right\rvert\)，故有\(\left\lvert \lambda\right\rvert \leq 1\)

连接矩阵P每列元素之和为1，为列随机矩阵
悬挂网页 (dangling link)
- 若某网页不链接到任意其他网页，将链接矩阵P中的对应列的所有元素由0修改为\(\frac{1}{n}\)，得到（修正）连接矩阵\(\overline{\mathbf{P}}\)
若\(\overline{\mathbf{P}}\)有两个属于特征值1的线性无关的特征向量重要度向量排序不唯一
于是将\(\overline{\mathbf{P}}\)修改为（最终）链接矩阵\(\overline{\overline{\mathbf{P}}}=\alpha \overline{\mathbf{P}}+(1-\alpha)\frac{1}{n}\mathbf{11}^T,\alpha =0.85\)
- 易知\(\overline{\overline{\mathbf{P}}}\)为完全正矩阵(totally positive matrix)与列随机矩阵
- \(\mathbf{1}^T\overline{\overline{\mathbf{P}}}=\alpha\mathbf{1}^T\overline{\mathbf{P}}+(1-\alpha)\frac{1}{n}\mathbf{1}^T\mathbf{11}^T=\alpha\mathbf{1}^T+(1-\alpha)\mathbf{1}^T=\mathbf{1}^T\)

完全正、列随机矩阵属于特征值1的特征向量分量之和不为0

证明（反证）

设\(\mathbf{x}=(x_1,\dots ,x_n)^T\)为完全正、列随机矩阵\(\mathbf{P}\)的属于特征值1的特征向量，则\(x_i=\Sigma_{j=1}^n p_{ij}x_j\)
若\(\Sigma_{x_i}^nx_i=0\)，则\(\mathbf{x}\)的分量有正有负，故\(\left\lvert x_i\right\rvert =\left\lvert \Sigma_{j=1}^np_{ij}x_j\right\rvert <\Sigma_{j=1}^np_{ij}\left\lvert x_j\right\rvert , i=1,\dots,n\)
\(\Sigma_{i=1}^n\left\lvert x_i\right\rvert<\Sigma_{i=1}^n\Sigma_{j=1}^np_{ij}\left\lvert x_j\right\rvert =\Sigma_{j=1}^n\left\lvert x_j\right\rvert (\Sigma_{i=1}^np_{ij})=\Sigma_{j=1}^n\left\lvert x_j\right\rvert\) 矛盾

完全正、列随机矩阵仅有1个属于特征值1的线性无关的特征向量

证明（反证）

设\(\mathbf{v}=(v_1,\dots,v_n)^T,\mathbf{w}=(w_1,\dots,w_n)^T\)是完全正、列随机矩阵\(\mathbf{P}\)的两个属于特征值1的线性无关的特征向量
令\(V=\Sigma_{k=1}^nv_k\neq 0,W=\Sigma_{k=1}^nw_k,\mathbf{x}=-\frac{W}{V}\mathbf{v}+\mathbf{w}\)，有\(\mathbf{Px}=-\frac{W}{V}\mathbf{Pv}+\mathbf{Pw}=-\frac{W}{V}\mathbf{v}+\mathbf{w}=\mathbf{x}\)，\(\mathbf{x}\)也为\(\mathbf{P}\)属于特征值1的特征向量
又有\(\Sigma_{i=1}^nx_i=-\frac{W}{V}\Sigma_{i=1}^nv_i+\Sigma_{i=1}^nw_i=-\frac{W}{V}\cdot V+W=0\)，与前一条性质不符

若矩阵A为非负不可约(irreducible)矩阵，则
- A的模最大特征值为正实数
- 该特征值代数重数为1
- 存在该特征值的一个特征向量，其分量全为正

按以下模式浏览网页

两种模式的比例为 \(5:1\) ，即为前文的0.85的来源

于是有：从任意网页开始，充分长时间后，访问各网页的概率即为网页重要度

记事件{\(X_m=j\)}为时刻\(m\)访问网页\(j\)，则\(P\{X_m=i|X_{m-1}=j\}=p_{ij}\)

若\(P\{X_{m-1}=j\}=x_j , j=1,\dots,n\)，则