网页排名PR值及其他：搜索引擎排序的科学

揭开搜索引擎的奥秘，全中文索引

艾米·N·兰维尔，是查尔斯顿学院的数学教授。
卡尔·D·梅耶，是北卡罗莱纳州立大学的数学教授。
他们是《谁排第一？关于评价和排序的科学》（机械工业出版社&普林斯顿大学出版社）的作者。

“（对）于任何希望深究PageRank如何运作的人而言，我都会向他们推荐《网页排名PR值及其他》。”
——斯蒂芬 H怀尔德斯特洛姆（Stephen HWildstrom），《商业周刊》

“（本书）对PageRank及相关的搜索引擎算法进行了综合而广博的介绍，并用一种平易近人的方式一一写来。”
——乔纳森（Jonathan），《时代·高等教育副刊》

“（一本）对搜索引擎如何运作感兴趣的人们的必读之作。”
——迈克尔 W贝里（Michael WBerry），《SIAM评论》

“（一部）优秀的作品。”
——伊安 D高登（Ian DGondon），《图书馆学报》

“如果我现在还正在修读或讲授线性代数的课程，那这本书将对我助益匪浅。”
——埃德盖斯特纳（Ed Gerstner），《自然·物理》

“《网页排名PR值及其他》对于任何希望了解搜索引擎细节的人——学生或专业人士——而言，都会是一次不错的阅读体验。”
——詹姆斯·亨德勒（James Hendler），《今日物理》

前言Ⅲ
第1章网络搜索引擎简介1
1 1信息检索简史1
1 2传统信息检索回顾5
1 3网络信息检索9
第2章网络爬行、索引建立和查询处理15
2 1网络爬行15
2 2内容索引19
2 3查询处理21
第3章通过欢迎度对网页排名25
3 11998年的情景25
3 2两篇论文26
3 3查询无关性30
第4章谷歌PageRank的数学31
4 1PageRank的原始求和公式32
4 2求和方程的矩阵表示33
4 3迭代过程问题34
4 4一点关于马尔可夫链理论的介绍36
4 5基本模型的早期修正36
4 6PageRank向量的计算39
4 7谷歌矩阵的谱定理及其证明45
第5章PageRank模型中的参数47
5 1α因子47
5 2超链接矩阵H48
5 3跳转矩阵E49
第6章PageRank的敏感性57
6 1对α的敏感性57
6 2对H的敏感性62
6 3对vT的敏感性63
6 4其他敏感性分析63
6 5有关敏感性的定理和证明66
第7章作为线性系统的PageRank问题71
7 1(I-αS)的性质71
7 2(I-αH)的性质72
7 3PageRank稀疏线性系统的证明73
第8章PageRank大规模实现中的问题75
8 1存储问题75
8 2收敛准则79
8 3精度79
8 4悬挂结点80
8 5对后退按钮建模84
第9章加速PageRank计算89
9 1一种自适应的幂法89
9 2外插90
9 3聚合94
9 4其他数值方法97
第10章更新PageRank向量99
10 1两类更新问题及其发展历程100
10 2重启幂法101
10 3使用近似聚合进行近似更新102
10 4精确聚合104
10 5精确聚合与近似聚合的比较105
10 6利用迭代聚合进行更新107
10 7确定划分109
10 8结论111
第11章HITS网页排名方法115
11 1HITS算法115
11 2HITS的实现117
11 3HITS的收敛性119
11 4HITS示例120
11 5HITS的优点与缺点122
11 6HITS与文献统计学的关系123
11 7查询无关的HITS124
11 8加速HITS126
11 9HITS的敏感性126
第12章网页排名的其他链接方法131
12 1SALSA131
12 2混成排名方法135
12 3基于流量的排名136
第13章网络信息检索的未来139
13 1垃圾信息139
13 2个性化142
13 3聚类142
13 4智能体143
13 5趋势与时间敏感搜索144
13 6隐私和审查146
13 7图书馆分类方式147
13 8数据融合148
第14章网络信息检索资源149
14 1入门阶段的资源149
14 2用于严肃的科学研究的资源150
第15章数学指南153
15 1线性代数153
15 2佩隆弗罗贝尼乌斯定理167
15 3马尔可夫链175
15 4佩隆补186
15 5随机补192
15 6设限194
15 7聚合195
15 8去聚合198
第16章术语汇编201
参考文献207
索引218

目的
作为教授线性代数的老师，我们希望能够撰写一本书，以帮助学生和普通公众去欣赏和理解线性代数在今天最为激动人心的应用之一——网络搜索引擎所使用的链接分析。这个题材天生就是颇为有趣、恰逢其时且为人所熟知的。例如本书将回答如下这些能够勾起人们好奇心的问题：搜索引擎是如何工作的？有的搜索引擎为什么如此优秀？什么是搜索引擎炸弹？我可以如何提高自己的主页在Teoma中的排名？
我们还希望这本书能够成为有关网络搜索引擎排名方面资料的独立而全面的来源。本题材已有大量的文献著作，但相关内容目前却散布于为数众多的技术报告、预印本、会议论文集、文章和讨论之中。在本书中，我们将对网络排名这门技艺的现状进行总结和清晰阐述，并加以浓缩和归类。
适宜读者
我们在写作本书时，考虑了两类不同的读者：一般性的对科学感兴趣的读者，以及技术科学方面的读者。书名体现了本书在技术层面上的内容，但除了增长技术方面的知识之外，我们还尝试给出若干与搜索引擎及其工作机理有关的有趣特性和轻松话题。
数学
我们写作本书的目的是能够满足一个很有挑战性的读者群，它由对科学通论感兴趣的公众以及对技术科学感兴趣的人群所构成。当然，要透彻理解链接分析，需要熟悉许多数学思想。尽管如此，我们仍然希望让本书的大部分内容能够为科学通论方面的公众所理解。例如书中的章节是根据数学知识、专业知识和预备知识渐次安排的。在这样的安排下，第1章到第4章是面向科学通论方面的读者的网络搜索和链接分析的相关介绍；第6章、第9章和第10章的数学内容则尤为多些；最后一章，即第15章数学指南，是之前各章中所用的所有数学概念的浓缩而完整的参考。在整本书中，关键的数学概念均用阴影框加以强调。将数学定义以及公式推后到第15章（而非分散在全书各处）的做法，使我们得以写出一本同样能够取悦于在数学方面见多识广的读者的书。在我们看来，这种写作方式是一种折中，使得我们能同时服务于以上两类读者：对科学通论感兴趣的公众，以及对技术科学感兴趣的公众。
杂谈
本书的一个轻松愉快的特色便是杂谈。这些杂谈包括了娱乐性的新闻故事、实用的搜索提示、诙谐的引述和激烈的法庭辩论。在每一章中，即使是在非常技术性的章节中，也包含了若干杂谈。不时出现的轻松杂谈，可以在一段时间的严肃的数学思考之后提供完美的小憩。简短的杂谈包含在阴影框中，而延跨多页的更长的杂谈则由水平条和楷体字给出。我们希望您能享受这些读间休息——我们发现自己都会有些迫不及待地想进行杂谈部分的写作。
计算和代码
要真正掌握一门学科，就需要对其中的思路进行实验。因此，我们在书中加入了MATLAB代码，以鼓励读者进行实验，并为实验开一个头。虽然任何编程语言都能够达到这个目的，但我们出于三方面的原因而选择了MATLAB：（1）它的矩阵存储构架和内建命令特别适合于本书的大规模稀疏链接分析矩阵；（2）在众多学院和大学中，MATLAB都是数学软件方面的市场领先者；（3）它对于用户非常友好。本书中的MATLAB程序是按指导性代码的标准而非商业代码标准编写的。我们希望通过这些程序激发起读者创建新模型和新算法的灵感。
致谢
我们对普林斯顿大学出版社对本书的支持表示感谢。我们尤其乐于与普林斯顿大学出版社的编审薇琪·克恩（Vickie Kearn）共事。薇琪，感谢您所展现出的耐心和柔中带刚的完美结合。对于这样一本题材如此适时的书，您对我们表现出了令人吃惊的信任。感谢所有审阅了本书草稿并使它更臻完美的人们。当然，我们还要感谢家人和朋友们的鼓励。你们对我们怀抱的骄傲之情给了我们强大的驱动力。
题词
我们谨以此书献给全世界所有的导师和学生。师生之间的这种关系所迸发出的能量、灵感和支持，能够启迪伟大的产物。对于我们而言，这一产物就是本书，而比本书更为重要的，则是一段美妙互惠的友谊。