《数学之美（第一版）》笔记 —— 第10章

第10章 PageRank——Google的民主表决式网页排名技术

• 搜索结果的排名取决于两组信息：关于网页的质量信息，和这个查询与每个网页的相关性信息。
• PageRank核心思想：在互联网上，如果一个网页被很多其他网页所链接，说明它受到普遍的承认和信赖，那么它的排名就高。（解决网页质量的问题）
• PageRank的计算方式：
  • 计算搜索结果的网页排名过程会用到网页本身的排名。
  • 使用一个二维矩阵相乘来迭代解决：首先假定所有网页的排名是相同的，并且根据这个初值，算出各个网页的第一次迭代排名，然后再根据第一次迭代排名算出第二次排名。理论上证明不论初始值如何选取，这种算法都保证了网页排名的估计值能收敛到排名的真实值。
  • 由于矩阵非常大，所以使用稀疏矩阵计算的技巧来简化计算量。
  • 使用MapReduce并行计算工具来加速网页更新的周期。

• 补充
  • 稀疏矩阵的存储方式：
    • https://www.cnblogs.com/xbinworld/p/4273506.html
    • https://zhuanlan.zhihu.com/p/37525925
  • 稀疏矩阵的计算方式：
    • 基于CRS：https://xupsh.github.io/pp4fpgas-cn/06-Sparse-Matrix-Vector-Multiplication.html
    • LeetCode：https://www.cnblogs.com/grandyang/p/5282959.html