PageRank的延伸及其在股权关系探查上的应用

原创
222 天前
3864


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


01.PageRank原理

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

如下图所示:

 


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)

 

总 结 

从有向网络图的邻接矩阵幂序列收敛这个角度出发,肯定还有其他的可以达到幂序列收敛的情景。PageRank适合于网页排序,编者的延伸则适合于上市公司实际控制人探查。研究经典的网络图上的算法在很多时候还是能带来有益的启发,重点还是了解算法的本质,结合业务本质,进行融合发酵,从而发挥算法的魅力。

作者简介:史晓春,北京大学基础数学博士,BBD高级大数据建模工程师  

BBD

3篇

文章总数

10009

浏览数

新闻排行

周熙涵:新职业里看懂新业态新经济

2020年2月,全国首个“区块链工程”专业获批,“区块链工程”正式作为本科开设的专业进入大学。

央行牵手滴滴要闹大!数字货币+新基建大爆发,概念股早有准备已涨疯

7月8日,滴滴方面宣布,日前,中国人民银行数字货币研究所与滴滴出行正式达成战略合作协议,共同研究探索数字人民币在智慧出行领域的场景创新和应用。

ChainsMap周报:活跃数据小幅反弹,国内大所正遭遇国外两大所强势吸金?

链上数据从交易额上小幅下降,但是其它活跃性数据大都小幅反弹,而币安和火币两大交易所的链上交易额则都明显增长,且整体流入增长更大,火币净流入率先转正

韩国考虑建立基于区块链运营的自贸区

7月7日,韩国庆尚北道的安东市宣布,他们已经获得了经营工业大麻自由贸易区的许可。此外,他们还宣布将通过一个基于区块链的平台来管理他们的业务。

Ystar如何诠释区块链引爆数字经济的蜕变之道? | 空中课堂

Ystar创始人、YottaChain创始人、国际顶级密码学应用科学家王东临做客猎云财经《空中课堂》直播间,给大家带来了精彩有料的分享。

Dora:去中心化交易所赛道领跑者亿币

从一开始亿币就确立了明确的三大目标:第一是数字货币交易;第二是数字股权交易;第三是数字货币支付。

云象黄步添:区块链和隐私计算打破数据安全流动矛盾,构建数据要素市场基石

7月9日,2020世界人工智能大会云端峰会开幕式在上海世博中心金厅召开,因疫情原因,大会以线上为主。大量线下产业受到重大影响的大环境下,线上包括在线教育、视频娱乐、数字经济等产业却逆势而上,迎来一轮快速增长,尤其是数字经济搭上了新基建的快车和数据生产要素化的政策,一跃成为上半年热词。