xiaoming
搜索引擎中最早网页搜索结果排序效果比较优的算法就是Google创始人提出的Page Rank算法，作为搜索领域的从业者必须要了解该经典算法的思想。本文结合实际案例一篇讲懂Page Rank算法的基本思想，同时还为大家介绍后续优化后的Page Rank算法。
一、基本假设
在正式介绍Page Rank算法前我们先通过实际生活中的一个案例入手。日常我们写论文时经常会引用别人的论文，某个行业里的经典论文会被大量的论文所引用。如果该论文恰好还被另外一篇经典论文所引用的话，则更加能够凸显出该篇论文的重要性和权威性，其实网页的重要性和权威性也是如此。
于是我们设定以下两大假设。
数量假设：当一个网页被其他网页链接的数量越多，入链数越大，则该网页越重要。
如上图所示，网站“WWW1”被众多网站引用，形成了链接，则说明网站“WWW1”很重要。
质量假设：被高质量的网页链接时，说明被链接的网页质量也很高，权威性也很强。
如上图所示，网站“WWW8”被高质量网站“WWW1”引用，形成了链接，说明网站“WWW8”同样也很权威。PageRank算法的整体思想都是建立在上述假设上的。
二、Page Rank基本算法
基于以上两大假设，我们展开介绍Page Rank算法。首先我们将互联网想象为一个图网络，网络的每一个节点（Node）就是一个个独立的网页，如果两个网页之间存在超链接的关系，则它们两个之间存在一条有方向的边（Edge），每个节点向外链接的节点数被称为该节点的出度。
每个节点的Page Rank值（以下简称PR值）表示该节点的权威性。我们核心是构建一个用户在图网络中的游走模型，基于游走模型来进行PR值的更新迭代。
上面即为Page Rank算法的基本定义，首先节点 ν_1 的PR值是由链接到该节点的其他节点PR值决定的，假设链接节点是 ν_2、ν_3 。链接的其他节点越多则该节点的PR值越大，所以算法迭代使用累加 ∑ 。需要将节点 ν_2、ν_3 的PR值进行累加，此迭代思路对应着上述的“数量假设”。
链接的其他节点PR值越大，则该节点的PR值也越大，对应着上述的“质量假设”。同时 ν_2、ν_3 节点还链接其他节点，用户通过节点 ν_2、ν_3 跳转到节点 ν_1 的概率为 1/O(ν_j ) ， O(ν_j ) 为节点 ν_j 的出度。节点 ν_2、ν_3 的PR值分别乘以 1/O(ν_2 )和1/O(ν_3 ) ，再进行累加即为节点 ν_1 的PR值。我们通过该方式不断迭代更新节点的PR值，直到最终整个网络里所有节点的PR值满足收敛条件。
三、具体案例
下面我们通过一个例子来详细介绍Page Rank算法的迭代过程。
初始时4个节点的PR值均为1/4。经过第一次迭代，我们得到了 R_1 =[3/8,5/24,5/24,5/24]^T 。我们可以将上述计算过程变成一个矩阵计算，通过矩阵化的表达，可以快速的计算得到PR值。
首先我们基于各个节点的出度构建一个转移概率矩阵 M ，节点A的出度为3，链接了B、C、D三个节点，我们认为节点A转移到B、C、D节点的概率均为1/3，以此类推我们可以得到一个转移概率矩阵 M 。那么PR的迭代公式就变为： M*R_t=R_(t+1) 。
如上所示 M*R_1=R_2 ，和我们最上方计算的结果完全一致。但是上述Page Rank基本算法应用时会存在以下两大问题：
问题一：很多网站并没有和其他网站建立任何的链接，出度为0。这类网站的出现会导致按照上述算法进行 R_i 迭代，最终所有节点的PR值归于零。
问题二：用户打开某一个网站后，即使该网站链接了其他网站，但是用户还是可能会随机打开其他网站，所以没有链接的其他网站转移概率不应该是0，系统可以设置一个随机概率。
四、Page Rank优化算法
基于Page Rank基本算法存在的两大问题上，科学家们又对Page Rank算法进行了优化，优化后的Page Rank算法可以适用于所有的网络结构，更加贴近于实际用户浏览行为。优化后的算法PR值更新迭代如下：
R_(t+1)=d*M*R_t+(1-d)*E/N
全新迭代公式的业务理解是：用户在浏览网页时有两种情况，第一种情况是以概率 d(0≤d≤1) 完全按照原本的转移概率矩阵进行游走，第二种情况是以概率（1- d ）随机访问任何其他的节点，每个节点的链接概率都是1/N， E 是元素1填满的N*N矩阵。
d 又被成为阻尼因子， d 的取值一般由经验决定，正常在0.8-0.9之间。当 d 接近1时，用户随机游走主要依照转移概率矩阵 M 进行；当 d 接近0时，用户随机游走主要以等概率随机访问各个结点。
虽然目前搜索引擎的排序算法已经优化迭代了很多版本，但是Page Rank算法的核心思想仍然在被使用，也应用到了其他领域。Page Rank是从事搜索领域人士必须要了解的算法之一。
本文由 @King James 原创发布于人人都是产品经理。未经许可，禁止转载。
题图来自 Unsplash，基于 CC0 协议
该文观点仅代表作者本人，人人都是产品经理平台仅提供信息存储空间服务。