请列举数据挖掘领域常见的图算法，并详细说明 PageRank 算法是如何实现对网页重要性排序的？
考察说明
考查对图算法体系的了解程度以及 PageRank 的核心原理和计算过程。
回答思路
- 【回答框架 1】图算法用于处理图结构数据，常见的有社区发现算法（如 Louvain、标签传播）、路径算法（如 Dijkstra、Floyd）、图嵌入算法（如 DeepWalk、Node2Vec）以及节点重要性算法（如 PageRank、HITS）。
- 【回答框架 2】PageRank 的基本假设是：一个网页的重要性由其被链接的数量和质量决定。每个网页将自身的 PageRank 值按出链平均分配，一个网页的 PageRank 值等于所有入链网页传递的值的总和。
- 【回答框架 3】计算过程通常采用迭代法：初始化每个页面的 PageRank 值为 1/N（N 为网页总数），然后不断执行值传递和更新，直到收敛。为防止悬挂节点和收敛问题，引入阻尼系数 d（通常取 0.85），公式为 PR(A) = (1-d)/N + d * Σ(PR(入链页面)/其出链数)。
- 【回答框架 4】PageRank 的物理意义是模拟随机游走过程，用户以概率 d 点击链接继续浏览，以概率 1-d 跳转到任意随机页面。其收敛性可以通过马尔可夫链理论保证，最终得到的稳定分布即为各页面的重要度排序。
- 【关键点 1】常见图算法包括社区发现、路径计算、图嵌入和节点重要性算法。
- 【关键点 2】PageRank 核心思想是链接即投票，且来自高权重页面的投票更有价值。
- 【关键点 3】迭代公式为 PR(A) = (1-d)/N + d * Σ(PR(入链页面)/其出链数)，d 常取 0.85。
- 【关键点 4】阻尼系数用于模拟跳转行为和避免悬挂节点问题。
- 【关键点 5】PageRank 收敛性由马尔可夫链保证，稳态分布即重要性得分。
- 【易错点 1】注意 PageRank 只考虑入链，不考虑出链权重，但出链数会稀释自身传递的权重。
- 【易错点 2】不能简单认为 PageRank 就是点击率或用户喜好，它只是基于链接结构的静态排序。
- 【易错点 3】实际工程中，PageRank 的并行实现需要考虑数据划分和通信开销。