架构第十三周作业

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

PageRank 简单说就是民主表决。将整个互联网看做一张图，网站是图上的点，网页链接是图上的边。每个网页都有一个权威性得分，称作 PageRank，可以把它当做是一种“投票权”，将每一个超链接作为一次“投票”， 每个网页的 PageRank 等于所有具有指向该网页超链接的网页的 PageRank 的加权和，这些权值等于这些网页各自向外链接数目的倒数。

在互联网上如果一个网页被很多其他网页所链接，说明它受到普遍的承认和信赖，它的排名就高，这是 PageRank 的核心思想。实际算法更加复杂，比如对不同网页区别对待，排名更高的网页的链接更可靠，要给这些链接更大的权重。这个思想有一个问题：对网页排名的过程需要用到网页本身的排名。后来把这个问题转化成二维矩阵相乘并用迭代解决。先假定所有网页的排名是相同的，并根据这个初始值算出各网页的第一次迭代值，再根据第一次迭代值计算第二次迭代值，从理论证明不论初始值如何选取，这种算法都能保证网页排名的估计值都能收敛到排名的真实值。互联网网页数量巨大，矩阵相乘计算量非常大，用稀疏矩阵技巧简化计算量。