搜索引擎如何推荐网页

搜索引擎如何推荐网页？

Google 的选择是 PageRank。

PageRank，又称网页排名、谷歌左侧排名、PR，是Google公司所使用的对其搜索引擎搜索结果中的网页进行排名的一种算法。

PageRank 与矩阵的关系

我们先来看下 PageRank 是如何计算的。我假设一共有 4 个网页 A、B、C、D。它们之间的链接信息如图所示：





与图形对应的简化公式可以表示为：



我们再来对比看看矩阵点乘的计算公式。

以上两个公式在形式上是基本一致的。

因此，可以把 PageRank 简化公式的计算，分解为两个矩阵的点乘。一个矩阵是当前每张网页的 PageRank 得分，另一个矩阵就是邻接矩阵。所谓邻接矩阵，其实就是表示图结点相邻关系的矩阵。



为了方便理解，用下面这个拓扑图作为例子详细解释。





基于上面这个图，原始矩阵为：





有了上述这个邻接矩阵，我们就可以开始最简单的 PageRank 计算。PageRank 的计算是采样迭代法实现的。这里我把初始值都设为 1，并把第一次计算的结果列在这里。





已经成功迈出了第一步，但是还需要考虑随机跳转的可能性。

可以把上述公式分解为如下两个矩阵的点乘：

仍然使用前面的例子，来看看经过随机跳转之后，PageRank 值变成了多少。这里 α 取 0.9。





我们前面提到，PageRank 算法需要迭代式计算。为了避免计算后的数值越来越大甚至溢出，我们可以进行归一化处理，保证所有结点的数值之和为 1。经过这个处理之后，我们得到第一轮的 PageRank 数值，也就是下面这个行向量：

[0.37027027 0.24864865 0.37027027 0.00540541 0.00540541]

接下来，我们只需要再重复之前的步骤，直到每个结点的值趋于稳定就可以了。

PageRank 的程序实现

这个过程的 Python 实现:

import numpy as np
# 设置确定随机跳转概率的alpha、网页结点数
alpha = 0.9
N = 5
# 初始化随机跳转概率的矩阵
jump = np.full([2,1], [[alpha], [1-alpha]], dtype=float)
# 邻接矩阵的构建
adj = np.full([N,N], [[0,0,1,0,0],[1,0,1,0,0],[1,0,0,0,0],[0,0,0,0,0],[0,1,0,0,0]], dtype=float)
# 对邻接矩阵进行归一化
row_sums = adj.sum(axis=1)      # 对每一行求和
row_sums[row_sums == 0] = 0.1   # 防止由于分母出现0而导致的Nan
adj = adj / row_sums[:, np.newaxis] # 除以每行之和的归一化
# 初始的PageRank值，通常是设置所有值为1.0
pr = np.full([1,N], 1, dtype=float)



# PageRank算法本身是采样迭代方式进行的，当最终的取值趋于稳定后结束。
for i in range(0, 20):
    # 进行点乘，计算Σ(PR(pj)/L(pj))
    pr = np.dot(pr, adj)
    # 转置保存Σ(PR(pj)/L(pj))结果的矩阵，并增加长度为N的列向量，其中每个元素的值为1/N，便于下一步的点乘。
    pr_jump = np.full([N, 2], [[0, 1/N]])
    pr_jump[:,:-1] = pr.transpose()
    # 进行点乘，计算α(Σ(PR(pj)/L(pj))) + (1-α)/N)
    pr = np.dot(pr_jump, jump)
    # 归一化PageRank得分
    pr = pr.transpose()
    pr = pr / pr.sum()
    print("round", i + 1, pr)



运行结果如图：





有一个关于图论和网络建模的工具叫 NetworkX，它是用 Python 语言开发的工具，内置了常用的图与网络分析算法，可以方便我们进行网络数据分析。





希拉里邮件事件相信你也有耳闻，对这个数据的背景我们就不做介绍了。你可以从 GitHub 上下载这个数据集：https://github.com/cystanford/PageRank。

执行后可以得到如下图示：







参考

https://zh.wikipedia.org/wiki/PageRank

https://time.geekbang.org/column/article/85194

https://time.geekbang.org/column/article/83034

https://time.geekbang.org/column/article/83471