MMDS Chapter 5: Link Analysis（链接分析）

Posted on In Word count in article: 6.6k Reading time ≈ 24 mins.
> 教材：Mining of Massive Datasets

MMDS Chapter 5: Link Analysis（链接分析）

教材：Mining of Massive Datasets 作者：Jure Leskovec, Anand Rajaraman, Jeffrey D. Ullman

一、概述与背景

链接分析 (Link Analysis) 是大规模网络数据挖掘中的核心主题之一。本章深入探讨如何利用网页之间的链接关系来评估网页的重要性，这是现代搜索引擎的关键技术基础。

互联网的本质是一个庞大的有向图，其中每个网页是一个节点，超链接则形成了节点之间的有向边。通过分析这种链接结构，我们可以发现哪些网页对用户最有价值，以及如何利用这些信息改进搜索引擎的排名。

二、PageRank 算法基础

2.1 早期搜索引擎与术语垃圾

在 Google 搜索引擎出现之前，早期的搜索引擎采用了相对简单的方法：

  • 爬虫技术：网络爬虫遍历万维网，获取每个网页的内容
  • 倒排索引：建立从术语到网页的映射，即 (Inverted Index) 结构
  • 排名方法：基于查询词在网页中的出现频率、位置（如标题、头部）等因素进行排名

然而，这种方法存在严重的安全漏洞——术语垃圾 (Term Spam)：

恶意网页创建者可以通过以下技巧欺骗搜索引擎： 1. 在网页中无限次重复与实际内容无关的热门搜索词（如"电影"） 2. 将这些重复的词设置为与背景色相同，使用户看不见但搜索引擎能检测到 3. 复制排名靠前的网页内容以获得高排名

Google 的两项创新： 1. PageRank 算法：通过随机游走模型来评估网页的重要性，基于网页被其他网页链接的频率 2. 链接锚文本分析：考虑指向网页的链接及其上下文词汇，而不仅仅是网页本身的内容

这两项创新共同解决了术语垃圾问题，因为： - 简单的链接计数虽然看起来可行，但垃圾制造者可以创建数百万个链接指向目标网页 - 需要更复杂的算法来区分有意义的链接和垃圾链接

2.2 PageRank 的定义

PageRank 是基于随机游走模型的网页排名算法。其核心思想是：一个网页的重要性取决于有多少个重要的网页链接到它。

2.2.1 网络图表示

将万维网表示为有向图 \(G=(V,E)\)： - 顶点集 \(V\)：所有网页 - 边集 \(E\)：所有超链接 - 出度 (Out-Degree)：\(d_j\) 表示网页 \(j\) 的出链数量

2.2.2 转移矩阵

设网络包含 \(n\) 个网页，定义 \(n \times n\) 的转移矩阵 \(M\)（也称为 Transition Matrix）：

\[M_{ij} = \begin{cases} \frac{1}{d_j} & \text{if page } j \text{ has a link to page } i \\ 0 & \text{otherwise} \end{cases}\]

其中 \(d_j\) 是网页 \(j\) 的出链数。矩阵 \(M\) 是列随机的 (Column-Stochastic)，即每列的和为 1。

示例 5.1：四节点网络

考虑有向图：\(A \rightarrow B\)，\(B \rightarrow C\)，\(C \rightarrow A, B\)，\(D \rightarrow C, D\)

各页面出度：\(d_A=1, d_B=1, d_C=2, d_D=2\)

转移矩阵为：

\[M = \begin{pmatrix} 0 & 0 & 1/2 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1/2 \\ 0 & 0 & 1/2 & 1/2 \end{pmatrix}\]

2.2.3 随机游走模型

随机游走 (Random Walk/Random Surfer) 的过程： 1. 初始时，游走者从 \(n\) 个网页中均匀随机选择一个（初始分布 \(v_0 = e/n\)，其中 \(e\) 是全1向量） 2. 在每个时步，游走者从当前网页随机选择一条出链，跳转到相邻网页 3. 重复此过程

在 \(t\) 步之后的概率分布为： \[v_t = M^t v_0\]

其中 \(v_t\) 是第 \(t\) 步的概率分布向量。

2.2.4 稳定分布与 PageRank

如果马尔可夫链 (Markov Chain) 满足以下条件： 1. 图是强连通的 (Strongly Connected) 2. 不存在死端 (Dead End)

则随机游走过程会收敛到唯一的稳定分布 \(v\)，满足： \[v = Mv\]

即 \(v\) 是矩阵 \(M\) 的特征值为 1 的特征向量（主特征向量）。

PageRank 就是这个稳定分布，通常在 50-75 次迭代后收敛到足够精度。

示例 5.2：计算四节点网络的 PageRank

从 \(v_0 = (1/4, 1/4, 1/4, 1/4)^T\) 开始迭代：

\[v_1 = M v_0 = \begin{pmatrix} 1/8 \\ 1/4 \\ 3/8 \\ 1/4 \end{pmatrix}\]

继续迭代直到收敛，最终稳定分布为： \[v = \left(\frac{3}{9}, \frac{2}{9}, \frac{2}{9}, \frac{2}{9}\right)^T\]

网页 A 的 PageRank 最高（1/3），因为有两个网页链接到它。

2.3 真实网络的结构问题

真实网络与理论假设有重大差异，不满足强连通性和无死端的要求。

蝴蝶结构 (Bow-Tie Structure)： - 强连通分量 (SCC, Strongly Connected Component)：约占网页 27%，形成网络的核心 - 入分量 (In-Component)：能到达 SCC 但不能从 SCC 返回的网页（约 21%） - 出分量 (Out-Component)：能从 SCC 到达但不能被 SCC 到达的网页（约 21%） - 须条 (Tendrils)：连接到 In 和 Out 的网页 - 管道 (Tubes)：直接连接 In 到 Out 的网页 - 孤立分量 (Disconnected Components)：与其他部分无连接

这种结构导致 PageRank 收敛条件不满足，需要特殊处理。

2.4 处理死端问题

死端 (Dead End) 是指没有任何出链的网页。在转移矩阵中，死端对应一个全零列。

问题： - 死端使矩阵 \(M\) 失去列随机性质（成为亚随机矩阵） - 随机游走者进入死端后无法离开，概率会逐步积累 - 最终所有网页的 PageRank 趋向于 0

示例 5.3：如果在示例 5.1 中移除 \(C \rightarrow A\) 的链接，使 C 成为死端，则所有 PageRank 最终都趋向于 0。

解决方案 1：递归删除法 (Recursive Deletion)

步骤如下： 1. 识别所有死端网页 2. 从图中删除死端及其出链 3. 重复直到没有新的死端 4. 在删除死端的网页上计算 PageRank 5. 按相反顺序恢复被删除网页的 PageRank

恢复公式：对于被删除的死端网页 \(p\)，其 PageRank 为： \[r_p = \sum_{q \in pred(p)} \frac{r_q}{d_q}\]

其中 \(pred(p)\) 是指向 \(p\) 的所有网页，\(r_q\) 是 \(q\) 的 PageRank，\(d_q\) 是 \(q\) 的出度。

示例 5.4：多级死端

如果移除 C 的出链使其成为死端，这进而可能使 B 也成为死端（如果 B 只链接到 C）。需要逐级处理： 1. 第一级：删除 E（初始死端） 2. 第二级：删除 C（删除 E 后成为死端） 3. 在简化图上计算 PageRank 4. 按 C、E 的顺序恢复

2.5 蜘蛛陷阱与税收方法

蜘蛛陷阱 (Spider Trap) 是指一组网页，其中所有出链都指向组内网页，与其他网络部分无连接。

问题： - 随机游走者一旦进入陷阱，永远无法离开 - 所有 PageRank 最终聚集在陷阱中的网页 - 其他网页的 PageRank 趋向于 0

示例 5.5：如果 D 有自环（D 指向自己）且没有其他出链，在收敛后： \[v \rightarrow (0, 0, 0, 1)^T\]

解决方案：税收方法 (Taxation Method) 或 传送方法 (Teleportation Method)

改进的 PageRank 公式： \[v' = \beta M v + \frac{1-\beta}{n} e\]

其中： - \(\beta \in [0.8, 0.9]\) 通常为 0.85，称为 阻尼因子 (Damping Factor) - \(e\) 是全 1 向量 - \(n\) 是网页数量

概率解释： - 以概率 \(\beta\) 执行随机游走的标准步骤（跟随出链） - 以概率 \(1-\beta\) 进行"传送"，均匀随机跳转到任意网页 - 传送相当于在键盘上随机输入 URL

示例 5.6：使用 \(\beta = 0.8\) 和 D 的自环

迭代过程会收敛到： \[v = (15/148, 19/148, 95/148, 19/148)^T\]

虽然 D 仍然获得最高 PageRank，但不再是全部（95/148 ≈ 0.642），其他网页也获得合理的分值。

2.6 在搜索引擎中使用 PageRank

Google 搜索引擎的排名因素： - Google 使用 250+ 种排名属性和信号 - PageRank 是其中重要的一个，但不是唯一决定因素

综合排名过程： 1. 网页必须包含用户查询的搜索词 2. PageRank 作为一般性重要性指标 3. 其他重要因素包括： - 搜索词在标题中的位置和频率 - 搜索词在指向该网页的链接的锚文本中的出现情况 - 指向该网页的高 PageRank 网页数量及其相关性

三、PageRank 的高效计算

3.1 转移矩阵的稀疏表示

互联网图极为稀疏——平均每个网页约有 10 条出链，而总页数高达数十亿。

密集矩阵表示的问题： - 完整的 \(n \times n\) 矩阵需要 \(n^2\) 空间 - 对于 \(n = 10^9\)，这将需要 \(10^{18}\) 字节的存储，完全不可行

稀疏表示方案：

  1. 坐标表示 (Coordinate Format)
    • 存储每个非零元素的行号、列号和值
    • 每个元素约需 16 字节
  2. 按列优化表示 (Column-wise Representation)
    • 对每列，存储：出度 \(d_j\)、该列非零元素的行号列表
    • 每个元素约需 4 字节
    • 是计算矩阵-向量乘积的最高效格式

示例 5.7：列表表示

对于示例 5.1 的矩阵，按列表示为：

列1: 出度=1, 目标={2}
列2: 出度=1, 目标={3}
列3: 出度=2, 目标={1,4}
列4: 出度=2, 目标={3,4}

这种表示紧凑且便于计算 \(v' = Mv\)：对每列 \(j\)，将 \(v_j/d_j\) 添加到对应的行中。

3.2 基于 MapReduce 的 PageRank 迭代

在处理超大规模网络时，计算机的内存可能无法存储完整的向量 \(v\)，需要使用分布式计算框架。

单机可行情况： - 矩阵 \(M\) 无法一次性加载，但向量 \(v\) 可以存储在内存中 - 每次迭代执行 \(v' = \beta M v + (1-\beta)e/n\) - 使用流式处理方法：逐块读取 \(M\)，更新对应的 \(v'\) 部分

3.3 使用 Combiner 合并结果向量

当数据规模极大时，即使向量 \(v\) 也可能无法存储在单台机器的内存中。

条带化方法 (Striping)： - 将矩阵 \(M\) 分解为 \(k\) 个竖条带 - 将向量 \(v\) 和 \(v'\) 分解为 \(k\) 个段 - \(k\) 个 Map 任务，每个处理一个条带

问题：向量 \(v'\) 的不同段可能来自多个 Map 任务的输出，导致： - 多个任务输出同一向量位置的部分计算 - 需要合并这些部分贡献（Reduce）

分块矩阵方法 (Block Matrix Approach)：

将矩阵分解为 \(k \times k\) 的块矩阵：

\[M = \begin{pmatrix} M_{11} & M_{12} & \cdots & M_{1k} \\ M_{21} & M_{22} & \cdots & M_{2k} \\ \vdots & \vdots & \ddots & \vdots \\ M_{k1} & M_{k2} & \cdots & M_{kk} \end{pmatrix}, \quad v = \begin{pmatrix} v_1 \\ v_2 \\ \vdots \\ v_k \end{pmatrix}\]

矩阵-向量乘积： \[v'_i = \sum_{j=1}^{k} M_{ij} v_j\]

MapReduce 实现： - 创建 \(k^2\) 个 Map 任务，每个任务 \((i,j)\) 处理块 \(M_{ij}\) 和向量分片 \(v_j\) - 块 \(M_{ij}\) 与 \(v_j\) 的乘积仅贡献到 \(v'_i\) - 所有贡献到 \(v'_i\) 的部分可在 Reduce 阶段合并 - 使用 Combiner 在 Map 端进行局部求和，减少网络传输

3.4 转移矩阵块的表示

块表示格式： - 对每个块 \(M_{ij}\)，列出所有非零元素 - 对每列，记录出度和目标行号列表 - 空间复杂度略高于条带表示（最多 2 倍），但便于块级处理

3.5 其他高效方法

行块分配： - 将矩阵的行块分配给单个 Map 任务 - 每个 Map 任务读取整个向量 \(v\)，但仅读取矩阵的 1/k 部分 - Map 任务数减少到 \(k\)（而非 \(k^2\)）

单机优化： - 模拟行逐行处理 - 仅读取一次矩阵，读取 \(k\) 次向量 - 在现代 CPU 缓存体系下可能比块方法更高效

四、主题敏感的 PageRank

4.1 基本动机

不同用户对相同搜索词的理解和需求差异巨大。

例子：搜索"美洲虎"(Jaguar) - 用户 A：寻找关于美洲虎动物的信息 - 用户 B：搜索美洲虎汽车品牌 - 用户 C：查找 macOS Jaguar 操作系统 - 用户 D：寻找美洲虎游戏机 (Atari)

全局 PageRank 的问题： - 对所有用户和查询使用相同的 PageRank 向量 - 无法体现个人或主题兴趣 - 理想方案是为每个用户维护个性化 PageRank，但不可行（数十亿用户）

实际方案：主题敏感 PageRank (Topic-Sensitive PageRank) - 预计算少量主题特定的 PageRank 向量（如 16-32 个） - 根据用户兴趣选择对应向量 - 可行性强，计算量合理

4.2 有偏随机游走

传送集合 (Teleport Set) \(S\)：一组已知属于特定主题的网页。

有偏 PageRank 公式： \[v' = \beta M v + \frac{1-\beta}{|S|} e_S\]

其中 \(e_S\) 是一个向量，仅在 \(S\) 中的位置为 1，其他位置为 0。

概率解释： - 以概率 \(\beta\) 执行随机游走的标准步骤 - 以概率 \(1-\beta\) 进行"传送"，但仅传送到 \(S\) 中的网页，均匀分布 - 相比标准 PageRank，新网页访问仅限制在特定主题范围内

初始化： \[v_0 = \frac{e_S}{|S|}\]

游走始终从主题网页开始。

4.3 主题敏感 PageRank 的使用

实现步骤：

  1. 选择主题：使用预定义分类体系（如 DMOZ 开放目录的 16 个顶级分类）

    • 商业、科技、艺术、体育等

  2. 定义传送集合：对每个主题，选择具有代表性的权威网页

    • 可人工精选高质量网站
    • 或自动从目录中抽取

  3. 预计算向量：为每个主题离线计算 PageRank 向量（50-75 次迭代）

  4. 用户分类：在搜索时确定用户兴趣主题

    • 用户选择（显式菜单）
    • 推断自浏览历史、搜索历史
    • 从用户的书签或社交媒体推断

  5. 生成排名：使用对应主题的 PageRank 向量排名搜索结果

4.4 混合向量的使用

对于多主题兴趣用户，可以加权组合多个主题向量： \[v_{user} = \sum_{i=1}^{k} w_i v_{topic_i}\]

其中 \(w_i\) 是主题 \(i\) 的权重，\(\sum w_i = 1\)。

示例 5.10：

设有 4 个网页，传送集合 \(S = \{B, D\}\)（网页 B 和 D）：

使用公式 \(v' = 0.8 Mv + 0.2(e_S/|S|) = 0.8Mv + 0.1(e_B + e_D)\)

迭代会偏向于提高 B 和 D 的 PageRank，以及与它们紧密相连的网页。

4.5 从文本推断主题

基本思路：识别每个主题的特征词汇，根据网页文本对其分类。

步骤：

  1. 提取特征词：对每个主题，计算其中文档中特定词汇出现的频率

  2. 识别主题特有词：选择在某主题中频率远高于一般背景的词

  3. 相似度计算：使用杰卡德相似度 (Jaccard Similarity) 等度量 \[J(A, B) = \frac{|A \cap B|}{|A \cup B|}\] 其中 \(A\) 是网页的词集合，\(B\) 是主题的特征词集合

  4. 页面分类：将网页分配给杰卡德相似度最高的主题

  5. 用户分类：推断用户兴趣为其浏览网页所属主题的加权组合

五、链接垃圾和对抗

5.1 垃圾农场的架构

链接垃圾 (Link Spam) 是指通过人为操纵链接结构来虚增网页 PageRank 的技术。

垃圾农场 (Spam Farm) 结构： - 目标页面 \(t\)：垃圾创建者想要提升排名的页面 - 支持页面 \(m\) 个：垃圾创建者创建的辅助页面 - 链接策略： - 所有 \(m\) 个支持页面都链接到目标页面 \(t\) - 支持页面之间可以链接，但所有出链最终都指向 \(t\) - 垃圾创建者利用可访问网页（如博客评论）来获得外部链接，指向支持页面或目标页面

外部贡献： - 设外部网页对目标页面的 PageRank 贡献为 \(x\) - 不属于垃圾农场的网页提供的传入链接价值总和

5.2 垃圾农场的分析

支持页面的 PageRank：

每个支持页面 \(s_i\) 的 PageRank 来自： 1. 外部贡献通过 \(t\) 的反馈：从 \(t\) 接收 \(m\) 个支持页面的均匀分配 2. 传送贡献：\((1-\beta)/n\)

计算得： \[r_s = \frac{\beta y}{m} + \frac{1-\beta}{n}\]

其中 \(y\) 是目标页面的 PageRank。

目标页面的 PageRank：

\[y = x + \sum_{i=1}^{m} \beta r_s = x + m \cdot \beta \left(\frac{\beta y}{m} + \frac{1-\beta}{n}\right)\]

化简： \[y = x + \beta^2 y + \frac{m\beta(1-\beta)}{n}\]

\[y(1 - \beta^2) = x + \frac{m\beta(1-\beta)}{n}\]

\[y = \frac{x}{1-\beta^2} + \frac{m\beta(1-\beta)}{n(1-\beta^2)}\]

定义放大因子 (Amplification Factor)： \[A = \frac{1}{1-\beta^2}\]

和系数： \[c = \frac{\beta(1-\beta)}{1-\beta^2} = \frac{\beta}{1+\beta}\]

则： \[y = A \cdot x + c \cdot \frac{m}{n}\]

数值分析（\(\beta = 0.85\)）：

\[A = \frac{1}{1-0.85^2} = \frac{1}{1-0.7225} = \frac{1}{0.2775} \approx 3.604\]

\[c = \frac{0.85}{1.85} \approx 0.459\]

结论： - 外部贡献 \(x\) 被放大 360% - 支持页面数量 \(m\) 的贡献达到 \(0.459 \cdot m/n\) - 因此，通过创建足够多的支持页面并获得一点外部链接，可以大幅提升目标页面的排名

5.3 对抗链接垃圾的方法

方法 1：检测和删除垃圾农场结构 - 识别具有异常出链模式的页面集合（所有指向单一目标） - 识别以同一组页面作为入链来源的页面 - 检测已知垃圾域名和人工生成的内容特征

方法 2：修改 PageRank 定义 - TrustRank：使用受信任网页的主题敏感 PageRank - Spam Mass：计算网页的垃圾度量

5.4 TrustRank

基本思想：受信任的网页不太可能链接到垃圾网页。

实现：使用主题敏感 PageRank，但传送集合 \(S\) 选择为高信任网页：

\[v' = \beta M v + \frac{1-\beta}{|S|} e_S\]

信任集合的选择：

  1. 人工精选：专家手工选择高质量网站（如权威学术网站）
  2. 域名控制：自动信任特定域名
    • .edu（教育机构）
    • .gov（政府机构）
    • .mil（军事机构）
    • 国际等价物（如 .ac.uk, .edu.au）

直观解释： - 从受信任网页开始随机游走 - 跟随链接时，优先访问受信任网页链接的目标 - 垃圾网页通常不被受信任网页链接，所以获得低 TrustRank

5.5 垃圾质量度量

定义：对于网页 \(p\)： \[\text{Spam Mass}_p = \frac{r_p - t_p}{r_p}\]

其中： - \(r_p\)：标准 PageRank - \(t_p\)：TrustRank

解释： - 负值或接近 0：高度可信，不太可能是垃圾 - 接近 1：PageRank 远高于 TrustRank，强烈提示垃圾 - 中等值（如 0.5-0.8）：可疑，需要进一步调查

过滤策略： - 垃圾质量 > 阈值的网页从搜索索引中删除或降低排名 - 可基于页面内容和链接模式进一步验证

六、HITS 算法：枢纽与权威

6.1 HITS 算法的直观理解

HITS (Hyperlink-Induced Topic Search) 是另一种基于链接分析的页面排名算法，采用二维评分体系。

核心思想：互联网中存在两类重要网页： 1. 权威页 (Authorities)：包含某个主题相关的优质内容 2. 枢纽页 (Hubs)：汇聚指向权威页的大量链接（如目录、列表、综述页）

相互强化关系： - 好的枢纽页链接到许多好的权威页 - 好的权威页被许多好的枢纽页链接 - 这形成相互递归的定义

示例： - 权威页：Apple、Amazon、Microsoft 官方网站（技术公司主题） - 枢纽页："Top 10 Tech Companies"、科技行业目录、技术新闻聚合站点

6.2 枢纽和权威的形式化

评分定义：

每个网页 \(p\) 获得两个评分： - 枢纽性评分 \(h_p\)：页面作为枢纽的重要程度 - 权威性评分 \(a_p\)：页面作为权威的重要程度

更新规则：相互强化

\[h_p = \sum_{q: p \rightarrow q} a_q \quad \text{(枢纽性 = 所有被链接页的权威和)}\]

\[a_p = \sum_{q: q \rightarrow p} h_q \quad \text{(权威性 = 所有链接源的枢纽和)}\]

矩阵形式：

定义链接矩阵 \(L\)（\(n \times n\)）： \[L_{ij} = \begin{cases} 1 & \text{if page } i \text{ links to page } j \\ 0 & \text{otherwise} \end{cases}\]

定义向量 \(h = (h_1, \ldots, h_n)^T\) 和 \(a = (a_1, \ldots, a_n)^T\)，则： \[h = La\] \[a = L^T h\]

代入得特征向量方程： \[h = LL^T h\] \[a = L^T L a\]

因此： - \(h\) 是矩阵 \(LL^T\) 特征值为最大的特征向量 - \(a\) 是矩阵 \(L^T L\) 特征值为最大的特征向量

6.3 HITS 算法的迭代过程

标准迭代算法：

初始化：\(h^{(0)} = \mathbf{1}\)（全 1 向量）

对于 \(k = 0, 1, 2, \ldots\)： 1. 权威更新：\(a^{(k+1)} = L^T h^{(k)}\) 2. 规范化：\(a^{(k+1)} := a^{(k+1)} / \|a^{(k+1)}\|_\infty\)（使最大值为 1） 3. 枢纽更新：\(h^{(k+1)} = L a^{(k+1)}\) 4. 规范化：\(h^{(k+1)} := h^{(k+1)} / \|h^{(k+1)}\|_\infty\)

收敛判定：当 \(\|h^{(k+1)} - h^{(k)}\| < \epsilon\) 且 \(\|a^{(k+1)} - a^{(k)}\| < \epsilon\) 时停止。

6.4 HITS 的具体例子

示例 5.14-5.15：五节点图

假设有 5 个网页，链接关系为： - A → B, C - B → C - C → A, B, D - D → E - E → D

链接矩阵 \(L\)： \[L = \begin{pmatrix} 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{pmatrix}\]

第一次迭代（\(k=0\)，初始 \(h = (1,1,1,1,1)^T\)）：

权威： \[a^{(1)} = L^T h^{(0)} = \begin{pmatrix} 2 \\ 1 \\ 4 \\ 2 \\ 1 \end{pmatrix} \Rightarrow \text{规范化} \Rightarrow a^{(1)} = \begin{pmatrix} 0.5 \\ 0.25 \\ 1 \\ 0.5 \\ 0.25 \end{pmatrix}\]

枢纽： \[h^{(1)} = L a^{(1)} = \begin{pmatrix} 1 \\ 1.5 \\ 0.75 \\ 1.5 \\ 0.5 \end{pmatrix} \Rightarrow \text{规范化} \Rightarrow h^{(1)} = \begin{pmatrix} 2/3 \\ 1 \\ 0.5 \\ 1 \\ 1/3 \end{pmatrix}\]

后续迭代继续执行，最终收敛到： \[h^{(\infty)} = (1, 0.3583, 0, 0.7165, 0)^T\] \[a^{(\infty)} = (0.2087, 1, 1, 0.7913, 0)^T\]

解释： - B 和 C 是权威页（权威分别为 1 和 1） - A 和 C 是枢纽页（枢纽分别为 1 和 0.7165） - D 和 E 形成孤立的链接圈，几乎没有权威或枢纽性

6.5 HITS vs PageRank

主要区别：

特性 PageRank HITS
计算方式 全局，离线预计算 查询相关，按需计算
图要求 需要处理死端和陷阱 无需特殊处理
评分维度 单一（重要性） 二维（枢纽+权威）
应用场景 通用网页排名 特定查询的权威发现

HITS 的优势： - 自然地区分不同类型的重要页面 - 不需要税收方法处理陷阱 - 更能反映某特定主题的链接生态

HITS 的劣势： - 需要为每次查询计算，延迟高 - 对于广泛查询结果可能过度分散 - 更易被链接操纵（相比 PageRank）

6.6 HITS 的特征向量分析

示例 5.16：解析求解

对于某些简单图，可以解析计算 \(LL^T\) 和 \(L^TL\) 的特征向量。

考虑具体的 \(LL^T\) 矩阵，计算其特征多项式： \[\det(LL^T - \lambda I) = 0\]

对于小规模图，可能得到如： \[\lambda_{\max} = \frac{5 + \sqrt{21}}{2} \approx 4.791\]

对应的特征向量即为收敛的枢纽评分向量。

七、总结与应用

7.1 链接分析的核心概念

链接分析为现代搜索引擎和网络分析提供了坚实的理论基础：

  1. PageRank 通过随机游走和特征向量方法，从全局链接结构推导网页重要性
  2. 主题敏感 PageRank 适应用户多样化需求，实现个性化搜索
  3. TrustRank 和垃圾质量度量提供了对抗链接操纵的防护
  4. HITS 提供了补充的视角，区分权威和枢纽角色

7.2 实际应用

搜索引擎： - Google 的核心排名算法 - 其他搜索引擎的类似方案

社交网络分析： - 识别影响力用户（权威） - 识别信息传播中心（枢纽）

学术文献分析： - 识别高引论文（权威） - 识别综述和综合论文（枢纽）

推荐系统： - 基于链接结构的相似性度量 - 社交网络信任推断

7.3 当代挑战

链接垃圾的演进： - 垃圾农场技术不断进化 - 需要持续改进检测算法

大规模计算： - 互联网持续增长，矩阵规模数十亿 - 分布式计算框架的优化至关重要

个性化与隐私： - 收集用户兴趣数据带来隐私问题 - 需要平衡个性化推荐与用户隐私

术语汇总表

中文术语 English Term 简要说明
链接分析 Link Analysis 通过网页链接结构评估重要性的方法
页面排名 PageRank Google 的核心算法，基于随机游走
转移矩阵 Transition Matrix 表示网页链接关系的列随机矩阵
随机游走 Random Walk/Random Surfer 模拟虚拟用户在网页间的浏览过程
稳定分布 Stationary Distribution 随机游走过程收敛的概率分布
特征向量 Eigenvector 转移矩阵特征值为 1 的向量
死端 Dead End 没有出链的网页
蜘蛛陷阱 Spider Trap 自我链接形成的陷阱，导致 PageRank 积累
阻尼因子 Damping Factor PageRank 公式中的参数 β
传送方法 Teleportation Method 通过随机跳转解决陷阱问题的技术
蝴蝶结结构 Bow-Tie Structure 真实网络的结构模式，包含 SCC 和多个分量
强连通分量 Strongly Connected Component (SCC) 任意两页相互可达的最大子图
稀疏表示 Sparse Representation 利用稀疏矩阵结构优化存储和计算
主题敏感 PageRank Topic-Sensitive PageRank 针对特定主题的偏向 PageRank
传送集合 Teleport Set 主题敏感 PageRank 中的受限跳转目标
链接垃圾 Link Spam 人为操纵链接结构来提升排名
垃圾农场 Spam Farm 垃圾页面的组织结构
TrustRank TrustRank 从受信任页面出发的主题敏感 PageRank
垃圾质量 Spam Mass 网页垃圾程度的度量指标
HITS 算法 HITS 基于权威和枢纽的链接分析算法
权威页 Authorities 包含高质量内容的网页
枢纽页 Hubs 汇聚多个权威页链接的网页
出度 Out-Degree 网页的出链数量
入度 In-Degree 网页的入链数量
列随机矩阵 Column-Stochastic Matrix 每列和为 1 的矩阵
杰卡德相似度 Jaccard Similarity 两个集合的交集与并集的比值
特征值 Eigenvalue 满足 Av = λv 的标量 λ
迭代方法 Iterative Method 通过重复应用矩阵乘法求解 PageRank
MapReduce MapReduce 分布式计算框架
分块矩阵 Block Matrix 将大矩阵分解为较小块的表示方法
词汇特征 Feature Words 代表特定主题的特征词

版本信息 - 教材版本：Mining of Massive Datasets (Version 3.0) - 笔记日期：2026-04-13 - 覆盖章节：Chapter 5 - Link Analysis - 详细程度：深入讲解，包含所有公式和示例