Google Page Rank 算法(转载).doc

Google Page Rank 算法(转载)
Google Page Rank 算法(转载)
分类： 网络技术2005-12-23 15:255708人阅读评论(6)收藏举报
PageRank 、PageRank(网页级别)的概念
互联网发展早期的搜索引擎，对web页面的排序，是根据搜索的词组（短语）在页面中的出现次数（occurence ），并用页面长度和html标签的重要性提示等进行权重修订。链接名气(link popularity)技术通过其它文档链接到当前页面（inbound links）的链接数量来决定当前页的重要性，这样可以有效地抵制被人为加工的页面欺骗搜索引擎的手法。 PageRank计算页面的重要性，对每个链入(inbound)赋以不同的权值，链接提供页面的越重要则此链接入越高。当前页的重要性，是由其它页面的重要性决定的。、PageRank算法1　　PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))
其中：PR(A):页面A的网页级别,
PR(Ti)：页面Ti的网页级别，页面Ti链向页面A，
C(Ti)：页面Ti链出的链接数量，
d：阻尼系数，取值在0－1之间. 由此可见，1）这个算法不以站点排序，页面网页级别由一个个独立的页面决定；2）页面的网页级别由链向它的页面的网页级别决定，但每个链入页面的贡献的值是不同的。如果Ti页面中链出越多，它对当前页面A的贡献就越小。A的链入页面越多，其网页级别也越高；3）阻尼系数的使用，减少了其它页面对当前页面A的排序贡献。 由此可见，1）这个算法不以站点排序，页面网页级别由一个个独立的页面决定；2）页面的网页级别由链向它的页面的网页级别决定，但每个链入页面的贡献的值是不同的。如果Ti页面中链出越多，它对当前页面A的贡献就越小。A的链入页面越多，其网页级别也越高；3）阻尼系数的使用，减少了其它页面对当前页面A的排序贡献。 、随机冲浪模型
　　Lawrence Page 和 Sergey Brin 提出了用户行为的随机冲浪模型，来解释上述算法。他们把用户点击链接的行为，视为一种不关心内容的随机行为。而用户点击页面内的链接的概率，完全由页面上链接数量的多少决定的，这也是上面PR(Ti)/C(Ti)的原因。一个页面通过随机冲浪到达的概率就是链入它的别的页面上的链接的被点击概率的和。阻尼系数d的引入，是因为用户不可能无限的点击链接，常常因劳累而随机跳入另一个页面。d可以视为用户无限点击下去的概率，（1－d）则就是页面本身所具有的网页级别。、PageRank算法2（对算法1的修订）PR(A) = (1-d) / N + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))
其中N是互联网上所有网页的数量由此，所有页面的网页级别形成的一个概率分布，所有页面的网页级别之和是1。在算法1中，随机冲浪访问某个页面的概率由互联网的总页数决定，在算法2中，网页级别是一个页面被随机访问的期望值。
　　以下讲解，皆基于算法1，主要是计算简单，因为不用考虑N的值。 由此，所有页面的网页级别形成的一个概率分布，所有页面的网页级