架构师训练营第十三周作业

Google 搜索引擎是如何对搜索结果进行排序的？（请用自己的语言描述 PageRank 算法。）

概念

PageRank

PageRank 是一个函数，输入 Web 页面的 URL，输出该页面的 PangeRank 值。一个页面的 PageRank 值越高，该页面越重要。

Web 转移矩阵(transmission matrix)

我们可以使用一个有向图描述 Web，图中的节点代表一个页面，如果页面 A 存在到页面 B 的链接，则这两个节点之间存在一条由 A 到 B 的有向边。

Web 转移矩阵则描述了页面之间的转移概率。

1. 转移矩阵是一个 n*n 的矩阵，其中 n 是 Web 页面的总数。

2. 矩阵 M 的元素 M[i, j]表示由页面 j 到页面 i 的概率。

假设页面 j 的所有出链总数为 k，则 M[i, j] = 1/k

概率分布向量

概率分布向量是一个 n 为的列向量，其中向量中的第 j 个分量表示冲浪者位于页面 j 的概率。

步骤

1. 给定转移矩阵 M，初始概率分布向量为 v(向量的每维的值为 1/n，表示冲浪者位于 n 个网页的初始概率相等)；

2. 通过将矩阵 M 左乘分布向量 v 得到新的向量 v'，表示冲浪者下一步可能访问的页面的概率；

3. 如果得到的 v'和 v 的值相差较大，则设置 v=v'，然后回到步骤 2，得到新的 v'，直到 v 和 v'的值差值在允许的阈值内，表示概率分布向量已经稳定；

4. 此时得到的 v'可以用作页面的 PageRank，即：PageRank(j) = v'[j]

实现

由于 Web 页面数量(n)较大，所以计算概率分布向量的过程可以用多个 Map-Reduce 过程实现。

1. Mapper 的输入的值包括表示转移矩阵某个元素的(i, j, p)以及当前的分布向量 v，输出的 Key 为 i，输出的值是(i, p * v[j])；

2. Reducer 则把所有得到的值相加，得到某个页面 i 对应的概率分布。