法律状态公告日
法律状态信息
法律状态
2012-10-10
未缴年费专利权终止 IPC(主分类):G06F17/30 授权公告日:20090708 终止日期:20110810 申请日:20050810
专利权的终止
2009-07-08
授权
授权
2007-09-19
实质审查的生效
实质审查的生效
2007-07-25
公开
公开
相关申请的交叉引用
本申请要求2004年8月16日提交的美国申请序列号10/918,713的优先权，其全部内容在此通过参考被合并。本申请还包含与2003年10月29日提交的美国专利申请序列号10/687,602相关的主题，其全部内容在此通过参考被合并。
技术领域
本发明包括一种利用超文本链接对在分布式网络中找到的信息源进行排序的方法、系统和计算机程序产品。具体地说，本发明涉及对来自分布式网络环境中的搜索的命中进行基于链接分析的排序。本方法的软件/固件构成了借助对来自分布式网络环境中的搜索的命中进行基于链接分析的排序，用于搜索分布式信息系统的一个系统的一个组件。该方法适用于文档或其它文件通过链接相关的环境，例如因特网。
背景技术
图1是因特网的基本表示，示出了共同用来构造环球网(WWW)的搜索引擎的多个部分。爬行器1收集关于出现在WWW2上的网页的信息。所有相关文本信息被馈送到倒排索引3中，用作在WWW的爬过部分上的可用信息的脱机快照。关于链接结构的信息——即每个网页正指向哪些其它网页——被保存在一个链接数据库4中。当用户执行搜索时，她发出一个搜索查询5，此查询被发送给倒排索引3。扫描倒排索引的结果是一个未区分优先级的命中列表。这个命中列表然后根据文本相关性6和链接结构7而被排序。两个排序措施然后整合成一个有优先次序并经过排序的列表8，此列表8作为一个有优先次序的搜索结果9被返回给始发该搜索查询的用户。
当从倒排索引中获得查询结果时，它们一般将包含位于因特网上的不同WWW域上的命中/文档。文档相互引用(指向)的方式暗中构成一个有向图。这个有向图由作为节点的文档和作为有向边的超文本链接组成，正是这个有向图被用于基于链接的排序。基于链接的排序然后不但基于命中(文档)自身的内容而且还基于它们如何定位在更大的信息网络(有向图)中来估计这些命中(文档)的″权重″或″重要性″。
基于链接分析的排序在以下环境中是有用的：其中，待排序的文档通过从一个文档指向另一文档的定向链接建立关系，并且其中，链接可以被理解为一种推荐的形式。即，从文档u指向文档v的一个链接意味着对文档u感兴趣的用户还可能对文档v感兴趣。链接分析允许人们按照一种有用的方式合并包含在所有这些′推荐′(链接)中的信息，因此人们可以在全局上对文档排序。这种方法的突出例子是Google的PageRank方法对被称为环球网的链接文档集合的应用。
这里存在着一些执行基于链接的排序并寻找文档′权重′的替换方式。在不同修正方案中的所有方法都基于查找图形的邻接矩阵A的主特征向量(与最大特征值相关的特征向量)。Google的PageRank方法(下面讨论)通过计算列被归一化的转置邻接矩阵的主特征向量来获得每个文档的排序。在HITS方法中，由于Kleinberg(下面讨论)，获得两个排序：1)通过计算用其自身的转置矩阵构成的邻接矩阵的主特征向量来获得中心分数(hub score)；和2)通过获得用它本身的邻接矩阵构成的转置邻接矩阵的主特征向量来计算出权限分数(authority score)。然而，没有任何实施方案解决因未修改的邻接矩阵(单独被使用)及其转置(同样单独被使用)而来的排序。
通过定义两个简单的运算符-F(正向)和B(反向)-以及它们各自的标准化形式f和b，则最容易解释链接分析的各种方法。按照随机漫游的精神，可想象与有向图上的每个节点相关的某一权重(一个正数)。F运算符在每个节点u处采用权重w(u)并正向发送它，即，发送到被节点u指向的所有节点。B运算符与箭头相反地发送w(u)，即，发送到指向节点u的每个节点。B是邻接矩阵A，而F是它的转置。f是F的列标准化形式；它在节点u处采用权重w(u)，用节点u的输出端数(outdegree)kout，u除以它，并发送结果w(u)/kout，u给被节点u指向的每个节点。类似地，b是反向运算符B的标准化形式。
PageRank使用被“随机冲浪”运算符(参见下面)补充的f(标准化的正向)运算符。HITS方法使用复合运算符FB来获得权限分数，并且使用BF来获得中心分数。本发明可以与遭受陷问题的任何运算符一起使用，尤其是基本运算符F、B、f或b中的任何一个。
所有基于链接的排序方案必须处理的一个问题是在有向链接图结构中的′陷(sink)′情况。一个′陷′是一个节点或者一组节点，它只具有指向它的链接，但没有从该组陷节点指向位于该组陷节点之外的其它节点的链接。典型情况下，陷由一组节点而非一个节点组成；这样一个组被称为一个′陷区域′。同时，一个陷区域中的每个节点都被称为′陷节点′。
在有向图上随机漫游的一个问题是：它们很容易陷入到图形的陷区域中，有方法进入却无法出来。PageRank通过以某种概率加入完全随机的跳跃(与链接无关)来纠正陷，而WiseNut通过采用一个″页面权重库″来纠正陷，页面权重库是一个假想的节点，它与图中所有其它节点双向连接。陷一般存在于分布式超文本系统中；因此，涉及在有向图上随机漫游的每种方法都必须以某种方式处理这个问题。
基于IBM的CLEVER项目所做工作的另外一种方法已被Cornell大学(美国)的Jon Kleinberg申请专利(美国专利No.6,112,202，其内容在此通过参考被合并)。该算法常常被称为HITS(″超文本引导主题选择″)。
在HITS方法中不存在已知的陷问题，因为在应用HITS运算符BF或者FB中的任何一个时，人们在顺着那些箭头(有向弧)以及逆着它们移动这两种动作之间交替。在多个专利(例如美国专利6,112,203，6,321,220，6,356,899和6,560,600，其内容在此通过参考被合并)中阐述了这种方法及其变体。
一个有13个节点(文档)的简单图形如图2所示。在图2中，有两个陷区域：一个陷区域包括节点组(6，7，8)，而另外一个陷区域包括节点组(10，11，12，13)。仅仅顺着这些箭头的任何移动一旦先到达任一个陷区域，都将陷入该区域中。
陷的存在对于通过链接分析的重要性排序提出一个很大的实际问题。这个问题是：对于某些方法，陷节点或陷区域可以累积所有的权重，而其它非陷节点(文档)获得零权重。这样一来，在整个有向图上不可能获得一个稳定的非零正权重分布。没有这样一个权重分布，则一个有意义的文档排序变为不可能。也就是说，文档典型情况下经由链接分析被排序：通过计算每个节点的非零正“重要性权重”——从邻接矩阵的选定修改的主特征向量中获得——然后使用该′链接分析重要性权重′以及其它重要性度量(比如文本与查询的相关性)来计算一个总权重，这个总权重接着给出文档的排序。当这里存在陷时，这个主特征向量易于在这张图形的大部分区域上具有零权重。基于这样一个特征向量的重要性排序失去作用。
从数学上看，说一幅图形具有陷相当于说该图形不是强连接的。一个有向强连接图是这样的一个图形：对于图形中的任何一对节点u和v，都存在至少一条从u到v的有向路径以及至少一条从v到u的有向路径。这些路径未必是穿过同一组图形节点。更通俗来说：在顺着有向链接移动穿过一个强连接图时，人们可以从任何开始位置到达任何节点。陷节点或陷区域的存在妨碍了这种情况：人们会“受骗”到陷中，再也出不来。因此，具有陷的任何图形都不是强连接的，因此对陷问题的任何补救都想使整个链接图变为强连接的。
Google的PageRank算法通过增加从每个节点到任何其它节点的一个链接来补救陷问题。就是说，对于图中的每个节点，增加一个被给了一个小权重的出链接(outlink)到所有其它节点。这种修正被称为′随机冲浪′运算符，因为它模仿了可以从任何页面(节点)随机跳到任何其它页面的网页冲浪者的效果。
理论上，当随机冲浪运算符被使用时，原始链接图被一个完整图结构扰乱。一个完整图是一张从任何节点到图中任何其它节点具有一个有向连接的图形。链接图被完整图扰乱导致一张还是完整的新图形。陷问题因此被解决——因为新的图形是强连接的——并且因此对于所有的节点确保一个整体排序。可是，这并非毫无代价而来。要付出的代价就是：牺牲链接图的稀疏结构并被一个稠密的新扰乱的图形所代替。这会导致两种可能类型的问题：1)当矩阵是稠密的时候通常用于计算排序的算法变得更费时，以及2)链接图的结构改变。
第一个问题对于PageRank方法并不出现。由于随机冲浪运算符的特殊(完整并且对称)结构，它的效果可以很容易地被计算。因此，PageRank算法的计算时间不会由于增加完整图结构的而显著增加。
第二个问题还在。当然，不以某种方式改变图形的结构就把一个非强连接图改变为强连接图是不可能的。可是，实际上PageRank修改很大。也就是说：假设原始图很大——假设它有一百万个节点。(在环球网中的文档数目以十亿为单位。)于是，说这张图是′稀疏的′就是在说图中的链接总数大概与节点数目(在这种情况下是几百万)成比例。(这个数字是平均节点程度)。可是在执行PageRank修改之后，链接数目是一百万乘一百万——大约一万亿左右。
图3示出了随机冲浪运算符对图2的图形的影响。在这里，只示出了被加到节点1的出链接。也就是说，在增加随机冲浪链接之后，节点1有12个出链接而非2个。图形中的所有其它节点也将有12个出链接。图2中的所有其它冲浪链接没有画出，只是为了避免视觉混淆(对于这张图形总共有135个随机冲浪链接。)
简而言之，PageRank陷补救涉及把一个可能很大数量的新链接加到原始图上。这种改变虽然在某种意义上很大，但是至少可以通过向所有增加的链接给出相等的权重来以一种不偏斜的方式而被执行。目前公开的方法还想同样以一种不偏斜的方式但是通过只是增加少数链接到原始图上来使图形强连接。
被WiseNut搜索引擎使用的另外一种算法(美国专利申请2002-0129014)有点类似于PageRank。WiseNut方法(被称为WiseRank)通过把每个节点双向连接到一个″页面权重库″(被表示为R)也增加了大量的链接。这使得每个节点达到所有其它节点；并且实际上，在该算法中，两个跳跃u→R→v被挤压为一个。因此，在拓扑上，这与PageRank相同。可是，使用通过R的跳跃的可能性在WiseNut规则中是不同的——具有较低输出度的节点具有使用R的更高可能性。虽然如此，从专利申请中它显出：以与PageRank矩阵中找到的相同的方式，不稀少的结果的WiseNut矩阵较易管理。因此，对于WiseNut，同样的优势与劣势存在，正如上面对于PageRank所述的那样。
基于IBM的CLEVER项目所做工作的链接分析的第三种方法是Cornell大学(美国)的Jon Kleinberg的(美国No.6,112,202，其内容在此通过参考被合并)。该算法常常被称为HITS(″超文本引导主题选择″)。HITS算法没有直接使用邻接矩阵；相反，它使用复合矩阵，如此构造复合矩阵以避免有陷。因此，可以说HITS方法包括一种用于避免陷问题的方法。可是，复合矩阵有它们自己的问题。其一，它们可以给出一个′有效图形′，它在原始图中链接的节点之间没有连接。在有些情况下，这会通向一个已连接的原始图，导致一个断开的实际图形。这无法获得断开图的一个有意义的整体重要性函数；因此在这种情况下那么需要进一步假设或修改。
复合矩阵也将连接在原始图中未连接的许多节点对。因此，在复合矩阵中有比原始邻接矩阵中更多的非零条目。可是，实验研究暗示这些复合矩阵仍然比较稀疏：在一个示例中，对于原始邻接矩阵中的每个节点平均大约有8个链接，在每个节点的有效图形中找到有大约43个链接。因此，HITS方法看上去同样给出了一个易管理的数字计算。
最后，使用复合矩阵几乎还没有商业使用，而非复合的PageRank方法已经获得了巨大成功。在申请人自己的试验(未公开)中，HITS方法给出了相当差的结果，而PageRank与美国专利申请10/687,602的方法二者都给出了优良的结果。(在这些测试中，′优良的结果′是指对最佳节点给出一个高排序。)因此似乎HITS和相关方法虽然计算精致但是在排序方面没有给出优良的性能。本发明人发现的所期望的一个特征是一种不依赖于使用复合矩阵的方法。
发明内容
鉴于超文本链接分析的目前可用方案的上述缺点，本发明的一个目的是提供一个基于规则的方法以及相应的系统和基于计算机的产品，用于排序超级链接网络中的文档。
如上所指出，通常的有向图结构不是强连接的。具体地说，它们会有陷节点和/或陷区域，这在执行链接分析中引起问题。可是，典型的有向图具有强连接的组件(SCC)。一个强连接的组件只不过是一组节点(通常不是整个图)，对于这些节点，总是有一条从任何节点u到任何其它节点v的路径，只要u和v位于同一SCC中。
在不同的SCC之间也有链接。可是这些链接总是单向的。这是由于如果在SCC_1和SCC_2之间在两个方向上有定向链接，那么两个SCC实际上只是一个。
本发明提供两个新的解决技术问题的方法，该问题在人们试图执行基于链接分析的排序时出现——即，陷问题。具体地说，本发明建议了用于解决陷问题的两个新方法。这两个方法每一个都具有两个所希望的设备：
●它们适合与任何类型的(正向，后向，标准化的，非标准化的)非复合矩阵一起使用。
●它们不把原始的稀疏图形改变为一个稠密的图形。相反，它们按照一种让图形稀疏的方式来修改图形。
●方法1向原始图增加了少数的链接；而方法2没有增加新的链接。
附图说明
正如通过当结合附图考虑时参考如下详细说明变得更好理解那样，将很容易获得本发明的更完整评价以及它的许多附属优点，附图中：
图1描述了一个一般的搜索环境；
图2描述了一个具有陷区域的示例图形；
图3描述了随机冲浪运算符对图2的图形的影响；
图4描述了与图2的示例图形对应的完整元图(metagraph)；
图5描述了与图2的示例图形对应的挤压图(collapsed graph)；
图6描述了方法1对图2的示例图形的影响；
图7描述了方法1对图4所示的元图的影响；
图8描述了方法2对图4所示的元图的影响；和
图9是与本发明相关联的一个计算机系统的方框图。
具体实施方式
本发明使用链接分析来计算每个节点u的节点链接分析权重LA(u)。为了排序目的，这是计算每个节点的一个文本相关性节点权重TR(u)的通常做法。一个最终节点权重W(u)然后可以作为这两个权重的加权和而被获得：
W(u)＝a·TR(u)+b·LA(u)
因为权重W(u)被纯粹用于排序，并且只有比值a/b对排序有任何影响，所以两个参数a和b中只有一个是一个独立的调整参数。
包括在本发明中描述的那个方法在内的任何链接分析方法的出发点都是一个有向图，其中：节点是信息文档，并且链接是从一个节点到另一节点的指针。这张图形通常通过爬行或测量一组链接文档之间的链接而获得。我们将称这张图形为′已测量的图形′。
根据必须处理质量控制的各种准则来编辑已测量的图形常常是有用的。例如，如果确定为了人为升高一个或多个文档的排序的目的已经产生了大量的链接，那么这些链接可以被删除以便给出一个更精确且公平的排序。类似地，节点可以被删除；例如，如果多个节点有着几乎完全相同的内容，并且位于文档系统那同一区域中——，以使它们可以基本上被视为彼此的拷贝——那么这样的节点除了一个以外全部可以被删除。当然，当节点被删除时，连接到这些节点的链接也必须被删除。
我们注意到这样的编辑总是采用修剪的形式：节点和/或链接的删除，以便增强导致的超级链接图的能力来精确表示链接文档组的实际结构。当用这种方式修剪已测量的图时，我们称结果图为′已修剪图′。
可以在链接分析中的任何阶段执行修剪。在开始链接分析之前检查并修剪图形始终是可能的。可是，链接分析进程本身揭露了关于节点和/或链接的质量信息也可能发生，这推动了进一步的修剪。因此，在链接分析期间的任何阶段修剪还是可能的，并且常常是所希望的。为此缘故，本发明允许在链接分析之前或链接分析期间修剪。
为了语言简洁并且在区别不是很重要的那些情况中，我们将经常使用名词′原始图′来指代已测量图或者已修剪图。在这里的要点是：本发明涉及原始图的修改使得消除陷问题。如果没有执行修剪，那么修改被应用到已测量图上；否则，修改被应用到已修剪图上。原始图然后正是通过本发明的方法修改了的那张图。已测量和已修剪图二者都可以通过一个相应的邻接矩阵表示。我们在这里使用协定：′邻接矩阵A′是指原始图的邻接矩阵。本发明的每个方法都修改这个矩阵。为了注释简洁，我们对于任一方法把如此修改了的矩阵表示为MSK(在此，MSK代表′陷补救′)。
本发明使用′元图′的概念以便找到处理陷的新方法。对于任何给出的有向图，如下从原始图形成元图：
●找到所有的SCC。
●用单个′元节点′代替每个SCC。
●SCC内部的链接从而被忽略。
●SCC之间的链接保持不变。也就是说，从SCC_a中的某些节点到SCC_b中的其它节点的有向连接变成从元节点a到元节点b的链接。
结果元图没有循环——即(在此有向链接暗指有向流)；元图仅仅由一个方向上(从源到陷)的流组成。这样一个图被称为一个′有向非周期图′(DAG)。
从图2的示例图形中获得的元图如图4所示。在这里很显然：任意流在一个方向上移动——从′源区′(1，2)经由中间区域到陷区域(6，7，8)和(10，11，12，13)。
在标准的文献中可了解被称为″挤压图″的一个密切相关的图形。除了它没有给出关于所有的SCC间链接的信息之外，它与元图相同。相反，它只是给出每对SCC之间的所有链接的方向(如果存在任何链接的话)。因此，挤压图是与元图相同的DAG，可是，每对SCC之间的所有并行链接被单个链接替代。元图和挤压图之间的这个区别在下面的讨论中将很有用。图2的挤压图如图5所示。
本发明合并了用于解决陷技术问题的两个新方法。这两个新方法都采用挤压图作为它们的出发点。因此，我们用三个步骤来呈现新的解决方案：
找到挤压图
方法1(反转链接)
方法2(泵压源)
找到挤压图
找到一个有向图的SCC是一种用可用的标准算法已经解决了的问题。这种解决方案的一个重要的方面是：它″随图的尺寸是线性的″——也被表示为″N阶的″或者更简洁地表示为O(N)。在这里，″图的尺寸″被视为节点(文档)的数目，即N。这是指随着图形增大，解决这个问题需要的时间量只是随着图的尺寸(节点数，即：N)线性增长。SCC算法随图尺寸的这种缓慢增长对于目前公开的方法对大图的应用性很重要。许多文档系统具有巨大的文档数量——例如，环球网的尺寸现在估计大约为40亿个文档。因此，被应用到大图的任何方法都绝不需要随图尺寸N非常快速增长的计算或存储；并且线性的O(N)增长是当前可接受的科技发展水平。
涉及稀疏矩阵的任何方法计算节点权重将需要这样一个计算时间，该时间随图尺寸至少线性地增长。即：节点权重计算需要被邻接矩阵重复相乘。如果邻接矩阵是稀疏的，那么它里面的非零条目数目将是O(N)——即，与图形中的节点数目成比例——并且因此每次乘法将要求与N线性增长一次。然后，如果迭代(乘法)数目根本没有随图尺寸增长，则总计算时间也将随N线性增长。有证据说明PageRank计算需要只是随图尺寸弱增长(即使有的话)的若干迭代(参见T.H.Haveliwala的Efficient Computation of PageRank，斯坦福大学技术报告，1999，其全部内容在此通过参考被合并)。因此，PageRank计算并且推断诸如在美国专利申请10/687,602中公开的方法之类的类似技术可能只是随图尺寸线性增长。
简而言之：节点权重计算所需要的时间随节点数目(图尺寸)N线性增长(或者也许比线性稍微快一点)。因此，找到已知只随N线性增长的SCC所需要的附加计算时间是完全可接受的。
SCC查找算法的存储要求也是可接受的。例如，Tarjan的算法需要存储所有节点，因此存储需求为O(N)。(参见Robert E.Tarian的Depth-first Search and Linear Graph Algorithms，SIAM Journal onComputing，1(2)：146-160，1972，其全部内容在此通过参考被合并)。Tarjan的算法的一个改良版本需要甚至更少的存储。(参见EskoNuutila和Eljas Soisalon-Soininen的On Finding the StronglyConnected Components in aDirected Graph，Information ProcessingLetters 49(1993)9-14，其全部内容在此通过参考被合并)。
元图不但包含了有关所有SCC的信息；它还包括所有的SCC间链接。这个进一步的信息通常不可以从标准算法中获得。这些替代地给出“挤压图”，挤压图把所有SCC作为元节点(与元图相同)。可是，挤压图对定向链接的每对SCC通常只给出一个SCC间链接。(把示出完整元图的图4与示出挤压图的图5比较。)挤压图就这样示出了任意两个互相链接的SCC之间的流动方向；但是它没有对于本发明的方法给出足够的信息。因为两个公开的方法需要不同类型的附加信息(除挤压图以外)，所以每种方法被分别讨论。
方法1
方法1需要完整元图：它必须知道所有的SCC间链接(正如在图4的示例图形中看到的那样)，包括它们的开始点和结束点(可从图2中的完整图中获得)。
在典型情况下，稀疏有向图的邻接矩阵被存储为一个有序对列表。例如，如果链接u→v存在于该图形中，则在列表中将有这样形式的一行：uv。
假设有两个SCC：SCC_1和SCC_2；并且假设人们从挤压图(从标准算法获得)中已知它们被链接。最后假设链接如下：SCC_1→SCC_2。然后人们知道这两个SCC之间的所有链接始于SCC_1并结束于SCC_2。人们(同样从标准算法中)还知道哪些节点位于SCC_1中并且哪些位于SCC_2中。因此，人们可以扫描有序对列表(即，稀疏邻接矩阵)，寻找始于SCC_1中的一个节点并以SCC_2中的一个节点结束的所有条目。在最坏情况中，这将花费的时间等于链接数目——对于一个稀疏矩阵，它与节点数目成正比，因此是O(N)级的。如果邻接矩阵被分类(这是很典型的情况)——以使始于一个给定节点u的所有条目被归组在一起——则人们通常将不需要搜索整个列表；但是所需的时间在任何情况下都为O(N)级的。
因此，存在一种简单的算法，使用O(N)级的时间来查找所有的SCC间链接，因此将查找整个元图。给定完整元图，那么增加每个SCC间链接的反向不是问题。
例如：假设SCC_1和SCC_2有如下链接加入它们：
u1→vx
u2→vy
u3→vz
即，每个u节点位于SCC_1中，并且每个v节点位于SCC_2中。(注意：这两个SCC之间的所有链接具有相同的方向——与SCC_1和SCC_2是两个不同的SCC的假设一致。)
目前公开的方法于是建议通过增加如下链接使这两个SCC成为单个SCC：
u1←vx
u2←vy
u3←vz
因此，在本发明的一个实施例中，每个SCC间链接(即，元图中的每个链接)补充一个反向链接。在这里，我们回想一下：元图是从可能已被修剪的原始图中形成而来。因此，元图中的SCC间链接可能都被视为′优良的′链接；并且因此一个不偏斜的方法要反转它们全部。
在一个替换实施例中，只有SCC间链接的一个子集补充了一个反向链接。即，对于每对已链接SCC只要反转至少一个SCC间链接就可解决陷问题；并且有时候，人们可以反转甚至更少的SCC间链接，而仍然使整个图形强连接。通过只反转SCC间链接的一个子集可能引起利用这个灵活性有利的时机。
此外，给这些陷补救链接一个权重ε是可能的，它可以被调整以便给出最佳性能。在一个实施例中，ε的值被保持低于原始链接的值(它通常为一)。用这种方式可避免太强烈地扰乱原始图。
再一次参见图2和6，它们示出了方法1对一个简单图的影响：每个SCC间链接被给出一个相反的伙伴；并且不需要其它新链接。
最后，一旦通过方法1已经使这张图强连接，则人们可以使用邻接矩阵的任何非复合形式(正向或反向，标准化或非标准化)来找到节点权重以及节点排序。
方法1对图2的示例图形的影响如图6所示。增加的链接是虚线。图7示出了方法1对相应元图的影响，元图的未修改形式如图4所示。图7更清楚地示出了方法1对于每个SCC间链接只需要一个新的链接。即：对于这个简单图，方法1增加6个新的链接，而PageRank的随机冲浪运算符增加135个新的链接。对于极大的图形，两个方法之间的这种区别变得巨大。
方法2
方法2需要与方法1所使用的信息稍微不同的信息。方法2像方法1那样始于挤压图。每个这样的图形是一个非循环有向图，或者说是DAG。这样的图形始终有至少一个源和至少一个陷。如果权重被置于源(元节点)处，并按照元图中的箭头方向移动，则这些权重将从源流向陷，一般除了陷元节点之外，在任何元节点处剩下零权重。
可是，在图形邻接矩阵的行动下，权重被一个给定因子放大。对于诸如PageRank之类的标准化方法，这个因子小于等于一；而对于诸如Canright和Eng_-Monsen在美国专利申请10/687,602中公开的方法之类的非标准化方法，这个放大因子通常大于一。不管在哪种情况下，被视为与所有其它SCC(即，忽略全部SCC间链接)隔离的每个SCC有一个给定放大因子或者′增益′。
如果元图中所有源SCC的′增益′(i)相等，并且(ii)大于任何其它SCC的增益，那么权重流可以达到一个平衡分布，并且在图中每个节点处有一个正权重。换言之，当这两个条件保持时，则邻接矩阵的主特征向量在各处都为正。这个论点的证明可以在申请人在2004年5月2日递交给JACM将要发布的文章″Importance Functions for DirectedGraphs″中可以找到，其全部内容在此通过参考被合并
总地来说，条件(i)和条件(ii)都没有保持。方法2通过调整位于源SCC内的所有链接的权重来强迫两个条件都保持。这样做时，人们调节源SCC的增益，直到两个条件(i)和(ii)都满足为止。
方法2然后包括如下步骤：
首先，人们取用元图中的每个SCC，并且忽略把这个SCC连接到任何其它SCC的所有链接。即：每个SCC被认为是与其它SCC相隔离的。该方法然后对于每个SCC需要所有的SCC内链接——位于SCC内部的所有链接。这些可以通过一个基本上与方法1中被用来查找SCC间链接的过程相同的O(N)过程来查找。这然后为每个孤立的SCC给出完整的邻接矩阵。
人们然后使用期望形式的邻接矩阵(正向或反向，标准化或非标准化)来计算每个(孤立)SCC的增益(主特征值)。选择在这个步骤中使用哪个矩阵由这样一个矩阵来规定：该矩阵在计算重要性特征向量(参见下面)时被用于整个图形。即：在每个步骤中必须使用相同的矩阵类型。
接下来，人们确定哪个SCC是源SCC。在比O(N)更少(通常少很多)的时间内很容易地从挤压图中获得该信息：源SCC是在挤压图中只有出链接的那些元节点。
如通常情况那样假定有一个以上的源SCC；这些源SCC有不等的增益；并且至少一个源SCC的增益小于某个其它SCC的增益。然后目的是增大所有源SCC的增益，直到满足如下两个条件：(i)所有的源SCC必须具有相同的增益；和(ii)源SCC的公共增益因子必须大于任何其它SCC的增益因子。
具体地说，假设一个给定源SCC具有增益g，并且人们希望把它的增益增加到G＞g。在该实施例中，这里有这么做的一个不偏斜的方式如下：把给定源SCC中的所有原始的内部链接权重(其同样通常为一)乘以因子G/g。这个简单的变化将造成期望的效果。在源SCC由单个节点组成并因此没有内部链接的特殊情况中，人们可以增加从该节点指向它自己的一个′自链接′并且给这个链接一个增益G。
通过为所有的源SCC选择相同的增益G，同时确保G大于任何其它(非源)SCC的增益，则条件(i)和(ii)被满足。然后，如三个发明者(下面引用)的预印本中所示，完整的修改图的主特征向量(正如在这里详述的那样，唯一的修改是所有源SCC中的内部链接权重的调整)在图形各处将为正。因此，这样一个特征向量可被用作节点的重要性度量。
用这种方法，通过使G只是比在所有非源SCC之中找到的最大增益g_max稍微大一点，对原始图的干扰可以被保持得尽可能小。
在这里应该再三重复：在完整的修改图上用来查找整个图的重要性度量的矩阵必须是与被用来查找每个孤立SCC的增益的矩阵具有相同的矩阵类型(正向或反向，标准化或非标准化)。
在本发明的一个替换实施例中，只对源SCC的一个子集调整(增大)增益。可是常规规则仍然保持：被泵压(pumped)的源SCC的公共增益必须被选择为大于任何非泵压的SCC(不论是源SCC与否)的未修改增益。这么做的效果——如发明人的预印本中所示——是向非泵压源SCC中的全部节点给出零权重。同样，对于权重流只(直接地或间接地)依赖于非泵压源SCC的任何SCC也将得到零权重。尽管如此，对于某些源SCC，可能希望这么做。例如，假设一个源SCC由指向一个或多个SCC的单个节点组成，并且这些SCC可以从其它源SCC中得到权重。这个单个源节点因此指到图形的其余部分中(文档组)；但是没有文档指向这个节点。因此相对于完整的链接文档组，这个节点(文档)可能被判断为具有非常小的重要性。给这个节点一个增益G使得这个小源SCC注入和其它源SCC同样多的权重到图中。可能允许这样一个很小、几乎孤立的SCC注入那么多权重被判断为没有给出最佳结果。然后，在方法2的替换实施例中，人们可以选择不泵压一些源SCC——从而在得到的链接分析中给它们零权重。对于具有许多这样很小的、几乎孤立的源SCC的图形，使用本发明的方法1代替使用方法2可能有利。
如上所指出，选择不泵压一个源SCC导致向该源SCC中的节点给出零权重。这还意味着该SCC没有注入权重到图的其余部分中。因此，非泵压的源SCC可被认为已从图中被修剪掉。此外，在希望不泵压源SCC C_x——可是它的未修改增益g_x大于图形中任何其它SCC的增益——的情况(也许不太可能)中，人们面临两个选择而非一个。即，人们可以将所有其它源SCC泵压到增益G＞g_x；或者，人们可以只从图中修剪掉该SCC C_x。后一个选择允许把剩余的源SCC泵压到一个较低的增益，因此对原始图修改较小。这些选择的任何一个都具有向非泵压的SCC C_x中的节点给出零权重的效果。
可能希望不向这样的一个或多个SCC给出零权重：这些SCC是一个非泵压的源SCC的′下游′，而且对于权重，它们只依赖于非泵压的源SCC。例如，如果人们判断图3中的源SCC(1，2)不重要，并且选择不泵压它，那么下游的SCC(3，4，5)(并且在这种情况下，实际上是所有的其它SCC)将获得零权重。我们可以说在这种情况下，不泵压源SCC(1，2)使得SCC(3，4，5)成为一个′有效源′。更精确地：一个SCC是一个有效源，如果(i)对于权重，它只依赖于非泵压源SCC；并且(ii)如果从元图中修剪掉非泵压源SCC则变得一个源SCC。这个定义很有用，因为它建议了方法2的另外一个实施例。人们可以选择泵压任何有效的源，按照被用于任何其它源SCC的相同准则给它一个增益G。即：在图3中，如果人们选择不泵压SCC(1，2)，那么人们获得泵压SCC(3，4，5)的选择。
关于方法2应该澄清另外一个要点。即：诸如PageRank方法之类的某些方法使用一个规范化矩阵(如上所述用全矩阵修改了的)来计算节点权重。把一个图形的邻接矩阵标准化有这样的影响：具有陷的所有SCC增益为1，而所有其它SCC(包括源SCC)增益小于一。因此方法2只能以失去严格的标准化属性作为代价被应用到这样的情况——因为对于方法2，源SCC的增益必须被设置为大于1的某些值G。可是增益G只需要稍微大于一；因此人们可以认为严格的标准化的变化很小。在这种意义上讲，人们可以把方法2应用到标准化以及非标准化矩阵上。
图8说明了方法2对图2的示例图形的影响。注意：没有增加新链接。相反，单个源区(1，2)的′增益′被增强，用大阴影圆形表示该区域。对于一个具有多个源区的常规图，在应用方法2之后所有的都将具有相同的增强增益。
个性化
当前，对″个性化″搜索存在更大的兴趣。即：寻求这样一个搜索服务，该服务对于同一查询向每个用户不给出相同的答复，而是给出一个以某种有用的方法适合每个用户兴趣的答复。进一步简言之：对于个性化的搜索，查询答复应该取决于查询以及谁在查询。
目前，在找到个性化搜索的好方法的竞赛中还不存在明显的领先者。同样，还存在大量的各种方法。在此可以把注意力集中在一个自然并且容易遵循PageRank和WiseRank的陷补救方法的方法，以便指出本发明的陷补救还把自身容易引导到一个类似的个性化类型。
如上所述，PageRank和WiseRank用它变成稠密的这类方法来修改给定的邻接矩阵-事实上，它具有从所有节点到所有节点的链接。然而，所添加的链接用这样一个方法被权重，即它们的影响可以根据简单地向原始的未修改邻接矩阵的乘法结果添加一个权重列表(向量)。
即：假定M是邻接矩阵的期望形式，而M′是由所添加链接形成的矩阵，因此被修改矩阵的最终形式是M+M′。然后，对于每个节点的权重寻找通过使用重复乘以被修改矩阵而被完成。即，权重x的试验向量被重复地乘以矩阵M+M′，直到该权重向量收敛成一个稳定模式为止。
对于PageRank和WiseRank，被添加链接的矩阵M′具有这样一个形式，即大多数或所有的乘法可以被脱机完成：
(M+M′)x＝Mx+s
即，权重s的补充向量可以不用稠密矩阵M′来进行矩阵乘法而被计算。
对于PageRank和WiseRank的非个性化型式，补充向量s向每个节点(文档)添加相同的权重-然后如上所述，其主要效果是防止权重在陷区域中被陷入。然而，一个简单的个性化方法出现：人们可以偏置补充向量s，并且用对于每个搜索器都定制的方法来这样做。例如，如果搜索器具有一个兴趣档案P，(例如)被表示为一个具有每个关键字的权重的关键字列表，则每个文档u可以被给定一个分数P(u)(用已知的文本相关方法)。该分数表示文档有多匹配用户档案，并且对于每个用户和每个文档只需要被计算一次。然后，这些分数可以被用来形成一个个性化的补充向量：人们可以简单地将分数P(u)用于补充向量的第u个条目。这类个性化的补充向量的应用将产生更多的权重被给予在最终(收敛)权重中分数P(u)较高的页面。
因此，在PageRank和WiseRank方法中都出现的补充向量s可以被个性化，从而给出了个性化搜索。
然而，本发明的用于补救陷问题的上述方法没有在它们自身中产生这样的补充向量。事实上，很少的(方法1)或没有(方法2)链接被添加到原始图。尽管如此，通过使用在邻接矩阵自己的链接上有可能个性化权重的事实，目前公开方法还允许应用几十种形式的P(u)。例如，假定从文档u(具有分数P(u))到文档v(具有分数P(v))存在一个链接。在基于链接分析的排序中，每个链接都被看作是一种推荐。因此，对于个性化排序，根据″推荐者″(u)有多匹配用户兴趣来加权推荐(链接)是很自然的。因此，人们可以简单地通过分数P(u)来加权链接。
别的可能性将使用关于节点的分数可用的所有信息。即，人们可以不仅通过指向节点u的个人兴趣分数，而且还通过被指节点v的个人兴趣分数来加权链接。这样做的一个简单方法是通过和(P(u)+P(v))来加权每个u→v的链接。
其它变化也是可能的。通常在大多数情况下，人们可以选择(P(u)+P(v))的任何单调递增函数f(P(u)，p(v))。如果递增x或y(或其二者)得出该函数地增加的结果，则函数f(x，y)用x和y单调增加。因此，在其大多数一般形式中，本发明允许用(P(u)+P(v))的单调递增函数f(P(u)，p(v))来加权链接从而个性化链接分析。我们注意到，这类个性化的计算负担只不过是需要计算分数自身。这个负担对于任何使用这类分数的方法来说都一样。
总结以上所述：每个节点(文档)u可以被给予一个个人兴趣分数P(u)，其标识该文档有多匹配一个单独的用户兴趣。然后，个人兴趣分数可以被用来偏置从u指向v的链接的权重。每个链接u-v都可以被给予权重P(u)；或者替换地，每个链接u→v都可以被给予权重P(u)+P(v)。其它规则也是可能的，反映了如果链接指向具有高个人兴趣分数的节点或从那里被指向，则它们得到高权重的一般规则。然后，结果的个性化邻接矩阵A*(在链接上具有个性化权重)可以将标准邻接矩阵A(包括1和0的)代替为一个用于链接分析的起始点。即，个性化邻接矩阵A*本身是个性化后向矩阵B*；其转置是个性化正向矩阵F*；并且这些的列标准化型式分别是个性化规范矩阵b*和f*。本发明的方法1或方法2可以被应用到任何个性化矩阵。
简而言之：用于节点的个人兴趣分数可用于重新权重图形的链接。然后，使用方法1或方法2的链接分析(经由主特征向量)给出可以被用来排序节点的节点权重LA(u)。用于节点的个人兴趣分数P(w)是个性化的起始点，并且不应该与从链接分析中获得的最终节点权重相混淆。
其它的个性化形式可以与本发明相结合。在本发明的替换实施例中，被适当地权重的个人兴趣分数P(u)可以被组合到个性化的补充向量s中。即：我们可以用一个调节参数α来设置s(u)＝αP(u)。这个向量可以在乘法进程每次迭代时被添加到节点权重向量x：
xnew＝MSRxold+s
在此，MSR是用方法1或方法2规定的陷补救来修改的原始矩阵(正向或后向，标准化或非标准化)。然后，这个等式被一直迭代到节点权重x收敛为止；然后，结果给出了链接分析权重LA(u)。
这方法相当于向已修改的原始图添加一个完整图。因为这个事实，所以当使用这个形式的个性化时，人们事实上可以选择不使用方法1或方法2的补救；而是使用下面的一个迭代：
xnew＝Mxold+s
使用未修改的原始图M，加上前一段落中定义的补充向量。本发明的这个实施例不同于PageRank之处在于它使用非标准化运算符：M矩阵不是列标准化，并且补充向量s没有其条目之和的约束条件。因此，如Canright和Eng_-Monsen在美国专利申请10/687,602中所公开的方法所述，这个方法可以被用来基于F或B运算符来个性化链接分析。
只要列标准化的约束条件被丢弃，其它形式的补充向量就是可能的。具体地说，人们可以令
