PageRank 算法随记

栏目: 后端 · 发布时间: 5年前

内容简介:递归的意思是:假如现在要求C,指向C的入链只有B,那么得先求B的重要度,B重要度的大小取决于指向B的入链以及这些入链的重要度。“随机”的解释:从i这个页面开始,它可能有di种选择,而且他做每一种选择的时候,选择的概率是相同的,即他决定到下一个页面是一个随机的选择(应该跳到那个页面),我们把上面图中的矩阵叫随机邻接矩阵。Σri=1在这里表示限定条件,和流方程一样,不加限定条件会有无穷多个解。所以这里的限定条件是假定所有网页的重要度求和等于1。

递归的意思是:假如现在要求C,指向C的入链只有B,那么得先求B的重要度,B重要度的大小取决于指向B的入链以及这些入链的重要度。

PageRank 算法随记
PageRank 算法随记

“随机”的解释:从i这个页面开始,它可能有di种选择,而且他做每一种选择的时候,选择的概率是相同的,即他决定到下一个页面是一个随机的选择(应该跳到那个页面),我们把上面图中的矩阵叫随机邻接矩阵。

矩阵方程

PageRank 算法随记

Σri=1在这里表示限定条件,和流方程一样,不加限定条件会有无穷多个解。所以这里的限定条件是假定所有网页的重要度求和等于1。

PageRank 算法随记

矩阵的行和r向量相乘的时候就是对流公式的表示。

矩阵方程实例

PageRank 算法随记

幂迭代方法

PageRank 算法随记

两个向量的1范数,其实是对应位置的差值绝对值之和。

r向量是所有网页的重要程度组成的向量。

幂迭代求解

PageRank 算法随记

总共是3个节点,初始化每个节点的重要度分别是1/3。

r=r'的意思是,最后求得r'的值趋于稳定,不再变化。

随机游动的解释

PageRank 算法随记

如果有很多页面指向页面j的话,那么它的重要度是很高的。

平稳分布

PageRank 算法随记

存在性和唯一性

PageRank 算法随记

在节点少的图中,如果新增一个节点的话,整个图是需要重新算的。但是在亿级节点的话,多一个节点少一个节点,对图的影响不一定大。像百度和谷歌就不会频繁的去计算。

按照流公式迭代不一定会收敛到我们想要的结果。

收不收敛?

PageRank 算法随记

a,b节点图,如果用1,0去初始化的话,会发现他们一直再对调。

ABCD图,所有的权重最后都归到了C这一个点。

PageRank 算法随记

随着矩阵运算的迭代,拿到的ABCD四个值都会非常非常趋于零。

PageRank问题

PageRank 算法随记
PageRank 算法随记

m这个点就是个陷阱问题,最终所有的权重都被吸到m这个点上。

PageRank 算法随记

终结者问题,最后的迭代结果是零零零,m这个点没有任何出链。

解决办法:随机传送

PageRank 算法随记

e代表全部的网页,就是说浏览者会随机的在全部网页中打开一个。

pagerank是一个针对图的算法,有名是因为,最早的时候谷歌用它做了一个所谓比较公正的网络排序,但后来人们对他做了各种优化,争取通过他的规则,把自己的网页提高比较靠前的位置,也通过优化来使结果更加的稳定。

pagerank可以帮你在有关联的图中找到最重要的节点。


以上所述就是小编给大家介绍的《PageRank 算法随记》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

算法设计与分析

算法设计与分析

张德富 / 2009-8 / 36.00元

《算法设计与分析》主要取材于算法设计与分析领域的经典内容,并介绍了算法设计的发展趋势。内容主要包括非常经典的算法设计技术,例如递归与分治、动态规划、贪心、回溯、分支限界、图算法,也包括了一些高级的算法设计主题,例如网络流和匹配、启发式搜索、线性规划、数论以及计算几何。在算法分析方面,介绍了概率分析以及最新的分摊分析和实验分析方法。在算法的理论方面,介绍了问题的下界、算法的正确性证明以及NP完全理论......一起来看看 《算法设计与分析》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

html转js在线工具
html转js在线工具

html转js在线工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具