

BBD技术控丨PageRank的延伸及其在股权关系探查上的应用

BBD Data

2019-11-06

导读：如何发挥算法的魅力？

文丨北京大学基础数学博士 BBD高级大数据建模工程师史晓春

PageRank是谷歌创立之初用来给网页排序的算法。可以说,正是有了这个算法，才有了谷歌的伟大开局。PageRank算法简洁而高效，而且理论上有完备的数学证明,是算法应用于商业的典范。今天我们来谈谈PageRank算法的原理，并由此延伸出另外一种网络图排序算法，并利用该算法探索上市公司股权关系网络中的实际控制人。

01.

PageRank原理

PageRank的原理是，通过计算链接到一个网页的数量及质量来对该网页的重要程度有一个估计。它所依赖的假设是越重要的网页通常会有更多的网页链接到他。——-from wiki

如下图所示：

有很多链接指向网页B，因此它很重要；

网页C因为网页B指向它也变得重要。

02.

算法流程如下

1）给定网页链接网络图，如上图所示，为每一个结点（网页）设置一个初始分数（比如均为1）；

2）对每个节点（网页）出去的链接进行归一化赋权（也就是每一条出边权重相等而且和为1）；

3）逐轮刷新每个结点的分数，直到所有结点的分数不再变化为止，刷新规则如下：

随机取一个节点x，考虑所有指向x的网页链接，将这些网页的分数乘以链接的权重后进行求和，将和赋予节点x,作为x的更新后分数。

从上述算法流程可以看出，PageRank算法比较简单。通过步骤2）的链接赋权和步骤3）的网页投票打分，该算法最终将收敛到一个稳定的分数排名。然而步骤2）的赋权并不足以保证步骤3）就一定能收敛。谷歌最初的创始人发现了上述步骤2）的缺陷，然后进行了改进（任何一个算法都必须经过数据上的测试和验证）。步骤2）有两个缺陷，首先,有一些结点没有出去的链接;其次,有一些没有出去的链接但是有指向自己的链接。第一个缺陷可能导致网页分数都收敛到0，第二个缺陷导致缺陷点的分数不收敛。所以对上述步骤2）的赋权进行了一定的更改，其更改如下：

其中e = e = (1, 1, 1, …, 1)T，S为网页链接矩阵（需要归一化）的转置矩阵。通常的取值为0.85。上述矩阵A也有现实意义上的解释，等式右边第一部分（）可视为用户点击链接从一个网页跳转到另一个网页，第二部分可视为是用户手动输入一个网址进入某一个网页。

03.

PageRank算法收敛性证明：

PageRank步骤3）刷新分数的过程相当于求Anx，x为初始分数。算法收敛即Anx收敛。可以证明如下结论：

给定矩阵A，如果A满足以下条件：

1）本原的，如果A非负（A的每一个元素非负），且存在正整数k使得Ak > 0（每一个元素都大于0）；

2）随机的，即A的每一行之和都为1，

那么，序列{An}将收敛到一个特殊矩阵，其中P为正的且元素之和等于1的行向量。这是马尔科夫链理论中一个经典定理，即本原随机矩阵的幂序列收敛（细节可参考相关数学教材）。很明显,PageRank的矩阵A的转置矩阵是本原随机的，因此An是收敛的（转置矩阵的幂序列收敛等价于其本身的幂序列收敛）。

04.

PageRank延伸算法

针对以上通过网络邻接矩阵的幂序列收敛性来打分的PageRank算法，作者在此考虑另外一种幂序列收敛的邻接矩阵。我们有以下结论：

A是有向网络图G的邻接矩阵，如果图G无圈，那么A的幂序列收敛。作者在这里不给出具体证明，图论中有相关结论。证明思路如下，对于有向无圈网络图G，其邻接矩阵的足够大的有限次幂等于0。

G有圈时指G中存在一条首尾相接的路径。从这样一个结论出发，我们可以考虑以下与PageRank类似的网络节点排序算法，即为PageRank延伸算法。给定连通有权有向无圈网络图G及正数C，进行以下操作：

1）为图G的所有节点赋予相同初始分数C；

2）逐轮刷新所有节点的分数，直到所有节点的分数不再变化为止。刷新分数的规则如下：

i）给定节点及其出边方向的邻居，将其出边邻居的分数乘以边权重（非归一化权重）求和，再加上C（也可以是和C不同的常数），得到的数值作为新的分数赋予该节点。

ii）按照步骤i）随机刷新所有节点的分数

上述算法可以看作一个溯源算法，如下图所示：

源头为右下角的节点，所以最终的分数排名可以看做是离源头的距离，距离源头越近，分数越高。

05.

PageRank延伸算法在股权关系探查上的应用

上市公司中存在的一个主体（企业或者个人）直接或者间接控制多家公司的现象，可以描述为资本系。资本系是股权关系趋于集中（可以认为是一种资本垄断趋势）的体现。我们在研究资本系现象的时候，就需要找到资本系的实际控制人。实际控制人恰恰可以看做一个资本系的源头。在资本系持股比例关系网络图上应用上述PageRank延伸算法从而找到实际控制人。这里展示一下部分结果：2011和2226是上市公司代码（002011/002226）