技术专栏
作者：刘忠雨
由萝卜兔编辑整理
从本章开始，我们就会陆续讲一些图算法。本文首先给大家聊一聊图传播算法，对于图传播算法，并没有确切的定义，但是这类算法都有着十分明确和统一的范式，理解了这一范式之后，就能迅速掌握此类算法。
给定图G={V,E}，V表示节点集合，E表示边集合，设N(Vi)表示节点Vi的邻居节点构成的集合，若G为有向图：
其中Nin(Vi)表示Vi的入边节点集合，Nout(Vi)表示Vi的出边节点集合。
假设我们对Vi节点的衡量指标表示为Rvi（比如后面会具体谈到的指标PageRank值、hub值、Authority值等）衡量指标的更新规则为函数f，则图传播算法的一般步骤执行如下：
1、初始化Rvi
2、While（不满足停止条件）
3、
上述步骤的核心在于第三行中的更新函数f，一般来说f具有以下两个特点：
a. f是无参的，就是说f是直接进行量化计算的，不需要参数学习过程。这样的特点就决定了f的设计需要十分精巧，符合一定的基本经验直觉，总结来说就是：
b. f是作用在节点一阶邻域上的。这一点是很多以节点为中心的算法的共同特点，每一次节点在更新过程中，只有邻居节点参与运算，但是随着更新次数的增加，信息的流通也变得更Global。
另外，停止条件一般选取一个最大的迭代轮数或者Rvi不再变化。下面，我们结合4个经典的图传播算法来看看该范式是怎么发挥实际作用的。
第一个：PageRank
如果将每一个网页都抽象成一个节点，网页A有链接指向B，则存在一条有向边从节点A指向节点B，那么整个Web网页就抽象成为一张有向图。PageRank算法要做的就是对图中的每个节点进行重要性排名。
经验假设：
数量假设——被更多网页链接到的网页更重要；
权重假设——有更少外链的网页将会传递更高的权重。
数量假设表示重要性的计算是加和的，权重假设是说重要性的计算是加权的，因此，如果要量化重要性的计算，其在数学形式上一定是加权求和的。
下面我们直接给出更新函数的向量化形式：
Rvi表示节点Vi的重要度排名
Vj的权重
下面我们举个经典的例子来说明PageRank算法是怎么计算的。假设有A,B,C,D四个网页，其构成的有向图如下：
邻接矩阵
Adj(ij)=1,则表示有节点从j指向节点i的边，对Adj按列进行归一化得到：
我们称M为转移矩阵（Transition,Matrix）Mij表示从节点j跳转到节点i的概率，可以看到：
初始时设每个网页的排名都是1/N
依据上面更新函数，将其写成矩阵形式则更新后：
之后，不断重复这个过程会发现，R最终是收敛的。这里我们需要注意到一个重要的性质，如果R初始化后加和为1，则R在之后的迭代过程中，R的加和永远保持为1，我们可以证明下：
R=MR，两边求和，我们看右边
Mcol为M矩阵列向量之和组成的向量，由M的定义可知，M矩阵每一列加和为1，所以这里Mcol是一个全1向量，因此：
由于R初始化后加和为1，则上式恒等于1。更严格来说，如果有向图是强连通的（任意两个节点之间至少存在一条路径可达），R的初始化加和为1，则可证明R是收敛的。实际上，Web网页并不是强连通的图，存在以下两种情况导致PageRank计算失败：
1、DeadEnds，有节点不存在外链。这会导致什么问题呢？我们举个例子：
D节点不存在任何外链，如果我们进行迭代计算，由于上面的性质可得：
可以看到，新得到的R的求和是不断减小的，这个过程如果一直不断迭代下去，R全部都会变成0，使得计算失效。
2、Spider traps：有些节点只存在指向自己的外链，这又会导致什么问题呢？同样举个例：
节点D只存在指向自己的外链，首先
符合R永远是加和为1的，但是注意
可以看到D的排名R4永远比上一轮大，因此计算下去会快速的发现最后D的R值为1，其他节点都为0。
在实际应用中，为了有效避免上述两个问题，会使用到一个小技巧，就是假设每个节点都有一个假想的外链指向其它任一节点，这样整个图就变成了一个强连通图了。当然，为了尽量不影响最终计算的PageRank值，节点通过假想外链传递的PageRank值会乘一个权重因子β，β一般取0.2或者更小。因此，实际中PageRank的更新公式变成了：
如果按照这个更新公式下去，每个页面都会得到一个合理的排名值。
关于其他的算法，我们会在下篇中继续介绍。
相关阅读：
网友评论