- 浏览: 95149 次
- 性别:
- 来自: 上海
文章分类
最新评论
-
xqxmh:
哈哈哈哈哈哈
12月编程语言榜单公布 C#等评级创新高 - CSDN新闻 -
niechanggang:
这个图片很是形象,linux也来祭奠了。。
【转】悼念一个伟大的公司——Sun - CSDN新闻
先保存一下,待有时间好好研究
1.Google PageRank 算法
1.1、PageRank(网页级别)的概念
互联网发展早期的搜索引擎,对web页面的排序,是根据搜索的词组(短语)在页面中的出现次数(occurence ),并用页面长度和html标签的重要性提示等进行权重修订。链接名气(link popularity)技术通过其它文档链接到当前页面(inbound links)的链接数量来决定当前页的重要性,这样可以有效地抵制被人为加工的页面欺骗搜索引擎的手法。PageRank计算页面的重要性,对每个链入(inbound)赋以不同的权值,链接提供页面的越重要则此链接入越高。当前页的重要性,是由其它页面的重要性决定的。
1.2、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的排序贡献。
1.3、随机冲浪模型
Lawrence Page 和 Sergey Brin 提出了用户行为的随机冲浪模型,来解释上述算法。他们把用户点击链接的行为,视为一种不关心内容的随机行为。而用户点击页面内的链接的概率,完全由页面上链接数量的多少决定的,这也是上面PR(Ti)/C(Ti)的原因。一个页面通过随机冲浪到达的概率就是链入它的别的页面上的链接的被点击概率的和。阻尼系数d的引入,是因为用户不可能无限的点击链接,常常因劳累而随机跳入另一个页面。d可以视为用户无限点击下去的概率,(1-d)则就是页面本身所具有的网页级别。1.4、PageRank算法2(对算法1的修订)
PR(A) = (1-d) / N + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))
其中N是互联网上所有网页的数量由此,所有页面的网页级别形成的一个概率分布,所有页面的网页级别之和是1。在算法1中,随机冲浪访问某个页面的概率由互联网的总页数决定,在算法2中,网页级别是一个页面被随机访问的期望值。
以下讲解,皆基于算法1,主要是计算简单,因为不用考虑N的值。由此,所有页面的网页级别形成的一个概率分布,所有页面的网页级别之和是1。在算法1中,随机冲浪访问某个页面的概率由互联网的总页数决定,在算法2中,网页级别是一个页面被随机访问的期望值。
以下讲解,皆基于算法1,主要是计算简单,因为不用考虑N的值。1.5、PageRank的特性
所有页面的网页级别之和等于互联网的总页数。在网页数比较少的情况下,网页级别方程可以解出,而面对互联网上成亿的网页,再解方程是不可能的。
此处设阻尼系数为0.5,虽然Lawrence Page 和 Sergey Brin在实际将其设为 0.85.PR(A) = 0.5 + 0.5 PR(C)
PR(B) = 0.5 + 0.5 (PR(A) / 2)
PR(C) = 0.5 + 0.5 (PR(A) / 2 + PR(B))
解得:
PR(A) = 14/13 = 1.07692308
PR(B) = 10/13 = 0.76923077
PR(C) = 15/13 = 1.15384615
有:
PR(A)+PR(B)+PR(C)=31.6、迭代计算pagerank
Google采用一种近似的迭代的方法计算网页的网页级别的,也就是先给每个网页一个初始值,然后利用上面的公式,循环进行有限次运算得到近似的网页级别。根据Lawrence Page 和 Sergey Brin公开发表的文章,他们实际需要进行100次迭代才能得到整个互联网的满意的网页级别值,这儿的例子只用了10多次就可以了。在迭代的过程中,每个网页的网页级别的和是收敛于整个网络的页面数的。所以,每个页面的平均网页级别是1,实际上的值在(1-d)和(dN+(1-d))之间。迭代次数
PR(A)
PR(B)
PR(C)
0
1
1
1
1
1
0.75
1.125
2
1.0625
0.765625
1.1484375
3
1.07421875
0.76855469
1.15283203
4
1.07641602
0.76910400
1.15365601
5
1.07682800
0.76920700
1.15381050
6
1.07690525
0.76922631
1.15383947
7
1.07691973
0.76922993
1.15384490
8
1.07692245
0.76923061
1.15384592
9
1.07692296
0.76923074
1.15384611
10
1.07692305
0.76923076
1.15384615
11
1.07692307
0.76923077
1.15384615
12
1.07692308
0.76923077
1.15384615
1.7、Google搜索引擎的网页级别的实现
有三个因素决定的网页的等级:网页特定性因素、入链锚的文本、网页级别。
网页特定性因素包括网页的内容、标题及URL等。
为提供检索结果,Google根据网页特定性因素和入链锚的文本计算出网页的IR值,这个值被检索项在页面中的位置和重要性加权,以决定网页和检索请求相关性。IR值和网页级别联合标志网页的基本重要程度,这两个值的联合方式有多种,但明显的是不能相加的。
由于网页级别只对非特定的单个词的检索请求影响比较明显,对于由多个检索词构成的检索请求,内容相关性的分级标准的影响更大。1.8、用Google工具条显示当前页面的网页级别
Google工具条是Google公司开发的IE插件,需要从Google下载并安装。注意,显示网页级别的功能是其高级功能,这时会自动收集用户的信息,并会自动升级工具条。
这个工具条显示的网页级别分为0-10共11级,如果根据理论用(Nd+(1-d))测算,假定d=0.85,则推测实际网级别的对数即为显示的级别,且对数的基数在6-7之间。Google的目录服务可以显示网站的级别
此处级别分为7级。有人对两种级别进行了比较。
1.9、入链对计算页面级别的影响
入链总是能增加当前页面的级别,尤其当前页与其下级页面构成回路时,这种贡献更大。如右图例,设ABCD各 页初始级别为1,阻尼系数为0.5,PR(X)/C(X)=10。则易算出PR(A) = 19/3 = 6.33
PR(B) = 11/3 = 3.67
PR(C) = 7/3 = 2.33
PR(D) = 5/3 = 1.67如果A不在回路上,则只能得0.5*10=5的收益。
阻尼系数越大,页面级别的收益越大,且整个回路上都能收到更大的收益(即入链收益更能平均地分布到各个回路页面上。针对上例,将阻尼系数改为0.75,则有PR(A) = 419/35 = 11.97
PR(B) = 323/35 = 9.23
PR(C) = 251/35 = 7.17
PR(D) = 197/35 = 5.63除回路上各个页面的级别值明显增大外,PR(A)/PR(D)的值敢明显减少了。
入链对整个回路上所有页面的级别值的增加之和,可以由下面这个公式得出.(d / (1-d)) × (PR(X) / C(X))
这个公式,可以由 简单推导出。
1.10、出链对计算页面级别的影响
增加出链不会影响整个web的总级别,但一个站点失去的级别值等于链到的站点的增加值之和。对于两个封闭的站点,从一个站点链上另一个站点时,增加的和减少的都是(d(/(1-d) × (PR(X) / C(X)).如果这两个站点互相链接,则此值减少。用随机冲浪模型可以解释这种现象,就是出链的增加,减少了用户访问站内页面的概率。举例如图,设阻尼系数 为0.75,则PR(A) = 0.25 + 0.75 PR(B)
PR(B) = 0.25 + 0.375 PR(A)
PR(C) = 0.25 + 0.75 PR(D) + 0.375 PR(A)
PR(D) = 0.25 + 0.75 PR(C)
得:
PR(A) = 14/23
PR(B) = 11/23
PR(C) = 35/23
PR(D) = 32/23
PR(A)+PR(B)=25/23
PR(C)+PR(D)=67/23
PR(A)+PR(B)+PR(C)+PR(D)=92/23=4Page和Brin将这样的链接称为悬摆链,它链到页面没有出链。悬摆链对页 面的级别计算产生负面影响。如例,阻尼系数为0.75.
PR(A) = 0.25 + 0.75 PR(B)
PR(B) = 0.25 + 0.375 PR(A)
PR(C) = 0.25 + 0.375 PR(A)
得:
PR(A) = 14/23
PR(B) = 11/23
PR(C) = 11/23
PR(A)+PR(B)+PR(C)=36/23据Page和Brin,Google在索引页面时,悬摆链的量很大,
主要是由于限制robot.txt的限制及索引了一些没有链出的文件类
型如PDF等。为消除这种负面影响,google在计算级别时,将此
类链接从数据库里去掉,在计算完毕后,再单独计算悬摆链所链
到页面。由此可见,PDF类的文件还是可以放心地在网上发布的。
1.11、页面数量的影响
先看例子。阻尼系数为0.75,PR(X)/C(X)=10,则PR(A) = 0.25 + 0.75 (10 + PR(B) + PR(C))
PR(B) = PR(C) = 0.25 + 0.75 (PR(A) / 2)
得:PR(A) = 260/14
PR(B) = 101/14
PR(C) = 101/14
PR(A)+PR(B)+PR(C)=33;
增加页面D;
PR(A) = 0.25 + 0.75 (10 + PR(B) + PR(C) + PR(D))
PR(B) = PR(C) = PR(D) = 0.25 + 0.75 (PR(A) / 3)
得
PR(A) = 266/14
PR(B) = 70/14
PR(C) = 70/14
PR(D) = 70/14
PR(A)+PR(B)+PR(C)+PR(D)=34增加页面后,所有页面的级别值之和增加了1,A页略有增加,而B、C则用大幅下降。
再看右边的例子,假定同上。PR(A) = 0.25 + 0.75 (10 + PR(C))
PR(B) = 0.25 + 0.75 × PR(A)
PR(C) = 0.25 + 0.75 × PR(B)
得:
PR(A) = 517/37 = 13.97
PR(B) = 397/37 = 10.73
PR(C) = 307/37 = 8.30增加页面D:
PR(A) = 0.25 + 0.75 (10 + PR(D))
PR(B) = 0.25 + 0.75 × PR(A)
PR(C) = 0.25 + 0.75 × PR(B)
PR(D) = 0.25 + 0.75 × PR(C)
得:
PR(A) = 419/35 = 11.97
PR(B) = 323/35 = 9.23
PR(C) = 251/35 = 7.17
PR(D) = 197/35 = 5.63增加页面后,所有页面级别增加了1,但每个页面的级别值减少了,这是由于新加页面分享了入链代来的值。从这个结果看,增加页面减少了已有页面的级别值,露了google算法青睐小站点的特点。当然,大站点也会因内容丰富而吸引其它 站点的出链而得以级别值增加。
1.12、针对搜索引擎优化的级别分布
先看两个列子,阻尼系数为0.5,PR(X)/C(X)=10;BC之间无链接时:
PR(A) = 0.5 + 0.5 (10 + PR(B) + PR (C))
PR(B) = 0.5 + 0.5 (PR(A) / 2)
PR(C) = 0.5 + 0.5 (PR(A) / 2)
得
PR(A) = 8
PR(B) = 2.5
PR(C) = 2.5
BC之间互相链接时:
PR(A) = 0.5 + 0.5 (10 + PR(B) / 2 + PR(C) / 2)
PR(B) = 0.5 + 0.5 (PR(A) / 2 + PR(C) / 2)
PR(C) = 0.5 + 0.5 (PR(A) / 2 + PR(B) / 2)
得:
PR(A) = 7
PR(B) = 3
PR(C) = 3当BC 间互链时,虽然减少了A的级别,但BC都增加了。这符合优化站点所有页面而非只主页的优化思路,因为只有每个页面的级别都提高了,当有检索词命中这些页面时,它们才能排在前面。这种优化的方法也很明显了,就是尽可能地在所有页面间平均分布入链的贡献,各低级页面要增加互链。
只要不影响易用性,尽可能地将所有出链集中在一个或几个低级页面中,可以有效地降低出链对页面级别计算的负面影响。看列子:阻尼系数为0.5, PR(X)/C(X)=10;
BCD都有出链时:
PR(A) = 0.5 + 0.5 (PR(B) / 2 + PR(C) / 2 + PR(D) / 2)
PR(B) = PR(C) = PR(D) = 0.5 + 0.5 (PR(A) / 3)
得:
PR(A) = 1
PR(B) = 2/3
PR(C) = 2/3
PR(D) = 2/3
出链集中于D时:
PR(A) = 0.5 + 0.5 (PR(B) + PR(C) + PR(D) / 4)
PR(B) = PR(C) = PR(D) = 0.5 + 0.5 (PR(A) / 3)
得:
PR(A) = 17/13
PR(B) = 28/39
PR(C) = 28/39
PR(D) = 28/39从结果看,出链集中后,ABCD各页面的级别都上升了。
1.13、影响页面级别的其它因素
在Lawrence Page和Sergey Brin关于PageRank的论文发表以后,除了web的链接结构以外,还有没有别的因素被加到PageRank的算法当中曾经有过广泛地讨论。 Lawrence Page本人在PageRank的专利说明中曾指出以下潜在的影响因素:链接的能见度,链接在文档中的位置,web页面间的距离,出链页面的重要性,页面的不过时。这此因素的增加,可以更好用随机冲浪模型模拟人类利用web的行为。
不管上述附加因素有没有在实际计算PageRank时使用,如何实现这些附加因素仍要讨论。
首先算法公式需要改进.PR(A) = (1-d) + d (PR(T1)×L(T1,A) + ... + PR(Tn)×L(Tn,A))
此处,L(T1,A)是入链的评价值,由几个因素构成,只需要在迭代前计算一次,减少了对数据库的查询次数,虽然每次迭代的查询结果会有不同。
Lawrence Page在PageRank的专利说明中指出链接评价的两个因素是链接的可见性和在文档中的位置。链接评价取代了PR(A)/C(A),指出了对一特定的页面的链接,每个链接被点击的概率是不同的。
此处,每一链接有两个属性值,X表示可见度,如果没有被重点强调(如粗体、斜体等) 为1否则为2,Y表链接在文档中的位置,如果在文档下半部为1否则为3。则有X(A,B) × Y(A,B) = 1 × 3 = 3
X(A,C) × Y(A,C) = 1 × 1 = 1
X(B,A) × Y(B,A) = 2 × 3 = 6
X(B,C) × Y(B,C) = 2 × 1 = 2
X(C,A) × Y(C,A) = 2 × 3 = 6
X(C,B) × Y(C,B) = 2 × 1 = 2
易得:
Z(A) = X(A,B) × Y(A,B) + X(A,C) × Y(A,C) = 4
Z(B) = X(B,A) × Y(B,A) + X(B,C) × Y(B,C) = 8
Z(C) = X(C,A) × Y(C,A) + X(C,B) × Y(C,B) = 8
链接评价公式为:(页面T1指向T2)
L(T1,T2) = X(T1,T2) × Y(T1,T2) / Z(T1)
有:
L(A,B) = 0.75
L(A,C) = 0.25
L(B,A) = 0.75
L(B,C) = 0.25
L(C,A) = 0.75
L(C,B) = 0.25
最后利用改进的公式计算页面级别:
PR(A) = 0.5 + 0.5 (0.75 PR(B) + 0.75 PR(C))
PR(B) = 0.5 + 0.5 (0.75 PR(A) + 0.25 PR(C))
PR(C) = 0.5 + 0.5 (0.25 PR(A) + 0.25 PR(B))
得:
PR(A) = 819/693
PR(B) = 721/693
PR(C) = 539/693为了防止人为的级别优化,页面的距离被用来影响链接的评价。站内链接的权重小于站间链接的权重。页面的距离可能由页面是否在一个站内、一个服务器及物理距离等决定。
另一个影响页面重要性的能参数,是页面的不过时性(up-to-dateness),意指有越多的新建的页面指向某一个页面,则这个页面内容过时的可能性越小。
为增加这些因素的影响,要对公式进行修订如下:L(Ti,A) = K(Ti,A) × K1(Ti) × ... × Km(Ti)
其中,K(Ti,A)表示链接可见度及位置的权重,Kn(Ti)是第n个因素对页面Ti的影响。看列子:此处,从C引出的链接的重要性是其它 的4倍。
K(A) = 0.5
K(B) = 0.5
K(C) = 2
计算级别值:
PR(A) = 0.5 + 0.5 × 2 PR(C)
PR(B) = 0.5 + 0.5 × 0.5 × 0.5 PR(A)
PR(C) = 0.5 + 0.5 (0.5 PR(B) + 0.5 × 0.5 PR(A))
得:
PR(A) = 4/3
PR(B) = 2/3
PR(C) = 5/6此时,所有页面的级别之和不等于页面数量。
1.14 PageRank 算法的改进1. 主题敏感的PageRank(Topic-Sedsitive PageRank)
在这个算法中,我们需要预先计算离线时页面的重要性的分数;然后,我们为每一个页面计算多种重要性分数,即关于不同的主题来计算这个页面的重要性分数。在查询的时候,把这些重要性分数与根据被查询的主题的重要性分数综合在一起,就形成一个复合的PageRank分数。采用这种方法能形成更加精确的排序值,而不是原始普通的排序值。2. 二次方程推断法(Quadratic Extra polation)
这是一个可以加快PageRank的运算速度的方法。它能通过周期性的削减当前的矩阵乘幂迭代的非主要特征向量的方法,大大加快其收敛速度。使用这种方法计算PageRank值时,当计算一个包含8000万个节点的网络图时,与采用原来的PageRank方法相比,计算速度可以提高20%-300%。3. 分块矩阵排序算法(BlockRank Algo rithm)
该算法是PageRank算法的另一个加速算法,它首先把网络根据领域划分成不同的区域(块),为每个区域计算它们的局部PageRank值;估计它们的相对的重要性(每个区域的BlockRank值);用这个区域的Block-Rank.值来给每个区域的Block-Rank赋予一定的权重。然后再把这些加权的局部
的PageRank值近似地看作全局的PageRank向量,把这个向量作为标准的PageRank算法的开始向量。这种方法可以减少计算的迭代次数,可以把更多的时间用于收敛速度慢的区域的计算,提高了局部PageRank计算的有效性。BlockRank算法可以采取并行或分布的形式来进行计算,节约运算的时间。此外,局部的PageRank计算结果在以后的计算中可以被再利用。
Google Page Rank 算法(转载) - 北溟居 - CSDN博客
发表评论
-
互联网迟到的80 后:为什么中国出不了扎克伯格 - CSDN资讯
2010-03-11 09:13 677身为80后,明显能感觉 ... -
Google手机研发不为人知的故事 - CSDN资讯
2010-02-09 03:24 731Google首款自有品牌手机Nexus One受到了 ... -
改变IT世界的11大Apache开源技术 - Java编程 - JavaEye新闻
2010-02-26 09:14 938据国外媒体报道,转眼之间,Apache软件基金会已经 ... -
【转】搜索算法基础教程 - Kangsheng的专栏 - CSDN博客
2010-02-26 09:25 1388记录以待以后学习 ... -
【转】手机也能收发邮件 网易发布“网易掌上邮” - CNET科技资讯网
2010-01-30 06:54 2704这是个好消息,说明网易的用户体验做的越来越好了,攒 ... -
【转】方兴东: Google中国最佳战略:果断卖了自己! - CSDN新闻
2010-01-20 09:46 632呵呵,分析的确是透彻 ... -
用eclipse europa开发web service服务 - 东写西读终见大海无量 - JavaEye技术网站
2009-12-23 09:25 826用eclipse europa开发web service ... -
我国将于明年开展四项SOA国家标准制定_业界_科技时代_新浪网
2009-12-22 04:36 622我国将于明年开展四项SOA国家标准制定 http://w ... -
【转】浅谈javascript的分号 - 网页制作 - 蓝色理想
2009-12-09 07:39 899javascript的分号代表语句的结束符,但由于jav ... -
DB2的几个权限级别整理
2009-10-26 06:30 650 -
转:DB2 decimal 类型的长度问题
2009-11-10 09:12 2255http://www.cppblog.com/prayer/a ... -
谷歌发明编程语言Go简化应用开发 - CSDN新闻
2009-11-11 09:27 1156北京时间11月11日早间消息,据国外媒体报道,谷歌周二推 ... -
惠普宣布以27亿美元现金收购3Com 对战思科___电信通讯_eNet资讯频道
2009-11-12 04:39 826当今的世道乱啊,多少 ... -
什么是SAAS--是什么|什么叫|是什么意思
2009-11-17 09:05 803什么是SAAS 作者: ... -
如何用Rational Rose 2003 画 组合聚合关系(实心菱形)_如鱼得水
2009-11-18 13:49 3741如何用Rational Rose 2003 画 组合聚合 ... -
十年苦心重塑公众形象 微软终摘硅谷公敌恶名 - CSDN新闻
2009-12-01 08:29 427其实做公司和做人一样 ... -
12月编程语言榜单公布 C#等评级创新高 - CSDN新闻
2009-12-07 09:10 1051Tiobe今日发布了12月份的编程语言排行榜。榜单中,由 ... -
十年苦心重塑公众形象 微软终摘硅谷公敌恶名 - CSDN新闻
2009-12-01 08:29 602其实做公司和做人一样 ... -
必将改变Web的五大技术 - CSDN新闻
2009-12-09 04:09 507几年前当MP3格式问世 ...
相关推荐
Google page rank 算法经典论文,线性代数经典运用
主要讲解了pagerank算法,有兴趣的同学可以看一下,我觉得还不错
根据《集体智慧编程》实现的一个小型的搜索引擎,包括page rank算法和BF 神经网络算法的实现
PaRaMeter stands for "Page Rank Meter" - a free Google PageRank checking and monitoring tool. PageRank is one of the methods Google uses to determine how relevant and important a page is. PageRank is ...
用Fortran开发的基于Page-rank理论的网络重要性分析程序
Page-Rank-Algorithm:使用pyspak实现页面排名算法
【项目资源】:包含前端、后端、移动开发、操作系统、人工智能、物联网、信息化管理、数据库、硬件开发、大数据、课程资源、音视频、网站开发等各种技术项目的源码。...【项目质量】:所有源码都经过严格测试,可以直接...
SCE-UA算法是Qingyun Duan(段青云)、Soroosh Sorooshian 和Vijai Gupta等开发的一个具有复合优化策略的优化算法(Duan等,1992)。具体原理可以参考文献。笔者用C++实现了SCE-UA算法,并用常见的测试函数进行了...
STM32的USB详解-官方版本-免费下载blog.csdn.net-lanmanck.pdf
hadoop-page-rank MC6007 - Hadoop PageRank map-reduce
三、闰年算法 page17、 page107 四、连续小数相加减 page18、 page124 五、素数、整除问题 page18、 page124、 page126、 page127 六、大小写字母转换、密码问题 page51、 page87、 page89/4.9、 page104、 page67、...
许检查网站的网站等级
使用Mapper-Reducer实现PageRank算法 如何运行: hdfs dfs -rm -r / transition#删除HDFS中的/ transition目录,如果该目录不存在,则忽略错误信息。 hdfs dfs -mkdir / transition#在HDFS中创建/ transition...
ASP.NET百度权重,alexa排名,google page rank,google收录,百度收录和百度快照查询源代码.rar
Hadoop-MapReduce下的PageRank矩阵分块算法
1.google's page rank and beyond2.Understanding search engines附带阅读器,欢迎搜索爱好者和我联系交流,email:gigglesun@163.com.
基于page rank的个人搜索引擎项目
By agreement with the publisher, you can download the book for free from this page. Cambridge University Press does, however, retain copyright on the work, and we expect that you will obtain their ...