超链接环境下的权威资源(翻译)(共14页)

1、PAGE PAGE 17超链接环境(hunjng)下的权威资源(zyun)1 引言(ynyn)超链接的网络结构是一个有丰富资源的环境内容信息，它提供给我们一个有效的方法让我们去理解它。在这种情况下，我们针对这种环境下的链接结构开发了一系列的算法工具从中分离信息，并通过在试验中报告和说明它们在万维网中的多种多样内容中的有效作用。我们尤其关注它在一个广阔的搜索主题中分析和搜集相关网页以及发现最权威网页时链接的使用。对于万维网，当我们不缺乏技术的时候，我们发现搜索和结构分析的问题在区域上下文中尤其重要。万维网是一个巨大而复杂的超文本资料库，它同时在以惊人的速度持续扩展着。更甚者，它可以看做一个错综复

2、杂的超媒体结构。它同时有数以百万计的在线参与者，这些参与者们有着多种多样互相冲突的目标，同时他们还在不断的创造超链接内容。所以，当每个人都在以一种极端的本地层次强制整理信息时，全局的组织已经完全的改变了上层的结构只能通过之后的分析才能浮现出来。我们的工作就是源于万维网上的搜索问题。我们可以粗糙的定义为一个过程给出查询，提供相关的网页。由于相关性是主观存在的，所以搜索方法的质量需要人类来评估。我们是从观察万维网上提高搜索方法的质量开始的。在现阶段，一个丰富而有趣的问题是在很多方式中，它们算法的有效性和存储性是互不相关的。尤其是现在的搜索引擎都是典型的只搜索万维网上的一定大小的内容的搜索引擎，同时

3、响应还是秒级别的。尽管可以提高响应时间来换取对于用户来说更重要的结果，但是对于搜索工具来说，用额外的时间来进行计算，这是非常不可行的。准确的说，我们缺乏一种具体定义的功能，这种功能客观上应满足我们想要搜索到的页面的质量。查询和权威资源。我们认为搜索是开始于用户提供的查询的。它不需要查询的统一概念性的视图；且它不止是一种查询，它需要运用不同的技术来处理。思考一下，比如说，有下面几种查询：特定查询，如“网景是否支持JDK 1.1代码签名的API（应用程序接口）？”广泛主题(zht)查询，如“找到关于(guny)JAVA编程语言的信息”相似(xin s)页面查询，如“找到与相似的页面”我们现在专注前

4、两种类型的查询，我们可以看到它们现在又很多不同种类的障碍。处理特定查询时的困难是集中的，粗略地说，是围绕所说的稀缺问题的。有极少的页面包含这些所需的信息，并且通常很难确定这些页面的真正来源。对于广泛主题查询，另一方面，我们期待在万维网上找到数以千计的相关页面。这样的一组页面可能通过标引项匹配（如输入一个字符串“Gates”，“search engines”，“censorship”到搜索引擎AltaVista17），或者更复杂的方式产生。因此，这并不是一个稀缺问题，相反，其基本困难在于丰度问题：可以作为相关页面合理地返回的页面数目太大，以至于人们很难消化。在这些条件下，为了提供有效的搜索方法，

5、就需要一种方法，从巨大的相关网页集合中筛选出最“权威”或“彻底”的那些。我们对于广泛主题的查询，可以将权威这一概念，作为我们工作中的中心焦点。我们在处理这一问题所面临的基本障碍之一是准确地模型化在特定的查询主题上下文中的权威网页。鉴于某一网页，我们如何辨别其权威？讨论一些在这里出现的复杂难懂的问题是很有用的。首先，考虑报告的自然目标，即哈佛大学主页为查询“哈佛”的最权威页面之一。不幸的是，在万维网上有超过 100 万的网页使用了目标词 “Harvard”。同时 不是最常使用的，或者使用最突出的，或者以任何其他方式支持一种基于文本的排序函数。事实上，一个疑问是，是否存在一个纯粹的内源性措施去适当

6、地评估一个页面的权威。第二个问题是找到主要的www 搜索引擎的主页。我们可以从查询“搜索引擎”开始，但是这存在一个困难，事实上很多权威网站（雅虎，Excite，AltaVista） 都没有在其页面上使用这个词。这是一个基本的和重复出现的现象 另一个例子，我们就没有理由指望本田或丰田的主页包含术语“汽车制造商”。链接结构分析。万维网的网页之间的超链接结构分析，给了我们一个方式来处理许多上文讨论过的困难。超链接隐含了大量潜在的人为判断，我们认为这种类型的判断正是我们制定一个权威的概念所需要的。具体来说，万维网上链接的建立是以下判断类型的具体表现：页 p，通过包括页面 q的链接，就可以在在某种程度上

7、赋予 页面q 的权威性。此外，链接通过指向它们页面，让我们完全有机会找到潜在的权威性的东西 ；针对很多突出的页面没有充足地自我描述的网页，这种方式围绕着以上的问题提供了一种方法。当然(dngrn)，这种情况下，有大量的链接(lin ji)的应用程序(chngx)中有很多的潜在缺陷。首先，针对各种各样的原因创建的链接，其中有很多与权威性无关。例如，主要用于导航目的而创建大量的链接（ “点击此处返回到主菜单”） ；其他表示的付费的广告。另一个问题是很难找到相关性和流行性标准之间的适当的平衡，而这两个都有助于权威这个直觉概念的判断。这对在下面这个简单的启发式算法定位权威页面所固有的严重问题的思考具有

8、指导性作用：包含查询字符串的所有页，都返回导入链接的最大数目。我们之前已经讨论的许多查询 （搜索引擎、汽车制造商，)，其中的一些查询的最权威页面不包含相关的查询字符串。反之，这启发式算法会考虑普遍受欢迎的网页，如 或 所包含的任何查询字符串，它极具权威性。在这项工作中，我们针对权威的授予，提出了一个基于链接的模型，并提出它是如何统一标识与广泛搜索主题相关的、 权威的 www 页面的方法。我们的模型基于权威性的主题与这些权威性页面所链接到的许多有关权威性页面之间所存在的关系我们把后面的这一种类型的页面叫做枢纽。我们观察到枢纽和由链接结构定义在图中权值之间存在的某种自然的平衡，我们利用这一点开发算

9、法，能同时识别两种类型的页面。这种算法操作于我们构建的基于文本的 www 搜索引擎输出中的子图 ；我们构建这些子图的技术是设计产生一个小的可能包含一个给定的主题最权威页面集合。概述(i sh)。我们(w men)发现权威万维网资源(zyun)的方法必须要具有全球性质： 我们希望确定万维网中广泛搜索主题的最中央页作为一个整体。全局办法涉及到了表示和过滤大容量的信息的基本问题，因为所有的与主题有关的广泛主题查询的页面有数以百万计。这与查询本地的方法不同，理解万维网中的页面的相互连接属于单个逻辑站点或内联网； 在这种情况下，本地方法数据量小得多，经常考虑不同组的主导地位。注意到我们主要关心的这个是一

10、个从根本上与聚类问题不同的问题也是很重要的。聚类问题剖析了异构迁入子图，在某种程度上这更有凝聚力 ；在万维网的背景下，这可能涉及到要区分不同含义或感觉的被查询词相关的网页。因此，聚类的本质上是不同于那些通过权威性而发现提取出广泛主题的问题，虽然后面的部分将表明某些联系。即使我们完全能够分析含糊不清的查询词 （如Windows或Gates） 的多个意义，我们将仍然留下一个潜在问题，那就是表示和过滤掉与每个查询词主要意思相关的大量页面。本文的结构如下。第二部分讨论的是通过广泛主题搜索来构建万维网上的子图从而产生一系列丰富而理想的相关权威页面的方法。第三部分和第四部分讨论在这样的一个子图上识别枢纽和

11、权威性的资源的主要算法，以及该算法的一些应用。第五部分讨论万维网的搜索、 文献计量学，和社会网络研究领域的相关工作和联系。第六部分描述了如何扩展我们基本的算法，进而去搜集多个枢纽页面和相同链接结构内的权威页面。最后，第七部分研究为了让我们的技术更有效，我们应该如何定义所搜索的主题的“广泛性”。第八部分针对在这里提出的方法的调查工作，我们进行了一些评价的问题。2 万维网中构造一个集中性的子图我们可以将任何集合 V 的超链接的页面作为一个有向图 G = （V ；E）： 节点对应于页面，一个有向的边 （p，q） E 表示的从 p 到 q 的一个链接。我们知道一个节点 p 出度是其所链接到其他的节点的

12、数目。而 p 的入度是其它的节点链接到P的数目。在一个图 G中，我们可以通过以下方式隔离小区域或子图。假设W V是一些页面的子集，我们使用 G W 来表示图中的W： 其节点是在W中的页面，且它的边对应于 W.在页面之间的所有链接。假设(jish)我们针对字符串进行(jnxng)广泛主题查询。我们希望通过链接结构的分析找到权威性高的页面(y min)；但首先我们应该找到我们算法所操作的在万维网中的那个子图。在这里我们主要是关注在相关页面上的计算量。因此，在这里我们举个例子，我们可以将分析限制在集合Q（），此处Q（）是包含所查询字符串的所有页面，但这有两个明显的弊端。首先，这个集合可能会包含超过百

13、万的页面，因此需要大量的计算成本；第二，我们发现部分或大部分最适合主题的资源可能不属于这一集合。理想情况下，我们关注于具有以下属性的页面的集合S（）。（ = 1 * ROMAN I）S（）相对小。（ = 2 * ROMAN II）S（）是具有很多相关的页面。（ = 3 * ROMAN III）S（） 包含大部分 （或许多） 最权威的资源。通过保持集合 S（） 小，我们就能够负担得起应用非平凡算法的计算开销 ； 通过确保S（）具有很多相关的页面，我们能容易找到好的权威资源，因为这些页面很可能需要大量引用。我们怎样才能找到这样的一个集合呢？对于参数t（通常设置其值为200），我们首先从一个基于文本

14、的搜索引擎 AltaVista 17 或Hotbot 57 搜索查询字符串 ，并从中收集 t 个排名最高的页面。我们将这t个页面作为根集合R（）。根集合满足前面所需要的（）和（）两条性质。但它一般是不满足 (iii)的。我们看一下这个，最上层的 t个 页面由我们使用的基于文本的搜索引擎所返回返回的，它们包含所查询的字符串 。因此 R() 显然是集合Q()的子集，且Q()是所有包含的页面。我们争论的是 Q() 往往不满足条件 (iii)。它观察在 Q()也是很有趣的，R()页面之间通常链接是极少的，这通常是无结构的。例如，在我们的实验中，查询词java的根集在不同域中的页面之间包含15个链接；查

15、询词 censorship 的根集在不同域中的页面之间包含28个链接. 这些数字都是典型的多种查询尝试 ；他们应与根集页面之间存在的200*199 = 39800个潜在链接进行比较。然而，我们可以(ky)使用根集 S()，来产生(chnshng)一组页面集合(jh)S()，它将满足我们一直在寻找的那些条件。考虑针对查询主题，那些强有力的权威资源尽管它不在集合 R()，但是很可能会在 R() 所指向的链接中的至少一个页面中。因此，我们可以通过扩大 R() ，在子图中增加权威资源的权值，并沿着链接，进入和离开它。具体而言，我们定义了下面的过程。即：对于(duy)子图(,E,t,d): 所查询(ch

16、xn)字符串.E : 基于(jy)文本的搜索引擎T， d : 自然数R（）：针对字符串，搜索引擎E的结果中的前t 个排名最高的页面使 S（）:= R（）对于每个页面 p （）使T+(p) 表示p指向的所有的页面使T(p) 指向p的所有页面将T+(p)中的所有页面添加到 S()中如果T(p)的绝对值 d 则：将T(p)中的所有(suyu)页面添加到 S()中.否则(fuz)从T(p)中添加(tin ji)d个页面中到 S()中.结束返回S()因此，我们通过与日俱增的 R()，获得 S()。其中包括了R()中的一个页面所指向的任意页面，以及其他指向R()的任意页面。限制条件是我们允许R()中单个页

17、面所指向的最多d个页面加入到 S()中。后一点至关重要，因为一些万维网上的的网页由数十万个页面指向它，但如果我们想要保持S()相对小，S() 中就不能完全包括所有的这些页面。我们提到了 S() 是 的基本集合 ；在我们的实验中，我们通过在搜索引擎 AltaVista中调用子图过程，设置t = 200 和 d = 50来构建它。我们发现S()通常满足上面多提到的（），（）和（）它的大小通常是在10005000范围内；而且，如上所述，权威的资源只能被根集 R() 中的 200 个页面中的任何一个进行添加，才能被添加到 S()中。在下一部分，我们将描述我们计算枢纽以及计算基本集合S()中权威资源的算

18、法。在谈到这之前, 我们讨论一个提供纯粹导航功能的启发式算法，它对于消除链接的影响非常有用。首先，让 GS() 表示上面所说的，在 S() 页面上所引导出来的子图。我们将GS()中的两种链接区分开来。如果是链接不同域名之间的页面，则该链接是横向链接，如果是相同域名之间的链接，则称它为内部链接。这里的“域名”，我们指的是在与网页关联的 URL 字符串的第一级。由于内部链接往往是一个网页基础结构的导航，他们比横向链接所指向的页面传送的权威信息少。因此，我们从GS()中删除所有的内部链接，保持只留下对应于横向链接的边缘部分 ；最终产生了图 G()。这是一个(y )非常简单的启发法，但我们(w men

19、)发现它有效避免了许多(xdu)如其他链接同样的方式所产生的异常状态。还有其他简单的启发式算法，可以用于消除那些看起来并不直观的链接，以此来产生权威资源。其中值得一提的是我们基于以下的观察。假设同一个域名中的大量页面指向同一个页面p。很多时候，在这些引用页页中，这对应于很多的代言、 广告或一些其他类型的的“合谋” 例如这句话“此站点设计的”和相应的链接，在给定域中的每一页的底部。要消除这种现象，我们可以设置参数 m （通常为m 4-8 ），并仅允许来自单个域最多m页可以指向任何给定的页面 p。再次，在某些情况下，这将是一个有效的启发式算法，尽管我们做接下来的实验时并没有使用它。3 计算枢纽及权

20、威资源上一节的方法提供了一个比较集中的查询主题的小的子图G()它有许多相关的页面和很权威的资源。现在我们单纯地通过 G() 的链接结构分析，来从页面的整体集合中提取这些很权威的资源。最简单的方法，可以说，通过他们的入度指向在 G()它们的链接的数量来进行排序。早些时候，当它被应用到包含所查询目标字符串 中搜集页面的时候，我们没有考虑这种想法。 但是现在我们明显需要构建一个相关页面的小集合，而这个集合是包含我们想要找的大部分的权威资源的。因此，这些权威资源既属于 G()，也被G()中的页面大量引用。事实上，纯粹由入度的排序方法通常在G() 的上下文中所起的效果比我们之前所预想的要好 ；在某些情况

21、下，它可以产生一律的高质量的结果。然而，该方法还保留着几个重大问题。例如，查询“java”，具有最大的入度的页面包括 和 ，以及广告加勒比海度假，和亚马逊书主页的页面。这样的混杂是从这个简单排序方案产生问题的类型所产生的代表： 虽然这些页面的前两个当然是“好”的答案，其他与查询主题无关 ；它们虽然入度较大但缺乏主题统一性。这表明基本的困难是在子图G()的入度最具权威性的和简单“普遍流行”的网页之间存在的内在的张力；我们最后需要的网页是入度较大，且符合我们的查询主题。你也许(yx)会疑惑是否需要(xyo)围绕这些(zhxi)问题，针对基础集合，进一步利用页面的文本内容，而不仅仅是利用G() 的链

22、接结构。我们现在表明情况并非如此它其实可以更有效地从链接提取信息我们开始以下的观察。和权威网页内容相关的初始查询不仅要查询入度较大的 ；更因为它们共同话题中的所有权威资源，所以也应该考虑是否与指向它们的页面集重叠。因此，除了极具权威性的页面之外，我们也期望找到所谓的枢纽页：这些是链接到多个相关权威页面的的页面。这些枢纽页“齐心协力”围绕一个共同的主题，并使我们能够从入度较大的页面中抛弃不相关的页面。（如图 2 所示，这是一个梗概性的例子； 当然，在现实中，这幅画并不是如此简单的）枢纽页面和权威页面表现出相辅相成的关系： 一个良好的枢纽页是指向许多好的权威性资源的页面 ； 同时一个好的权威性页面

23、是许多的枢纽页所指向的网页。显然，如果我们想要在子图 G（）内确定枢纽页和权威性页面，我们需要一种方法来打破这种循环。一种(y zhn)迭代算法。我们通过迭代(di di)算法，利用集枢纽页和权威页面之间的关系，来保持和更新每个页面的权重(qun zhn)数值。对于每一个页面P,我们赋予一个非负的代表权威程度的权值x(p)，也赋予一个代表枢纽程度的一个权值y(p)。我们把权重的每种类型都进行归一化，保持其平方的总和为 1不变： 我们将有最大的x和y的值的页面分别作为最好的权威页面和枢纽页面。数值，它自然地表达了枢纽页面与权威页面之间相辅相成的关系，如接下来所示：如果具有较大的 x 值的页面p

24、指向许多页面，那么它就应该获得较大的 y 值 ；如果页面 p被许多页具有较大的 y值的页面所指，那么它就应该获得较大的 x 值。我们用I和 O定义了以下两个关于权重的操作，给出权重 x(p),y(p)，I操作可更新 x 权重如下所示：而O操作可以更新y的权重：因此 I 和 O 操作是枢纽页面和权威页面加强彼此的基本手段。（参见图 3）。现在(xinzi)，若要查找所需的“平衡(pnghng)”值权重(qun zhn)，一个是可以交替使用I和 O 操作中，看看是否到达了一个固定的点。事实上，我们现在可以说明我们基本的算法的一个描述。我们将权重 x(p)的集合作为一个向量集 x，它是 G()中每个页面的一个坐标 ；类似地，我们将权重 y(p) 的集合作为一个向量 y。此过程可用于以下(yxi)简单方法(fngf)来筛选出前c个权威(qunwi)页面和前 c 个枢纽页面。我们将在与G()等价的集合G 上应用筛选过程，通常与 c 5-10，。要解决如何最好地选择 k的问题，我们首先申明，将一个任意大的 k 值作为迭代次数使用迭代，数列x(k)和y(k