这是一个很棒的算法。当前文章内容来自个人思考，如果你有疑惑和觉得不妥的地方，还请不吝赐教，万分感谢！

前言

本文将先进行原理介绍，再给出一些我个人的思考与收获。

 

一、基础概念

 PageRank算法最早用于推算网络冲浪者停留在某网站页面的概率，想象现在又一个无聊的网民，他随机打开一个网页，然后随机点击页面上的链接跳转到下一个网页，无线循环。而PageRank，本质就是在这个网民无数次点击后，最终停留在某个特定网页上的数学期望/概率。这个过程也被称之为随机冲浪者模型。

        在详细论述模型原理前，你需要知道以下概念：

1.节点

        你可以将它理解为PageRank这个网络拓补结构中的单元，在冲浪者模型中就是各个网页。

 

2.有向边

        这个可以理解为冲浪者模型中，网页的超链接。请注意，重点不止在于链接，还在于有向。即这些边是有指向性的，比如冲浪者模型中的某网页中又超链接，这个超链接代表了这个网页于该超链接指向的网页的关系，所以方向不可忽略。

 

3.悬挂节点或蜘蛛陷阱

        你在阅读模型原理时可能会碰到这两个名词。这是什么意思呢？按照前两点的叙述，你应该可以理解，网页的价值，等于所有指向它的网页的价值，除以它们各自的出度（超链接个数）后的总，呢么可以推出一个基础公式：当前节点的PR值（你可以先理解为该节点价值，后面会详细介绍）=其他与之相连的节点可以分给它的价值总和，即

PR(A) 是目标网页A的 PageRank 值。

PR(Ti) 是指向网页A的网页Ti的 PageRank 值。

C(Ti)是网页Ti的出度（即Ti页面上有多少个向外的超链接）。

 

        我们看这个公式，思考两个问题：

（1）如果存在一个网页，能通过别的网页到达，但不含超链接呢？

        这就是悬挂节点，PR网络的各节点价值是通过迭代不断更新的，试想如果碰到了这样一个“黑洞”，迭代还怎么继续呢？

（2）如果有网页形成“小团体”了呢？

        如果现在有几个网页互相链接，形成一个闭环，且没有任何指向环外的链接，系统的权重就会在这个小圈子里无限循环累加，那其他节点的价值还如何计算呢？这就是蜘蛛陷阱。

        在这里我一开始很疑惑，这个黑洞和蜘蛛到底是怎么影响的PR网络的呢？这就牵涉到PR网络的构建方式了。其实本质上来说，就是两个矩阵相乘。我们引入转移概率矩阵M，来记录网络的拓补结构，即谁谁相连，相指。这在迭代中通常是不会改变的，除非你的网络结构变化了；另外一个矩阵（列向量）就是PR值，新的PR值就是这俩乘积，不断更新，知道PR值波动不大，完成收敛。所以如果出现黑洞与蜘蛛，你的M矩阵就会出现异常值，乘出来的新PR值会越来越怪。

 

4.阻尼系数

        这其实是求解PR值公式中的一个变量，但我认为值得单独介绍。假设现在有阻尼系数d=0.85;那么它的意义是：冲浪者浏览网页时，有85%的概率继续点击链接，有 15% 的概率感到厌烦，直接在浏览器地址栏输入一个新网址。

        还记得前面提到的悬挂节点与蜘蛛陷阱吗？它们的影响网络的原因根本上来说时一样的，就是让PR网络的遍历停留在某个或某些固定节点，而阻尼系数的加入，提供了跳出当下链接的途径（15%概率厌烦跳出的操作)，重要性显而易见。

 

5.PR值

        这就是前文提到的，网页的“价值”了。PR值的计算公式为：

N是网络中的总节点数；

d是阻尼系数；

L(j)为节点 j 链接的节点总数；

 

二、PageRank算法

1.算法原理

        PageRank 是由 Google 创始人拉里·佩奇（Larry Page）和谢尔盖·布林（Sergey Brin）于 1996 年提出的算法。它的底层逻辑为：如果一个网页被很多高质量的网页链接，那么它本身也是高质量的。

        PageRank 将整个互联网看作一张巨大的有向图，网页是节点，超链接是边。

想象一个“随机冲浪者”在网上点链接：

1. 他随机打开一个网页。

2. 他点击当前页面上的任意一个链接跳转到下一个页面。

3. 枯燥点： 如果他点累了，或者这个页面根本没有链接（死胡同），他会随机在浏览器地址栏输入一个全新的网址跳转。

PageRank 值（PR值） 实际上就是：当这个冲浪者访问时间足够长时，他停留在某个特定页面的概率分布。

 

2.算法流程

1.构建转移概率矩阵

（1）构建邻接矩阵

根据节点之间的链接关系构建邻接矩阵。

（2）列归一化

将邻接矩阵每一列归一化，保证每列和为1。

（３）悬挂节点填充

对于链接了０个节点的节点，将它的列值统一赋值为１／Ｎ（N是节点总数）；

（４）计算Google矩阵

其中，S是归一化且填充完毕的矩阵；E是全1矩阵。

Google矩阵即转移概率矩阵。

2.迭代终止

新PR=旧PR*矩阵G；不断更新，直到新旧差距极小。

 

至此结束。

---

总结

这个模型虽然最早是计算网页停留概率，但是这样的网络结构能解决很多相似问题。比如引入到一个有物种入侵的食物网中，通过对比物种入侵前后各物种PR值的变化，来判断对生态的影响程度等等。我的想法大体这样，能力有限，欢迎指正交流。