049 | PageRank算法的核心思想是什么？
洪亮劼
该思维导图由 AI 生成，仅供参考
上周我们介绍了信息搜索系统的历史进程，剖析了搜索系统的多轮打分系统，还深入探讨了倒排索引，聊了聊它的核心技术。
这周我要和你分享的是在互联网搜索引擎兴起之后的一个研发需要，那就是如何理解网页和网页之间的关系，特别是怎么从这些关系中提取网页中除文字以外的其他特性。这部分的一些核心算法曾是提高搜索引擎质量的重要推进力量。另外，我们这周要分享的算法也适用于其他能够把信息用结点与结点关系来表达的信息网络。
今天，我们先看一看用图来表达网页与网页之间的关系，并且计算网页重要性的经典算法：PageRank。
PageRank 的简要历史
时至今日，谢尔盖·布林（Sergey Brin）和拉里·佩奇（Larry Page）作为 Google 这一雄厚科技帝国的创始人，已经耳熟能详。但在 1995 年，他们两人还都是在斯坦福大学计算机系苦读的博士生。那个年代，互联网方兴未艾。雅虎作为信息时代的第一代巨人诞生了，布林和佩奇都希望能够创立属于自己的搜索引擎。1998 年夏天，两个人都暂时离开斯坦福大学的博士生项目，转而全职投入到 Google 的研发工作中。他们把整个项目的一个总结发表在了 1998 年的万维网国际会议上（ WWW7，the seventh international conference on World Wide Web）（见参考文献[1]）。这是 PageRank 算法的第一次完整表述。
PageRank 一经提出就在学术界引起了很大反响，各类变形以及对 PageRank 的各种解释和分析层出不穷。在这之后很长的一段时间里，PageRank 几乎成了网页链接分析的代名词。给你推荐一篇参考文献[2]，作为进一步深入了解的阅读资料。
PageRank 的基本原理
我在这里先介绍一下 PageRank 的最基本形式，这也是布林和佩奇最早发表 PageRank 时的思路。
首先，我们来看一下每一个网页的周边结构。每一个网页都有一个“输出链接”（Outlink）的集合。这里，输出链接指的是从当前网页出发所指向的其他页面。比如，从页面 A 有一个链接到页面 B。那么 B 就是 A 的输出链接。根据这个定义，可以同样定义“输入链接”（Inlink），指的就是指向当前页面的其他页面。比如，页面 C 指向页面 A，那么 C 就是 A 的输入链接。
有了输入链接和输出链接的概念后，下面我们来定义一个页面的 PageRank。我们假定每一个页面都有一个值，叫作 PageRank，来衡量这个页面的重要程度。这个值是这么定义的，当前页面 I 的 PageRank 值，是 I 的所有输入链接 PageRank 值的加权和。
那么，权重是多少呢？对于 I 的某一个输入链接 J，假设其有 N 个输出链接，那么这个权重就是 N 分之一。也就是说，J 把自己的 PageRank 的 N 分之一分给 I。从这个意义上来看，I 的 PageRank，就是其所有输入链接把他们自身的 PageRank 按照他们各自输出链接的比例分配给 I。谁的输出链接多，谁分配的就少一些；反之，谁的输出链接少，谁分配的就多一些。这是一个非常形象直观的定义。
然而，有了这个定义还是远远不够的，因为在这个定义下，页面 I 和页面 J，以及其他任何页面的 PageRank 值是事先不知道的。也就是等式两边都有未知数，这看上去是个无解的问题。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
PageRank算法是谷歌创始人布林和佩奇在1998年提出的一种用于衡量网页重要性的算法。该算法的核心思想是通过分析网页之间的链接关系来确定网页的重要程度。具体而言，PageRank算法通过对网页的输入链接和输出链接进行分析，将每个页面的重要性用一个数值来表示，该数值是由其所有输入链接的PageRank值的加权和得到的。为了解决一些问题，布林和佩奇对原始的PageRank算法进行了改进，包括解决悬空结点问题和引入随机跳转机制。此外，学者们还提出了不同的解释方法，如将PageRank算法转化为求解随机矩阵的“左特征向量”过程或者将其视为一个“线性系统”的求解过程。总的来说，PageRank算法是现代搜索技术中的一个重要分支，通过分析网页之间的链接关系来确定网页的重要性，为搜索引擎的发展提供了重要的推动力。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《AI 技术内参》，新⼈⾸单¥98
《AI 技术内参》，新⼈⾸单¥98
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(2)
- 最新
- 精选
DasonCheng浏览到这里，总体感受是不够系统，多为知识点的搬运堆砌，给人一种“混”的感觉2018-12-1114
韩 * *我觉得脉络挺清楚的，很多关键点梳理出来了，需要的时候可以按图索骥，自己拓展学习。我是等更新完按模块来看的，挺舒服。2019-08-03
收起评论