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

论文摘要

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

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 研究的背景
• 1.2 目前国内外研究现状
• 1.3 本文的主要研究内容
• 1.4 本文的组织
• 第二章 马氏（Markov）链
• 2.1 马氏链的定义及性质
• 2.2 状态的分类
• 2.3 状态空间的分解
• 2.4 P"的极限性态与平稳分布
• 第三章 传统PageRank算法
• 3.1 算法解析
• 3.2 解PageRank值
• 第四章 PageRank新算法
• 4.1 传统PageRank算法缺陷
• 4.2 算法改进思想
• 4.3 初步实验结论
• 4.4 实验验证
• 4.5 小结
• 第五章 误差分析
• 5.1 矩阵的条件数
• 5.2 分析解PageRank值的条件数
• 5.3 提高近似解精度
• 5.4 小结
• 第六章 结论与展望
• 6.1 总结
• 6.2 展望
• 参考文献
• 致谢
• 附录