第 13 周命题作业

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

总体来说：如果一个网页能被很多其他网页链接到，说明这个网页比较重要，对应的 PageRank 值较高。一个 PageRank 值很高的网页链接到一个其他网页，链接到的网页的 PageRank 值也会提高。

将每个网页视为 1 个节点；如果一个页面 A 直接链接到 B，则 A 指向 B；即 A→B。

初始时用户访问每个页面的概率均等，假设总共有 N 个页面，访问每个页面的概率位 1/N，可以认为每个页面的初始 PR 值为 1/N。

场景推演：共 A，B，C，D 四个页面

场景 1：A→B；B→A；C→A；D→C；B 链接到 A 页面，C 链接到 A 页面；

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

场景 2：A→B；B→A；B→D；C→A；D→C；B 能同时链接到 A、D 页面，C 链接到 A 页面；

则 PR(A) = PR(B)/2 + PR(C)

场景 3：A→B；B→A；B→D；D→C；C 没有链接到任何一个网页；因为 C 没有对其他网页作出贡献，那么认为它对所有网页包括自己，都有贡献；

则 PR(A) = PR(B)/2 + PR(C)/4

场景 4：A→B；B→A；B→D；D→C；C→C；C 只链接到自己；

访问页面有 2 种可能：从当前页面点击链接访问另外一个页面；直接在地址栏输入地址访问另外一个页面。通过点击链接访问另外一个页面的概率认为是α。

则 PR(A) =α(PR(B)/2) + (1-α)/4

将场景 4 拓展到一般场景

则

L(Pj) 表示 Pj 页面的链出总数；Mpi 表示能够链接到 pi 的所有网页集合