学位论文 > 优秀研究生学位论文题录展示

基于谷歌矩阵第二特征值重数的两类外推加速算法

作　者: 苟江涛
导　师: 白峰杉
学　校: 清华大学
专　业: 数学
关键词: PageRank 特征值计算预测加速算法
分类号: O151.21
类　型: 硕士论文
年　份: 2009年
下　载: 21次
引　用: 0次
阅　读: 论文下载

内容摘要

本文主要阐述了关于谷歌矩阵的理论结果以及用于加速网页排序的PageRank的计算的新算法。本文主要分为三个部分:一个有关于谷歌矩阵第二大特征值重数的定理,一系列有关两类基本预测加速算法的误差分析,以及两类新的预测加速算法和数值实验结果。首先,作者得到了谷歌矩阵的第二大特征值的重数是由相应的互联网图结构的不可约闭子集的数目决定的,这个定理使我们对于谷歌矩阵有了新的认识,同时指出了如何才能更有效地计算PageRank。其次,应用新得到的定理对于现有的预测加速算法进行了理论上的误差分析。第三,通过联合和归一化,本文构造了两类新的预测加速算法。接下来在特定网络结构数据集上进行的数值实验表明了联合预测加速算法相比较于原有的预测算法,收敛更快,表现也更为稳定,尤其是当阻尼因子(一个有关谷歌矩阵的预先设定的参量)比较接近于1时。本文的贡献在于增进对谷歌矩阵了解的新定理,以及加速PageRank计算的新预测加速算法。

全文目录

摘要  3-4
Abstract  4-8
第1章引言  8-14
  1.1 搜索引擎的历史和分类  9-10
  1.2 全文搜索引擎架构分析  10-14
第2章谷歌矩阵  14-21
  2.1 PageRank模型  14-16
  2.2 模型迭代速度和问题条件分析  16-17
  2.3 实际计算前的准备  17-21
    2.3.1 链接的存储  17
    2.3.2 转移概率矩阵的存储  17-18
    2.3.3 分块技术  18
    2.3.4 悬挂节点的处理  18-19
    2.3.5 迭代收敛判定  19-21
第3章关于特征值的理论结果  21-27
第4章误差分析  27-33
  4.1 A~d 预测算法的误差分析  27-30
  4.2 Aitken 预测算法的误差分析  30-33
第5章两类新的预测加速算法  33-38
  5.1 联合A~d 预测和Aitken 预测  33-35
  5.2 归一化简单预测  35-36
  5.3 预测加速算法的复杂度分析  36-38
第6章数值实验结果  38-48
  6.1 实验准备  38
  6.2 实验结果  38-46
  6.3 实验讨论  46-48
第7章结论  48-49
参考文献  49-52
致谢  52-53
附录 A C程序头文件  53-57
附录 B 数值实验数据集节选示意  57-59
个人简历  59

基于谷歌矩阵第二特征值重数的两类外推加速算法

内容摘要

全文目录

相似论文