搜索引擎信息覆盖率评测模型研究报告

1、-PAGE . z搜索引擎的信息覆盖率评测模型研究孟涛 李晓明 闫宏飞大学计算机科学技术系 ，100871摘 要本文从有向图构造出发，总结分析了搜索引擎搜集子系统网页搜集不完全性的假设干因素，指出信息覆盖率这一概念的研究意义，由此提出了三类比拟重要的信息覆盖率概念。在对信息覆盖率建立量化研究模型之后，本文以北大天网WebInfomall平台为考察对象，以不同的方式对中国Web进展取样，用PageRank和HITS这两类典型的权值算法计算出其中的重要网页作为样本，从量和质的角度上考察webinfomall的信息覆盖率，得到合理的数量覆盖率和质量覆盖率实验数据，从而验证了WebInfomall信息

2、覆盖率结论的合理性和信息覆盖率评测模型的可靠性。关键词搜索引擎，信息覆盖率，取样，权值计算，验证，数量覆盖率，质量覆盖率研究背景World Wide Web自1989年诞生并于次年开场运行以来,在迄今为止的十多年里开展迅猛，已逐渐成为人类社会信息资源中的一个重要组成局部。它以超文本和超媒体为核心技术，将文本、图形、图像、音频和视频等信息有机结合起来，给人们以丰富的信息表示空间。随着Internet技术和应用的不断开展，社会的信息化进程不断加快，越来越多的社会信息资源开场选择Web作为其载体。当前，上大约有8,745,000个，约2,500,000,000网页，包含了至少19TB以上的数据，而且

3、这些网页正以每天净增7,500,000的速度膨胀1 2。而在中国，根据中国互联网络中心NIC于2002年1月进展的互联网统计报告3，下注册的域名数为127,319个，共有277,100个Web站点。到2002年为止，中国境内的Web站点共有53,432,598个网页，主要分布在约49,146个中4。面对浩瀚的互联网络资源，人们假设不借助其他工具很难快速的查找到自己所需要的信息，这带来了搜索引擎的诞生。从1994年诞生的第一代搜索引擎Lycos和InfoSeek等开场，开展到当前流行的Google、Altavista等系统，它们已逐渐成为人们进展网际冲浪的重要工具之一。根据弗吉尼亚理工大学GVU

4、中心的调查报告5 ，全世界有84.8%的用户通过搜索引擎获得自己所需网页，足见搜索引擎功用之一斑。我们将每一条独立的信息称为一个网页，它有一个唯一的资源定位地址称为URL(Uniform Resource Location)。搜索引擎便是利用URL之间的连接关系，搜集其对应的网页信息，建立索引，供用户查询。因此，搜索引擎搜集的网页集合便是用户所能得到查询结果的最大范围；这个范围越接近，搜索引擎越优秀。事实上，没有任何一个搜索引擎能搜集完的所有网页。著名的搜索引擎Google系统和WiseNut系统，搜集到并提供应用户查询的网页数量分别是2,073,418,204个6和1,571,413,207

5、7个，最多不过静态网页总数的80%。而根据Greg R.Notes在200.年3月发表的搜索引擎统计数据8.，这两个系统的网页数据量是最大的。网络上的信息数量巨大而且种类繁多，任何一个实际运行的搜集系统都不可能将其全部搜尽。优秀的搜索引擎总会搜集尽量多的网页，更好的满足用户的查询要求。考察搜索引擎对信息资源的搜集覆盖程度，可作为不断改良搜集系统的根据，对评价搜索引擎的性能好坏具有积极的作用。另一方面，随着社会信息化程度的不断提高，将是该阶段人类社会信息资源在网络上的投影，记录着人类社会的历史开展进程。基于搜索引擎技术开发的网络信息博物馆正以此为目的，力图通过搜索引擎的网页搜集系统不断搜集上的所

6、有网页，假设干年后能够同时在时间和空间上展示的每一个角落。因此，研究搜索引擎的信息覆盖率对验证网络信息博物馆网页资源的有效性也有着十分重大的意义。本文的研究工作基于上述目的，针对大学计算机系网络与分布式系统实验室开发的搜索引擎8及以此为根底开发的网上信息博物馆WebInfomall9，采取多种方法从多个角度计算其信息覆盖率，证明了该网页搜集系统获得的中国网络信息资源是根本有效的。模型概述网页搜集的不完全性如果把中的每一个网页看作一个顶点，则这个顶点以URL作为它的唯一标记；又由于网页中存在其它网页的URL，可以把这种网页间的看作连接顶点的边，则整个构成了一张有向图，如图1示。相应的，每一个顶点

7、的入度和出度对应着链向该网页的网页数量和该网页链向其他网页的数量。显然，这是一张不完全图，因为里面存在很多入度或出度为0的顶点。当前的网页搜集系统都是基于对这种构造的理解，依据网页之间的关系，从*一个种子URL开场，不断的从新搜到的网页中提取出URL，从而到达其它的网页。搜集过程中，通常需要对网页重要性作初步的判断，优先搜集相对有价值的网页。在这种搜集机制里面，存在着以下问题，导致无法遍历所有的网页。局部网页的入度为0，即从任何一个网页开场，都不存在到它的路径，这类网页的数量约占全体网页数量的10%10 。选择的种子URL集合中，任何一个网页都不存在到该网页的路径。中的有向图构造中，只有约21

8、.3%的顶点能被选取作为起始点去遍历剩下的约90%的顶点10。由于在网页搜集的过程中出现了优先排序，搜集系统资源本身的限制磁盘容量和时间限量导致局部网页直到搜集过程中止都没有被搜集，出现Starve的情况11。本身处于不断的膨胀过程之中，大量新出现的网页来不及搜集。搜集系统自身一般都有搜集周期，而*些网页如实时新闻网页的更新频率远大于搜集频率。从广义的角度而言，但凡上的信息都应该被搜集，而现在的搜索引擎一般只搜集了局部格式的网页信息。当前搜集的一般都是静态网页中类似于HTML文档的信息资源，没有考虑到包括动态网页在内的巨量深层网络文档。据估计，当前中的所有网页包括深层网页约有5500亿之多，搜

9、索引擎所覆盖的不到其百分之一12！因此，可以肯定任何一个实际运行的网页搜集系统都不可能将当前中的所有网页全部抓尽。这种搜集性能越优异，意味着它所获得网页集合在数量和质量上越接近于实际的，网页之间的关系也越逼近实际的有向图构造。搜索引擎的信息覆盖率正是对这种接近程度的衡量，它表达了一个网页搜集系统所获得的网页集合及关系所占实际的比例。几类重要的覆盖率广义的信息资源，应该定义为互联网上的一切信息，即所有存在于上的文档。这些文档有些能通过浏览器浏览，有些则不能；有些存在于的数据库中，经过动态的请求方能生成，有些则是静态存在的且被其它网页到。搜索引擎当前所能搜集的绝大多数就是这种静态的网页，且在处理过

10、程中进一步过滤掉了*些不可浏览的局部如可执行文件等。在这里，我们所研究的搜集系统覆盖目标是上的所有静态网页，它们通常可通过浏览器显示内容，且其URL一般静态存在于其它网页中。我们可以从多个角度来考虑搜索引擎对信息资源的覆盖程度。搜集系统应该力图遍历的所有网页，在数量这一角度上到达完全覆盖的程度。这提供一个衡量搜集系统覆盖信息能力的全局标准。例如当前上的网页估计约为2,500,000,000个2 ，Google系统的网页搜集数量是2,073,418,204个6 ，因此可以估计其数量覆盖率为百分之八十左右。如果系统的数量覆盖率足够高，我们就可以认为它根本上覆盖了上的所有信息资源。高的数量覆盖率应该

11、是任何一个搜集系统及以此为根底的网上信息博物馆的首要目标。网上信息资源极为丰富，但也存在不少冗余，大量的广告页面和内容重复页面便是此例。即使去除这些冗余后，用户感兴趣的网页通常也只是数以十亿计的数量中的极少数。因此，考虑搜集系统在质量上对网页的覆盖程度显得尤为重要。这一指标可以告诉我们，对那些用户会感兴趣的重要的网页，系统覆盖了其中的百分之几。从更深的层次来说，如果搜集系统覆盖了绝大多数的重要网页，它也就覆盖了当前社会信息在每一个重要主题上映射到上的局部，成为它的一个有效特征子集。类似于WebInfomall的系统如果将这些重要网页全部记录下来，以后就能通过历史网页回放来重现人类社会信息资源在

12、时间和空间两维上的每一个角落。从信息的表现形式来看，搜集系统当前存储的信息中相当一局部日后将是不可见的。这一方面是由于存储系统的资源所限，未能搜集类似于图片影音之类的大文档；另一方面是因为搜集技术的不成熟，无法获得类似于JavaScript、Applet等格式的网页。因此，考察搜集系统对可视网上信息资源的覆盖率，也有着积极的意义。它可以告诉我们当前所搜集到的网页当中，多大比例的一局部能够在假设干年后通过浏览器重新浏览。在本文的研究中，将对前面的两种进展详细的讨论和量化分析。信息覆盖率评测模型我们定义搜集系统的信息覆盖率为它所收集的网页集合在中所占的比例。考虑到的构造，将其视为一张有向图G=V

13、，E，则搜集系统所获得的网页集合是G的强连通子图.不一定是强连通图G=V，E，每一个顶点都有唯一的标记URL。则信息覆盖率的表达式为：C=需要加一句对公式的解释。G的相关属性在搜集过程中已得到，但是因为搜索引擎搜集网页的不完全性，G的相关属性却只能去估计。为了得到准确的信息覆盖率数据，我们采取对取样的方法，即采取随机的方式从中获得一张子图=V，E，考察V中的顶点落在V中所占V的比例C作为C的近似值。如果足够大或是随机性足够好,则C非常接近于C。此时的C即搜集系统的数量覆盖率。我们可以用类似的思想去计算搜集系统的质量覆盖率。考虑中的所有重要网页构成的连通子图G，我们可以用随机的方法获得*些重要网

14、页组成的集合S作为样本，来考察搜集系统覆盖S中的子集S所占样本容量的比例，作为近似的质量覆盖率C,因此质量覆盖率的表达式为：为什么用双竖线.C=因此，我们需要通过对随机取样获得网页样本；需要采取*些方法得到随机的重要网页集合，这通常要利用网页之间的关系来对网页进展权值估算；在得到网页样本之后，再检查搜集系统的网页覆盖其中的比例，在检查过程中，必须对网页过滤，扔掉无法连接到的网页。总体的工作流程大致如以下图所示：数量覆盖率我们可以从不同的角度来对来进展采样。如果不考虑顶点之间的关系，仅从顶点的标记URL所对应的IP地址出发，可以采取随机产生IP的方法来获得一个网页集合，从而得到样本，这种考虑基于

15、全局的视点；如果考虑到顶点之间的关系，则可以模仿搜索引擎搜集系统的工作方式，采取绝对广度优先的方法，从*一个顶点种子URL出发，逐渐扩展遍历，得到一个网页集合作为样本，这是一种从局部来进展取样的方法。随机IP法在Edward T.ONeil和和 Patrick D.M的工作13中，他们提出了通过随机产生IP来对进展取样的方法。首先获得上已经分配使用的所有IP地址，假设共有M个。可以利用IP的分段将它们一一映射到0到M-1之间的*个整数作为唯一标记。这样，我们可以利用随机算法产生小于M的整数，得到一个IP标记集合，再逆映射回到IP地址，即得到一组随机IP样本。如果搜集系统以域名标志地址，还需要将

16、其转换为域名。这种取样原理如图3所示：3.1.1取样我们在研究工作中获得了中国国内已分配的所有IP地址分段4322个，例如至55为其中一个分段，被分配给大学使用。如果统一用点分十进制表示所有网络地址，则所有的IP分段可以表示如下A1.B1.C1.D1A2.B2.C2.D2An.Bn.DnAn.Bn.DnAt.Bt.Ct.Dt中的函数值为：F(a.b.c.d)=+a-At*+(b-Bt)*+ (c-Ct)*+ (d-Dt)于是我们将每一个IP都对应到一个整数，便可以用随机算法在其中选取假设干，逆映射转变为IP地址，便得到一个IP地址集合。去掉此集合

17、中不提供效劳包括与网络无连接的元素，就得到了一个样本。由于大约93.6%14的通过80端口提供 效劳，我们可以顺次扫描这些网络地址上的80端口。得到的存在 效劳的IP地址集合经反向域名解析便可得到样本URL集合。通过对中国国内的IP进展随机取样并进展扫描，我们得到了如下结果：编号12345678910随机IP数100K200K300K400K500K600K700K800K900K1M存在 数95172252336418478570652717817表格中间线太粗，而且第三条应该是不可见的在上面的统计中，我们选取了多组不同数量的随机IP，得到的存在 效劳的IP地址数量与随机数大致成比例，说明选

18、出的IP地址具有很好的随机性。3.1.2验证由于搜集系统一般以包含域名的URL来记录网页，我们要检验这些网页是否已被覆盖，应该将其转化为相应的域名。由于网络中DNS效劳器提供的IP反向解析功能有限，而搜集系统在搜集过程中通常记录了搜到的网页域名与IP地址的对应关系，我们可以由此直接检验被覆盖的IP地址数量。我们的目的是对所有的IP地址进展建模，接下来的问题应该是该用多少数据才能满足要求使得样本有效。尽管我们就这一问题无法给出准确的数量，但是可以从少量的数据开场，然后逐步增加数据量。如果我们这种通过随机产生IP对取样的方法是正确的，在原先样本的根底上逐步增加数据集将不会影响信息覆盖率的结果。因此

19、，我们可以对样本容量从小到大的各组数据统计得到的覆盖率进展分析，看是否满足以上条件。下表是在各组随机IP地址样本中，被搜集系统覆盖的IP地址所占比例。编号12345678910存在 数95172252336418478570652717817覆盖IP数47913162128364347可以通过最小二乘法对结果进展线性拟合，得到以下的二维图像。其中，横轴代表随机IP地址样本容量，纵轴代表搜集系统覆盖样本的数量，直线的斜率则表示信息覆盖率。从图中可知，自变量和因变量之间存在很好的一次函数关系，覆盖率根本保持在5.72%左右。由此可以推断，当样本扩展到所有的IP地址时，WebInfomall的覆盖率

20、将会保持在这个数量左右。3.1.3模型修正和结果分析随机IP法产生了大量的随机IP地址，用这种方法可以很好的对上的所有提供 效劳的Web效劳器进展取样；随着样本容量的增加，样本的准确性也会增加。但是，这种采样方法存在一些缺乏，导致信息覆盖率具有较大偏差。首先，IP地址标记的是Web效劳器的网络地址，在大多数情况下，它等同于该效劳器上运行的首页。这使得我们最终得到的网页集合实际上是上首页的一个样本。使用IP地址将使得我们对所有的一视*，忽略了的大小之别。一个只有三五个网页的个人小如和一个有着上千网页的大商业如/，为.sina./的IP地址是不等同的，然而这种区别在随机IP地址取样中无法表达。另外

21、，大量存在 效劳的效劳器并非是实际意义上的。大多数Windows系列操作系统自带的IIS效劳器软件，Linu*系统自带安装的Apache软件，如此众多，都会在缺省条件下提供Web效劳，而这些首页是没有实际意义的测试网页。类似的，也有大量的在*个IP地址短暂出现的网页例如临时通过 效劳共享文件等等。在上述随机IP取样方法中，这些根本无效的网页都被简单的等同于重要首页参加了样本之中。因此，我们有必要对此模型作出修正。既要利用随机IP方法具有的优异的随机性和全局性，又要保证通过随机IP地址获得的网页的有效性。解决方法是利用网页之间的关系，不再将各个网页看作独立的点，通过发现网页中的URL而进展适当扩

22、展。我们在研究中将得到的所有随机IP地址视为根本集合R ，通过 1.0协议取得这些IP地址上的网页内容，提取出其中的，参加R，作为网页样本，如以下图所示：为了将无效网页的影响降至最低，还可以对作多级扩展。经过这种处理后，上述第一种情况可以得到修正，因为大的首页通常存在较大的出度；第二种情况中默认网页链出的网页一般指向该软件生产厂家的首页，页面一样且数量少，且因其通常在国外故可在研究WebInfomall时过滤掉。我们从上述的随机样本中抽取了5组，经过扩展以后的网页样本数量以及覆盖数量如下：编号135710存在 数95252418570817扩展样本容量10842584385954848094覆

23、盖URL数17459684112041899在验证的过程中，我们将用IP地址表示的URL转化成域名URL，以便搜集系统的验证。这种转换经过了两级反向解析，第一步是通过网上DNS效劳器的解析，第二步是通过搜集系统保存的域名与IP对应数据。对得到的结果作线性拟合，得到的图几没有标如下，从拟合结果可得到信息覆盖率约为23.5%。可见，在对模型作修正之后，覆盖率有很大的增幅；如果考虑到域名与IP之间的动态关系即大量域名的IP是可变的，DNS系统每隔几分钟更新一次，我们去除掉样本中以IP表示的URL，数量覆盖率数据将还会有小幅度的提高，这才是真正的数量覆盖率大小。通过随机IP法产生的网页样本很好的考察了

24、搜集系统对有向图*些入度为0或是从出发顶点无法到达顶点的覆盖情况。这启示我们在搜集网页过程中，选取适当数量的以随机IP法产生的URL作为起始顶点集合的一局部，能提高搜集系统的数量信息覆盖率和WebInfomall中网页信息的有效性。广度优先法随机IP法虽然具有较好的随机性和全局性，但在使用过程中发现许多有待改良之处；为了使对的取样在逻辑构造上与实际情况更加接近，考虑到对随机IP法作修正时对逻辑关系的利用，我们提出了绝对广度优先搜集取样的方法。这种方法实现的实际就是一个最原始的搜集系统的工作过程，只是在搜集过程中按照绝对广度优先的方式一级级的扩展开去。这种取样是从局部的角度来进展的，原理如以下图

25、所示。3.2.1取样我们选取了五个URL作为起始点，采取上述绝对广度优先搜集网页的方法分别获得五组网页样本，样本容量从几万到数十万不等。算法如下：1选取*个网页S作为起始URL；2创立队列Q存储未搜集的网页，S入队列；创立构造数组A存储已经搜集过的网页，按照URL字符串排序；3取得队列头元素，通过 1.0协议获取H的源文件，提取出其中包含的的全部URL，并记录关系；4在A中用二分法寻找3中得到的URL是否已被搜集，如果没有搜集，则使其进入队列Q；5判断A中的网页数量是否已到达要求，假设没有继续3。得到的结果列表如下：样本编组12345种子URL..sina.

26、扩展URL数668912116291543147238661740783.2.2验证和分析得到网页样本之后，我们可以在WebInfomall的网页数据库中验证被覆盖的比例。为了快速的检验数据，到达磁盘性能的极限，我们启动了数百个进程从URL列表中读取并通过Hash算法从库中查找。得到的覆盖率数据如下表所示。对于这组离散的覆盖率值，我们计算均值和方差分别为41.6%和0.0230，前者即为通过绝对广度优先法得到的数量覆盖率。样本编组12345扩展URL数66891211629154314723866174078覆盖数量26732875626717827306674370数量覆盖率40.0%41.

27、4%43.5%37.7%42.7%对于使用这种采样方法得到的数量覆盖率41.6%，较之采用随机IP法具有较高的覆盖率值是可以理解的。因为这两批数据是从两个不同的方面说明搜集系统的信息覆盖情况：随机IP法着眼于全局，而绝对广度优先法着眼于局部，更类似于搜索引擎的搜集过程。通常搜集系统是在中的最*通子图内遍历，绝对广度优先法恰好反映了搜集系统对这一最*通子图的覆盖比例。由于这一最*通子图占据了中90%10左右的网页，而且我们选取的起始URL均落在这一子图之内，故绝对广度优先法得到的结论应该修正为乘以90%这一参数才能在全局角度上反映搜集系统的覆盖率，因此准确的数量覆盖率应该是37.4%。当样本容量

28、越大,覆盖率就应该约逼近此值,这从我们采用的大容量样本(第4组)结果中已经得到了验证。随机IP法反映的是搜集系统对中所有点的覆盖情况，因此这种采样更容易采集到入度为0或由于其他原因导致搜集系统无法遍历到的网页称为不可到达网页。由于不可到达网页中大量的点是孤立点，在没有很好的区分这些IP地址上所存在的网页数据量的情况下，这种样本需要经过多级扩展才能全面的反映真实的。也就是说，如果对初始URL不断作扩展，最后的数据会不断接近37.4%，这在我们作第一级扩展之后已经有了好的反映。我们可以预测到，如果将两种采样方法的优点结合起来，通过随机IP法产生URL集合作为绝对广度优先法取样的种子集合再进展扩展，

29、在样本容量足够大之后，最后的数量覆盖率数据应该与通过文献10 的工作做的估计相符，在37.4%附近。质量覆盖率考察搜集系统在质量上对的信息覆盖率，需要通过有效的网页重要性评测方法找到一组重要网页样本。尽管通常可以通过用户评选提交的方式得到他们在浏览网页过程中发现的重要网页集合作为样本，但在本文研究中，为了保证样本的随机性和客观性，我们采用两类基于对构造的分析而对中重要网页进展取样的有效方法。这些方法的根本思想都是找到一组具有较强关系的网页初始取样，通过基于分析的网页权值算法，求出其中所有网页的相对重要性值，从而可以对网页进展排序取出前假设干位作为重要网页的样本。这些经典的权值算法包括斯坦福大学

30、开发Google系统提出的PageRank算法15和IBM研究院开发Clever系统提出的HITS算法16 Hyperlink-Induced Topic Search，它们都是基于对有向图构造的理解提出的。网页重要性评测方法上的信息资源数量如此之大，无论是搜集系统本身还是承受返回结果的查询用户，都要求有好的方法对网页集合按照重要性进展排序，因为系统搜集的和用户关心的一般都只是其中的*一子集。准确的区分出重要的网页加以优先搜集，准确的计算出重要的网页返回给用户优先浏览，要做到这些，我们需要适宜的网页重要性评定方法。这里，网页的重要性用权值来衡量，权值越高表示网页越重要。我们可以从三个角度来分析

31、网页的权值，讨论它的相关因素。从网页本身的唯一属性URL出发来考虑：网页的权值可以从URL的属性中得到反映。一般而言，URL所在的域名越短，所在上相对于根目录的层次越浅，网页的权值越大。例如，大学的首页../ 一般被认为比大学计算机系首页 .. 的权值要高；而../page1.htm比../dir1/dir2/page2.htm 的权值显然也要高。这一原理可以在网页搜集过程中加以利用。从网页作为有向图的一个节点来考虑：网页的权值可以根据它的认可度来判断，由于网页间的通常代表着认可度的传递，我们可以统计网页的入度来评判其重要性。如果网

32、页A上存在网页B的URL，排除掉纯粹导航的因素，表示着网页A的作者存在对网页B的认可；而这种认可的增多则意味着网页B权值的上升。因此，入度越大，权值通常越高。从网页本身的内容出发来考虑：在搜索引擎搜集网页的过程中，通常都要保存网页的关键词或全文信息，以便建立索引。由于网页的重要性一般又对应着用户较高的关心程度，我们可以通过对用户递交给搜索引擎的查询词与网页的内容全文或关键词进展匹配，匹配程度越高意味着网页的权值越高。当然，这要求用户递交的查询是希望得到大量相关网页的宽主题查询。该情况在Kleinberg的论文18中有详细讨论。当前大多数搜索引擎所采用的网页权值计算方法正是上面提到的的PageR

33、ank算法和HITS算法两种，它们分别利用了上述中的后两种原理，而且对其间的网页关系作了更深层次的挖掘。PageRank算法15是一种利用网页间关系进展权值计算的典型方法，它是学术论文引用统计原理在上的推广，它统计每个网页被引用的次数，但每一次引用又因引用者权值的不同而不同；而HITS算法17 将网页的权值分为目录型权值和权威型权值分别进展计算，目录型权值高表示它链向很多权威型权值高的网页，而权威型权值高则表示它被很多目录型权值高的网页所到。目录型、权威型没有解释基于这两种权值算法，我们提出了下面的两类质量覆盖率确定方法。广度优先法4.2.1 取样PageRank算法根据网页间的关系来评判网页

34、的重要性，因此我们选取的初始网页集合必须和有着大致一样的构造，保证初始样本中每个网页的入度与实际互联网络相差不大，或者网页入度的相对大小变化不大。这样才能使得初始样本中的相对网页权值保持不变。我们可以利用绝对广度优先的方法，从初始URL开场向外遍历。随着初始样本容量的加大，每个样本网页的入度越来越接近于它在中的实际入度，样本网页的入度相对大小也越来越固定。我们以数量覆盖率研究中的广度优先法所获样本作为初始样本，它们的数量一般在数十万，已能根本保证其中相当数量网页的相对入度大小。用PageRank算法从中计算选出权值在前M位的网页集合作为样本。显然，M值越小，样本的有效性越容易得到保证。4.2.

35、2 PageRank算法假定网页A在里面被网页T1Tn所链到，C(A)表示从A链出去的网页数量即出度，则A的权值可以表示如下：PR(A)=17这种根本思想可以从以下图中表达：考虑到用户从Ti出发只有d0d1的可能性继续浏览网页 ，则相应的权值也只有相应比例的一局部传到 A ，因此 PR(A) 可以调整如下：PR(A)=1-d+ d15如果将所有的网页依次编号为1至 N ，他们的权值可以看作矢量W， 则W的转秩是这个秩吗.为PR1，PR2，PRN；考虑矩阵R ，如果存在从网页 i到网页 j的，则Ri,j=1/C(i) ，否则Ri,j=0；则所有的网页权值可以写成如下式子：W=d*WR + E其间

36、，E为常数向量。我们可以用迭代的方法求W的值 , 反复计算Wi+1=d*W(i)R + E ，直到W经判断已经收敛。事实上，这里的d已经成了一个收敛因子，尽管其实际意义为继续浏览网页的概率。没看懂4.2.3 算法实现和试验结果根据以上算法的需求，我们在网页搜集过程中记录了所有搜集到的网页间的关系，随着这个样本网页群体的增大，它在关系上将与越来越接近。出于对系统内存需求的考虑，所有的网页都被以整数统一编号而代替其URL字符串；网页之间的关系以二元组的形式存入关系数据库。当网页的数量足够大时，所有的网页及其属性无法一次全部存入内存中，故需要分块对矩阵进展迭代。具体的实现算法如下：创立数据构造存储网

37、页的整数ID、权值、出度、入度以及所有链入网页的ID，以此作为矢量W的单元；根据网页的平均入度2估计系统内存一次能存放的URL数量N，在我们的系统中，估计约为1MB ；从数据库中导出N个URL到内存，按ID排序；再将全部的关系导入，对于上述N中的每一个，填充进它的属性；对于N中的每一个，用二分法找到它的链入URL的数组下标，如果不在当前内存中则其权值以平均值计算，运用PageRank算法计算其权值；如果全部的URL都已经导入计算过，则对该矢量进展处理使得所有URL的权值之和为1；否则继续4；如果先后两次计算的W距离足够小，则对权值排序选取前M个输出到文件；否则继续3。将输出文件中的所有URL

38、整数ID转换为URL字符串。实验在Red Hat 7.2 系统上运行，主要硬件指标是1GB 内存 ，P = 3 * ROMAN III 550 CPU。我们以数量覆盖率计算中得到的五组样本作为初始样本，如果选择权值排序位于前面约5%左右的网页作为重要网页的标准，得到了如下结果：样本编组12345种子URL..sina.初始扩展数量66891211629154314723866174078PageRank取数352384978702334368408占前百分之几5.3%4.0%5.6%4.6%4.8%覆盖URL数154240324754177173456质量覆

39、盖率43.8%47.5%54.6%53.0%41.1%取前M个,为什么每组占前百分之几不一样。对五组样本检验得到的质量覆盖率计算均值和方差分别是48.0%和0.0579。为了保证所求样本网页的重要性有效，我们选取了上述样本中的第2组和第4组，改变判断重要性的标准，质量覆盖率随此而变化的情形如下表所示。对于第二组网页样本：重要网页个数18113434511768088497占前百分之几0.86%1.62%2.42%3.22%4.02%覆盖网页数11452068278833634032质量覆盖率63.2%60.2%54.5%49.4%47.5%以下图是随着重要性标准的放松，质量覆盖率的变化情况：对

40、于第四组网页样本：重要网页个数1732133436491986445079155占前百分之几2.39%4.62%6.80%8.90%10.9%覆盖网页数990317717247183112636780质量覆盖率57.2%53.0%50.2%48.3%46.5%以下图是随着重要性标准的放松，质量覆盖率的变化情况：从这两张图中可以看出，当重要标准很苛刻时重要网页样本容量很小，此时搜集系统的覆盖率很高；但随着重要标准的放松导致样本容量的增大，搜集系统的质量覆盖率会越来越低；当重要性的标准放至最低，即所有网页的地位平等时，质量覆盖率变为最小，为数量覆盖率值。这两张图中都显示，当重要标准降至约5%左右时

41、，曲线开场逐渐变得平缓，因此此点的覆盖率数据48.0%无疑最适合作为我们所测的的搜集系统质量覆盖率。主题查询法网页具有作为有向图构造中一个顶点的相关逻辑属性，它又可根据其内容本身而属于人类社会信息资源的*一主题类别。例如，网页可以根据其内容分为属于社会、人文或休闲娱乐等类别以及它们的子类的网页。基于这一点的考虑，我们的研究工作中采取了通过主题查询获得重要网页样本的方法。这类似于文献19 的工作中HITS算法选择的网页集合所采用的方法。由于上同一主题的网页之间具有较强的关系19，我们可用HITS算法对此网页集合进展权值计算，进展排序后得到前假设干网页作为在这一主题类别的重要网页样本。4.3.1

42、取样假设我们希望得到关于主题T的重要网页样本，我们一般会通过递交假设干与T相关的查询词Q提交给搜索引擎，它返回的网页集合为R。对于通常的搜索引擎，R的网页一般都具有和T较高的相关度，因为查询中通常使用字符串匹配，使得返回的网页中大多含有Q之类的字样。但是，也有大量的重要网页不适合这种情况，例如天网系统的主页并没有搜索引擎的字样供匹配。出于对这种特殊现象的考虑，需要对R以适当的扩展，参加R网页链出去的网页和链向R元素的网页得到初始样本S ，如图示：我们选择了八个主题的查询词递交给天网搜索引擎，在用以上的方式对返回结果进展扩展之后，得到了八组初始网页样本如下：样本编组12345678查询词大学考研

43、股票Linu*教程联想集团三个代表世界杯返回数量18021802180218021355180218021802扩展数量11667193791340311006265481549811608208234.3.2 HITS算法上图中的S正是我们用HITS算法进展权值计算的对象。对于S中的任意一个元素P ，设H(P)表示其目录型权值Hub Weight，A(P)表示其权威型权值Authority Weight，F1,F2,Fm是链到P的网页，T1,T2,Tn是从P链出的网页，则A(P)和H(P)可以从下面的式子计算：A(P)=H(P)=同PageRank算法类似，我们可以将所有的网页的目录型权值看

44、作矢量H，将所有网页的权威型权值看作矢量A，设样本中所有网页及关系构成的有向图的邻接矩阵为M，考虑到两个URL之间最多有一个使得假设存在网页i到网页j的则Mi,j=1否则Mi,j=0，则上面的式子可以写成：A=MHH=MA由此两式可得A= MMA，即实际上A是MM的特征向量；同理H是MM的特征向量，我们因此也可以用幂法或QR算法等来通过迭代来求得A和H的值。但考虑到系统内存对初始样本容量的限制，假设数量很大的时候需要分块对两个矩阵进展迭代。4.3.3 试验结果在我们的研究工作中，我们没有通过计算特征向量而采取了根据前一组公式直接进展迭代计算A和H值的方法，具体的实现算法如下：采集初始样本时将所

45、有的URL编号存入数据库，同时存入URL之间的关系；创立相关的数据构造存储每个URL的Hub和Auth权值及关系，从数据库中导出所有URL属性并填充到数据构造中；给予H和A*个初始值，分别计算Ai+1=MHi和H(i+1)=MA(i)，直至A(i+1)和A(i)的距离足够小为止；分别对Auth和Hub值进展冒泡排序，输出前假设干个URL到文件中。在确定重要网页的界限时，我们选取的是初始网页样本中权值排在前面约15%左右的局部，大致与搜索引擎响应查询词返回的网页数量相当。即搜索引擎就此主题返回*个重要网页，我们经过计算后也给出*个真正重要的网页，检查搜集系统覆盖其中的比例作为质量覆盖率。对于具有

46、较高Hub权值的重要网页，实验的数据如下：样本编组12345678查询词大学考研股票Linu*教程联想集团三个代表世界杯初始数量1166719379134031100626548154981160820823Hub取数16711701153210401508142818591961覆盖数量958956578312772514793651覆盖率57.3%56.2%37.7%30%51.2%36.0%42.7%33.2%八组样本所得的质量覆盖率分别为表几所示，它们的均值和方差分别为43.0%和0.106，前者即为搜集系统对Hub型重要网页的覆盖率。对于具有较高Auth权值的重要网页，实验的数据如下

47、：样本编组12345678查询词大学考研股票Linu*教程联想集团三个代表世界杯初始数量1166719379134031100626548154981160820823Auth取数1400157211249301197104715811985覆盖数量9439303853016926319271052覆盖率67.4%59.2%34.3%32.4%57.8%60.3%58.6%53.0%八组样本所得的质量覆盖率分别为，它们的均值为，表几所示方差为52.9%和0.1269，前者即为搜集系统对Auth型重要网页的质量覆盖率。4.3.3 修正与分析在上述的HITS算法中，我们将所有的地位视为平等，而事实

48、上并非如此，我们可以从它的导向词与查询词的匹配度的不同处着手，这在Soumen Chakrabarti和 Byron Dom的工作19中有论述。这里的导向词指的是该出现在网页源文件的地方前后约150个字符之内的信息，它们一般含有该网页内容或属性的说明。即，*个网页中两个url1和url2，如果url1的导向词中出现大学10次，而url2的导向词中未出现此字眼，在查询的主题是大学时，url1的地位要高于url2。我们称以此为根底的算法为扩展HITS算法。假定查询词是Q，存在网页A到B的，提取出网页A中B的导向词，设F(A,B)为Q在导向词中匹配的次数，则可以对HITS算法作如下修正：A(P)=H

49、(P)=我们用这种算法对上述的8组初始样本进展计算，然后分别选取Hub权值和Auth权值在前假设干位的重要网页作为重要网页样本，从Hub和Auth两个角度求得的搜集系统信息质量覆盖率均值分别为46.2%和50.3%。从实验数据可以看出，广度优先法和主题查询法所求得的质量覆盖率数据能够很好的符合，WebInfomall的搜集系统对普通的重要网页覆盖率在50%左右。如果对重要网页的标准提高一些，则质量覆盖率的数据还要更高。结论本文针对搜索引擎搜集子系统对的信息覆盖能力，创立了信息覆盖率的量化研究模型。在这个模型中，我们提出两套取样方法，采取了两类典型的网页权值算法，分别从量和质的角度上分析计算搜集

50、系统的信息覆盖率。运用这个模型，我们针对中国Web进展样本采集，从而对北大天网系统的WebInfomall平台所存储的中国国内网页数据的信息覆盖率进展评估。得到的数据显示，在数量上WebInfomall平台覆盖了中国国内网页总数的37%，而在质量上覆盖了重要网页总数的50%左右。这个数据也显示天网的覆盖率与国际上诸如Google的几个大搜索引擎系统相当，尤其是在数量覆盖率这一方面。对于同一类型的信息覆盖率，采用不同取样和权值计算方法所验证得到的数据能够很好的符合，证明了信息覆盖率模型的正确性以及所获得WebInfomall平台信息覆盖率的准确性。实验结果肯定了天网搜集系统的较强搜集能力，并对进一步改良这种搜集能力及相关WebInfomall平台的性能提供了重要的客观依据。本文缺乏之处在于对网页重要性的定性标准不够严密，对于PageRank算法，我们选取了权值位于前5%的网页作为重要网页；而对于HITS算法计算的查询所得扩展网页集合，我们选取重要的标准是和初始返回结果相等的量，约占权值排序后前面的10%。如文中所述，在实验中通过对其中两组样