标点符(钱魏 Way)

基于PageRank算法的搜索引擎优化策略

 最近几年来, Google已经成为世界范围内使用最为广泛的搜索引擎之一。Google的优点不仅仅在于去除无用的(广告)标语构成单一页面的功能、独自的Cache 系统、动态制成摘要信息、为实现高速检索而设置的分散系统(数千台规模的L inux群集器)等[ ,而最大的优点正是其检索结果的正确性,与其他搜索引擎相比更优的搜索结果排名,有利于用户尽可能快地找到所需的信息。而研究目前国内互联网网站,可以发现我们在处理网页间的链接结构时,往往存在很大的随意性。殊不知网页间的链接结构正是决定网站在搜索结果中排名的重要因素之一。这种搜索结果排名技术建立在一种针对Web文档的复杂算法上,称之为PageRank算法。

本文的目的是在对PageRank算法分析的基础上,分析各类网络链接结构对搜索结果( PageRank值)的影响,以及由此产生的搜索引擎优化策略。

1 PageRank算法

简单的说, PageRank是代表互联网上某个页面重要性的一个数值。

一般搜索引擎将PageRank值与网页搜索结果相似度共同作为搜索结果的排序依据。就像后边即将阐述的一样,检索语句不会呈现在PageRank 自己的计算式上。不管得到多少检索语句, PageRank也是一定的、文件固有的评分量,该值仅仅依赖于网络的链接结构。

PageRank算法的具体思路是,将某个页面的PageRank除以存在于这个页面的正向链接,由此得到的值分别和正向链接所指向的页面的PageRank相加,即得到了被链接的页面的PageRank。算法基于“从许多优质的网页链接过来的网页,必定还是优质网页”的回归关系,来判定所有网页的重要性。一个网页的得票越多,则认为它的重要性也就越高。进一步说,投票网页的重要性也决定着票本身的重要程度。

计算某个网页PageRank值时所有的入链接都要考虑在内,页面A的PageRank值计算公式如下:

PR (A ) = (1 – d) + d ( PR ( t1) /C ( t1)+ ⋯ + PR ( tn) /C ( tn) )

公式中的PR代表页面的PageRank数值, t1 ~ tn 代表有链接指向页面A的网页, C是网页出链接的数量, d是阻尼系数(常数, Google通常取值0. 85) 。由于用户在互联网浏览时可能不按当前页面中的链接前进, 而随机跳跃到完全无关页面,所以d实际上代表的是用户跟随网页链接浏览,而不产生随机跳跃的概率值。

(1)式是在计算网页PageRank值的最初公式。由于至今Google都没有对外公布它所采用的算法,所以可能Google在使用时采取了该公式的一些变形。但这也几乎不影响下面的分析。

由(1)式可知,计算某个网页的PageRank值总是依赖于其他的相关页面,所以计算PageRank值实际上是一个迭代的过程,计算结果的精确程度依赖于初值的选取和迭代的次数。对于初值一般取1,而为了保证实际应用中这个结果总是收敛的,则加入了阻尼系数d 。

另外需要说明的是PR值与PageRank值的区别。安装了Google工具栏的用户也许看到工具栏上的PageRank显示条,这个工具可以即时地反映出浏览器当前访问的网页在Google中的PageRank值的标记,该值在0至10范围内变化。之所以称之为“标记”是因为它并非网页的真实PageRank值,而是真实值的一个对数指标,对数基应该是5~6范围内的某个数值。

网页对它的所有出链接的页面进行PageRank“投票”。由于随机跳转的可能性,投出的PageRank总值比网页本身的PageRank值稍小(本身值3 d ) 。这个值在所有出链接中平均分配。因而指向你的网页的页面的PageRank值固然重要,但该页面的出链接数量也同样不可忽略:出链接越多,你的网页得到的PageRank值就越少。另外由于PR 值是PageRank真实值的对数指标,这意味着一个网页从某个较高的PR值得到提升要比从较低的PR值上升过来需要更多的PageRank值。在这种情况下,一个较多出度的PR8网页和另一个只有较少出链接的PR4页面相比,哪个更有效些? 这可能依赖于PR值的对数基和具体的链接情况了。

需要注意的是当一个网页以“投票“方式影响其他页面的PageRank值时, 不会减少自身的PageRank 值。这并非PageRank的转移过程。

2 基于PageRank的优化策略

假设我们有一个网站,很显然将网站的PageRank平均分配到各个网页(如果可能的话)是非常不明智的,因为我们不可能、也没有必要使网站的所有网页搜索排名都做到很高。如果能将网站的大部分PageRank值以某种方式导向其中的一个或少数网页,使得它(们)的排名大大提高,其效果当然要好于平均分配的结果。所以下边讨论的重点不在单个网页的权值,而是考虑整个网站或者说网站中的重要页面的PageRank值,这些页面可能是索引页、中心页或是专门为某些搜索术语优化的页面。

2. 1 考虑内部链接的影响

网站PageRank值即为网站内部所有页面PageRank值的和。一个网站的PageRank最大值等于它的页面数量。入站链接可以增加这个最大值,而出站链接则能减少之。网站内部链接组织不好,网站可能会达不到最大的PageRank值,但是却不可能超过该值。需要注意,虽然增加页面可以增加网站的PageRank值,但不是随便增加什么页面都能达到效果。那些完全相同或几乎相同的页面称为cookie2cutter, Google认为是垃圾信息并会引发相应的警报机制使得页面甚至是整个网站受到处罚。所以从根本上来说网页要有一定的质量。

下面分析一下网站内部链接如何影响PageRank值。在这里我们考虑的是一个相对独立的网站,入站链接和出站链接的影响暂不考虑在内。

假设一个包含三个网页的网站,没有外部链接(图1) 。在( a) , ( b) , ( c)的情况下,我们为每个网页分配初值1,阻尼系数保持与Google一致(0. 85) ,经过迭代收敛后,得到三种情况的PageRank值如下:

  • ( a ) : PageRank A = 0. 15, PageRank B = 0. 15, PageRank C = 0. 15;
  • ( b ) : PageRank A = 0. 15, PageRank B = 0. 277 5, PageRank C = 0. 15;
  • ( c ) : PageRank A = 1, PageRank B = 1, PageRank C = 1;

网站( a ) 的PageRank 值为0. 45, 严重浪费了潜在的PageRank值。( b)的情况稍好一些,总值0. 577 5比上一个例子有所增加,但仍然只是最大值的一小部分(对于该结构存在的摇摆页情况,在这里不作讨论) 。在( c)的链接结构下,网站达到了PageRank最大值,也可以通过环形结果获得: A到B,B到C, C再到A。同样的情况也可以将页面增加到3个以上。

可见链接的不好,完全可能浪费潜在的PageRank值。根据试验的规律,得出针对内部链接结构的第一个优化策略:一般来说,环形链接或者任意两个页面都有相互链接时能达到网站PageRank大值。

假设把A作为索引页,有( a) , ( b)两种链接结构,省略计算过程后迭代结果如下:

( a) : Page A = 1. 459 459, Page B = 0. 770 270 3, Page C =0. 770 270 3;

( b) : Page A = 1. 298 245, Page B = 0. 999 999 9, Page C =0. 701 754 3;

两种结构的总值仍然是3 (最大值) ,所以没有浪费。但( b)的情况下,A明显损失了PageRank,页面C也损失了一部分PageRank,因为A、B分享方式替代了A独享,A通过A→C链接反馈回C的值也就减小。

所以得出第二条优化策略: 为了获得索引页的最大PageRank值,其他页面应该尽可能减少相互链接。如果某个页面链接到的页面有回路链接,那么在这个页面上增加一个新的出链接会导致间接损失一部分的PageRank值。如果没有这样的回路,则不会减少PageRank值。这在内部链接中并不十分重要,但对发生到网站外的链接时就不一样了。可见,通过组织内部链接,可以将网站的PageRank值导向某个选定的页面。内部链接可以根据网站的PageRank需要来组织,但必须是Google认可的页面。

2. 2 入站链接和出站链接

入站链接(由网站外部进入的链接) 是增加网站PageRank值的方式之一。入站链接来自何处并不重要,Google认为只要网站管理员没有对链入网站的其他网站产生控制,就不会因为这种链接做出处罚。

链接页的PageRank值很重要,但同时出链接的数量也相当关键。例如:如果是一个PageRank值为2的网页的唯一出链接,将得到0. 15 + 0. 85 (2 /1) = 1. 85的值;而一个100个出链接的PageRank 8 网页,得到的是0. 15 + 0. 85 (7 /100) =0. 209 5。很明显, PR2链接更有效。一旦有PageRank值注入到网站中,计算将需要重新进行。某些页面的值增加,某些保持不变,这依赖于内部链接结构,但肯定不会有页面会损失PageRank值。

入站链接指向你试图导向的重要页面更有好处,如果PageRank注入到其他页,则会因为内部链接分散到网站中。索引页也会得到提升,但不如直接链接提升得多。直接得到入站链接的页面得到的值最大。

第三条优化策略:将网站索引页作为引入入站链接的最佳目标。

出站链接会导致网站PageRank值的消耗。为了抵消这种消耗,需要确保链接是互给的。互惠链接可能得到也可能损失PageRank值,所以交换链接时需要特别小心。

当PageRank值随着指向另一个网站的链接而引出时,内部链接的所有页面都将受到影响。虽然具体的PageRank值变化情况依赖于链接结构,但一般来说给出链接的网页往往是损失PageRank值最大的,因此得出第四条优化策略:出站链接放在PageRank较低的页面,造成的PageRank损失较小。

任何一个网站都几乎不可能没有出站链接,但不巧的是,所有的“正常”链接都会泄漏PageRank值。但还有些“特别”的链接方式不用泄漏。PageRank泄漏与否依赖于Google能否识别出链接,这样可以使用Google不能识别或是不考虑的链接,包括表单处理(form action)和包含JavaScript代码的链接。

表单的action属性不一定是处理表单脚本的url,它可以指向任何网站的任何一个页面。例子:< form name = “myform” action =”http: / / cs. scu. edu. cn / somepage. html” >< a href = ” javascrip t: document. myform. submit () ” >四川大学计算机学院< / a >

此外, action 属性甚至可以不必位于form 表单而在JavaScrip t代码中,而JavaScrip t代码可以位于存储路径的js目录下,而该目录一般Google的sp ider程序都不访问。

3 总结及PageRank改进

PageRank值由网络链接结构决定,与具体的检索内容无关,因而检索期间消耗很小,优于早期的H ITS算法。在不考虑网页内容具体需要的情况下,提出的优化策略有利于提高网站在基于PageRank算法排名的搜索引擎搜索结果中的排名。这种效应也许短时间内尚不明显,但随着页面的增加和网站间链接的逐渐增多,最终的效果还是可观的。

同时,由于PageRank算法的检索无关性,也可能导致一些不利的结果,例如对一些词汇在特定的上下文中有特定的含义,或是一些专业词汇,仅仅依靠PageRank排名的结果可能不太令人满意,比如同样是查找“结构”这个词,在建筑学的上下文中,和芯片制造的上下文中,用户希望得到的检索结果必然不尽相同。但由于PageRank是网页的固定属性,可能就达不到期望的效果了。如果将整个互联网看成一个维度,那么PageRank则是该维度上的一个矢量,针对以上的缺陷,可以考虑建立这类矢量的一个矢量集。换句话说,可以针对某些指定的主题词计算出多个PageRank值,然后根据检索内容匹配相应主题词的网页PageRank值[ 4 ]。当然,在结果排序时用到的PageRank值仍然是唯一的。这种改进在检索期间的消耗上有所增加,但在结果排序上却有大大提高。

参考文献:
[1 ] BR IN S, PAGE L. The anatomy of a large2scale hypertextual websearch engine[A ]. Proceedings of the Seventh International World WideWeb Conference[C ], 1998.
[2 ] BABA H, 馬場肇. Google の秘密- PageRank 底解説[ EB /OL ]. http: / /www. kusastro. kyoto2u. ac. jp /~ baba /wais/pagerank. html, 2003.
[3 ] JEH G, W IDOM J. Scaling personalized web search [R ]. StanfordUniversity, 2002.
[4 ] HAVEL IWALA TH. Top ic2Sensitive PageRank[A ]. Proceedings ofthe Eleventh InternationalWorldWideWeb Conference[C ], 2002.

本文作者:张 巍,李志蜀 (四川大学计算机学院,四川成都610065)

码字很辛苦,转载请注明来自标点符《基于PageRank算法的搜索引擎优化策略》

评论

  1. tiger #1

    不错,这个很有意思,但一般用软件分析日志

    回复
    2011-06-20
  2. tiger #2

    这个有点长,之后慢慢啃

    回复
    2011-06-20