PageRank 算法

PageRank 有点像一场层层传递的人气投票，但每一票的分量并不一样。一个网页链接到另一个网页，就相当于投了一票；来自重要网页的票，比如这个例子中的《纽约时报》，比来自冷门网页的票更有分量。所以，网站 B 会胜出：那一个权威网站传来的重要性，超过了 500 个小博客各自传来的微弱影响。关键是质量，不只是数量。

想一想：在你的职业生涯中，50 个泛泛之交和一位受尊敬的行业领袖建立深厚联系，哪个影响可能更大？

解释 PageRank 的核心机制时，人们常用“随机浏览者”模型。想象有人上网时完全随机地点击链接。PageRank 估算的是：在任意时刻，这个人落在某个特定网页上的概率。有许多路径通向的网页，尤其是那些经常被访问的网页也链接到它时，出现的概率（排名）就更高。由于浏览者更可能待在热门网页上，来自热门网页的链接也会把相当一部分访问机会（或概率）传给它指向的网页。

算法还用“阻尼系数”（通常设为 0.85）来模拟浏览者失去兴趣的情况。这样，随机浏览者就不会一直困在两个网页之间，而是偶尔会“瞬移”到一个完全随机的网址。这能避免无限循环，也让每个网页都有微小但不为零的访问概率，使数学模型保持稳定。

PageRank 因网页搜索而出名，但这套思路也适用于其他复杂系统。在神经科学中，研究人员用它绘制大脑网络图，找出汇集许多其他活跃区域信息的“枢纽”区域。在体育数据分析中，它也能根据球队战胜了谁来排名，而不只是数胜场：击败冠军带来的排名提升，远大于击败新手。

从数学上说，PageRank 是一种马尔可夫链的平稳分布。这条马尔可夫链描述了在图上随机游走的过程。PageRank 也是特征向量中心性的一种变体。

• Page 等人（1999）提出了递归定义：一个网页的排名等于指向它的网页的排名，分别除以那些网页的出站链接数后，再相加。[1]
• Langville 和 Meyer（2004）分析了阻尼系数。他们发现，0.85 能兼顾计算速度和准确性；更低的值能让排名更不易受垃圾链接干扰，但也会降低排名对网络真实结构的敏感度。[2]
• Gleich（2015）展示了 PageRank 如何解决网页之外的中心性问题，包括找出食物网中的关键物种，以及给化学反应的重要性排序。[3]

对于规模庞大且频繁变化的图（如现代互联网），PageRank 的计算成本很高。它也容易受到“链接农场”的影响：一些网站人为制造链接循环来抬高排名。因此，人们开发了 TrustRank 等防滥用改进方法。