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

原创
115 天前
3489


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篇

文章总数

9218

浏览数

新闻排行

关于OKCoin Japan正式获得日本数字货币交易平台从业许可的公告

3月30日,欧科集团旗下子公司OKCoin Japan通过了日本金融厅的数字资产交易从业许可审批,正式取得日本数字货币交易所牌照。

专访币核科技,交易平台如何应对312极端市场 | TI对话首席

本期《对话首席》特邀币核科技副总裁-白洋作为主嘉宾,同时,我们邀请了链闻-潘致雄、链得得-齐灵鸽作为媒体观察团,为大家带了精彩的问答。

快讯:未来矿场通证FM将于3月28日上线Aofex交易所

据未来矿场Future Mine官方公告,FM将于3月28日15:00正式上线Aofex交易所。

沐荣:智能跨链交互系统LCS

数据安全、公开公平、匿名自由,是区块链重要属性,也是人类社会发展的必然。

明泽资本高杉:5G流量提前爆发,新基建投资炙手可热-算力大学

新基建大潮下,投资机会在哪里?算力智库邀请了明泽资本高级合伙人高杉,解读疫情期间,伴随着流量激增环境下的投资机会。

算力智库燕丽:数字新基建时代ABCDI带来商业机会-算力大学公开课

2020年被称为是中国数字经济元年,由于全球范围内错峰爆发的新冠疫情,催生无接触经济的需求,迫使我们加速拥抱数字化进程。

极端行情如何投资 | TokenInsight

极端行情下,各类资产和交易所之间受影响程度不同。此时投资者必须选择具有投资价值的高质量资产,避免空气币;克服投机心理,采用低风险投资策略;选择拥有足够高资产沉淀能力和合理风控制度的交易所,才能平稳度过极端行情,保护自己的权益。