加速PageRank计算的方法研究

史 倩，张家健，张 伟

（1.河海大学 商学院，江苏 南京210000；2.江苏省邮电规划设计院有限公司 江苏 南京210000）

加速PageRank计算的方法研究

史 倩1，张家健2，张 伟2

（1.河海大学 商学院，江苏 南京210000；2.江苏省邮电规划设计院有限公司 江苏 南京210000）

网络矩阵的规模以及稀疏性导致了对求解方法的限制，并使得幂法占据了主导地位。但是幂法的收敛速度是缓慢的，尤其在网络规模的矩阵上运行的每次幂法迭代的时间和成本是高昂的。因此，其他加速PageRank计算的方法逐渐得到研究者的重视。文中首先对布尔搜索引擎、向量空间模型引擎、概率模型搜索引擎、元搜索引擎等基本搜索引擎模型进行综述，总结各基本搜索引擎模型的特征和优缺点。文中立足于加速PageRank计算的方法研究，并总结出自适应幂法、外插方法、BlockRank聚合方法的特征和优缺点。

PageRank；自适应幂法；外插方法；聚合方法

网络矩阵的规模以及稀疏性导致了对求解方法的限制，并使得幂法占据了主导地位。但是幂法的收敛速度是缓慢的，尤其在网络规模的矩阵上运行的每次幂法迭代的时间和成本是高昂的。减少迭代方法计算负荷的途径包括减少每次迭代中的计算量或者减少总的迭代次数，但是，两种途径的目标存在明显对立，即减少迭代次数会导致每次迭代中计算量的上升，反之亦然。因此，保持该额外计算量为最小值，那么加速方法即为可行。本文立足于加速PageRank计算的方法研究，包括自适应幂法、外插方法、BlockRank聚合方法。

1　基本模型

如何准确并快速地在巨量的信息世界中寻找到对自己有价值的内容？当然这离不开搜索引擎，影响搜索引擎有效性的因素有许多，但从根本上说，关键在于搜索引擎自身的链接算法设计。网络信息检索是在世界上最大且相互链接的文档集中进行的搜索，大多数搜索引擎依赖于以下基本模型中的一种或者多种：

1）布尔搜索引擎

信息检索的布尔模型是最早最简单的检索方法之一，它使用严格匹配来将文档与用户的查询进行比对。该模型经过改良的派生方法为大多数图书馆所使用。信息检索的布尔模型工作原理是考察在文档中有哪些关键词出现了或未曾出现，并据此判定文档与检索相关或无关［1］。但是标准的布尔引擎无法返回那些语义相关但关键词未被包括在原始查询中的文档。许多布尔搜索引擎要求用户熟悉布尔运算符以及引擎的特殊语法。布尔模型的各种变体构成了许多搜索引擎的基础，其优点包括：建立并编写布尔引擎是直接的；查询处理迅速，可以采用并行方式对文档的关键词文件进行快速扫描；布尔模型可以很好地扩展到大的文档集［2］。

2）向量空间模型引擎

该模型中，向量空间模型被用于避开前述的若干信息检索难题［3］。向量空间模型将文本数据变换为数值向量和矩阵，使用矩阵分析方法来发现文档集之中的关键特征和联系。一旦成立，即当相邻迭代所得的值之间的差别足够小时，便可锁定元素i，其中ε是一个微观容许限，自适应PageRank方法会锁定该部分页面，并且在之后的迭代中不再计算该部分页面。

1.2自适应幂法优缺点分析

自适应幂法的优点为：该算法对PageRank向量的计算进行了中等程度的提速，通过尝试减少幂法在每次迭代中的计算量，自适应算法为PageRank的加速计算做出了具有实用意义的贡献；自适应幂法的缺点为：尽管自适应幂法在若干数据集上表明它存在收敛，但是依然存在问题。首先，收敛性并未得到证明，算法可能收敛也可能不收敛。其次，即使存在收敛，最后的答案也有可能存在错误。因为在确定锁定的决策过程中，该算法仅考虑了短期的动态行为，所以并不清楚算法最终是否会收敛到真实的PageRank值上，或者收敛在某个比较粗略的估值上。最后，近解耦链的每个簇都会显示出短期的稳定性进而经过一段时间到达全局平衡点，最终的全局平衡点常常不具有类似于短期平衡点的性质，这就意味着自适应方法可能会过早地停止，并对耦链给出一个不精确的答案。

2　外插方法及其优缺点分析

该算法旨在减少幂法的迭代次数，幂法的期望迭代次数由次主特征所决定。假设G可对角化，并且。幂法的迭代如下：

式中Xi和Yi分别是G对应于λi的右特征向量和左特征向量，且γi=π（0）TXi。该式子表明，λK2γ2YT2在幂法中一直发挥作用，πT一直存在着，直到λK2→0，而当较大时，

幂法计算就需要大量时间。外插方法可以解决这一问题，即：

在该式中，（*）2表示对向量（*）逐元求平方。同理，如果λ2和λ3成复共轭，那么可以将其搁置，进行二次外插。

外插方法的优点为：外插方法可以实现中等程度的加速，二次外插能够以最少的额外计算将PageRank的计算时间有效缩短。外插方法的缺点为：首先，由于外插需要额外计算并保存接下去两次迭代的数据，因此它应该是每隔一段时间才使用一次。如果λ2和λ3成复共轭，即些高级向量空间模型能够访问文档集中隐含的语义结构［4］。该模型的优点包括：相关性评分，通过给每个文档赋予一个0到1之间的数，向量空间模型允许进行文档的部分匹配查询。该数值可以被解释为文档与查询之间的相关似然度。进而检索到的文档集可以根据相关程度进行排序。按照这一方式，向量空间模型以有序的列表返回结果文档，按照相关性的分数排序，返回的第一个文档被认为是与用户查询最为相关者，一些向量空间搜索引擎以相似度比例的形式给出相关性的评分。该模型的缺点为：必须计算每个文档和查询之间的距离度量，随着文档集的增大，矩阵分解的开销将使模型不再具有可行性［5］；向量空间模型无法很好地扩展，它仅局限于小文档集。

3）概率模型搜索引擎

概率模型试图对用户找到某个特定相关文档的概率进行估计，检索得到的文档根据它们的相关几率进行排名。概率模型以递归的方式运行，并要求算法能够猜测得到初始参数，进而逐次尝试改善这一初始猜测，以得到最终的相关几率的排位［6］。概率模型的缺点为：构建和编程难度较大，因此限制了其扩展性。同时该模型要求做出若干不现实的假设。该模型的优点在于概率框架可以自然地纳入先验偏好，可以做到针对单个用户的偏好调整搜索结果。

4）元搜索引擎

该模型将以上3种模型相结合，其工作原理是用一个搜索引擎来搜索可以完成任务时，用两个或以上搜索引擎搜索的效果更显著。一个搜索引擎可能在某个任务上十分出色，而第二个搜索引擎则可能在另一项任务上表现好于第一个搜索引擎。元搜索引擎可以充分利用许多单独的搜索引擎各自具有的最佳特性，可以同时将一个查询发送至数个搜索引擎，并将所有这些搜索引擎的结果以一个统一的列表返回。元搜索引擎可以应用于某个特定学科内的搜索［7］。

1.1自适应幂法

PageRank的目的是计算G的稳态向量πT，从技术分析可知，迭代求幂π（K）T，使得‖π（K）T-π（K-1）T‖1<τ，其中，τ是一个可接受的收敛判据。在整个迭代过程中，有两种方法可以得出每次迭代π（K）T与最终的解πT之间的距离：1）宏观的视角分析，计算‖π（K）T-πT‖1，并从宏观的角度考察当前迭代π（K）T与πT之间的距离，使用以上范数，各个元素位置上的误差被归总为一个单一的标量，进而可以得出总误差［8］。标准的幂法在每次迭代中采取该宏观视角，利用总误差‖π（K）T-π（K-1）T‖1来测试收敛情况，其中，页面以宏观的视角考虑收敛的标准幂法不能迅速的收敛到页面中所属的PageRank值。2）微观的视角分析，测量两个向量的各个单独元素在每次迭代中，π（K）T与πi之间的距离。其中，大多数页面都可以迅速收敛到它们最终的PageRank值，有些页面会比其他页面更快地收敛到它们的PageRank值［9］。值得注意，由于一小部分的页面需要更长的时间才能收敛到最终的PageRank值，因此幂法的运行时间被延时。随着PageRank向量的各个元素逐渐收敛，一时，该方法将占用较高的时间成本。其次，虽然二次外插可以有效减少计算时间，但是二次外插的计算代价高昂，只能每隔一段时间使用一次。

3　BlockRank聚合方法及优缺点分析

BlockRank聚合方法以实现两个加速为目标，即减少迭代次数以及每次迭代中的计算量，它将万维网的不同部分依据主站而归总到一起。在BlockRank开始时，它首先获取网络图，然后将其压缩为一个主站图。主站是高层网页，其下链接则是主站间的链接，他们将不同的主站链接起来，在全局的主站图中，内部链接可以被忽略。当PageRank模型应用于该主站图是，就会输出一个HostRank向量。主站I的HostRank排名给出了该主站的相对重要性。由于HostRank问题规模以原来的PageRank的问题小，由此可知，单个页面的重要性，而不是单个主站的重要性。为了获取全局PageRank向量，可以先计算每个独立站点内的页面的PageRank向量，这一过程仅使用内部链接，PageRank模型可以被应用于高层网页的每个主站。由此，可得到一个全局的为主站的数量，以及个局部PageRank向量，每个向量的大小为，其中为主站Hi中的页面数量。通过将主站Hi的局部PageRan向量乘以该主站的访问概率即可得出全局PageRan向量的近似值，访问概率可由HostRank向量的第i个元素给出［10-11］。

可以利用近解耦链分析BlockRank方法的聚合原理，在此先给出7结点的图。由于结点1，2，3和7之间有强内部关联，可将其视为主站1；而结点4，5和6则构成了主站2。BlockRank算法将这个7结点的图聚合为一个更小的2结点的主站图，与主站图相关联的转移矩阵为：

取值α=0.9和υT=（0.5 0.5），可知，该主站图的HostRank向量即主站图的谷歌矩阵的稳态向量（0.367 6 0.632 4），即在36.76%的时间内，随机浏览者均会访问主站1下的某个状态，即网页1，2，3和7。

图1　7个网页所构成的网络近解耦图

计算每个主站的局部PageRank向量，对主站1，超链接矩阵为：

在此过程中，求取H1时仅使用了主站内的链接，而所有主站之间的链接均被忽略，即3→4被忽略。对于α=0.9和VT=（0.250.250.250.25），主站1的局部PageRank向量为（0.167 10.317 50.348 30.167 1）。进一步分析，主站2的局部超链接矩阵为：

而主站2的局部PageRank向量为（1/31/31/3）。

最后的去聚合步骤将使用这3个较小的向量产生一个1×7阶的向量π～T，它近似与精确的PageRank向量πT，其中：

BlockRank聚合方法的优点为：首先该方法实现了两个加速为目标，即减少迭代次数以及每次迭代中的计算量［12］。其次，网络链在一定程度上是解耦的，因此只要进行了适当程度的主站聚合，BlockRan聚合方法就能够良好运行，而且对于近解耦马尔可夫链［13-14］，该方法可以减少计算稳态向量的工作量；BlockRank聚合方法的缺点为：BlockRank聚合方法得出的结果是有幂法计算所得的真实PageRank向量的一个近似［15］，因为该方法的每一步都忽略了某些链接，即某些有价值的信息在压缩或聚合的步骤中被丢失。大小的HostRank向量，其中

4　结　论

尽管不同的加速计算方法对加速PageRank计算提供帮助的这一方面已经展现了有效性，但是无论是自适应幂法、外插方法或是BlockRank，目前的研究都还不尽完善，尽管取得了进展，但都仅仅只是开始而已，如果实时个性化搜索能够得以实现，那就必须获得速度上的极大改进，这一改进也许通过创新型的新算法以达到，或许将当前的许多加速方法简单地合并为一个算法而得以实现。

［1］方永锋，陈建军.多状态可修复k/n系统的随时间响应可靠性研究［J］.高技术通讯，2016（2）：32-37.

［2］宋涛，基于二次聚类和隐马尔可夫链的持卡消费行为预测［J］.计算机应用，2016（5）:15-29.

［3］Gerard Salton and Chris Buckley.Introduction to Modern Information Retrieval［M］.McGraw-Hill，New York，2003.

［4］Susan T.Dumais.Improving the retrieval of information from external sources［C］∥ Behavior Research Methods，Instru ments and Computers，1991：221-246.

［5］Carl D.Meyer.Matrix Analysis and Applied Linear Algebra［C］∥SIAM，Philadelphia，2000.

［6］MichaelW.Berry and Murray Browne.Understanding Search Engines:Mathematical Modeling andText Retrieval［J］. SIAM，Philadelphia，2an edition，2005（16）:78-93.

［7］Paolo Boldiand Sebastiano Vigna.TheWebGraph framework II.Codes for the World Wide Web［C］∥ Technical Report 286-03，Universita diMilano，Dipartimento diScienze dell' Informazione Engineering，2013.

［8］Matthew Richardson，Petro Domingos.The intelligent surfer: Probabilistic combination of link and content information in PageRank［J］.Advances in Neural Information Processing Systems，2012（14）:1398-1399.

［9］Sepandar D.Kamvar，Taher H.Haveliwala，Christopher D. Manning，et al.Extrapolationmethods for accelerating PageRank computations［C］∥In Twelfth International World WideWeb Conference，New York，2003.

［10］Grace E.Cho and Carl D.Meyer.Aggregation/disaggregation errors for nearly uncoupled Markov chains［R］.Technical report，NCSU Tech.Report，2013.

［11］William J.Stewart Numerical experimentswith iteration and aggregationfor Markov chains［J］.ORSAJournal on Computing，2011，4（3）:50-336.

［12］Cleve B.Moler.Numerical computing with MATLAB［M］. SIAM，2004.

［13］Grace E.Cho，Carl D.Meyer.Aggregation/disaggregation errors for nearly uncoupled Markov chains［R］.Technical report，NCSU Tech，2013.

［14］William J.Stewart.Introduction to the numerical solution of markov chains［M］.Princeton University Press，2014.

［15］Ilse CF，Ipsen.Convergence analysis of a PageRank updatingalgorithm by Langvilleand Meyer［J］.SIAM Journaln Matrix Analysis and Applications，2006，27（14）：952-967.

Study ofmethod about accelerating PageRank calculation

SHIQian1，ZHANG Jia-jian2，ZHANGWei2
（1.Business School of Hohai University，Nanjing 210000，China；2.Jiangsu Posts&Telecommunication Planning and Designing Institute Co.Ltd，Nanjing 210000，China）

Scale and sparse network matrix led to restrictions on solvingmethod，andmakes the powermethod to occupy the dominantposition.Butconvergence speed is slow，especially in the network every time powermethod to run on the size of the matrix iterative time and cost is high.Therefore，other accelerate PageRank calculationmethod gradually got the attention of the researchers.This paper summarizes the basic characteristics and advantages and disadvantages of search enginemodel，including the Boolean search engine，vector spacemodel engines，search engines，metasearch engines.Finally，this paper analyzes the accelerate the PageRank calculation method of study，Summed up the characteristics and advantages and disadvantages including adaptive powermethod，extrapolationmethod，polymerizationmethod.

PageRank；adaptive power law；extrapolationmethod；polymerizationmethods

TN98

A

1674-6236（2016）19-0004-03

2016-02-24稿件编号：201602117

江苏省社科联研究基金（201035）；中央高校基本科研业务费项目（2010B10714）

史 倩（1987—），女，江苏南京人，硕士。研究方向：企业管理、技术经济。