网页信息搜索中特征向量方法.doc

网页信息搜索中特征向量方法

摘要：网页信息搜索比传统的小规模信息搜索更具挑战。传统信息搜索与网页信息搜索的主要区别在于后者基于网页的超链接结构。目前主流网络搜索引擎全都采用了这种方法，尤其是Google和Teoma。在这份调查报告中，我们将着重考察那些使用特征向量算法的网页搜索，并展示三个最流行的模型：HITS，PageRank, SALSA。
关键字：特征向量，马科夫链，信息搜索，HITS, PageRank, SALSA
AMS 科目分类. 65F15, 65F10, 68P20, 15A18, 15A51, 65C40
DOI. 10.1137/S0036144503424786
1.简介
信息时代为信息搜索者带来了空前的机遇和便捷，同时也给信息搜索研发人员带来了空前的挑战。许多预言家声称，在不久的未来，信息爆炸将永无止境。然而，当用户在理论上有大量信息可搜索时，信息搜索的精度却令人大为失望，研发人员也只能持续改进系统。我们将从历史发展的角度来调查以现代线性代数为基础的信息搜索方法。
如今有多种信息搜索方法，从布尔型到概率再到向量空间模型。其中，向量空间模型与线性代数结合最密切。小型文件集合的向量空间法主要采用潜在语义索引的方法（LSI）。Berry，Drmac和Jessup撰写的1999年SIAM综合评论成功调查并介绍了向量空间模型，并为LSI着墨不少。LSI在术语-文件矩阵中借用奇异值分解法（SVD），从而能够捕捉潜在的语义联系。LSI由于能有效处理复杂的包括一词多义和同义词的索引而声名远扬。SVD让LSI天生就能将文件与术语整合成概念。例如，对同义词‘车’‘汽车’‘车辆’可归为一类，而一词多义词的集合可以根据不同意义分类（金融机构、陡坡、台球等）。然而，由SVD演变而来的LSI的鉴别能力也只能局限在小型文件集合中。术语-文件矩阵中SVD的计算和储存是昂贵的。由于在特定集合中文件数与术语-文件矩阵的列数相同，像万维网那样的巨量文件集合远远超出LSI的能力。
不仅万维网的巨量文件特性让久经沙场的算法失效，它的其他特性也使文件分析学面临巨大挑战。网络缺乏审查功能。因此，网页上包含了许多冗余文件、断链和一些低质量的文件。而且网络也是持续更新的，因为网页能随时加入或退出网络。网页信息的不断变化留给了信息检索研发人员两个选择：要么持续规则地更新要么牺牲精度换取便捷。网络也具有潜在的商业价值，以至于有些用户故意欺骗IR系统以获利。例如，有为网页作者写的在不同IR系统中“刷新排名”的论文。理论上，IR系统不会受这种欺骗误导。但用户对排名机制的青睐也加剧了IR系统面临的挑战。用户常常输入简短的索引词，几乎不利用反馈信息修改搜索的词汇，也很少使用系统的高级用法。他们往往只关注反馈的前10到20个结果。这些倾向性使IR系统中速度和精度成了技术关键。本文最关键的部分就是网络特有的超链接结构的介绍。这个内在结构提供了额外信息以改进IR系统。
超链接结构被三种最主要的IR方法使用：HITS（超文本诱导话题搜索）PageRank 和SALSA。HITS 由Jon Kleinberg在1997年开发而成。不久，Sergey Brin和Larry Page研发了著名的PageRank方法。SALSA为应对HITS和PageRank的缺点而在2000年研发完成。
2.网络超链接结构的使用
每个网页/文件在网络的整个操作图中扮演了节点的角色。节点间的有向连线代表了文件间的超链接。图一是网络操作图的样本。
图一 6节点网络超链接结构样本
网络搜索特征向量方法

HITS的IR方法定义了授权者和收集者。授权者在文件中有几个链入 (Inlink：指向某页面的链接。一般而言，这个链接应该来自某个特定集合以外的页面，例如，一个网站的链入就是其他网站里任何页面指向该网站里任何页面的链接。类似地，一个网页的链入就是其他网页指向该网页的链接。“链入”与“反向链接”同义；“接受链入” 与“被链接”同义。) 见图一。收集者对应链出 (Outlink：从某页面链出的链接。一般而言，这个链接应该指向某个特定集合以外的页面，例如，一个网站的链出就是该网站里任何页面指向其他网站里任何页面的链接，类似地，一个网页的链出就是该网页指向其他网页的链接。）见图二。
图二 授权（Auth）节点和收集（Hub）节点

HITS的论点是：好的收集者指向好的授权者，好的授权者被好的收集者指向。HITS给每个网页分配一个收集者分数和一个授权者分数。例如，特定页的授权分越高，其权威性就越高。
另一方面，PageRank用超链接结构将链入视为其链入作者对该网页的推荐。来自优秀网页的链入（有高度地位的作家）比边际网页具有更高权重。每个网页都能被分到一个恰当的PageRank分数以评估该网页的重要性。图三刻画了PageRank的论点。粗线表示重要网页具有的额外权重。
这两种衡量网页重要度的想法既联系密切又各表一枝。在接下来的几节，我们将轮流分析这两个IR方法。
3.HITS。
我们重复一下HITS的论点：好的授权者被好的收集者指向，好的收集者指向了好的授权者。第i页有授权分和收集分。令E是网络操作图中所有有向边的集合，表示从节点i到j的有向边。每页在初始都分配到授权分和收集分。HITS通过计算相继完善这些分数。
图三 PageRank理论（粗线表示重要网页具有额外权重）

和 k=2,3,…
这些方程可通过相邻矩阵L化为矩阵形式。

例如，在图四中L可写为：

在矩阵表示中（3.1）中的方程为

由此导出了以下的迭代算法以计算最终的授权分x和收集分y：
1.初始化： ,e是一列元素全为1的列向量。其他正项初始向量也可使用。
2.直到收敛

标准化
图四 小型四点网络节点链接操作图

网络搜索特征向量方法

在算法的第二步，

能被化为

这两个方程是计算 和 主特征向量的迭代幂法。由于决定了授权分，因此被称为授权矩阵，而被称为收集矩阵。和是对称半正定矩阵。计算授权向量x和收集向量y就意味着分别寻找和的右手特征向量。
3.1.HITS的实施.
HITS的实施包括两个主要步骤。首先，建立与搜索词汇相近的临近操作图N。其次，每个在N中的文件授权分和收集分将被计算并且最具权威的文件和最具收集力的文件将按排名陈列给用户。由于第二步在前一节中已有叙述，我们将关注于第一步。所有文件所涉及的词都被放入临近操作图N。有不同的方式确定这些文件，一个简易的方法是访问反转文件。这种文件如下：

对每个词，文件声明：词汇将储存在列表中。对词10和11的索引将把文件15, 3, 101, 19, 1199, 673, 56,94, 和 31 放入 N。接下来，N中子集邻近的操作图将通过增加或是指向N中节点、或是由N中节点所指向的节点而扩充。该扩充将生成基于潜在语义的联系。即若搜索词汇‘车’，由于包含单词‘车’的文件已扩充，一些包含单词‘车辆’的文件也加入了N，由此就更有希望解决一词同义的问题。然而，由于扩充，集合N会变得非常庞大。一个包含索引词汇的文件可能具有巨量的入度和出度。在实际中，N中的特定节点其链入和链出最大节点数是固定的，比如100。即只有文件前100个包含了索引词汇的链出节点会加入到N中。建立邻近操作图的过程与信息过滤联系紧密。信息过滤将稀疏矩阵降维到更小但索引更多的矩阵中。
一旦建立了集合N，就构建了邻近矩阵L在N中的对应节点。L的秩远比网络中节点总数小。因此，用和的主特征向量计算授权分和收集分的代价较小。若把网络中所有文件放入N，计算授权分和收集分的代价将大很多。
还有一个降低计算成本的方式：只计算一个文件的特征向量：和的特征向量之一 。例如，授权向量x能通过计算主特征向量获得；然后收集向量y能通过y = Lx获得。换种顺序求解也可行。
3.2. HITS收敛
计算HITS向量的迭代算法实际是将幂法运用到了和中。对于对角矩阵，其特征值为{λ1, λ2, . . . , λk}，使|λ1| > |λ2| ≥ |λ3| ≥· ·· ≥ |λk|，若初始向量，幂法通过迭代步骤

是由导出的标准化的标量。例如，将作为最大级的一部分（若有多于一个，取第一个）， 收敛到主特征值λ1，收敛到相关的标准化的特征向量。如果只使用一个主特征向量（但不是λ1），那么就可以使用。（如果λ1 < 0，那么不能收敛到λ1，但是 仍可收敛到与λ1有关的标准化特征向量。）
和是对称半正定阵，非负，因此，特征值{λ1, λ2, . . . , λk}非负为实，且λ1 > λ2 > · · · > λk ≥ 0。换句话说，谱半径上无重特征值。HITS使用幂法的专业性极大避免了收敛的差错——标准化HITS总能收敛。然而，关于授权向量和收集向量极限的唯一性问题是需要讨论的。当λ1 > λ2，L的结构可能允许λ1是特征多项式的重根。相关的特征空间可能是多维的。这意味着不同的授权向量和收集向量的极限可由不同的初始向量得出。在例子中，

授权矩阵和收集矩阵和有两特征值分别是λ1 = 2 和 λ2 = 0,，每个都出现两次。，幂法（用1范数）收敛到 。但对，幂法收敛到。唯一性问题的本质就是可约性。
方阵B可约，当存在排列阵Q使得，X和Z都是方阵。
若不然，B不可约。Perron-Frobenius定理确保了一个非负不可约矩阵具有唯一标准化正主特征向量，称为Perron向量。因此，是矩阵的可约性使HITS算法收敛到唯一解。
PageRank遇到同样的唯一性问题，但Google的创立者建议校正矩阵，迫使其具有不可约性并确保排序向量的存在性与唯一性——见4.3节。与Google技巧相似的校正也可用于HITS算法。
最后一个有关幂法的注意点是初始向量。一般，不论迭代矩阵B的主特征值λ1是单独还是重复的，只要初始向量不在范围内，就能使迭代收敛到非零向量。如果是随机生成的，基本肯定这种情况可以成立，所以在实际中这其实并不是个问题。Farahat等人开发了HITS的改进，称为HITS的指数型输入，其中改进了以上提到的一些收敛性问题。
3.3. HITS例子
我们现将展示HITS算法的实施实例。首先，用户在HITS IR系统中输入索引词。有几种方案可以确定哪些节点包含了索引词。例如，可以取用使用至少一个索引词的节点。或建立一个较小的稀疏图，然后仅取用那些使用了全部索引词的节点。在我们的例子中，假设包含索引词的节点子集为{1，6}。那么，文件1和6包含了索引词。然后，建立关于节点1，6的相邻操作图，形成操作图N，如图5。
图五 N：文件1和6的相邻操作图

由N生成相邻矩阵L：

授权矩阵和收集矩阵如下：

授权分x和收集分y的标准化主特征向量为

在实际中遇到的大型矩阵，不可能在主特征向量中出现相同值。使用“先来先服务”的策略，授权和收集分能按重要度排序如下：

即文件6对索引有最大授权分，文件1对索引有最大收集分。
3.4.HITS优点和缺点
HITS算法的优点在于其提供双排名。一个告诉用户对索引具有最大授权能力的文件，另一个告诉最大收集能力的文件。HITS通过寻找小矩阵的主特征向量使网络搜索问题简化。相比网络文件数而言，这些矩阵非常小。
然而，HITS缺点也非常明显。HITS索引的依赖性是主要问题。在搜索过程中，必须建立相邻操作图，至少需要计算一次矩阵特征值问题。每次搜索都必须执行这些操作。HITS对于“刷排名”的敏感性造成了其第二大缺点。从用户页面加出或加入的链接能造成用户页面授权分和收集分的轻微变动。这些分数的轻微变动可能提升一些页面触点从而反馈给IR用户更高排名。通常 IR用户在排名中只关注前20名，广告效应和经济利益促使网页作者提升这种排名。从网页作者的角度来看，从一网页加外链比把链入加入该网页要轻松的多。因此，不难影响用户的收集分数。由于授权分和收集分相互依赖，当收集分增加时授权分也会增加。同样，相对总体网络而言相邻操作图是微小的，因此链接结构的局部变化也会变得可观。Bharat和Henzinger提出了改进的HITS，用L1标准化步骤来缓和“刷排名”的问题。
HITS最后一个缺点是“主题位移”（链接与主题无关）。在为索引建立相邻操作图时，很有可能一个具有高授权但与主题无关的文件被链接到了包含索引词的文件中。这个高授权文件权重高到足以使其以及其相邻文件主导其反馈给用户的相关排名，使搜索结果与主题文件内容相左。Bharat和Henzinger提出一种方案，通过测量索引的相关度来权衡N中节点的授权收集分。事实上，为测量N中节点的索引相关度，他们采用了向量空间法（例如LSI）中常用的余弦相似度算法。
3.5.HITS与文献计量学
HITS的IR算法与文献计量学的研究关系密切。文献计量学是对文献及其引用结构的研究。该研究用文件主体的引用结构来进行论文重要度和影响度的数值测量。Ding 等人发现了HITS和两种文献计量学概念——共指引用和共指关系三者之间的深层联系。
在文献计量学中，共指引用是指两份文件都被同一份第三方文件引用。共指关系是指两份文件都指向同一份第三方文件。在IR中，共指引用是指两个节点共享同一个链入节点，共指关系是指两个节点共享同一个链出节点。Ding 等人 发现HITS的授权阵直接对应‘共同引用’，而收集阵对应‘共同关系’。假设再次研究图四中小型超链接操作图，相邻矩阵如下：

于是，授权阵与收集阵为

Ding 等人 发现，是对角阵，对角线上元素为每个节点的引用次数（入度）。是共同引用矩阵。例如，阵中3行3列位置的元素表示节点3有2次引用次数（入度为2）。阵中1行3列位置的元素表示节点1和节点3共用一个链入点：节点2，由图四易得。中4行3列位置的元素表示节点3和节点4不共享一个链入点，由图四易得。类似的，收集阵为，是出度对角阵，是共指关系阵。阵中1行2列的元素表示节点1和节点2共用一个链出点，节点3。阵中4行2列元素表示节点4和节点2不共享一个链出点。Ding 等人利用授权与共同引用以及收集与共指关系之间的联系，指出：链入排序给出了HITS授权分较好的近似值，链出排序给出了收集分较好的近似值。
我们即将结束本节。现在，HITS已经并入了IBM在Almaden 研发中心的CLEVER计划，它也成为搜索引擎Teoma使用的底层排序技术的一部分。
4.PageRank
1998年（同年HITS诞生），Google创始人Larry Page和Sergey Brin创立了PageRank概念并将其作为搜索引擎的基石。正如Google网页所述：“PageRank是我们软件的核心…它为我们所有的网页搜索提供了工具。”通过排除HITS内在缺陷，PageRank成功使Google跻身世界级搜索引擎的行列。
PageRank现在更关注搜索时间的节省。这使用户能在搜索时间内几乎立刻得到按索引词条相关度排序的页面。PageRank靠“投票”机制评定网页的重要度，即通过网络其他网页的链接来确定该网页的重要度。其思想是：来自重要网站的链接比来自次要网站的链接具有更高权重。“得票”网页的重要度需以“投票”网页的已知重要度除以被其链接的网页总数，最后求和来计算。即定义网页P的排名

此为递归定义。要达计算要求还需证明收敛性。若有n个网页，初始排名，则可迭代计算（4.1）
设并迭代计算（4.1）
是从页指出的链接数。这里又用到了幂法。若极限存在，PageRank向量可定义为且第i个即为的PageRank。这是原型思想，出于实际与理论的考虑（确保收敛性、制定排名、调整收敛率），校正矩阵P成了必须。4.3节讨论如何校正矩阵。
4.1.Markov模型
Google初始矩阵P非负，行和为1或0。0行表示该页无指出的链接（外链）——或称此为死点情况。若人为加入适当链接使所有行和为1即可认为网络中不存在死点，并称此P为行随机矩阵。这表明PageRank迭代是Markov链的进化形态。更确切的说，此时Markov链在Google数据库网页的链接结构图中随机游动。例如，考虑按图一连接的6网页微型网络超链接结构。Markov模型用随机过渡阵P刻画了微型网络操作图。P中元素是从i页到j页的跳转概率（鼠标的一次点击）。假设，从任何节点出发，到达任意另一节点的概率相同，

这就是（4.1）刻画的微型网络Google初始阵。当而，也可使用更准确的概率分布。
例如，若网络使用记录表明在网页2，用户跳转网页1的概率是其跳转网页3的2倍，则（P的第2行）可写为
依此类推可得其他行的变动情况。
一般，每个随机阵P的主特征值。因此，若PageRank迭代收敛，其必收敛到左手特征向量使得（4.2）（e是列元素为1的向量）。此为Markov平稳分布。这就是为什么Google能直观地给出每个网站的PageRank值：随着在网站上逗留时间的累积，用户永远都在随意点击链接。
4.2.PageRank计算
PageRank计算可归结为：解特征向量问题（4.2）或解类似的线性问题：当时使。这让PageRank的计算看起来很容易。然而恰恰相反，解的规模（现今Google数据库中包含超过80亿个网页）牢牢限定算法的选择范围。事实上，这是“世界上最大矩阵”的计算。直接法（即使利用稀疏性）和特征解法对这个规模的计算无能为力，只能求助幂法的变异型。据说，Google计算PageRank向量需要几天的时间。
4.3.矩阵P的校正
严格遵照网络超链接结构建立刻画PageRank的概率过渡矩阵会产生几个问题。
首先，Google的初始阵P可能不是随机阵，P可能出现行和为0的情况。用替换0行可以解决这个问题（n是P的阶数）。令新矩阵为。但此举不可一劳永逸。
另一个主要问题也由此产生：由于底层链可约而可能是可约阵。可约链包含使链停滞的状态集——通过状态再排序，可约链的过渡阵可规范化。

该矩阵表示，一旦达到集合的状态，链就不可回到的状态。
例如，若网页只包含一个到网页的链，且也只包含一个到的链，那么Google的随机访客只能永远在该两页中徘徊。这就是可约性的本质。
不可约Markov链中每个状态都一定能从其他状态达到。即对。不可约性是个极好的性质，它确保Markov链有唯一正的平稳分布向量，，该性质背后有Perron-Frobenius定理作支撑。
将Google初始阵P校正为就生成了随机阵，万维网的结构使几乎必为可约阵。因此还需为不可约性作进一步校正。Brin和Page使每个状态都能直接从其他状态得到，从而制造不可约性。起先，他们在中加了一个干扰阵，并构造
。Google认为该随机阵刻画了这样一种“瞬移”倾向，即用户会在命令行随机输入URL并跳转至任意页面（假设每个URL被选择的概率相同）。之后Google选用了一个更实际更灵活的干扰阵，“个性化”向量是随机向量，它使进入特定网页的概率具有独特性。更重要的是，从商业角度来看，若采用的形式，就可以通过校正来改变PageRank的排名从而实施商业策略。其他干扰阵也可使用，但是两随机阵P和E的凸结合，因此具有唯一平稳分布。现在，被称为“Google矩阵”，其平稳分布向量被称为PageRank向量。
在节点中添加直接路径制造不可约性的方法可能存在牵强之处。要最小限度制造不可约性，P阵首先规范化（4.3），然后将2行1列位置的矩阵块用一个非零矩阵替代。即

如此，将不可约。当然也可使用其他方法制造不可约性，但Google似乎更青睐。
此外，Google还得到一个意外收获，的特征广义函数被改进了。正如先前所述，幂法渐近收敛率由主次特征值的分离度决定，Google矩阵中谱分别为，，则（4.4），（不论个性化向量在取何值，均如上）。另外，网络链接结构使（或至少）。因此，若选取远离1，则能扩大1和的分离度从而加快PageRank的收敛速度。Google初定，这也让。由于，这表明经过114步幂法迭代，Google的PageRank计算能得到精度为的结果，比实际要求的精度更高。作为结论，最大限度不可约方法相对最低限度不可约方法更大地改变了链的本质。
最低限度不可约阵和最大限度不可约阵的实验性比较可能会得出一些有趣结论，包括对用户行为模式的研究和PageRank对干扰阵的敏感度分析等。
4.4.PageRank的实施
注意，PageRank是给每个网页重要度评分而不是给相关度评分。因而PageRank只是PageRank排序机制中的一部分。事实上，PageRank要与其他分数结合才能给出综合评定。为简化，我们将采用PageRank中的基本模型。在本模型中，PageRank的IR系统实施包括两个步骤。首先，对所有文件扫描以确定包含索引词的节点子集。这个子集称为索引词的相关集。这与HITS的第一步类似，即建立相邻操作图。第二步，将相关集根据集中每个文件的PageRank分数排序。因此，PageRank不依赖索引。事实上，每个文件都有独立于所有索引的PageRank分数。据报道，Google每几周就会计算一次所有网络文件的PageRank分。如先前所述，计算PageRank分代价不菲。寻找动辄数十亿阶的不可约随机矩阵的平稳向量耗时耗力。在此情形下，Google除了使用幂法，别无他法。为Google矩阵计算PageRank向量的步骤可描述为：设定参量，并使，n为P的阶数，然后按（4.5）迭代直到达到收敛要求。
（4.5）式有以下目标。第一，方法不损坏矩阵内在稀疏性。第二，要求内积稀疏，且易并行实施。对此规模的问题并行实施是必须的。更先进的迭代系统 / 特征算法在理论上加速了收敛，但在实际中，由于其巨量的存储需求和计算复杂度使计算不可实施。Brin和Page声称简易幂法拥有更高收敛速度——一个阶数为322000000的矩阵P经过50步迭代就能得到结果。
近年来关于PageRank算法和实施步骤的改进大部分由Stanford的研究人员提出。Arasu 等人.,提出用Gauss-Seidel方法取代简易幂法。他们在某次测试中声称得到更快的收敛速度，且在迭代的初始阶段加速尤为明显。另一组Stanford研究人员Kamvar 等人.,对幂法作了改进并提高了收敛速度。有一种与Aitken方法类似的二次方程外推法能提高PageRank向量的收敛速度。结果表明，相对基础幂法，该方法提高了50-300%的速度且只增加了非常小的费用。同组的研究人员也研发了BlockRank算法，它用聚集方法以因子2加快了收敛。最后一个算法用自适应方法监测PageRank向量中每个元素的收敛情况。只要这个向量中元素达到收敛要求，计算便可停止。实验证据表明每步迭代使工作量减少的同时其收敛速度也提高了17%。在近期的一些工作中，研发人员将根据死点与非死点的情况把矩阵划分为2个区域，然后采用聚集法，通过将所有死点归一（死点占网络节点总数的25%）来使问题简化。这些算法最迷人的性质在于，它们互不排斥。事实上，可以将几种算法结合以得到更快的收敛速度。
4.4.1.PageRank的收敛
PageRank中只涉及幂法的使用，这引发了一些争论。由于迭代阵是随机阵，谱半径。若可约，其在单位圆上可能有几个特征值，使幂法不收敛。这种问题被Brin和Page视为“排序陷阱”：一个没有外链的节点在每一部迭代后积聚越来越多的PageRank值。排序陷阱其实是Markov链中的吸收态。更一般地说，一个可约阵可能包含一个吸收类并使所有PageRank值陷入该类中的某一状态。网络图中可能包含一种类，使长期运行链的概率极大依赖于初始向量的选取。从长期运行来看，某些状态或类可能产生0秩，给出PageRank问题的无意义解。相反，若矩阵不可约，收敛情况将明朗的多。
对不可约随机矩阵，在单位圆上只有一个特征值，其他特征值的模严格小于1。这意味着对不可约随机阵P，使用幂法必将使迭代收敛到唯一的主特征向量——Markov矩阵的平稳分布向量和Google矩阵的PageRank向量。这也是Brin和Page加入“经验系数”矩阵制造不可约性的原因之一。不像HITS，它没有关于排序向量的唯一性问题，并且任何正概率向量都可用于初始迭代。
然而，即便对不可约随机阵使用幂法，收敛速度的提高仍是个棘手难题，特别是当矩阵-向量的维数以十亿计量时这种矛盾变得特别尖锐。与HITS不同，Google的PageRank考察的是整个网络的文件。如先前所述，渐近收敛率由的速率决定。（4.4）式渐近收敛率为的速率（不论向量在中的值为多少）。网络结构迫使（至少）的概率极大，所以（4.5）式的收敛率可归结为的速率。换句话说，Google工程师们可根据取得多小来决定收敛率有多快。
因此，Google工程师们的任务便是寻找一种精妙的平衡。越小，收敛越快；但决定网页重要度的网络超链接结构引用也越少（可信度降低）。的微小改变能对PageRank结果产生非常大的影响。而当时收敛变得异常缓慢，敏感度问题也随之浮出水面。
4.4.2.PageRank的精度
PageRank计算中另一问题是精度。PageRank计算精度必须足够高，以区分Google反馈的大量排序网页。由于是随机向量，每个元素。假设是1行40亿列的向量，因为PageRank向量服从幂次法则或Zipfian分布，所以这个向量的尾部一小块部分可能以降序排列如下。此时精度必须达到以上以区分排序子向量中的元素。然而，在此排序向量中，元素间的比较只发生在整体元素的子集中。全体PageRank向量元素都被压缩在（0，1）区间内，而与索引词相关的子集元素所在区间的元素密度比前者小得多，因此在此应用中，的精度是一种浪费。
Brin和Page在50步迭代后得到一个322000000阶矩阵其的合理估计表明两点：1.他们对的估计不够精确。2.迭代阵的次特征值远离1。前者是在说外行无法证实内部信息，因为Google从未公布其收敛测试结果。后者是在说“经验系数”矩阵（或）一定有很高的权重，且可能小于0.8以扩大特征值分离度加快收敛。一边降低，一边增大“经验系数”，概率过渡矩阵便能从网络原始超链接结构中运行得更远。观察家们提出网络自然链接结构会产生一个可完全分解的Markov链或NCD子图Markov链。例如，有证据表明，网络中的某部分，如非洲网络，就是绝对的NCD。
NCD现象可能被加重的经验系数权重所掩盖。如果发现NCD现象，则将为IR研究和实施打开便捷之门，因为大量为NCD系统平稳向量计算的准备工作已经完成。
4.4.3.PageRank的更新
PageRank的更新是非常重要的。因为的计算非常昂贵，Google声称PageRank最多也只能每几周才能更新一次。在每次的更新周期中，网络结构早已发生巨变，这也让Google工程师们面临绝境——更新周期到底设为多长才不至于使花费巨大人力财力得到的计算结果失去时效性。此外，先前计算的PageRank向量对下一次更新中幂法的初始迭代几乎无用，这使PageRank更新问题火上浇油。不得已，Google每次更新PageRank都只能从头开始计算。
近期的一些研究就这个问题提出了一些见解。它们旨在使用前一次PageRank的计算结果并结合网络结构的变化对下一次PageRank的计算结果进行估计，从而避免从头算起的局面。但是这些研究只考虑了链接的更新而没有考虑节点的更新。添加、删除或改变超链接会改变链接的情况。从网络中添加、删除网页会改变节点的状态。节点的更新会影响P的大小从而引发极为复杂的问题。
Markov链的更新问题已有精解的算法，但不适用于PageRank更新问题。将经典算法应用于PageRank可能比重新用幂法计算更费时间和精力。近似更新算法的代价精解的小，并可得出较合理的PageRank估计。
对PageRank更新问题的研究非常活跃，最近的技术突破使链接和节点能同时更新。在这些研究中最有前景的算法是迭代聚集技术和幂法的自适应性加速。这两种方法能有效以因子10降低PageRank计算耗费的精力和财力。一些初步的研究表明，若这两者结合使用，更能极大降低算法耗费的精力——细节就要揭晓了。
PageRank就收敛性、精度、更新方面的实施问题只是数值分析者和IR研究人员近期研究内容的一部分。其他领域包括聚类问题和并行计算问题。
4.5．PageRank实例
在这一节中，我们将展示一个非常小且简单的例子来巩固上PageRank思想。考虑图六中6节点微型网络。
图六 小型6节点微型网络

首先，建立Google初始阵如下：

因为没有来自第二页的外链，所以P的第二行全为0，P不是随机阵。（Brin和Page将节点2视为排序陷阱。）将1/6加入第二行的每个位置修正该问题，得：

现在矩阵为随机阵，但不可约。因此它不具有唯一正的平稳分布。为制造不可约性，

此时矩阵既为随机阵也为不可约阵。平稳向量（PageRank向量）为

这些PageRank值是独立于索引词的。假设一个索引词包含词1和词2。可进去以下反转词段-文档文件：

因此，词段1和词段2的相关集为。
比较4个文档的PageRank值，通过按相关PageRank以确定重要度的排序。

最后，文档4是相关文档中重要度最高的。接下来是文档6,3,1。如果输入其他索引词段，能通过查询反转词段-文档文件迅速确定相关集，并能迅速通过PageRank值排序。PageRank对索引的独立性是不容忽略的。
4.6.PageRank与HITS的联系
Ding 等人展示了PageRank与HITS之间优美的关系。他们指出了PageRank分与HITS授权分之间的相似点。Ding 等人甚至延伸了这种联系来为PageRank建立“收集”矩阵。在文中，作者声称文档的链入数可以用来近似文档PageRank值。但是，我们和Pandurangan，Raghavan还有Upfal发现，这种近似非常粗糙。仅仅计录链入数就忽略了PageRank理论。如果节点被其他更重要的节点链接，那么它们自己也可被认为是重要的。链入数计数法能测量链接的数量而不能测量链接的质量。
4.7.PageRank优点和缺点
我们已经讨论过PageRank的一个缺点了——由精确确定相关度分数而造成的“主题位移”问题。Google工程师们必须应用试探法来确定相关度分数，否则，不论PageRank定得有多好，若反馈信息与主题无关，再精确的排序也会失去实际意义。这引发了新问题，为何重要度与相关度关系密切？到底有无关系？强调某些文档的重要性，是否会遗失某些没有知名度但与主题相关度很高的文档？Bharat和Mihaila很简洁地指出了PageRank的这一弱点。“由于PageRank是独立于索引词段的，它不能靠自身区分在普遍意义中具有权威的网页和就索引词段而言具有权威的页面。”由于Google的私有性，某些问题是不可回答的，但他们仍有很大的思考价值。
另一方面，对重要度而非相关度的应用是Google的成功所在，也是它的力量之源。通过测量重要度，HITS对索引依赖性的主要缺点也就不太注目了。PageRank对重要度的测量是独立于索引的。在极短的搜索时间内查询反转文件以确定相关集，随后靠预先计算的PageRank将其排序。
PageRank的另一优势是其对“刷排名”现象的屏蔽。正如HITS模型有关章节描述，网页作者很难从更高权重的网页取得链入链接。Chien等人证明，若网页作者成功取得链入，PageRank必定会提高。然而，这种提高是不合逻辑的，因为PageRank是对全球网页的测量。相反，HITS的授权分和收集分是从局部相邻操作图中导出的，入链和链出的微小变动会引发巨大的相关影响。因此，总的来看，网页作者几乎不可能有能力改变PageRank值。尽管如此，仍有不少文章描述了影响PageRank值的方法和识别“刷排名”企图的方法。
最后，Google有充分的自由定义经验系数矩阵，个性化向量是其灵活性的来源。的选择既不影响数学性质也不影响计算结果，但它的确可以主动地改变PageRank值。这让Google拥有极大得影响某网站PageRank值的自主权，它可惩罚专卖链接的网站，也可嘉奖他们欣赏的客户。外界虽对Google的奖惩范围没有利害关系，但Google却对那些企图操纵PageRank值的人异常警戒。