基于PageRank排序算法改进的若干研究

全球资讯量最大,查询次数最多,知名度最高的搜索引擎是Google,而Google使用最久的排名算法就是PageRank排名算法。PageRank算法被广泛应用于度量网页重要性,它根据网页之间的链接结构来给每个网页打分,依据分数高低给出排名先后,从数学的角度来解释,可以被看作是一个马尔可夫随机游走模型,依据网页下一步的链接信息计算网页的转移概率,用马氏链的平稳分布作为最终的值给网页排序。 传统PageRank算法利用了Web的结构信息来判断网页的重要性,而且计算排名过程中将同一页面的所有链出页面看成同等重要,即对每个链出页面平均分配其PageRank值,本文认为这是传统PageRank算法的一个致命缺陷。本文通过分析传统PageRank算法的思想——每个链入页面看做是给自己“投票”的页面、重要页面的投票重要性高、票数多少决定页面重要性高低,得知同一页面的每个链出页面应根据其重要性的不同分得不同权重,从而给出了具有针对性的改进算法。理论上改进算法更切合传统PageRank算法的思想;通过Matlab实验迭代结果,比较传统PageRank算法和改进算法的计算结果,证明改进算法提升重要网页的PageRank值,降低不重要网页的PageRank值,而且能用d＜0.85的d值达到传统PageRank算法计算的PageRank值。 数值分析中,一个数值问题的条件数是该数量在数值计算中的容易程度的衡量,也就是该问题的适定性。一个低条件数的问题称为“良态”的,而高条件数的问题称为“病态”的。由于互联网上有成亿的网页,实际中计算排名不是解方程组而是用计算机模拟迭代计算其近似解,若一个方程组的病态程度愈严重,也就愈难用一般的计算方法求得比较准确的解。本文在第四章中通过讨论矩阵的条件数,分析其近似解的误差,证明降低阻尼因子d值能使求马氏链极限分布这个数值问题的条件数降低,即马氏链极限分布的近似解更精确。