2023-12-04

PageRank——网页重要度

引言:

PageRank是一种用于评估网页重要性的算法，最初由谷歌创始人之一拉里·佩奇（Larry Page）提出。该算法基于网络图的链接结构，通过分析网页之间的链接关系来确定网页的权重和排名。本文将着重介绍PageRank应用的数学模型，及一些重要的数学概念。

Page Rank

网页重要度：连接到某网页的其他网页对该网页有贡献度。网页重要度作为网页排序的依据。所有网页的重要度贡献之和等于该网页的重要度。

连接到网页A的所有网页对网页A的重要度均有贡献，贡献大小和这些网页本身的重要度有关

（1）传递性：重要度大的网页连接到网页A对网页A的重要度贡献比重比重要度小的网页连接到网页A的重要度贡献大。

（2）等效性：网页链接较多时对他所链接的网页的重要度的贡献比连接较少时对他所链接的网页的重要的的贡献小

（3）无关性：网页链接其他网页的多少，与其本身的重要度无关

（2）叠加性：链接到网页A的网页越多，则网页A越重要

网络连接图：
- 互联网中网页之间的链接关系应用图表示。
  - 顶点：网页
  - 弧：网页间的链接关系
  - 出度：以某顶点为起点的弧的总数，即该网页链接的网页的数量
网页重要度
- 网页的重要度记为，出度记为
  - 网页对其他网页重要度贡献之和为
  - 网页对他连接的个网页的贡献度之和为
  - 网页对它连接的个网页中的任一个的重要度贡献为
  - 若链接到网页的网页有则
  将网络链接图各方程联立组成线性方程组，解出线性方程组即可获得每个网页的重要度。 X为线性方程组X=PX的解为保证该线性方程组有解，必须保证邻接矩阵的行列式等于0 即
$秩$
邻接矩阵的特性：
- 邻接矩阵的每一列加起来都等于1
- 矩阵有特征值1（所有行向量是线性相关的）由此，邻接矩阵必有解。
随机矩阵
- 各行（列）元素之和为1的非负方阵成为行（列）随机矩阵。
- 各行与各列元素之和均为1的非负方阵成为双随机矩阵。
随机矩阵的模最大特征值
- 任一随机矩阵的模最大特征值

Prove: 设行随机矩阵的特征值，非零向量为属于特征值的特征向量设由得即

悬挂网页
- 某网页不链接其他任何网页
  - 链接矩阵中对应列元素全为0
  - 网络链接图中对应顶点的出度为0 解决方式：
- 将该列所有元素修改为1/n，链接矩阵成为随机矩阵
- 链接矩阵为一随机矩阵，该矩阵属于特征值1的特征向量即为重要度向量
唯一性：
- 若P有两个属于特征值1的线性无关的特征向量（属于特征值的特征子空间位数大于1），用上述方法可能得到相互矛盾的网页重要度比较结果。
- 完全正，列随机矩阵属于特征值1的特征向量分量之和不为0。
- 完全正，列随机矩阵仅有一个属于特征值1的线性无关的特征向量。
Perron定理
- 若矩阵A为完全正矩阵，则
  - A的模最大特征值唯一，且为正实数
  - 该特征值代数重数为1
  - 存在该特征值的一个特征向量，其分量全为正
- 链接矩阵与重要度向量
  - 链接矩阵为完全正，列随机矩阵，模最大特征值为1，重要度向量唯一且分量全为正。
Perron-Drobenius定理
- 弱矩阵A为非负且不可约矩阵，则
  - A的模最大特征值为正实数
  - 该特征值代数重数为1
  - 存在该特征值的一个特征向量，其分量全为正
不可约矩阵
- 若干个初等对换矩阵的乘积称为置换矩阵每个置换矩阵每行和每列都恰有一个元素为1，其余元素为0
- 若存在置换矩阵Q，使得其中XZ均为仿真，则称A为可约矩阵，否则A为不可约矩阵。
不可约矩阵与有向图
- 若对有向图中任一顶点对，既存在一条从到的有向路，也存在一条从到的有向路，则称有向图是强联通的。
- 给定非负矩阵构造有向图，其中,弧当且仅当
- A是不可约矩阵当且仅当A时强联通的。

矩阵计算

幂法（求模最大特征值）
- 任取初始向量 $且$
- 计算当x趋近于收敛即可。

随机浏览（马尔科夫链）

按一下模式浏览互联网中的网页
- 有时从当前网页的链接中随机打开一个网页（5）
- 有时键入网址新建一个网页（1）
从任一网页开始，充分长时间后，访问各网页的频率，即为网页重要度
极限概率
- 记事件为时刻m访问网页j，则
- 若，则
- 满足幂法
随机过程
- 描述随机现象随时间推移而烟花的一类数学模型
- 一族随机变量其中t是参数，T是参数集
  - T为整数集的随机过程称为随机序列
Markov过程
- 在已知目前的状态的条件下，它未来的演变不依赖于它以往的演变
- 随机序列