# PageRank 与马尔可夫链

[[MCS/day11/00 学习指南|day11 学习指南]] · [[MCS/00 MCS学习总览|十一天总览]] · [[MCS/day11/阅读核验与疑问|阅读核验与疑问]] · 上一篇：[[MCS/day11/03 评分矩阵与低秩推荐|评分矩阵与低秩推荐]] · 下一篇：[[MCS/day11/05 椭圆曲线与后量子密码课堂记录|椭圆曲线与后量子密码课堂记录]]

> 来源：[[MCS/day11概率统计与大数定律|day11概率统计与大数定律]]。用途：选学。原有推导、追问与解答保留；阅读时请结合本日核验说明。

PageRank 与图算法:
线性代数 概率论（马尔科夫链）图论
## PageRank、马尔可夫链与相关数学基础

---

### 一、PageRank 是什么

PageRank 是一个**图算法**，用来衡量网页的重要性。

它的核心是一个**特征向量问题**。

公式可以写成：

$\pi = \pi P$

其中：

- $\pi$：PageRank 向量，每个分量表示对应网页的重要性
- $P$：随机游走转移矩阵（random walk transition matrix）

含义：

> $\pi$ 是矩阵 $P$ 对应**特征值 1** 的**主特征向量**。

---

### 二、PageRank 的直觉

一个网页的重要性，取决于链接到它的网页的重要性。

这是一个**递归定义**：

- 网页 A 重要，是因为链接到 A 的网页 B、C 重要
- 网页 B 重要，又是因为链接到 B 的网页 D、E 重要
- 如此递归下去

数学上，这就归结为一个**特征向量问题**。

---

### 三、涉及的数学基础

PageRank 涉及三个数学领域：

| 领域 | 用到的内容 |
|---|---|
| 线性代数 | 特征值、特征向量、主特征向量 |
| 概率论 | 马尔可夫链、随机游走 |
| 图论 | 网页链接图、节点重要性传播 |

其中概率论部分主要用的是**马尔可夫链**。

---

### 四、马尔可夫链

#### 1. 定义

马尔可夫链是一个**随机状态序列**：

> 下一个状态是什么，只由**当前状态**决定，和之前的历史无关。

用数学表达：

$P(X_{t+1} \mid X_t, X_{t-1}, \dots) = P(X_{t+1} \mid X_t)$

#### 2. 无后效性

这个性质叫做：

> **无后效性（Markov property）**

因为发现这个性质的人是马尔可夫，所以也叫**马尔可夫性**。

一句话记住：

> **未来只看现在，不看过去。**

#### 3. 和 PageRank 的关系

- 网页上的随机游走就是一个马尔可夫链
- 随机游走转移矩阵 $P$ 就是马尔可夫链的转移矩阵
- PageRank 向量 $\pi$ 就是这条马尔可夫链的**平稳分布**
- 平稳分布正好对应矩阵 $P$ 特征值 1 的主特征向量

所以：

$\pi = \pi P$

---

### 五、整体逻辑链

> PageRank 衡量网页重要性  
> → 重要性递归定义：取决于链接到它的网页的重要性  
> → 数学上是特征向量问题：$\pi = \pi P$  
> → $P$ 是随机游走转移矩阵  
> → 随机游走是马尔可夫链  
> → 马尔可夫链的核心性质：无后效性（未来只看现在，不看过去）  
> → 涉及的数学基础：线性代数 + 概率论 + 图论

---

### 六、一句话总结

> PageRank 的本质是一个**特征向量问题**：  
> 网页重要性向量 $\pi$ 是随机游走转移矩阵 $P$ 对应特征值 1 的主特征向量；  
> 背后的数学基础是**线性代数 + 马尔可夫链 + 图论**；  
> 马尔可夫链的核心是**无后效性**：未来只看现在，不看过去。



## 马尔可夫链与 PageRank

---

### 一、马尔可夫链的两个组成部分

马尔可夫链由两个东西组成：

1. **状态集合（State Set）**，记作 $S$
2. **状态转移概率矩阵（Transition Probability Matrix）**，记作 $P$

---

### 二、状态集合 $S$

状态集合 $S$ 表示：

> 所有可能出现的状态。

举例：**天气模型（Weather Model）**

天气的可能状态：

- 晴天
- 阴天
- 雨天

那么状态集合就是：

$S = \{\text{晴天}, \text{阴天}, \text{雨天}\}$

---

### 三、状态转移概率矩阵 $P$

状态转移概率矩阵表示：

> 从一个状态跳到另一个状态的概率。

它描述的是：

- 当前状态（current state）
- 未来状态（next state）

之间的转移规则。

#### 关键规则

矩阵的**每一行所有数字加起来等于 1**。

为什么？

因为从当前状态出发，跳到某个状态的所有可能性总和是：

$100\%$

也就是：

$\sum_{j} P_{ij} = 1$

其中 $P_{ij}$ 表示从状态 $i$ 转移到状态 $j$ 的概率。

---

### 四、PageRank 与马尔可夫链的关系

PageRank 是 Google 搜索排名的底层算法。

但它的应用远不止搜索。

#### 1. PageRank 的本质

PageRank 的核心是一个**特征向量问题**：

$\pi = \pi P$

其中：

- $\pi$：PageRank 向量
- $P$：随机游走转移矩阵

$\pi$ 是矩阵 $P$ 对应**特征值 1** 的**主特征向量**。

#### 2. 涉及的数学基础

| 领域 | 用到的内容 |
|---|---|
| 线性代数 | 特征值、特征向量、主特征向量 |
| 概率论 | 马尔可夫链、随机游走 |
| 图论 | 网页链接图、节点重要性传播 |

#### 3. 马尔可夫链的核心性质

> **无后效性（Markov property）**

一句话记住：

> **未来只看现在，不看过去。**

数学表达：

$P(X_{t+1} \mid X_t, X_{t-1}, \dots) = P(X_{t+1} \mid X_t)$

---

### 五、PageRank 在近年的应用

在 2025 与 2026 年的研究中，PageRank 被广泛应用：

#### 1. 图神经网络（GNN）

- 作为**结构中心性**度量
- 用于**增强节点表示**

#### 2. 交通异常监测

- 通过 patch embed 预表征来增强感受
- 避免**过平滑（over-smoothing）**

#### 3. 反洗钱检测

- 通过**扩散（diffusion）** 与 PageRank 结合
- 生成**无监督节点嵌入**

---

### 六、整体逻辑链

> 马尔可夫链 = 状态集合 $S$ + 状态转移概率矩阵 $P$  
> → 矩阵每行和为 1，表示从当前状态出发所有可能性的总和为 100%  
> → PageRank 是随机游走转移矩阵 $P$ 的主特征向量问题：$\pi = \pi P$  
> → 涉及线性代数、概率论、图论  
> → 核心性质：无后效性（未来只看现在，不看过去）  
> → 近年广泛用于 GNN、交通异常监测、反洗钱检测等

---

### 七、一句话总结

> 马尔可夫链由**状态集合**和**状态转移概率矩阵**组成，矩阵每行和为 1；  
> PageRank 是 Google 搜索排名的底层算法，本质是随机游走转移矩阵的主特征向量问题 $\pi = \pi P$；  
> 它的数学基础是线性代数 + 马尔可夫链 + 图论，核心性质是无后效性；  
> 近年 PageRank 被广泛用于图神经网络、交通异常监测、反洗钱检测等领域。



$\pi P = 1 \cdot \pi$