Week 13 命题作业

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

解答：

PageRank 的核心思想：

如果一个网页被很多其他网页链接到的话说明这个网页比较重要，也就是 PageRank 值会相对较高。

如果一个 PageRank 值很高的网页链接到一个其他的网页，那么被链接到的网页的 PageRank 值会相应地因此而提高。

PageRank 算法主要分为两步：

1.给每个网页一个 PR 值（下面用 PR 值指代 PageRank 值）

2.通过（投票）算法不断迭代，直至达到平稳分布为止。

互联网中的众多网页可以看作一个有向图，比如下图:

由于 PR 值物理意义上为一个网页被访问概率，所以初始值可以假设为 1/N，其中 N 为网页总数。一般情况下，所有网页的 PR 值的总和为 1。

B、C、D 三个页面都链入到 A，则 A 的 PR 值将是 B、C、D 三个页面 PR 值的总和：

PR(A)=PR(B)+PR(C)+PR(D)

继续上面的假设，B 除了链接到 A，还链接到 C 和 D，C 除了链接到 A，还链接到 B，而 D 只链接到 A，所以在计算 A 的 PR 值时，B 的 PR 值只能投出 1/3​的票，C 的 PR 值只能投出 1/2​的票，而 D 只链接到 A，所以能投出全票，所以 A 的 PR 值总和应为：

PR(A)=PR(B)/3+PR(C)/2+PR(D)

所以可以得出一个网页的 PR 值计算公式应为：

其中，Bu ​是所有链接到网页 u 的网页集合，网页 v 是属于集合 Bu 的一个网页，L(v)则是网页 v 的对外链接数(即出度)。

计算的 PR 值如下：

经过几次迭代后，可以看出 PR 值逐渐收敛稳定。