Google的PageRank(网页级别)算法研究学习

1、PageRank(网页级别)的概念
　　互联网发展早期的搜索引擎，对web页面的排序，是根据搜索的词组（短语）在页面中的出现次数（occurence ），并用页面长度和html标签的重要性提示等进行权重修订。链接名气(link popularity)技术通过其它文档链接到当前页面（inbound links）的链接数量来决定当前页的重要性，这样可以有效地抵制被人为加工的页面欺骗搜索引擎的手法。
　　PageRank计算页面的重要性，对每个链入(inbound)赋以不同的权值，链接提供页面的越重要则此链接入越高。当前页的重要性，是由其它页面的重要性决定的。

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的排序贡献。

3、随机冲浪模型
　　Lawrence Page 和 Sergey Brin 提出了用户行为的随机冲浪模型，来解释上述算法。他们把用户点击链接的行为，视为一种不关心内容的随机行为。而用户点击页面内的链接的概率，完全由页面上链接数量的多少决定的，这也是上面PR(Ti)/C(Ti)的原因。一个页面通过随机冲浪到达的概率就是链入它的别的页面上的链接的被点击概率的和。阻尼系数d的引入，是因为用户不可能无限的点击链接，常常因劳累而随机跳入另一个页面。d可以视为用户无限点击下去的概率，（1－d）则就是页面本身所具有的网页级别。

4、PageRank算法2（对算法1的修订）

PR(A) = (1-d) / N + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))
其中N是互联网上所有网页的数量

由此，所有页面的网页级别形成的一个概率分布，所有页面的网页级别之和是1。在算法1中，随机冲浪访问某个页面的概率由互联网的总页数决定，在算法2中，网页级别是一个页面被随机访问的期望值。
　　以下讲解，皆基于算法1，主要是计算简单，因为不用考虑N的值。

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)=3

6、迭代计算pagerank
　　Google采用一种近似的迭代的方法计算网页的网页级别的，也就是先给每个网页一个初始值，然后利用上面的公式，循环进行有限次运算得到近似的网页级别。根据Lawrence Page 和 Sergey Brin公开发表的文章，他们实际需要进行100次迭代才能得到整个互联网的满意的网页级别值，这儿的例子只用了10多次就可以了。在迭代的过程中，每个网页的网页级别的和是收敛于整个网络的页面数的。所以，每个页面的平均网页级别是1，实际上的值在（1－d）和(dN+(1-d))之间。

7、Google搜索引擎的网页级别的实现
　　有三个因素决定的网页的等级：网页特定性因素、入链锚的文本、网页级别。
　　网页特定性因素包括网页的内容、标题及URL等。
　　为提供检索结果，Google根据网页特定性因素和入链锚的文本计算出网页的IR值，这个值被检索项在页面中的位置和重要性加权，以决定网页和检索请求相关性。IR值和网页级别联合标志网页的基本重要程度，这两个值要做乘法运算，明显的是不能相加的。
　　由于网页级别只对非特定的单个词的检索请求影响比较明显，对于由多个检索词构成的检索请求，内容相关性的分级标准的影响更大。

8、用Google工具条显示当前页面的网页级别
　　Google工具条是Google公司开发的IE插件，需要从Google下载并安装。注意，显示网页级别的功能是其高级功能，这时会自动收集用户的信息，并会自动升级工具条。
　　这个工具条显示的网页级别分为0－10共11级，如果根据理论用(Nd+(1-d))测算，假定d=0.85,则推测实际网级别的对数即为显示的级别，且对数的基数在6-7之间。
　　参考文献1中给出了一个方法，可以不经过toolbar就可以取得网站主页的网页级别，可惜因为版本或别的原因，已经不可行。下面我根据提示在IE缓冲目录里找到http://hedong.3322.org的获取URL.

http://216.239.33.104/search?client=navclient-auto&ch=5766303732&ie=UTF-8&oe=UTF-8&features=Rank:FVN&q=info:http%3A%2F%2Fhedong%2E3322%2Eorg%2F

　　我的主页的网页级别是0。:( isaac和chedong的分别是5和4。

9、Google的目录服务可以显示网站的级别
　　此处级别分为7级。有人对两种级别进行了比较。　　

Google的PageRank算法学习(2)

参考文献：
1、A Survey of Google's PageRank，http://pr.efactory.de/
2、认真从计算方法角度阐述PageRank机制2篇文章，chedong, http://www.cnblog.org/blog/archives/2003_06_15_cnblog_archive.html#95908517

Posted by Hilton at August 28, 2003 10:05 AM | TrackBack

Google的PageRank算法学习(2)

　　继续学习。

1、入链对计算页面级别的影响
　　入链总是能增加当前页面的级别，尤其当前页与其下级页面构成回路时，这种贡献更大。如右图例，设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))

这个公式，可以由 简单推导出。
2、出链对计算页面级别的影响
　　增加出链不会影响整个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=4

　　Page和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<3

　　据Page和Brin，Google在索引页面时，悬摆链的量很大，主要是由于限制robot.txt的限制及索引了一些没有链出的文件类型如PDF等。 为消除这种负面影响，google在计算级别时，将此类链接从数据库里去掉，在计算完毕后，再单独计算悬摆链所链到页面。由此可见，PDF类的文件还是可以放心地在网上发布的。

3、页面数量的影响
　　先看例子。阻尼系数为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算法青睐小站点的特点。当然，大站点也会因内容丰富而吸引其它站点的出链而得以级别值增加。

3、针对搜索引擎优化的级别分布
　　先看两个列子，阻尼系数为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都增加了。这符合优化站点所有页面而非只主页的优化思路，因为只有每个页面的级别都提高了，当有检索词命中这些页面时，它们才能排在前面。这种优化的方法也很明显了，就是尽可能地在所有页面间平均分布入链的贡献，各低级页面要增加互链。

4、只要不影响易用性，尽可能地将所有出链集中在一个或几个低级页面中，可以有效地降低出链对页面级别计算的负面影响。看列子：阻尼系数为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各页面的级别都上升了。

5、链接交换增加了实施交换的页面的级别，却减少了其它页面的级别。如图，阻尼系数为0.5，PR(X)/C(X)=10;

交换前，
PR(A) = 4/3
PR(B) = 5/6
PR(C) = 5/6

PR(D) = 4/3
PR(E) = 5/6
PR(F) = 5/6
交换后；
PR(A) = 0.5 + 0.5 (PR(B) + PR(C) + PR(D) / 3)
PR(B) = PR(C) = 0.5 + 0.5 (PR(A) / 3)
PR(D) = 0.5 + 0.5 (PR(E) + PR(F) + PR(A) / 3)
PR(E) = PR(F) = 0.5 + 0.5 (PR(D) / 3)
得
PR(A) = 3/2
PR(B) = 3/4
PR(C) = 3/4
PR(D) = 3/2
PR(E) = 3/4
PR(F) = 3/4

这情况恰好与增加站内互链的效果相反。由此，当需要对主页进行针对某一关键词的优化时，才取交换链接是可取的。
　　例中级别值的重新分布，更基本的前提是两个站点中参考交换的页面互相为对方提供的级别值是相等的。如果一个站的某个页面级别高或少出链，则这个站所有页面的级别会降低。这儿一个重要的影响因素是站点页面的数量。当一个站点的页面更多时，有更多的入链级别值被分布到站点的其它页面中，因而参考交换的页面不能提供更多贡献给对方。
　　
　　Google的PageRank算法学习(3)

　　继续学习。

1、很多针对搜索引擎做网站优化的专家，认为google给一些特殊站点以特定的级别而不是按前述算法进行计算，这些网站的级别很有可能来在Yahoo或ODP(Open Directory Project)。Lawrence Page在他们的专利说明中，提到随机冲浪模型中，用记不愿继续点击时，很有可能借助Yahoo的目录或ODP到另一个站点去。
　　由于前述的算法，无论初始的级别值如何，经过足够次数的迭代最终结果都是一样的，所以对这些特殊站点可能采用下述的公式。

PR(A) = E(A) (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

　　从另一个角度来看，如果给页面赋一个跟其实际级别相近的初始值，可以明显减少迭代次数。

2、影响页面级别的其它因素
　　在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

此时，所有页面的级别之和不等于页面数量。

3、基于主题或标题的搜索评级，因google没有采用，略去不看。

4、Google的PR0惩罚
　　Google对采用了搜索优化的网站的一种惩罚就是，把这个站的所有或很多网页的网页级别定为0，典型的表现就是原先不为0忽然变为0的情况。当然，PR为0不一定是受到了惩罚，可能只是因为没有重要页面链到它。
　　一个Google的员工在WebmasterWorld's Google News论坛上一再提醒网站管理员，一定不要“链接到坏邻居”。Raph Levien提出了一种技术分析链接结构获取页面的负面特征，与"PageRank"相似但目标相反，名之为“BadRank”。
　　BadRank基于“链到坏邻居”，对BadRank有影响显然是出链，因为对PageRank的算法加以改动，即会适合BadRank的计算。

BR(A) = E(A) (1-d) + d (BR(T1)/C(T1) + ... + BR(Tn)/C(Tn))

,其中，BR(A) 是页面A的BadRank, BR(Ti)页面Ti的BadRank,页面A有链接到Ti,C(Ti)页面Ti的入链数，d是阻尼系数，E(A)表示当前页面有没有被垃圾网页过滤系统检测到。当E(A)为0时，这个公式不再有意义，它只是变成了另一种分析链接结构的方法而已。所有页面的E(A)之和等页面总数。看例子 ,令E(A)=100,其它的为1，d=0.85,则有