搜索策略产品经理必读系列—第五讲Page Rank算法

搜索引擎中最早网页搜索结果排序效果比较优的算法就是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值满足收敛条件。