PageRank 算法

PageRank 是一种由搜索引擎根据网页之间相互的超链接计算排名的技术。

• 假设页面 Pi 的 PageRank 为 PR(Pi)

• 假设页面 Pi 包含的超链接数为 L(Pi)，则页面 i 对该页面上的所有超链接的投票数分别是 PR(Pi)/L(Pi)

• 假设包含页面 Px 超链接的页面为页面 P1~页面 Pn，则页面 x 的 PageRank 值为页面 P1~页面 Pn 对该页面的投票数之和

所以公式：PR(Px)=PR(P1)/L(P1)+PR(P2)/L(P2)+PR(P3)/L(P3)+......+PR(Pn)/L(Pn)

上述公式的问题：如果页面 A 只有一个包含自己的链接，则该公式就存在 A 页面循环投向自己的页面。

解决方案：所有页面存在一定的概率跳出到一个随机的页面，假定这个概率为α（一般取值 0.85），则公式演变为

PR(Px)=(1-α)/n+α(PR(P1)/L(P1)+PR(P2)/L(P2)+PR(P3)/L(P3)+......+PR(Pn)/L(Pn))

由于存在链入链出关系的页面是极少数，所以可以使用稀疏矩阵进行存储。