求解PageRank向量的一种松弛多步分裂迭代方法

基于求解PageRank向量的内外迭代格式,引入一个松弛因子得到一种松弛内外迭代方法。结合已有的多步分裂迭代框架,引入两个不同的松弛因子,提出了求解PageRank向量的松弛多步分裂迭代方法并分析了算法的收敛性。更进一步地,利用松弛内外迭代格式构造了加速投影子空间方法的预处理矩阵,理论分析相关谱分布情况,并给出了松弛多步分裂迭代方法及预处理矩阵中参数的选取准则。几个数值例子验证了松弛多步分裂迭代方法和预处理矩阵的有效性,通过选取合适的松弛因子,与多步分裂迭代方法相比具有更高的运算效率。

基于PageRank的有向加权复杂网络节点重要性评估方法

现有复杂网络节点重要性评估研究主要集中在无向、无权复杂网络上,未能全面客观反映真实复杂网络的情况。本文基于有向加权复杂网络模型,借鉴PageRank排名算法,并结合复杂网络节点重要性评估特点,提出节点重要性评估的新指标———DWCN-NodeRank和相应评估方法,该指标既反映出节点局部连接的特性,又从全局体现了有向加权复杂网络中整体链接关系对节点重要性的影响。采用真实的复杂网络数据集所进行的仿真实验结果表明,该方法能快速、有效地评估有向加权复杂网络节点的重要性,提高了复杂网络节点重要性评估的实用价值。

PageRank算法的优化和改进

在PageRank算法中是使用乘幂法对网络链接图的Markov矩阵进行迭代计算,利用迭代矩阵A=[CP+(1-c)E]T中Google矩阵P的稀疏性,优化每次迭代的计算量并且减少空间存储量。在乘幂法证明理论基础上,提出了一种修正的外推方法称为线性外推法,并且利用Google矩阵的第二特征值的性质,使得在乘幂法的计算过程中达到快速收敛。从而在不增加空间存储的基础上缩短计算时间。最后结合实际数据测试,说明理论推导的结果达到了良好的实际使用效果。

Pagerank二维线性收敛方法

在幂法证明理论的基础上,利用特征向量二维线性表达的假设,给出了一种方法,使得当使用修正后的幂法计算Pagerank时,求特征向量的过程可以达到快速收敛,从而在不增加空间存储的基础上缩短时间消耗。最后结合测试数据,说明理论的推导结果实际上达到了很好的收敛效果。

一种求解PageRank问题的修正乘幂法(英文)

在现代搜索引擎技术中,PageRank算法发挥了非常重要的作用,通常用幂法计算描述Web链接图的Google矩阵的特征向量,然而当最大特征值与次大特征值不能很好地分离时,幂法的表现较差,主要原因是当阻尼系数接近于1时,算法收敛速度会很慢.因此开发较原有幂法更高效的算法是非常有价值的.本文提出了一个针对PageRank问题的改进幂法,数值实验表明了新算法的有效性.

一类修正的幂外推法加速PageRank计算

PageRank是网络信息检索和搜索引擎中的一种重要的排序算法.设计了2种改进的方法加速计算PageRank,即一种基于超链接的网页重要性评估,并详细介绍了改进算法的过程及算法的执行.数值实验结果说明了改进算法的有效性.

基于Power Extrapolation和Adaptive Method的网页评估新算法

Google的PageRank算法通过对超链接结构的分析,有效地提高了搜索结果的排序质量。PowerExtrapolation算法通过特征值直接求解马尔可夫超链接矩阵的主特征向量,但该算法的迭代次数与参数d的选择密切相关,而参数d的确定目前无明显规律可寻。另一方面,AdaptiveMethod通过将马尔可夫超链接矩阵稀疏化以达到节省迭代时间的目的。文章在PowerExtrapolation算法的基础上引入AdaptiveMethod,实验结果初步证明了新算法可以减少迭代运算的时间。

基于改进PageRank的多属性水网节点综合评价

针对有向赋权水网的特点以及复杂网络中节点评价的片面性,提出了一种基于改进PageRank的多属性水网节点重要性综合评价方法。首先,阐述水系网络的特点,提出了与互联网络的不同之处,同时在网络拓扑结构上从四个方面对节点进行了描述;其次,将PageRank算法应用到水网节点的重要性评价中,针对该算法在水网中的两个不适用性作出改进,再结合网络节点的综合属性进行重要性评价;然后,通过Krackhardt设计的数据集合风筝网络验证了该方法的一般性和有效性;最后,将该评价方法应用到某省的复杂水网重要性排序工程中。该方法综合考虑了网络的拓扑属性和水网实际情况,较为全面地评价了水网节点的重要性程度,对于水网调度和安全管理具有重要的借鉴意义。

一种适用于大规模的改进PageRank算法

在经典PageRank算法的基础上,提出了一种适用于大规模网页链接结构的改进PageRank算法-LSIPR。该算法利用大规模网页链接邻接矩阵的稀疏性,巧妙地使用了细胞数组,缩短了算法的计算时间和乘幂迭代的迭代次数。通过仿真实验表明,同改进PageRank算法、幂迭代PageRank算法和修正PageRank算法相比,LSIPR算法在大规模网页排名方面具有很好的收敛性,可以满足工程化应用的需求。

Google的PageRank技术分析

讨论了PageRank的计算方法,并对PageRank值的计算公式进行了修正,最后给出了改进的建议。

求解PageRank问题改进的多分裂迭代法

引用两种加速计算PageRank的算法,分别为内外迭代法和多分裂迭代算法.从这两种方法中,得到改进的多分裂迭代方法.首先,详细介绍了算法实施过程.然后,对此算法的收敛性进行证明,并且将此算法的谱半径与原有的多分裂迭代算法的谱半径进行比较.最后,数值实验说明我们的算法的计算速度比原有的多分裂迭代法要快.

高阶PageRank问题的一个两步分裂迭代算法

在一般PageRank问题的基础上,Gleich等结合了马尔科夫链的性质提出了高阶PageRank问题.基于Gleich等提出的几个算法,结合两步分裂迭代的思想提出了解高阶PageRank问题的一个两步分裂迭代算法.该算法能增加收敛的范围,并且减少算法的迭代步数.

结合AHP方法与PageRank算法对电网节点进行综合评价的应用研究

PageRank算法是由Sergey Brin和Larry Page发明的,其最初目的是在搜索引擎优化中用于评价网页的重要性,从而提高搜索结果的准确性。PageRank算法的核心是利用超链接技术和介度中心技术相结合的优化思想实现其功能。AHP方法是由A L Saaty提出的用于解决复杂决策问题的系统分析方法,其核心是将复杂问题分解为若干层次和若干因素,通过对若干因素进行简单的两两比较和计算,得到不同方案的权重,从而为最佳方案选择提供依据。针对电网节点综合评价问题,笔者结合AHP方法与PageRank算法,应用软件Matlab进行实验仿真,结果表明:在充分考虑电网节点权重和电网节点路径因素的影响下,能够对所有电网节点给出准确的综合评价。

PageRank算法的二级加速优化方案

为有效提高搜索引擎中网页排序的效率,针对当今PageRank算法优化方案的加速效果仍无法满足高速增长的网络规模所带来的数据处理需求现状,提出一种二级加速优化方法。对网络图邻近矩阵实行预处理,将其原点平移转化为等效矩阵,实现对幂法收敛速度的一级加速;提出一种改进的Aitken加速算法,应用到等效矩阵的幂法计算中,实现二级加速。实例仿真计算结果表明,改进的Aitken算法将原算法加速效率提升约25%,二级加速后的PageRank算法将原算法的求解效率提升约60%,优于类似优化方案加速效果。

求解PageRank问题的重启GMRES修正的多分裂迭代法

PageRank算法已经成为网络搜索引擎的核心技术.针对PageRank问题导出的线性方程组,首先将Krylov子空间方法中的重启GMRES(generalized minimal residual)方法与多分裂迭代(multi-splitting iteration,MSI)方法相结合,提出了一种重启GMRES修正的多分裂迭代法;然后,给出了该算法的详细计算流程和收敛性分析;最后,通过数值实验验证了该算法的有效性.

An adaptive improvement on PageRank algorithm

In this article, we introduce the Google＇s method for quality ranking of web page in a formal mathematical format, use the power iteration to improve the PageRank, and also discuss the effect of different q to the PageRank, as well as how a PageRank will be changed if more links are added to one page or removed from some pages.

带权网络的个性化PageRank计算

Page Rank是衡量网络节点重要性的指标之一,个性化Page Rank是普通Page Rank的推广形式.目前关于(个性化)Page Rank的研究主要集中在无权网络,而关于带权网络的研究结果较少.有鉴于此,基于矩阵变换和蒙特卡罗方法,分别给出了在静态和动态带权网络中个性化Page Rank计算方法,并从理论上分析了算法的性能.实验结果显示,两种算法都优于传统的幂迭代算法.

加速PageRank计算的方法研究

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

求解PageRank的修正多步幂-多分裂内外迭代法

在一种基于多步幂法和多步分裂的IO迭代的变体(用MPMIO来表示)的基础上,提出了一种IO(PIO)迭代的变式,将多步幂法和多步分裂的IO迭代的结合扩展到更为一般的情形,讨论了该算法的全局收敛性,并通过数值算例说明了该方法的有效性。

基于复杂网络的软件方法重要性评估指标

为了探究软件方法对软件系统性能的影响,在复杂网络理论的基础上对软件中方法的重要性进行了研究。介绍了一种可以准确描述软件结构的动态软件网络模型,并基于该网络模型结合PageRank算法的思想,提出了软件系统的方法重要性评估指标——PRW。通过与现有指标的对比实验,验证了PRW指标能够更加准确地对软件方法的重要性进行评估,也更适用于软件系统。PRW值较大的方法应该优先得到优化,这样可以有效提升软件系统性能。