PageRank 算法-工具盒子

PageRank 算法是谷歌根据网页重要程度给网页排名的算法，该值越高说明网页越重要，当用户进行相关搜索时，越有可能优先展现给用户。

我们通过一个例子来理解 PageRank 的算法计算过程，我们现在有 3 个网页，网页之间都会相互链接，其中链接关系如下图：

网页 A 链接网页 C，对于网页 C 的权重计算提供 1 的贡献;
网页 B 链接网页 A、网页 C，网页 B 对网页 A、C 的权重计算提供的贡献分别是 1/2;
网页 C 没有链接任何网页，对其他网页权重计算的贡献为 0。

从这个链接关系上来说，A 被其他网页链接了 1 次，B 被其他网页链接 0 次，C 被其他的网页链接了 2 次，看起来 C 网页的 PR 更大一些，更重要一些。所以，PageRank 在评价网页时，是根据其他网页对当前网页的链接数量、链接质量来评价的，即: 比人说你好，你才真的好。

网页 PR 值的计算使用公式表示如下：

In(V~i~) 表示链接到网页 V~i~ 的所有网页,例如：对于 C 网页而言，A B 就是链接的网页
Out(V~j~) 表示链接网页的出链数量，例如：C 网页的链接网页是 A、B, A 的出链数量是 1，B 出链数量是 2
P(V~j~) 表示链接网页 A、B 的权重，即权重越大，对于提升 C 网页的权重贡献就越大。
d 叫做阻尼系数。当一个网页没有任何外部网页链接到它的时候，那么它的权重为 0，阻尼系数可以给网页一个保底的网页权重值，一般 d 这个值被设置为 0.85。

如果一个网页的出链有 N 个的话，那么对于被链接网页的重要程度的贡献就有 1/N，我们将上面的网页出链贡献，即: out 分之一写成如下矩阵形式：

上图中，左图第一行表示：网页B对网页A有链接，而网页A和网页C则没有到网页A的链接。

由于现在我们并不知道每个网页的 PR 值，我们共有 3 个网页，可以先将每个网页的 PR 值初始化为 1/3, 即：(1/3, 1/3, 1/3) 我们这里选择前者初始化。

接下来，如何计算这 3 个网页的重要程度呢？

我们使用上面的 PageRank 公式进行迭代计算，直到 PR 值的计算收敛或者小于某个阈值，如下代码所示：

import torch
import numpy as np


def page_rank():


    # 构建网页链接关系
    graph = torch.tensor([[0, 1, 0],
                         [0, 0, 0],
                         [1, 1, 0]])
    norm_graph = graph / torch.sum(graph, dim=0, keepdim=True)
    # 由于有些列全0，相除之后出现 nan，对这些 nan 列进行替换
    norm_graph[torch.isnan(norm_graph)] = 0

    # 设置网页初始 PR 值
    init_page_rank = torch.tensor([[1/3], [1/3], [1/3]], dtype=torch.float32)
    page_rank = init_page_rank

    # 设置阻尼系数
    d = 0.85

    # 开始迭代计算每个网页的 PR 值
    for _ in range(100):
        page_rank = (1 - d) * init_page_rank + d * (norm_graph @ page_rank)

    print(page_rank.reshape(1, -1))


if __name__ == '__main__':
    page_rank()

输出结果：