20 年后，回看 PageRank
以下文字内容主要来自
极客大学 架构师训练营第 1 期第 13 周内容
极客时间 洪亮劼 《AI技术内参》 049 | PageRank算法的核心思想是什么？
极客时间 李智慧 《从0开始学大数据》 38 | 如何发掘数据之间的关系？
极客时间 陈旸 《数据分析实战45讲》 32丨PageRank（上）：搞懂Google的PageRank算法
极客时间 陈旸 《数据分析实战45讲》 33丨PageRank（下）：分析希拉里邮件中的人物关系
极客时间 《程序员的数学基础课 》 25 | 马尔科夫模型：从PageRank到语音识别，背后是什么模型在支撑？
历史
1995 年，谢尔盖·布林（Sergey Brin）和拉里·佩奇（Larry Page）还都是在斯坦福大学计算机系苦读的博士生。雅虎作为信息时代的第一代巨人诞生了，布林和佩奇都希望能够创立属于自己的搜索引擎。1998 年夏天，两个人都暂时离开斯坦福大学的博士生项目，转而全职投入到 Google 的研发工作中。他们把整个项目的一个总结发表在了 1998 年的万维网国际会议上（ WWW7，the seventh international conference on World Wide Web）。这是 PageRank 算法的第一次完整表述。
原理
首先，我们来看一下每一个网页的周边结构。每一个网页都有一个“输出链接”（Outlink）的集合。这里，输出链接指的是从当前网页出发所指向的其他页面。比如，从页面 A 有一个链接到页面 B。那么 B 就是 A 的输出链接。根据这个定义，可以同样定义“输入链接”（Inlink），指的就是指向当前页面的其他页面。比如，页面 C 指向页面 A，那么 C 就是 A 的输入链接。
B 网页包含了 A、D 两个页面的超链接，相当于 B 网页给 A、D 每个页面投了一票，初始的时候，所有页面都是 1 分，那么经过这次投票后，B 给了 A 和 D 每个页面 1/2 分（B 包含了 A、D 两个超链接，所以每个投票值 1/2 分），自己从 C 页面得到 1/3 分（C 包含了 A、B、D 三个页面的超链接，每个投票值 1/3 分）。
而 A 页面则从 B、C、D 分别得到 1/2、1/3、1 分。用公式表示就是
PR(A) = PR(B)/2 + PR(C)/3 + PR(D)/1
有了输入链接和输出链接的概念后，下面我们来定义一个页面的 PageRank。我们假定每一个页面都有一个值，叫作 PageRank，来衡量这个页面的重要程度。这个值是这么定义的，当前页面 I 的 PageRank 值，是 I 的所有输入链接 PageRank 值的加权和。
那么，权重是多少呢？对于 I 的某一个输入链接 J，假设其有 N 个输出链接，那么这个权重就是 N 分之一。也就是说，J 把自己的 PageRank 的 N 分之一分给 I。从这个意义上来看，I 的 PageRank，就是其所有输入链接把他们自身的 PageRank 按照他们各自输出链接的比例分配给 I。谁的输出链接多，谁分配的就少一些；反之，谁的输出链接少，谁分配的就多一些。这是一个非常形象直观的定义。
然而，有了这个定义还是远远不够的，因为在这个定义下，页面 I 和页面 J，以及其他任何页面的 PageRank 值是事先不知道的。也就是等式两边都有未知数，这看上去是个无解的问题。
布林和佩奇在他们的论文中采用了一种迭代算法。这个算法很直观，那就是既然不知道这些 PageRank 的值，那我们就给他们一组初始值，这个初始值可以是这样的情形，所有页面有相同的 PageRank 值。然后，根据我们上面所说的这个定义，更新所有页面的 PageRank 值。就这么一遍一遍地更新下去，直到所有页面的 PageRank 不再发生很大变化，或者说最后收敛到一个固定值为止。他们在文章中展示了实际计算的情况，往往是在比较少的迭代次数后，PageRank 值就能够收敛。
以上就是整个 PageRank 算法的基本思想和一种迭代算法。
改进
第一个麻烦就是有一些页面并没有输出链接，比如某些 PDF 文件，或者一些图片文件。由于没有输出链接，这些页面只能聚集从上游输入链接散发过来的 PageRank 值，而不能把自己的 PageRank 值分发出去。这样的结果就是，这些页面成为一些“悬空”（Dangling）结点。悬空结点存在的最大问题就是会使得 PageRank 的计算变得不收敛。这些结点成了 PageRank 值的“黑洞”，导致悬空结点的 PageRank 值越来越大，直至“吸干”其他所有输入链接的值。
要解决这个问题，就要为悬空结点“引流”，能够把这些点的值分发出去、引出去。谢尔盖和拉里找到的一个方法是，对于每一个悬空结点，都认为这个结点能够随机到达整个网络上的其他任意一个结点。也就相当于人工地从这个结点连接到所有页面的一个结点，让当前悬空结点的 PageRank 能够“均匀”地分散出去到其他所有的结点，这就解决了悬空结点的问题。
然而原始的 PageRank 还存在其他问题。要想保证 PageRank 的收敛性，并且能够收敛到唯一解，我们还需要第二个改进。第二个改进就是，即便一个页面有自然的输出链接，我们也需要一个机制，能够从这个页面跳转到其他任何一个页面。这也就是模拟假设一个用户已经浏览到了某个页面，一方面用户可以顺着这个页面提供的输出链接继续浏览下去，另一方面，这个用户可以随机跳转到其他任何一个页面。
有了这个机制以后，对于所有的结点来说，PageRank 的分配也就自然地产生了变化。在之前的定义中，每个页面仅仅把自己的 PageRank 值输送给自己原生的所有输出链接中。而现在，这是一部分的“分享”，另外一部分还包括把自己的 PageRank 值分享到所有的页面。当然，后者的总量应该比前者要少。于是，这里可以引入一个参数，来控制有多大的比例我们是顺着输出链接走，而多大的比例跳转其他页面。通常情况下，这个参数的取值范围大约是 60%~85%。
有了这两个改进之后，整个网络上的每个页面实际上已经可以到达其他任何页面。也就是说，整个页面网络成了一个完全联通的图，PageRank 算法就有了唯一的收敛的解。
那么对于 N 个网页，任何一个页面 Pi 的 PageRank 计算公式如下
PageRank（Pi）=α Pj ∈M(Pi) ∑ PageRank(Pj)/L(Pj) + (1−α)/N
公式中，Pj ∈M(Pi) 表示所有包含有 Pi 超链接的 Pj，L(Pj) 表示 Pj 页面包含的超链接数，N 表示所有的网页总和。
马尔科夫模型
其实对于 PageRank 的改进，核心思想就是基于马尔科夫链。
马尔科夫链算法假设了一个“随机冲浪者”模型，冲浪者从某张网页出发，根据 Web 图中的链接关系随机访问。在每个步骤中，冲浪者都会从当前网页的链出网页中随机选取一张作为下一步访问的目标。在整个 Web 图中，绝大部分网页节点都会有链入和链出。那么冲浪者就可以永不停歇地冲浪，持续在图中走下去。
在随机访问的过程中，越是被频繁访问的链接，越是重要。可以看出，每个节点的 PageRank 值取决于 Web 图的链接结构。假如一个页面节点有很多的链入链接，或者是链入的网页有较高的被访问率，那么它也将会有更高的被访问概率。
在最基本的 PageRank 算法中，我们可以假设每张网页的出度是 n，那么从这张网页转移到任何下一张相连网页的概率都是 1/n，因此这个转移的概率只和当前页面有关，满足一阶马尔科夫模型的假设。
PageRank 在标准的马尔科夫链上，引入了随机的跳转操作，也就是假设冲浪者不按照 Web 图的拓扑结构走下去，只是随机挑选了一张网页进行跳转。这样的处理是类比人们打开一张新网页的行为，也是符合实际情况的，避免了信息孤岛的形成。最终，根据马尔科夫链的状态转移和随机跳转，可以得到最终的 PageRank 公式。
问题来了
对于 youtube 类视频网站，抖音类的短视频应用，还有微信这样一个对爬虫不友好的应用，如何进行搜索？
或者更具体一点，对于微信来说，如何进行搜索？微信文章内部的链接相对来说更少一些。如果只看阅读量，显然是有问题的。
参考文献
Sergey Brin and Lawrence Page. The anatomy of a large-scale hypertextual Web search engine. Proceedings of the seventh international conference on World Wide Web 7 (WWW7), Philip H. Enslow, Jr. and Allen Ellis (Eds.). Elsevier Science Publishers B. V., Amsterdam, The Netherlands, The Netherlands, 107-117, 1998.
Langville, Amy N.; Meyer, Carl D. Deeper Inside PageRank. Internet Math. no. 3, 335-380, 2003.
论文链接
版权声明: 本文为 InfoQ 作者【escray】的原创文章。
原文链接:【http://xie.infoq.cn/article/41e2b8c08fcbd61fb5570525b】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
Let's Go 2017.11.19 加入
大龄菜鸟项目经理
评论