PageRank 算法

定义

PageRank 是 Larry Page 与 Sergey Brin 于 1998 年前后在斯坦福大学提出的链接分析算法,是 Google 搜索引擎早期的核心排名信号,名称同时取自网页(page)与 Page 的姓氏。

原理

将万维网建模为有向图,设想一个随机冲浪者:以概率 d(阻尼系数,通常取 0.85)沿当前页面的出链随机跳转,以概率 1-d 随机传送到任意页面。PageRank 值即该马尔可夫链的平稳分布,可用幂迭代法计算:每轮把每个页面的分值按出链均分传递给目标页面,叠加传送项,迭代至收敛。

应用

除网页排名外,还被用于学术引文分析、社交网络影响力度量、蛋白质相互作用网络关键节点识别、推荐系统(Personalized PageRank)等图节点重要性问题。

说明

现代搜索排序融合了数百种信号,PageRank 仅是其中之一,但其"链接即投票"思想影响深远。