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

计算公式:

image.png

  • PR(A) 是页面A的PR值
  • PR(Ti)是页面Ti的PR值，在这里，页面Ti是指向A的所有页面中的某个页面
  • C(Ti)是页面Ti的出度，也就是Ti指向其他页面的边的个数
  • d 为阻尼系数，其意义是，在任意时刻，用户到达某页面后并继续向后浏览的概率

举例说明

image.png

A有两个链接指向B和C
B有一个链接指向C
C有一个链接指向A
我们假设每个页面的PR初始值为1，d为0.5。

PR(A) = (1-0.5)+0.5(PR(C)/1) = 1
PR(B) = (1-0.5) + 0.5 (PR(A)/2) = 0.5 + 0.50.5 = 0.75
PR(C) = (1-0.5) + 0.5 (PR(A)/2 + PR(B)/1) = 0.5 + 0.5*(0.5+0.75) = 1.125

经过12次迭代后的结果:

image.png

一般需要设置收敛条件:

  • 上次迭代结果比本次小于某个误差值
  • 最大迭代次数