社会环境下网页重要性的研究
息，用户必须从结果中进行筛选。这类搜索引擎的代表是： AltaVista 、Northern Light 、Excite 、Infos2 eek 、Inktomi 、FAST、Lycos 、Google ; 国内代表为：“天网”、 “百度”等。本文论述的Google 搜索引擎就是机器人搜索引擎，通过网络蜘蛛(Crawler) 搜集和发现网页排序所需要的信息。
目录式搜索引擎和机器人搜索引擎，各有优缺点，应用都很广泛。机器人搜索引擎的自动化程度比目录式搜索引擎高。网络信息量太大了，用计算机代替人去查找，可以节省大量的人力。
元搜索引擎：这类搜索引擎没有自己的数据，而是将用户的查询请求同时向多个搜索引擎递交，将返回的结果进行重复排除、重新排序等处理后，作为自己的结果返回给用户。服务方式为面向网页的全文检索。这类搜索引擎的优点是返回结果的信息量更大、更全，缺点是不能够充分使用搜索引擎的功能，用户需要做更多的筛选。这类搜索引擎的代表是WebCrawler 、InfoMarket 等 .
1.3 Google搜索引擎工作原理[3]
搜索引擎一般由网络爬行机器人crawler、知识库Repository、索引系统(包括索引器indexer，桶barrels ,文件索引等)、排序器Sorter和搜索器Searcher 5个部分组成。
Google PageRank一般一年更新四次(由crawler程序的效率及搜索引擎的规模决定)，所以刚上线的新网站不可能获得PR值。你的网站很可能在相当长的时间里面看不到PR值的变化，特别是一些新的网站。PR值暂时没有，这不是什么不好的事情，耐心等待就好了。Google PageRank每更新一次都是按照以下的步骤进行：
(1)Google使用高速的分布式爬行器(Crawler)系统中的漫游遍历器(Googlebot)定时地遍历网页，将遍历到的网页送到存储服务器(Store Server)中。
(2)存储服务器使用zlib格式压缩软件将这些网页进行无损压缩处理后存入数据Repository中。Repository获得了每个网页的完全Html代码后，对其压缩后的网页及URL进行分析，记录下网页长度、URL、URL长度和网页内容，并赋予每个网页一个文档号(docID)。
(3)索引器(Indexer)从Repository中读取数据，以后做以下四步工作：
(4)(a)将读取的数据解压缩后进行分析，它将网页中每个有意义的词进行统计后，转化为关键词(wordID)的若干索引项(Hits)，生成索引项列表，该列表包括关键词、关键词的位置、关键词的大小和大小写状态等。索引项列表被存入到数据桶(Barrels)中，并生成以文档号(docID)部分排序的顺排档索引。 索引项根据其重要程度分为两种：
当索引项中的关键词出现在URL、标题、锚文本(Anchor Text)和标签中时，表示该索引项比较重要，称为特殊索引项(Fancy Hits)；其余情况则称为普通索引项(Plain Hits)。 顺排档索引和Hit的存储结构如图1.1所示。
6
社会环境下网页重要性的研究
(b)索引器除了对网页中有意义的词进行分析外，还分析网页的所有超文本链接，将其Anchor Text、URL指向等关键信息存入到Anchor文档库中。
(c)索引器生成一个索引词表(Lexicon)，它包括两个部分：关键词的列表和指针列表，用于倒排档文档相连接(如图1.1所示)。
(d)索引器还将分析过的网页编排成一个与Repository相连接的文档索引(Document Index)，并记录下网页的URL和标题，以便可以准确查找出在Repository中存储的原网页内容。而且把没有分析的网页传给URL Server，以便在下一次工作流程中进行索引分析。
(5)URL分析器(URL Resolver)读取Anchor文档中的信息，然后做⑥中的工作。 (6)(a)将其锚文本(Anchor Text)所指向的URL转换成网页的docID；(b)将该docID与原网页的docID形成“链接对”，存入Link数据库中；(c)将Anchor Text指向的网页的docID与顺排档特殊索引项Anchor Hits相连接。
(7)数据库Link记录了网页的链接关系，用来计算网页的PageRank值。 (8)文档索引(Document Index)把没有进行索引分析的网页传递给URL Server，URL Server则向Crawler提供待遍历的URL，这样，这些未被索引的网页在下一次工作流程中将被索引分析。
(9)排序器(Sorter)对数据桶(Barrels)的顺排档索引重新进行排序，生成以关键词(wordID)为索引的倒排档索引。倒排档索引结构如图所示：
图1.1
(10)将生成的倒排档索引与先前由索引器产生的索引词表(Lexicon)相连接产生一个新的索引词表供搜索器(Searcher)使用。搜索器的功能是由网页服务器实现的，根据新产生的索引词表结合上述的文档索引(Document Index)和Link数据库计算的网页PageRank值来匹配检索。
在执行检索时，Google通常遵循以下步骤(以下所指的是单个检索词的情况)： (1)将检索词转化成相应的wordID；
7
社会环境下网页重要性的研究
(2)利用Lexicon，检索出包含该wordID的网页的docID；
(3)根据与Lexicon相连的倒排档索引，分析各网页中的相关索引项的情况，计算各网页和检索词的匹配程度，必要时调用顺排档索引；
(4)根据各网页的匹配程度，结合根据Link产生的相应网页的PageRank情况，对检索结果进行排序；
(5)调用Document Index中的docID及其相应的URL，将排序结果生成检索结果的最终列表，提供给检索用户。
这些过程都是离线进行的。当用户在线提交一个查询时，先从反向索引库中查找含有查询关键词的网页，返回一系列相关的网页的docID，由docID在存储PageRank的库中找到它们对应的PageRank值，然后将所有结果进行排序输出给用户。可以看出，整个过程中在线进行的只是查询，所有的计算都是离线进行的，因此搜索引擎能以较快的速度将结果返回给用户。另外，查询过程没有考虑用户提交的关键词和访问者的自身情况。基于链接的PageRank离线进行计算一次后，会在一段时间保持不变。据资料称，Google的PageRank计算周期大概是三个月。
8
社会环境下网页重要性的研究
2．传统Google PageRank算法分析
2.1 传统Google PageRank算法概述
我要做的工作是将PageRank的算法改进，所以先简述Google PageRank的情况方便下面的改进修改和对照。
超链分析技术主要是指利用网页间存在的各种超链指向, 对网页之间的引用关系进行分析，依据网页链入数的多少计算该网页的重要度权值，一般认为 ,如果A网页有超链指向B网页，相当于A网页投了B网页一票，即A认可B网页的重要性。深入理解超链分析算法，可以根据链接结构把整个网页文档集看作一个有向的拓扑图，其中每个网页都构成图中的一个结点，网页之间的链接就构成了结点间的有向边，按照这个思想，可以根据 每个结点的出度和入度来评价网页的作用。
其中有代表性的算法主要是 Larry Page等人设计的PageRank算法和 Kleinberg 创造的HITS算法。其中PageRank算法在实际使用中的效果要好于 HITS算法，这主要是由于以下原因: a. PageRank 算法可以一次性、脱机并且独立于查询地对网页进行预计算，以得到网页重要度的估计值，然后在具体的用户查询中，结合其他查询指标值再一齐对查询结果进行相关性排序，从而节省了系统查询时的运算开销；b. PageRank 算法是利用整个网页集合进行计算的，不像HITS算法易受到局部连接陷阱的影响而产生“主题漂移”,所以现在这种技术广泛地应用在许多信息检索系统和网络搜索引擎中，Google 搜索引擎的成功也表明了以超链分析为特征的网页相关度排序算法日益成熟。
但是 PageRank算法由于只考虑到网页间的超链关系并仅仅以此进行网页重要度的分析，所以不可避免地会产生很多问题，其中，比较明显的问题在于它在计算每个网页具体的重要度权值的时候，根本没有考虑到任何网页本身内容特征对权值的影响，如PageRank算法完全忽略了网页具有的不同主题，不同的主题应该具有不同的重要度权值，进一步说，在用户查询的时候，网页的重要程度值的大小与查询所表达的主题关系很大，其实，在HITS算法[5]中恰恰考虑了这种因素，所以它更易于表达与特定查询主题的相关度排序，有效地在PageRank算法中考虑查询主题对网页权重值的影响是一个有效改进此算法的重要方法，再如，PageRank算法也没有考虑网页的创建时间 ,并不对新旧网页进行有效的区分,相反 ,按照 PageRank 的既有算法甚至会产生旧网页比新网页具有较高重要度权值的可能性。这些都是Google PageRank存在的缺点，也是本文对PageRank算法进行改进的原因。
[4]
9
社会环境下网页重要性的研究
2.2 传统 PageRank算法回顾
PageRank技术：通过对由超过 50,000 万个变量和 20 亿个词汇组成的方程进行计算，PageRank 能够对网页的重要性做出客观的评价。PageRank 并不计算直接链接的数量，而是将从网页 A 指向网页 B 的链接解释为由网页 A 对网页 B 所投的一票。这样，PageRank 会根据网页 B 所收到的投票数量来评估该页的重要性。
虽然 PageRank 认为网页的链入超链数可以反应该网页的重要程度 ,但是现实中人们在设计网页的各种超链时往往并不严格，有很多网页的超链纯粹是为了诸如网页导航、商业推荐等目的而制作的，显然这类网页对于它所指向网页的重要度贡献程度并不高，但是，由于算法的复杂性，PageRank 没有过多考虑网页超链内容对网页重要度的影响,只是使用了两个相对简单的方法： 其一，如果一个网页的链出网页数太多，则它对每个链出网页重要度的认可能力相应降低；其二， 如果一个网页由于本身链入网页数很低造成它的重要度降低，则它对它的链出 网页重要度的影响也相应降低。综上而言，一个网页的重要性决定着同时也依赖于其他网页的重要性。
PageRank绝对是个很科学的小创意。说他科学，你会在我以后的文章中看到Google是如何将数学(具体来说多数是统计学)理论淋漓尽致地发挥在搜索技术之中。说他“小”，因为这些理论对于搞数学的人来说实在太微不足道了，甚至稍微有些科学高数知识的人都能理解。他所用到的统计学就是循环迭代计算收敛值的方法！[6]
2.2.1传统 PageRank算法代数表达形式
按照上面思路，Page给出了PageRank的简单定义[7]：
R?u??Cv?B?u??R?v??N?v? (2.1)
此处的u表示一个网页，R ( u) 表示网页u的PageRank值，B ( u)表示链接到网页u的网页集合，即网页u 的链入网页集合，N ( v ) 表示从网页 v 向外的链接数量，即网页v 的链出网页数，C为规范化因子，用于保证所有网页的PageRank总和为常量 (如为1)。
这就是算法的形式化描述，也可以用矩阵来描述此算法，设A为一个方阵，行和列对应网页集的网页。如果网页i有指向网页j的一个链接，则Aij=1/Ni，否则Aij=0。设V是对应网页集的一个向量，有V=cAV，V为A的特征根为c的特征向量。实际上只需要求出最大特征根的特征向量，就是网页集对应的最终PageRank值，这可以用迭代方法计算。
具体计算时，可以给每个网页一个初始的PageRank值，然后反复迭代运算，即 ：
R(i+1)(v)=
u?B?v??R(i)(u)/Nu (2.2)
此处的 v 代表所有的网页集合,每一个第i+1次的PageRank 值都是基于上次的PageRank值重新计算的。具体的迭代次数在实际运算中是有限的。
Lawrence Page和Sergey Brin在个别场合描述了PageRank最初的算法。这就是 PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn)) 式中：PR(A) :网页A页的PageRank值；
PR(Ti) :链接到A页的网页Ti的PageRank值；
10