PageRank算法 之我看

PageRank是google搜索中用于计算页面的重要程度，即PR值。下面就是其计算公式：

 

我们可以把这也页面的连接关系看成图的结构，页面就是图中的一个节点，边代表页面之间的链接关系，

其中P(n)代表的就是第n个节点的PR值，L(n)代表n节点的所有入度节点的集合，C(m)代表m节点的出度，
G代表的是所有的节点数目，a代表的是随机的跳转到任何一个页面的概率，1-a代表进入到当前页面中的连接的概率

 

伪代码：摘自Jimmy lin

（没有考虑 dangling节点 以及 随机概率）

 

问题：

最常见的问题是dangling节点（该节点的出度为零，即该网页内没有任何其他的网页的链接）的问题，如果把这个的节点算在内的话，那么整个图内的PR值会被该节点吸收掉 一定情况下  最终迭代结果不能够收敛，甚至其它节点的PR值为零。。

 

那么如何解决这个点的问题呢？

谷歌的官方文档上提到过这个问题，首先将这些dangling页面从图中去除，等其他页面计算收敛后，再来计算这些dangling页面的PR值。

 

在网上看到还有提出将这个dangling节点只想其他所有的节点，这样ＰＲ值又可以流到途中，不至于吸收到ｄａｎｇｌｉｎｇ节点。

 

还有一种办法就是每次迭代之后，将其他节点减少的ＰＲ值重新分配到其它节点上（除了ｄａｎｇｌｉｎｇ节点）同样是按上述的概率分配。这个办法上述的办法一致

 

至于谷歌使用的pageRank的算法适合其他的算法配合使用的，而且速度很快 ，就是牛逼啊--没办法

 

评论

1 楼 Vincent_jianpeng 2013-07-14  

你好，你的图片加载不了。。。能不能重新放一张，新人真心学习的