单点 PageRank 计算是什么？只算少数几个网页的重要性

单点 PageRank 计算（Single-node PageRank）是只计算网络中某一个或少数几个节点 PageRank 值的方法。比如只想知道某几个特定网站的 PageRank 得分，而不需要算出整个互联网上每个网页的得分。它是 PageRank 算法的一个变种。

先说 PageRank

PageRank 是谷歌创始人拉里·佩奇和谢尔盖·布林在 1998 年提出的算法，用来衡量网页的重要性，是谷歌搜索早期排名技术的核心。它的基本思想是：一个网页被越多的网页链接，而且链接它的网页本身越重要，它就越重要。可以想象一个在网上随机冲浪的人：他在每个网页上随机点击一个链接跳到下一个网页，偶尔也会随机跳到任意一个网页。长时间冲浪之后，他停留在每个网页上的概率，就是这个网页的 PageRank 值。

为什么需要单点计算

标准的 PageRank 计算要对整个网络进行迭代：每一轮都根据链接关系更新所有网页的得分，直到收敛。对于有几十亿个网页的互联网来说，这需要巨大的计算量，而且每次都要处理整个网络的链接数据。但在很多实际场景中，我们只关心少数几个节点：比如评估某个特定网站的重要性，分析社交网络中某几个账号的影响力，或者在一个巨大的知识图谱中判断某个实体的重要程度。为了这几个节点去计算整个网络，代价太大。

怎么高效计算

单点 PageRank 计算的研究目标，是用尽可能少的计算和数据访问，估算出目标节点的 PageRank 值，计算成本最好与网络的总规模无关，或者远小于计算整个网络的成本。常见的思路包括：从目标节点出发，沿着链接反向追溯，只探索对它的得分有显著贡献的那一部分网络（反向推送算法）；以及用随机游走进行蒙特卡洛模拟，通过大量随机冲浪的样本来估计停留在目标节点的概率；还有把两者结合起来的方法。理论计算机科学领域对这类问题的计算复杂度做了深入研究，近年来也有研究给出了在一定误差范围内估算单点 PageRank 所需计算量的更紧的理论界限。

除了网页排名，PageRank 及其变种还被广泛用于社交网络分析、推荐系统、引文网络分析、生物网络中的关键基因识别，以及图神经网络中的信息传播等领域。