【毕业学位论文】（Word原稿）搜索引擎的信息覆盖率评测模型研究

北京大学计算机科学技术系 网络与分布式系统实验室 孟涛学士论文 1 搜索引擎的信息覆盖率评测模型研究 摘 要 本文从 向图结构出发，总结分析了搜索引擎搜集子系统网页搜集不完全性的若干因素，指出信息覆盖率这一概念的研究意义，由此提出了三类比较重要的信息覆盖率概念。在对信息覆盖率建立量化研究模型之后，本文以北大天网 台为考察对象，以不同的方式对中国 行取样，用 两类典型的权值算法计算出其中的重要网页作为样本，从量和质的角度上考察 信息覆盖率，得到合理的数量覆盖率和质量覆盖率实验数据，从而验证 了 息覆盖率结论的合理性和信息覆盖率评测模型的可靠性。 关键词 搜索引擎，信息覆盖率，取样，权值计算，验证，数量覆盖率，质量覆盖率 1 研究背景 1989 年诞生并于次年开始运行以来 ,在迄今为止的十多年里发展迅猛，已逐渐成为人类社会信息资源中的一个重要组成部分。它以超文本和超媒体为核心技术，将文本、图形、图像、音频和视频等信息有机结合起来，给人们以丰富的信息表示空间。随着 术和应用的不断发展，社会的信息化进程不断加快，越来越多的社会信息 资源开始选择 为其载体。 当前， 大约有 8,745,000 个网站，约 2,500,000,000 网页，包含了至少 19且这些网页正以每天净增 7,500,000 的速度膨胀 1 2 。而在中国，根据中国互联网络中心（ 2002 年 1 月进行的互联网统计报告 3， 注册的域名数为 127,319 个，共有 277,100 个 点。到 2002 年为止，中国境内的 点共有 53,432,598 个网页，主要分布在约 49,146 个网站中 4。 面对浩瀚的互联网络资源，人们若 不借助其他工具很难快速的查找到自己所需要的信息，这带来了搜索引擎的诞生。从 1994 年诞生的第一代搜索引擎 展到当前流行的 系统，它们已逐渐成为人们进行网际冲浪的重要工具之一。根据弗吉尼亚理工大学 心的调查报告 5 ，全世界有 户通过搜索引擎获得自己所需网页，足见搜索引擎功用之一斑。 我们将每一条独立的 息称为一个网页，它有一个唯一的资源定位地址称为 搜索引擎便是利用 间的连接关系，搜集其对应的网页信息，建立索引，供用户查询。因此，搜索引擎搜集的网页集合便是用户所能得到查询结果的最大范围；这个范围越接近 索引擎越优秀。事实上，没有任何一个搜索引擎能搜集完 所有网页。著名的搜索引擎 统和 统，搜集到并提供给用户查询的网页数量分别是 2,073,418,204 个 6和 1,571,413,2077个，最多不过静态网页总数的 80%。而根据 200？年 3 月发表的搜索引擎统北京大学计算机科学技术系 网络与分布式系统实验室 孟涛学士论文 2 计数据 8？ ，这 两个系统的网页数据量是最大的。 网络上的信息数量巨大而且种类繁多，任何一个实际运行的搜集系统都不可能将其全部搜尽。优秀的搜索引擎总会搜集尽量多的网页，更好的满足用户的查询要求。考察搜索引擎对 息资源的搜集覆盖程度，可作为不断改进搜集系统的根据，对评价搜索引擎的性能好坏具有积极的作用。 另一方面，随着社会信息化程度的不断提高， 是该阶段人类社会信息资源在网络上的投影，记录着人类社会的历史发展进程。基于搜索引擎技术开发的网络信息博物馆正以此为目的，力图通过搜索引擎的网页搜集系统不断搜集 的所有 网页，若干年后能够同时在时间和空间上展示 每一个角落。因此，研究搜索引擎的信息覆盖率对验证网络信息博物馆网页资源的有效性也有着十分重大的意义。 本文的研究工作基于上述目的，针对北京大学计算机系网络与分布式系统实验室开发的 索引擎 8及以此为基础开发的网上信息博物馆 ，采取多种方法从多个角度计算其信息覆盖率，证明了该网页搜集系统获得的中国网络信息资源是基本有效的。 2 模型概述 页搜集的不完全性 如果把 的每一个网页看作一个顶点，则这个顶点以 为它的唯一标记； 又由于网页中存在其它网页的 以把这种网页间的链接看作连接顶点的边，则整个 成了一张有向图，如图 1 示。相应的，每一个顶点的入度和出度对应着链向该网页的网页数量和该网页链向其他网页的数量。显然， 这是一张不完全图，因为里面存在很多入度或出度为 0 的顶点。 当前的网页搜集系统都是基于对这种 接结构的理解， 依据网页之间的链接关系，从某一个种子 始，不断的从新搜到的网页中提取出 而到达其它的网页。搜集过程中，通常需要对网页重要性作初步的判断，优先搜集相对有价值的网页。在这种搜集机制里 面，存在着下列问题，导致无法遍历所有的网页。 部分网页的入度为 0，即从任何一个网页开始，都不存在到它的路径，这类网页的数量约占全体网页数量的 10%10 。 北京大学计算机科学技术系 网络与分布式系统实验室 孟涛学士论文 3 选择的种子 合中，任何一个网页都不存在到该网页的路径。 的有向图结构中，只有约 顶点能被选取作为起始点去遍历剩下的约 90%的顶点 10。 由于在网页搜集的过程中出现了优先排序，搜集系统资源本身的限制（磁盘容量和时间限量）导致部分网页直到搜集过程中止都没有被搜集，出现 情况 11。 身处于不断的膨胀过程之中 ，大量新出现的网页来不及搜集。搜集系统自身一般都有搜集周期，而某些网页（如实时新闻网页）的更新频率远大于搜集频率。 从广义的角度而言，凡是 的信息都应该被搜集，而现在的搜索引擎一般只搜集了部分格式的网页信息。当前搜集的一般都是静态网页中类似于档的信息资源，没有考虑到包括动态网页在内的巨量深层网络文档。据估计，当前 的所有网页（包括深层网页）约有 5500 亿之多，搜索引擎所覆盖的不到其百分之一 12！ 因此，可以肯定任何一个实际运行的网页搜集系统都不可能将当前 的所有网页全部抓尽。 这种搜集性能越优异，意味着它所获得网页集合在数量和质量上越接近于实际的 页之间的链接关系也越逼近实际的 向图结构。搜索引擎的信息覆盖率正是对这种接近程度的衡量，它体现了一个网页搜集系统所获得的网页集合及链接关系所占实际 比例。 类重要的覆盖率 广义的信息资源，应该定义为互联网上的一切信息，即所有存在于 的文档。这些文档有些能通过浏览器浏览，有些则不能；有些存在于网站的数据库中，经过动态的请求方能生成，有些则是静态存在的且被其它网页链接到。搜索引擎当前所能搜集的绝大多数就是这种静态 的网页，且在处理过程中进一步过滤掉了某些不可浏览的部分如可执行文件等。在这里，我们所研究的搜集系统覆盖目标是 的所有静态网页，它们通常可通过浏览器显示内容，且其 般静态存在于其它网页中。我们可以从多个角度来考虑搜索引擎对 息资源的覆盖程度。 搜集系统应该力图遍历 所有网页，在数量这一角度上达到完全覆盖的程度。这提供一个衡量搜集系统覆盖 息能力的全局标准。例如当前 的网页估计约为 2,500,000,000 个 2 ， 统的网页搜集数量是 2,073,418,204 个 6 ，因此可以估计其数量覆盖率为百分之八十左右。如果系统的数量覆盖率足够高，我们就可以认为它基本上覆盖了 的所有信息资源。高的数量覆盖率应该是任何一个搜集系统及以此为基础的网上信息博物馆的首要目标。 网上信息资源极为丰富，但也存在不少冗余，大量的广告页面和内容重复页面便是此例。即使去除这些冗余后，用户感兴趣的网页通常也只是数以十亿计的数量中的极少数。因此，考虑搜集系统在质量上对 页的覆盖程度显得尤为重要。这一指标可北京大学计算机科学技术系 网络与分布式系统实验室 孟涛学士论文 4 以告诉我们，对那些用户会感兴趣的重要的网页，系统覆盖了其中的百分之几。从更深的层次来说，如果搜集系统覆盖了绝大多数的“重要”网页，它也就覆盖了当前社会信息在每一个重要主题上映射到 的部分，成为它的一个有效特征子集。类似于系统如果将这些重要网页全部记录下来，以后就能通过历史网页回放来重现人类社会信息资源在时间和空间两维上的每一个角落。 从信息的表现形式来看，搜集系统当前存储的信息中相当一部分日后将是不可见的。这一方面是由于存储系统的资源所限，未能搜集类似于图片影音之类的大文档；另一方面是因为搜集技术的不成熟，无法获得类似于 格式的网页。因此，考察搜集系统对可视网上信息资源的覆盖率，也有着积极的意义。它可以告诉我们当前所搜集到的网页当中，多大比例的一部分能够在若干年后通过浏览器重新浏览。 在本文的研究中，将对前面的两种进行详细的讨论和量化分析。 息覆盖率评测模型 我们定义搜集系统的信息覆盖率为它所收集的网页集合在 所占的比例。考虑到 链接结构，将其视为一张有向图 G=（ V ， E），则搜集系统所获得的网页集合是 G 的强连通子图？（不一定是强连通图） G=（ V， E），每一个顶点都有唯一的标记 信息覆盖率 的表达式为： C=| | G的相关属性在搜集过程中已得到，但是因为搜索引擎搜集网页的不完全性， G 的相关属性却只能去估计。为了得到准确的信息覆盖率数据，我们采取对 样的方法，即采取随机的方式从中获得一张子图0G=（ 考察 V中的顶点落在 0的比例 的近似值。如果0 则 。此时的 我们可以用类似的思想去计算搜集系统的质量覆盖率。考虑 的所有重要网页构成的连通子图 们可以用随机的办法获得某些重要网页组成的集 合 S 作为样本，来考察搜集系统覆盖 S 中的子集 为近似的质量覆盖率此质量覆盖率的表达式为：（为什么用双竖线？） |S| | 0S 因此，我们需要通过对 机取样获得网页样本；需要采取某些方法得到随机的重要网页集合，这通常要利用网页之间的链接关系来对网页进行权值估算；在得到网页样本之后，再检查搜集系统的网页覆盖其 中的比例，在检查过程中，必须对网页过滤，扔掉无法连接到的网页。总体的工作流程大致如下图所示： 北京大学计算机科学技术系 网络与分布式系统实验室 孟涛学士论文 5 3 数量覆盖率 我们可以从不同的角度来对 进行采样。如果不考虑顶点之间的链接关系，仅从顶点的标记 对应的 址出发，可以采取随机产生 方法来获得一个网页集合，从而得到样本，这种考虑基于全局的视点；如果考虑到顶点之间的链接关系，则可以模仿搜索引擎搜集系统的工作方式，采取绝对广度优先的办法，从某一个顶点（种子 发，逐渐扩展遍历，得到一个网页集合作为样本，这是一种从局部来进行取样的办法。 机 在 和 工作 13中，他们提出了通过随机产生 行取样的方法。首先获得 已经分配使用的所有 址，假设共有 M 个。可以利用 分段将它们一一映射到 0 到 间的某个整数作为唯一标记。这样，我们可以利用随机算法产生小于 M 的整数，得到一个 记集合，再逆映射回到 址，即得到一组随机 本。如果搜集系统以域名标志网站地址，还需要将其转换为域名。这种取样原理如图 3 所示： 样 我们在研究工作中获得了中国国内已分 配的所有 址分段 4322 个， 其中一个分段，被分配给北京大学使用。如果统一用点北京大学计算机科学技术系 网络与分布式系统实验室 孟涛学士论文 6 分十进制表示所有网络地址，则所有的 段可以表示如下 12 n其中， 为 0 到 255 之间的整数。可见这些分段不相交，统计出每一个分段中的 址数量 则可以找到一一映射 F 使得 址 t）的函数值为： F(10（ * 3256 +(* 2256 + (*256 + (于是我们将每一个 对应到一个整数，便可以用随机算法在其中选取若干，逆映射转变为 址，便得到一个 址集合。去掉此集合中不提供 务（包括与网络无连接）的元素，就得到了一个网站样本。由于大约 14的网站通过 80 端口提供 务，我们可以顺次扫描这些网络地址上的 80 端口。得到的存在 务的址集合经反向域名解析便可得到样本 合。 通过对中国国内的 行随机取样并进行扫描，我们得到了如下结果： 编号 1 2 3 4 5 6 7 8 9 10 随机 100K 200K 300K 400K 500K 600K 700K 800K 900K 1M 存在 95 172 252 336 418 478 570 652 717 817 表格中间线太粗，而且第三条应该是不可见的 在上面的统计中，我们选取了多组不同数量的随机 到的存在 务的 明选出的 址具有很好的随机性。 证 由于搜集系统一般以包含域名的 记录网页，我们要检验这些网页是否已被覆盖，应该将其转化为相应的域名。由于网络中 务器提供的 向解析功能有限，而搜集系统在搜集过程中通常记录了搜到的网页域名与 址的对应关系，我们可以由此直接检验被覆盖的 址 数量。 我们的目的是对所有的 址进行建模，接下来的问题应该是该用多少数据才能满足要求使得样本有效。尽管我们就这一问题无法给出精确的数量，但是可以从少量的数据开始，然后逐步增加数据量。如果我们这种通过随机产生 样的办法是正确的，在原先样本的基础上逐步增加数据集将不会影响信息覆盖率的结果。因此，我们可以对样本容量从小到大的各组数据统计得到的覆盖率进行分析，看是否满足以上条件。 北京大学计算机科学技术系 网络与分布式系统实验室 孟涛学士论文 7 下表是在各组随机 址样本中，被搜集系统覆盖的 址所占比例。 编号 1 2 3 4 5 6 7 8 9 10 存在 95 172 252 336 418 478 570 652 717 817 覆盖 4 7 9 13 16 21 28 36 43 47 可以通过最小二乘法对结果进行线性拟合，得到以下的二维图像。其中，横轴代表随机 址样本容量，纵轴代表搜集系统覆盖样本的数量，直线的斜率则表示信息覆盖率。从图中可知，自变量和因变量之间存在很好的一次函数关系，右。由此可以推断，当样本扩展到所有的 址时， 覆盖率将会保持在这个数量左右。 型修正和结果分析 随机 产生了大量的随机 址，用这种方法可以很好的对 的所有提供 务的 务器进行取样；随着样本容量的增加，样本的精确性也会增加。但是，这种采样方法存在一些不足，导致信息覆盖率具有较大偏差。 首先， 址标记的是 务器的网络地址，在大多数情况下，它等同于该服务器上运行的网站首页。这使得我们最终得到的网页集合实际上是 网站首页的一个样本。使用 址将使得我们对所有的网站一视同仁，忽略了网站的大小之别。一个只有三五个网页的个人小网站（ 如 ）和一个有着上千网页的大商业网站（ 如 ，为 ）是不等同的，然而这种区别在随机 址取样中无法体现。 另外，大量存在 务的服务器并非是实际意义上的网站。大多 数 列操作系统自带的 务器软件， 统自带安装的 件，如此众多，都会在缺省条件下提供 务，而这些“网站首页”是没有实际意义的测试网页。类似的，也有大量的在某个 址短暂出现的网页（例如临时通过 务共享文件等等）。北京大学计算机科学技术系 网络与分布式系统实验室 孟涛学士论文 8 在上述随机 样方法中，这些基本无效的网页都被简单的等同于重要网站首页加入了样本之中。 因此，我们有必要对此模型作出修正。既要利用随机 法具有的优异的随机性和全局性，又要保证通过随机 址获得的网页的有效性。解决办法是利用网页之间的链接 关系，不再将各个网页看作独立的点，通过发现网页中的 进行适当扩展。我们在研究中将得到的所有随机 址视为基本集合 R ，通过 议取得这些 取出其中的链接，加入 R，作为 页样本，如下图所示： 为了将无效网页的影响降至最低，还可以对链接作多级扩展。经过这种处理后，上述第一种情况可以得到修正，因为大网站的首页通常存在较大的出度；第二种情况中默认网页链出的网页一般指向该软件生产厂家的首页，页面相同且数量少，且因其通常在国外故可在研究 过滤掉 。我们从上述的随机样本中抽取了 5 组，经过扩展以后的网页样本数量以及覆盖数量如下： 编号 1 3 5 7 10 存在 95 252 418 570 817 扩展样本容量 1084 2584 3859 5484 8094 覆盖 174 596 841 1204 1899 在验证的过程中，我们将用 址表示的 化成域名 便搜集系统的验证。这种转换经过了两级反向解析，第一步是通过网上 务器的解析，第二步是通过搜集系统保存的域名与 应数据。对得到的结果作线性拟合 ，得到的图几（没有标）如下，从拟合结果可得到信息覆盖率约为 可见，在对模型作修正之后，覆盖率有很大的增幅；如果考虑到域名与 间的动态关系（即大量域名的 可变的， 统每隔几分钟更新一次），我们去除掉样本中以 示的 量覆盖率数据将还会有小幅度的提高，这才是真正的数量覆盖率大小。 通过随机 产生的网页样本很好的考察了搜集系统对 向图某些入度为 0或是从出发顶点无法达到顶点的覆盖情况。这启示我们在搜集网页过程中，选取适当数量的以随机 产生的 为起始顶点集合的一 部分，能提高搜集系统的数量信息北京大学计算机科学技术系 网络与分布式系统实验室 孟涛学士论文 9 覆盖率和 网页信息的有效性。 度优先法 随机 虽然具有较好的随机性和全局性，但在使用过程中发现许多有待改进之处；为了使对 取样在逻辑结构上与实际情况更加接近，考虑到对随机 作修正时对逻辑链接关系的利用，我们提出了绝对广度优先搜集取样的办法。这种方法实现的实际就是一个最原始的搜集系统的工作过程，只是在搜集过程中按照绝对广度优先的方式一级级的扩展开去。这种取样是从局部的角度来进行的，原理如下图所示。 样 我们选取了五个 为起始点，采取上述绝对广度优先搜集网页的办法分别获得五组 页样本，样本容量从几万到数十万不等。算法如下： （ 1）选取某个网页 S 作为起始 （ 2）创建队列 Q 存储未搜集的网页， S 入队列；创建结构数组 A 存储已经搜集过的网页，按照 符串排序； （ 3）取得队列头元素，通过 议获取 H 的源文件，提取出其中包含的的全部 接，并记录链接关系； 北京大学计算机科学技术系 网络与分布式系统实验室 孟涛学士论文 10 （ 4）在 A 中用二分法寻找（ 3）中得到的 否已被搜集，如果没有搜集，则使其进入队列 Q； （ 5）判断 A 中的网页数量是否已达到要求，若没有继续（ 3）。 得到的结果列表如下： 样本编组 1 2 3 4 5 种子 展 66891 211629 154314 723866 174078 证和分析 得到网页样本之后，我们可以在 网页数据库中验证被覆盖的比例。为了快速的检验数据，达到磁盘性能的极限，我们启动了数百个进程从 表中读取并通过 法从库中查找。得到的覆盖率数据如下表所示。 对于这组离散的覆盖率值，我们计算均值和方差分别为 者即为通过绝对 广度优先法得到的数量覆盖率。 样本编组 1 2 3 4 5 扩展 66891 211629 154314 723866 174078 覆盖数量 26732 87562 67178 273066 74370 数量覆盖率 对于使用这种采样方法得到的数量覆盖率 较之采用随机 具有较高的覆盖率值是可以理解的。因为这两批数据是从两个不同的方面说明搜集系统的信息覆盖情况：随机 着眼于全局，而绝对广度优先法着眼于局部，更类似 于搜索引擎的搜集过程。 通常搜集系统是在 的最大连通子图内遍历，绝对广度优先法恰好反映了搜集系统对这一最大连通子图的覆盖比例。由于这一最大连通子图占据了 90%10左右的网页，而且我们选取的起始 落在这一子图之内，故绝对广度优先法得到的结论应该修正为乘以 90%这一参数才能在全局角度上反映搜集系统的覆盖率，因此准确的数量覆盖率应该是 当样本容量越大 ,覆盖率就应该约逼近此值 ,这从我们采用的大容量样本 (第 4 组 )结果中已经得到了验证。 随机 反映的是搜集系统对 所有点的覆盖 情况，因此这种采样更容易采集到入度为 0 或由于其他原因导致搜集系统无法遍历到的网页（称为不可到达网页）。由于不可到达网页中大量的点是孤立点，在没有很好的区分这些 址上所存在的网页数据量的情况下，这种样本需要经过多级链接扩展才能全面的反映真实的 就是说，如果对初始 断作链接扩展，最后的数据会不断接近 这在我们作第北京大学计算机科学技术系 网络与分布式系统实验室 孟涛学士论文 11 一级扩展之后已经有了好的反映。 我们可以预测到，如果将两种采样方法的优点结合起来，通过随机 产生 样本容量足够大之后 ，最后的数量覆盖率数据应该与通过文献 10 的工作做的估计相符，在 近。 4 质量覆盖率 考察搜集系统在质量上对 信息覆盖率，需要通过有效的网页重要性评测方法找到一组重要网页样本。尽管通常可以通过用户评选提交的方式得到他们在浏览网页过程中发现的重要网页集合作为样本，但在本文研究中，为了保证样本的随机性和客观性，我们采用两类基于对 接结构的分析而对 重要网页进行取样的有效方法。 这些方法的基本思想都是找到一组具有较强链接关系的网页（初始取样），通过基于链接分析的网页权值算法，求出其中 所有网页的相对重要性值，从而可以对网页进行排序取出前若干位作为重要网页的样本。这些经典的权值算法包括斯坦福大学开发 法 15和 究院开发 统提出的 法 16 （ 它们都是基于对 向图链接结构的理解提出的。 页重要性评测方法 的信息资源数量如此之大，无论是搜集系统本身还是接受返回结果的查询用户，都要求有好的方法对网页集合按照重要性进行排序，因为系统搜集的和用户关心的一般都只是其中的某一子集。准确的辨别出重要的网页加以优先搜集，准确的计算出重要的网页返回给用户优先浏览，要做到这些，我们需要合适的网页重要性评定方法。这里，网页的重要性用权值来衡量，权值越高表示网页越重要。 我们可以从三个角度来分析网页的权值，讨论它的相关因素。 从网页本身的唯一属性 发来考虑：网页的权值可以从 属性中得到反映。一般而言， 在 网站的域名越短，所在网站上相对于根目录的层次越浅，网页的权值越大。例如， 北京大学的网站首页 ；而 。这一原理可以在网页搜集过程中加以利用。 从网页作为 向图的一个节点来考虑：网页的权值可以根据它的认可度来判断，由于网页间的链接通常代表着认可度的传递，我们可以统计网页的入度来评判其重要性。如果网页 A 上存在网页 B 的 除掉纯粹导 航的因素，表示着网页 A 的作者存在对网页 B 的认可；而这种认可的增多则意味着网页 B 权值的上升。因此，入度越大，权值通常越高。 北京大学计算机科学技术系 网络与分布式系统实验室 孟涛学士论文 12 从网页本身的内容出发来考虑：在搜索引擎搜集网页的过程中，通常都要保存网页的关键词或全文信息，以便建立索引。由于网页的重要性一般又对应着用户较高的关心程度，我们可以通过对用户递交给搜索引擎的查询词与网页的内容（全文或关键词）进行匹配，匹配程度越高意味着网页的权值越高。当然，这要求用户递交的查询是希望得到大量相关网页的宽主题查询。该情况在论文 18中有详细讨论。 当前大 多数搜索引擎所采用的网页权值计算方法正是上面提到的的 法和 法两种，它们分别利用了上述中的后两种原理，而且对其间的网页链接关系作了更深层次的挖掘。 法 15是一种利用网页间链接关系进行权值计算的典型方法，它是学术论文引用统计原理在 的推广，它统计每个网页被引用的次数，但每一次引用又因引用者权值的不同而不同；而 法 17 将网页的权值分为目录型权值和权威型权值分别进行计算，目录型权值高表示它链向很多权威型权值高的网页，而权威型权值高则表示它被很多目录 型权值高的网页所链接到。（目录型、权威型没有解释） 基于这两种权值算法，我们提出了下面的两类质量覆盖率确定方法。 度优先法 样 法根据网页间的链接关系来评判网页的重要性，因此我们选取的初始网页集合必须和 着大致相同的链接结构，保证初始样本中每个网页的入度与实际互联网络相差不大，或者网页入度的相对大小变化不大。这样才能使得初始样本中的相对网页权值保持不变。 我们可以利用绝对广度优先的办法，从初始 始向外遍历。随着初始样本容量的加大，每个样本网页的入度越来越接近于它 在 的实际入度，样本网页的入度相对大小也越来越固定。我们以数量覆盖率研究中的广度优先法所获样本作为初始样本，它们的数量一般在数十万，已能基本保证其中相当数量网页的相对入度大小。用法从中计算选出权值在前 M 位的网页集合作为样本。显然， M 值越小，样本的有效性越容易得到保证。 法 假定网页 A 在 面被网页 链到， C(A)表示从 A 链出去的网页数量（即出度），则 A 的权值可以表示如下： )=)( 17 这种基本思想可以从下图中体现： 北京大学计算机科学技术系 网络与分布式系统实验室 孟涛学士论文 13 考虑到用户从 发只有 d（ 0的形式存入关系数据库。当网页的数量足够大时，所有的网页及其链接属性无法一次全部存入内存中，故需要分块对矩阵进行迭代。 具体的实现算法如下： （ 1） 创建数据结构存储网页的整数 值、出度、入度以及所有链入网页的此作为矢量 W 的单元； （ 2） 根据网页的平均入度 2估计系统内存一次能存放的 量 N，在我们的系统中，估计约为 1 （ 3） 从数据库中导出 N 个 内存，按 序；再将全部的链接关系导入，对于上述 N 中的每一个，填充进它的链接属性； （ 4） 对于 N 中的每一个，用二分法找到它的链入 数组下标，如果不在当前内存中则其权值以平均值计算，运用 法计算其权值； 北京大学计算机科学技术系 网络与分布式系统实验室 孟涛学士论文 14 （ 5） 如果全部的 已经导入计算过，则对该矢量进行处理使得所有 权值之和为 1；否则继续（ 4）； （ 6） 如果先后两次计算的 W 距离足够小，则对权值排序选取前 M 个输出到文件；否则继续（ 3）。 （ 7） 将输出文件中的所有 数 换为 符串。 实验在 统上运行，主要硬件指标是 1存 ， P 50 们以数量覆盖率计算中得到的五组样本作为初始样本，如果选择权值排序位于前面约 5%左右的网页作为重要网页的标准，得到了如下结果： 样本编组 1 2 3 4 5 种子 始扩展数量 66891 211629 154314 723866 174078 数 3523 8497 8702 33436 8408 占前百分之几 覆盖 1542 4032 4754 17717 3456 质量覆盖率 取前 M 个 ,为什么每组 占前百分之几不相同。 对五组样本检验得到的质量覆盖率计算均值和方差分别是 为了保证所求样本网页的重要性有效，我们选取了上述样本中的第 2 组和第 4 组，改变判断重要性的标准，质量覆盖率随此而变化的情形如下表所示。 对于第二组网页样本： 重要网页个数 1811 3434 5117 6808 8497 占前百分之几 覆盖网页数 1145 2068 2788 3363 4032 质量覆盖率 下图是随着重要性标准的放松，质量覆盖率的变化情况： 北京大学计算机科学技术系 网络与分布式系统实验室 孟涛学士论文 15 对于第四组网页样本： 重要网页个数 17321 33436 49198 64450 79155 占前百分之几 覆盖网页数 9903 17717 24718 31126 36780 质量覆盖率 下图是随着重要性标准的放松，质量覆 盖率的变化情况： 从这两张图中可以看出，当重要标准很苛刻时重要网页样本容量很小，此时搜集系统的覆盖率很高；但随着重要标准的放松导致样本容量的增大，搜集系统的质量覆盖率会越来越低；当重要性的标准放至最低，即所有网页的地位平等时，质量覆盖率变为最小，为数量覆盖率值。这两张图中都显示，当重要标准降至约 5%左右时，曲线开始逐渐变得平缓，因此此点的覆盖率数据 疑最适合作为我们所测的的搜集系统质量覆盖率。 北京大学计算机科学技术系 网络与分布式系统实验室 孟涛学士论文 16 题查询法 网页具有作为 向图结构中一个顶点的相关逻辑属性，它又可根据其内容本身而属于人类社 会信息资源的某一主题类别。例如，网页可以根据其内容分为属于社会、人文或休闲娱乐等类别以及它们的子类的网页。基于这一点的考虑，我们的研究工作中采取了通过主题查询获得 要网页样本的方法。这类似于文献 19 的工作中 于 同一主题的网页之间具有较强的链接关系 19，我们可用 法对此网页集合进行权值计算，进行排序后得到前若干网页作为 这一主题类别的重要网页样本。 样 假设我们希望得到 于主题 T 的重要网页样本，我们一般会通过递交 若干与T 相关的查询词 Q 提交给搜索引擎，它返回的网页集合为 R。对于通常的搜索引擎， 较高的相关度，因为查询中通常使用字符串匹配，使得返回的网页中大多含有 Q 之类的字样。但是，也有大量的重要网页不适合这种情况，例如天网系统的主页并没有搜索引擎的字样供匹配。出于对这种特殊现象的考虑，需要对 R 以适当的扩展，加入 R 网页链出去的网页和链向 R 元素的网页得到初始样本 S ，如图示： 我们选择了八个主题的查询词递交给天网搜索引擎，在用以上的方式对返回结果进行扩展之后，得到了八组初始网页样本如下： 样本编 组 1 2 3 4 5 6 7 8 查询词 北京大学 考研 股票 江泽民 程 联想集团 三个代表 世界杯 返回数量 1802 1802 1802 1802 1355 1802 1802 1802 扩展数量 11667 19379 13403 11006 26548 15498 11608 20823 法 北京大学计算机科学技术系 网络与分布式系统实验室 孟涛学士论文 17 上图中的 S 正是我们用 法进行权值计算的对象。对于 S 中的任意一个元素P ，设 H(P)表示其目录型权值（ A(P)表示其权威型权值（ 2, ,链到 P 的网页， 2, ,从 P 链出的网页，则 A(P)和 H(P)可以从下面的式子计算： A(P)= H(P)= 同 法类似，我们可以将所有的网页的目录型权值看作矢量 H，将所有网页的权威型权值看作矢量 A，设样本中所有网页及链接关系构成的有向图的邻接矩阵为 M，考虑到两个 间最多有一个链接使得若存在网页 i 到网页 j 的链接则 Mi,j=1否 则 Mi,j=0，那么上面的式子可以写成： A= H H=M A 由此两式可得 A= M A，即实际上 A 是 M 的特征向量；同理 H 是M 特征向量，我们因此也可以用幂法或 法等来通过迭代来求得 A 和 H 的值。但考虑到系统内存对初始样本容量的限制，若数量很大的时候需要分块对两个矩阵进行迭代。 验结果 在我们 的研究工作中，我们没有通过计算特征向量而采取了根据前一组公式直接进行迭代计算 A 和 H 值的办法，具体的实现算法如下： （ 1） 采集初始样本时将所有的 号存入数据库，同时存入 间的链接关系； （ 2） 创建相关的数据结构存储每个 值及链接关系，从数据库中导出所有 性并填充到数据结构中； （ 3） 给予 H 和 A 某个初始值，分别计算 A（ i+1） = H（ i）和 H(i+1)=M A(i)，直至 A(i+1)和 A(i)的距离足够小为止； （ 4） 分别对 进行 冒泡排序，输出前若干个 文件中。 在确定重要网页的界限时，我们选取的是初始网页样本中权值排在前面约 15%左右的部分，大致与搜索引擎响应查询词返回的网页数量相当。即搜索引擎就此主题返回 们经过计算后也给出 X 个“真正”重要的网页，检查搜集系统覆盖其中的比例作为质量覆盖率。 对于具有较高 值的重要网页，实验的数据如下： 样本编组 1 2 3 4 5 6 7 8 北京大学计算机科学技术系 网络与分布式系统实验室 孟涛学士论文 18 查询词 北京大学 考研 股票 江泽民 程 联想集团 三个代表 世界杯 初始数量 11667 19379 13403 11006 26548 15498 11608 20823 数 1671 1701 1532 1040 1508 1428 1859 1961 覆盖数量 958 956 578 312 772 514 793 651 覆盖率 30% 八组样本所得的质量覆盖率分别为表几所示，它们的均值和方差分别为 者即为搜集系统对 重要网页的覆盖率。 对于具有较高 值的重要网页，实 验的数据如下： 样本编组 1 2 3 4 5 6 7 8 查询词 北京大学 考研 股票 江泽民 程 联想集团 三个代表 世界杯 初始数量 11667 19379 13403 11006 26548 15498 11608 20823 数 1400 1572 1124 9