单点 PageRank 计算 Single-node PageRank

单点 PageRank 计算 (single-node PageRank) 是一种专注于计算互联网上特定网页 PageRank 得分的方法。这种方法特别关注于少量特定网页的 PageRank 得分计算，例如计算某几个知名网站的 PageRank 得分。它是 PageRank 算法的一个变种，专注于计算单个节点在网络中的 PageRank 值。 PageRank 算法是由谷歌创始人拉里·佩奇和谢尔盖·布林在 1998 年提出的，用于衡量网页的重要性或质量。单点 PageRank 计算则是在这一基础上发展而来，旨在估计随机游走在特定节点终止的概率。

单点 PageRank 计算通过随机游走模型来确定节点的重要性。在 PageRank 算法中，一个节点的 PageRank 值是由所有指向该节点的链接的 PageRank 值传递而来，同时考虑阻尼因子以模拟随机浏览者偶尔跳转到任意网页的行为。单点 PageRank 计算则专注于计算从所有节点出发的随机游走最终到达特定目标节点的概率。

中国人民大学的研究人员在 2024 年的 ACM 计算理论年会 (STOC) 上发表了一篇论文「Revisiting Local Computation of PageRank: Simple and Optimal」，将单点 PageRank 的计算复杂度优化至理论最优。这项研究通过重新分析 2016 年提出的 BiPPR 算法，成功优化了单点 PageRank 的计算复杂度，达到了理论下界的最优水平。