将链接视作投票
简单的递归公式
流模型
“随机”的解释:从i这个页面开始,它可能有di种选择,而且他做每一种选择的时候,选择的概率是相同的,即他决定到下一个页面是一个随机的选择(应该跳到那个页面),我们把上面图中的矩阵叫随机邻接矩阵。
矩阵方程
矩阵方程实例
幂迭代方法
r向量是所有网页的重要程度组成的向量。
幂迭代求解
r=r'的意思是,最后求得r'的值趋于稳定,不再变化。
随机游动的解释
平稳分布
存在性和唯一性
在节点少的图中,如果新增一个节点的话,整个图是需要重新算的。但是在亿级节点的话,多一个节点少一个节点,对图的影响不一定大。像百度和谷歌就不会频繁的去计算。
按照流公式迭代不一定会收敛到我们想要的结果。
收不收敛?
ABCD图,所有的权重最后都归到了C这一个点。
PageRank问题
解决办法:随机传送
pagerank是一个针对图的算法,有名是因为,最早的时候谷歌用它做了一个所谓比较公正的网络排序,但后来人们对他做了各种优化,争取通过他的规则,把自己的网页提高比较靠前的位置,也通过优化来使结果更加的稳定。
pagerank可以帮你在有关联的图中找到最重要的节点。