财新传媒
位置:博客 > 集智俱乐部 > 解读幂律与无标度网络 | 网络科学入门

解读幂律与无标度网络 | 网络科学入门

“贫穷限制了我们的想像力”是最近非常流行的网络语言。在这儿采用这个副标题不是为了哗众取宠,而是因为这个讲座的内容真的和经济金融相关,而且介绍的内容真的会超出你的想象力。本文节选自陈清华的线上讲座《解读幂律与无标度网络——贫穷限制了我们的想象力》。

本文围绕4个问题展开,分别是

  1. 什么是幂律分布

  2. 什么是无标度网络

  3. 如何产生幂律分布

  4. 如何估计和判断幂律分布

本文约10000字,预计阅读时间15分钟。

1.什么是幂律分布

1.1幂律分布(power law distribution)

1.1.1幂律分布的几个例子

概率论中心极限定理告诉我们,在复杂的多因素情况下,只要个体相互独立,集体效果就应该是正态分布。但世界这么大,总会有例外。

这个图是在研究金融市场里面发现的,展现了标准普尔500指数的日收益率的分布。在金融市场里面,股票的收益率无疑都是大家很关注的,收益率高代表挣钱多,是投资者所希望的。

这个分布图也具有中间高两边低的特征,和正态分布有点类似。它在收益率为0的附近是一个比较高的峰,而两边是快速下降的,要比正态分布下降快。如果把同样均值和方差的正态分布也画出来的话,差异就会暴露出来:实际的分布呈现尖峰胖尾的特征。

这种例外很多,我们看个更清楚的例子:美国的家户收入数据。可以发现它好像类似也就这种尖峰胖尾的特征,要比正态分布表现得峰更加尖,而尾巴会拖得更长更厚。

假设收入是正态分布,我们就不能期望出现偏离期望达到10倍标准差那么大的收入,而实际的收入让人吃惊,你会发现很多有人,他们有巨额的收入,而且有巨额收入的人会比你想象得多。

图2(b)是2015年福布斯公布的美国富豪榜,这里面是列出的他们的资产,虽然不是严格对应到收入上,但不妨碍我们来理解这个事情。从数据上看出前18位富豪中的最后一个有314亿美元的家产。这是一个数字是一个什么概念呢?图2(c)是2016年一些国家的GDP排名,排名100的拉脱维亚在2015年的GDP是312亿美元。也就意味着有18个富豪的财产大于100多个国家的整年的GDP。

这就是传说中的富可敌国。我们不知道这个世界上还有这么有钱的人,而更难以置信的是这么有钱的人还那么的多。

1.2.2 幂律分布的数学形式和图形表达

形象理解胖尾的含义,就是有些东西可以超出想象的大,而且出现这么大的东西的概率比想象的大(这个是相对正态分布来讲的)。这种陡峭而延伸很长的分布就是我们要说的幂律分布,就是分布函数服从幂函数。幂函数的数学形式为

对于幂律分布有一个更好的展示方式,就是双对数坐标。幂律分布函数呢在这个双对数坐标下呈现一个非常简洁漂亮的性质,是一个负斜率的直线。图7(b)就是原始的直方图我们改成了对数坐标形成的。因为这是一个比较纯的随机数发生器,所以它会生成得非常好。

为什么会出现一条直线?其实很简单,如果我们对上面的这个概率分布的概率密度函数两边取对数,我们就会得到这样一个函数形式。

要注意实际上的数往往不会有这么好的一致性。那就有必要讨论一些实际数据是否符合幂律,如何来进行估计和推断这个问题。实际可能服从幂律分布的数据还有那些呢?我们再看几个例子。

1.2.3 地震的能量

图5是地震研究得到的一个能量分布图。这表明地震的能量分布在双对数坐标下也大概是一条直线!大家可能认为这个横轴是震级,不是对数啊。那是因为震级和能量不是线性关系,震级相差1,能量关系会有10倍的差异,所以震级本身是已经类似于对能量取了对数后的指标。这个纯粹的物理系统表现出幂律分布的行为特征。

1.2.4 城市规模

复杂网络研究的大牛Newman在2005年发表了一篇文章,展示了城市规模的分布,如图6所示,左图是原始的分布,右图是双对数坐标,可以看出明显的直线特征,意味着幂律分布特征。城市的生成和维持是一个人类和自然交互形成的结果,这个系统中的一些现象也能表现出幂律分布特征。

1.2.5 回信的时间间隔

这篇文章研究的内容很有趣,它讨论个人的回信时间的长度分布,一个人收到一封信再回信的时间到底会间隔多少天?看起来这个问题应该是不好回答的,谁知道他按什么顺序回信。作者收集到爱因斯坦(Albert Einstein)和达尔文(Charles Darwin)这两个人的发出的邮件和收到的邮件做了配对,研究文他们收到一个信之后,多少天才回复的时间。最后的结果如图7所示,其中(b)为达尔文的回信情况,(c)为爱因斯坦的情况。大部分信很快就回了,但是有写信很长时间后才回复。可以发现,他们在双对数坐标下表现为直线,说明具有幂律分布特征,甚至幂律指数几乎是一样的,都在1.5。

如果回信的时间是幂律分布,我们假设爱因斯坦已经活了1000年,你猜他最长时间的回信时间多长?这将会很难估计,因为有些信根本都没有想回复。但如果假象这个回复时间的分布是正态的,那么只要猜测在期望值附近就好了。

1.2.6 幂律分布的期望和方差

我们再来看看幂律分布在数学上是如何突破我们的想像力的。对于任何分布来讲,矩是很有意义的,它们是一个个投影,能表现这个分布的一些特征。期望是一阶原点矩,方差是二阶中心矩。如果知道了这两个矩,整个正态分布的特征就清楚了。

但是经过数学分析,你会惊讶地发现幂律分布随机数的方差总是不存在的,在一些情况下,连期望都不存在。 

1.2.7 幂律分布的标度不变性

幂律分布的期望和方差让人意外,它还有一个让人意外特征,被称为标度不变性(scaling invariance)

形象地说,就像用一个放大镜观察这个分布,无论看什么细节,放大多少倍数,所得到的性质是一样的,这种现象被称为无特征尺度,而正态分布是有的,必须整体上看是一个钟的形状,放大任何局部都不会得到钟形的图案。

这还可以用马上会讲到的帕累托80/20法则来说,80/20法则说20%的人口掌握了80%的财富。而在这个掌握的80%财富的的20%人口中,又有20%掌握了其中的80%,而在穷人部分随便划出一部分,也会发现20%的较为富有的占有了这部分穷人总财富的80%。当看任何财富的区间,都会有同样的规律,这个规律和所划定的区间无关。

1.2.8 齐普夫律(Zipf’s law)

在幂律分布概念提出以前,已经有很多人研究类似的现象,这里面要两个重要人物,一个是齐普夫(G.K.Zipf),一个是帕累托(V. Pareto)

Zipf提出了Zipf律,实际上在他1932年和1935年研究不同语言的词频的时候就讨论了这个规律,把某种语言的文本数据拿来,分割成词,分完后数一下不同的词各出现了多少次,然后从多到少排序,例如对于汉语来讲排在最左边的是“的”,英语是“the”。将结果画在图上,横轴就是排序大小,纵轴就是对应的词出现的次数,如图9所示,在双对数坐标下呈现直线特征。Zipf律的数学表达是

其中,x是规模,r是排序,β是Zipf指数,在很多情况下,β=1。按现代观点看,Zipf律和power law分布实际上是一致的,这个将在稍后讨论。

1.2.9 帕累托法则(Pareto principle)和帕累托分布(Pareto distribution)

在19世纪90年代,Pareto注意到,20%的人口掌握意大利约有80%的土地。目前,这种“80/20”原则在管理领域流行度非常高。

1.2.10 Power Law分布、Zipf律、Pareto法则的关系

从图5、图9和图10可以看出,三者都是在双对数坐标先表现为负斜率的直线,但三者坐标不同,Zipf律描述从大到小排序后位置r与处于该处的元素尺度或者规模x之间的关系(公式3);Pareto分布描述累计分布函数的性质,大于等于某一个尺度x的总概率正比于x的一个幂函数(公式5);幂律分布概率密度函数的性质,表明某一个尺度x的概率密度正比于x的一个幂函数(公式1)。

以现代的观点来看,这三者是等价的,是对于同样数据的三种不同侧面的展示。

先看一个简单的好说的,就是Pareto分布和幂律分布是一回事。为什么?Pareto分布表现的是就是概率密度函数的逆累积分布函数,从某一个x积分到无穷大,幂律函数的积分还是幂律函数,但幂指数会加1。所以幂律分布就可以通过逆累积分布得到Pareto分布。相反,如果对于Pareto分布求导数,就可以得到幂函数形式的概率密度函数。故二者是等价的。

如果对于逆累积分布乘上样本的数量实际上可以得到一个排名,就是这个排名之前的样本的取值大于当前的取值,或者当前的x取值的排名就是样本总数乘以Pareto分布在当前样本的取值。Pareto分布和Zipf律实际上是颠倒了横轴和纵轴,他们从图形上是关于y=x对称的。对数直线的Pareto分布等价于对于直线的Zipf律,斜率互为倒数。综上,这三者是同一个数据的不同展示形式,在双对数坐标下均为负斜率的直线,且满足关系

2.复杂网络与无标度网络

2.1复杂网络(complex network)和度(degree)

世界很复杂,特别是人的参与会增加其不确定性和更为复杂的关系。复杂的系统会呈现诸多属性和特征,各个属性之间的关联错综复杂,从复杂的系统抓住最核心的因素和作用机制是能成功分析系统应用系统的必由之路。
 
复杂网络是人类认识复杂世界的一个典型工具。
 
在研究一些具体的例子时,可以做一些简化,复杂网络就是对于真实系统简化得来的。例如研究消息在社会中的传播,假如个体不掌握诸如CCTV这样的媒体信息,那么很多消息是通过社会关系(特别是朋友关系)传递出去的,所以朋友关系就是消息传播的重要载体。在研究消息传播时,我们不用考虑他们穿什么衣服,也可以简化性别差异的影响,最后发现最核心的影响传播行为的就是这个社会关系网,在这个网络中个体被抽象为节点,关系被抽象为连边,个体的生物功能等完全不用考虑,节点的唯一功能就是通过连边传递信息。
 
图11是一个社会关系网络的示意图,左边表示一个非常局部的网络,个人为节点而具有朋友关系就会在相应的节点之间连一条边。节点的连边数量称为度(degree),图11(b)中的两个人(在其他的人都只有2-3个度的时候)的度是5,在这个局部区域的信息传递中一定会起到重要的作用。
 
整个社会关系网可能如图11(b)一样,很多的节点的度会很小,而一些节点的度很大,微博上一些大V的粉丝惊人地多,他们在消息的传递上具有相当高的话语权。这种度的分布(均衡程度)对于网络的功能具有重要影响。
 

2.2 无标度网络

2.2.1 无标度网络的定义

无标度网络(scalefree network)是复杂网络大牛A.-L. Barabási在1999年提出的概念,简单地说就是度分布服从幂律分布的网络。他在2018年重新讲述了他如此命名的原因——“We named these networks scale-free, inspired by the scale-free nature of power laws observed in the vicinity of phase transitions.”[2]。无标度网络中其各节点之间的连接状况(度数)具有严重的不均匀分布性:网络中少数称之为Hub点的节点拥有极其多的连接,而大多数节点只有很少量的连接。少数Hub点对无标度网络的运行起着主导的作用。

Barabási的这篇文章是无标度网络研究里面非常著名的一篇,至今已经引用了3万多次。在这篇文章里面有3个例子,第一个最左边的是演员合作网,第二个是万维网,第三个是一个电力网

在演员合作网络中,演员是节点(群众演员不算),如果两个人出演过一部影片,就是有一次合作,就连上边。经常出演的明星就会有机会和很多不同的人合作,例如周星驰、成龙就比较多,而其他人的度就会少一些。而这些节点的度作为随机数具有幂律分布特征,有些人的度会大得超出很多人的想象。补充一个例子,数学家P. Erdős一生中同500多位合作者发表超过1450篇数学论文,无论从合作者的数量还是发表文章的篇数都让人惊叹。

万维网是各个网站之间的关系,他们通过页面链接建立关系,这种度分布的幂律特征说明绝大部分网站没有多少与站外的互链,但有一些网站有很多与其他网站的链接,例如一些门户网站,如中国的新浪网。

如果给定网络节点,任意节点之间以相同的概率连一条边就构成随机网络(ER network)。这个网络经常被用来和其他网络进行结构和功能上的对比研究。如图13(a)这个网络中度分布具有比较集中的范围,不会存在度很大的节点,尾部呈现指数下降特征,与13(b)网络结构具有很大差异。更有意思的是,无标度网络具有一些令人惊讶的功能特征。

2.2.2 无标度网络的鲁棒且脆弱性

无标度网络的鲁棒且脆弱性似乎显得有矛盾,鲁棒性说明能够抵抗干扰,脆弱性说明不能抵御干扰。这两个矛盾的东西怎么能够集成在一个网络中呢?2000年的时候,Barabási等人写了一篇文章,用随机网络和无标度网络进行对比研究,讨论了节点随机失效和被有意图攻击的不同结果。

如图14所示,横轴为移除的节点比例,随机失效情况下随机移除节点,有意攻击时候从度最大的节点开始移除。纵轴表示任意两个节点之间最短距离的平均长度。如果d小说明两个节点的最短路径的预期长度越小。

理论的无标度网络和是的Internet网和万维网一样,在随机的失效情况下极具鲁棒性,但在专门进行大度节点攻击的情况下显得很脆弱,平均最短距离大幅增加。而随机网络在这两种情况下表现很一致,平均最短距离会随着移除的节点增加只是有小幅上升

无标度网络中大部分的节点的度都很小,属于“叶子”节点,删除它对于整个网络影响不大,但一旦移除掉很大度的hub节点,网络就会变得一下子零碎,整个结构被严重破坏。

这个研究具有应用价值。已经研究发现一些国家的航空网络它是无标度的,那么在战争的时候一旦重要机场被敌军摧毁,整个国家的航空网络就崩溃了。另外,一些大V散播谣言就会被禁言,就相当于这些重要的这些节点被移除,那么整个网络就会从谣言或者是从一些不良信息的传播里面恢复到正常状态,这是目前社会治理中的一个研究内容。

2.2.2 无标度网络上流行病不可根除

经典的SIS模型讨论了易感者和被感染者之间的转换,是基于均匀混合的人群的,也就是任何两个人都有潜在的相同的概率相互感染

如果流行病的传播是通过无标度网络进行的,结果会让人吃惊。图17表明在很小的有效传染强度情况下,不同规模的无标度网络上的被感染节点的密度变化,当网络规模很大的时候,被感染节点的密度衰减很慢。数学分析表明,只有在的情况下,感染密度才会趋近0。也就是说在无标度网络上传染病一般是不能根除的。不管你传播强度如何的小,以及治愈的能力多么的大,那么这一个网络上的病毒是不可能根除的。

例如计算机病毒在Internet网络上就难以根除。无论杀毒软件再强,只要不是100%免疫,只要大家都联网,而网络的度分布服从幂律分布,那么就不可能把病毒从整个计算机网络上清除干净,只要计算机在网上,它就有被传染的危险。

 

了解无标度网络的特征之后,就可以加以利用,比如在社会舆论上我们如何去引导构建和谐的舆论氛围,对于这一些关键的节点该怎么去处理它,例如让他们经常发表积极向上的观点(流行的话是“正能量”)无疑对于社会治理是有益的。为了防范系统性金融风险,要先了解银行之间的借贷关系构建借贷网络,避免级联效应造成的大规模银行倒闭。

3.如何产生幂律分布

前面谈了幂律分布以及度分布服从幂律分布的无标度网络,下面还有两个问题:

1、什么机制产生幂律分布,

2、如何去估计和检验一个实际的分布。

能产生幂律分布的机制非常多,这儿只给出几个经典、有趣的例子。

3.1偏好依附(Preferential Attachment)模型

Barabási在1999年发表的文章,提出了著名的偏好依附模型,这是一个动态的网络生长模型,步骤如图16所示,初始时候网络上存在一些节点和连边,每次增加一个节点和固定的边数,这些边不是等概率找两个以前的节点连上,而是以较大的概率选择度比较多的节点,这就是偏好依附的思想体现,数学形式上可以写为

3.2 货币转移模型

在讨论收入和财富分布的时候,一个经典模型就是货币转移模型。这个模型很简单,如图17所示,就是一堆人来随机瓜分一堆钱,在模型的运行过程中,随机找出两个人进行交易,交易过程就是把他们的钱放一起再做一次随机分配。这个图上的连线表示交易关系。在不同的参数情况下模型会得到不同的结果。

交易相当于把两个个体的钱收集起来,放在一个大罐子里面摇一摇,然后再重新随机分一下给他们。然后大家重新了钱,再去等候下一次交易。模型在不同的储蓄率的情况下结果不同,如果储蓄率为0,就是大家都把钱都拿出来随机分配,最后个体的持币量的分布是指数分布。而如果大家有一个一样不为0的储蓄率,最后会得到出伽马分布。而如果每个个体的储蓄率不同,都是随机的,最后会产生幂律分布[3]。

3.3最小值限制随机乘数模型

3.4 猴子随机打字模型

幂律分布的产生机制还有非常多,大家有兴趣可以自行了解。如果对于幂律分布的广泛存在感到好奇,更应该了解广义中心极限定理,大概意思是在方差有限的情况下多个独立作用的效果的极限是正态分布,但如果方差无限的时候,极限行为是Levy稳定分布,而这种分布虽然没有明确的密度函数形式,但尾端可以用幂律分布描述。具体可以参考北师大系统科学学院张江老师的文章[5]。

4.如何估计和判断幂律分布

判断实际现象是否服从幂律分布以及估计这个幂律指数是应用的基础。试想一个社会关系网络是一个随机网络,但被误判为无标度网络,被应用进行社会治理等方法,结果不仅浪费资源和成本,还可能适得其反。对幂律分布的估计和检验主要主要是从经典的回归+决定系数向极大似然估计+KS检验转变。

4.1回归与决定系数

如果我们知道分布函数的形式,通过直方图就可以直接进行非线性回归,图18是我们对于一些随机数得到的直方图进行幂函数回归的结果,使用工具为origin 8。可以直接得到参数的估计置信区间(一般是95%)和说明拟合效果的决定系数R2。如果决定系数大,说明用幂律分布函数拟合是合适的。这儿采用的最小二乘法拟合是使得残差的平方和最小。

4.2极大似然估计与KS检验

对于幂律分布参数的极大似然估计可以参考2005年[7]和2009年[8]Newman他们的文章。这儿只是简要说一下思想。极大似然的思想就是说能看见的这些样本,就是因为你看见这些样本出现的概率最大。为了方便计算,一般先算对数似然函数,在对参数求偏导,获得参数的估计。

回到幂律分布检验,以前主要是通过最小二乘法得到的R2来进行检验,一般决定系数越大就说明理论分布符合得很好,但多少才算好难以判断,大家对于决定系数的临界值等信息难以计算或者获得。目前学术上比较常用的检验是KS(Kolmogorov-Smirnov)检验。

KS检验广泛运用于比较一个频率分布f(x)与理论分布g(x)或者两个观测值分布的检验方法。其原假设H0:两个数据分布一致或者数据符合理论分布。D=max| f(x)- g(x)|,当实际观测值D>D(n,α)则拒绝H0,否则就不拒绝H0假设。

如图是两个累计分布函数,一个是理论的一个是实际数据的,找到两个分布的最大间距D后通过查表就可以进行判断,如果D超出一定显著性水平下的临界值就拒绝实际数据符合理论分布的原假设。这个临界值表会因为理论分布和样本数量而不一样,如果不方便找到这种临界值表还可以使用计算机模拟生成随机数进行多次实验计算进行,具体也可以参考Newman等人2009年的文章。

目前,可以直接从网站获得有关于幂律分布随机数生成、幂律参数估计和幂律分布检验的程序,包括R语言的和Matlab的以及Python的,下载地址是http://tuvalu.santafe.edu/~aaronc/powerlaws/。

小结

简单总结一下,本文介绍了幂律分布的形式、特点以及无标度网络的形式和特点,特别是无标度网络在于抵御攻击和传染病传播上的特异性。列举了一些经典的幂律分布随机变量生成机制,最后简介了对数线性回归和极大似然对于幂律指数的估计方式以及KS检验在幂律分布检验上的应用。

参考文献

[1] Hardy, M. (2010). Pareto’s law. The Mathematical Intelligencer, 32(3),38-43.

[2] https://www.barabasilab.com/post/love-is-all-you-need

[3] Repetowicz, P., Hutzler, S., & Richmond, P. (2005). Dynamics ofmoney and income distributions. Physica A: Statistical Mechanics and its Applications, 356(2-4), 641-654.

[4] Mitzenmacher, M. (2004). A brief history of generative models forpower law and lognormal distributions. Internet mathematics, 1(2),226-251.

[5] http://swarmagents.cn.13442.m8849.cn/files/jake2011616211724.pdf

[6] Gabaix, X., & Ibragimov, R. (2011). Rank− 1/2: a simple way to improve the OLS estimation of tailexponents. Journal of Business & Economic Statistics, 29(1),24-39.

[7] Newman, M. E. (2005). Power laws, Pareto distributions and Zipf'slaw. Contemporary physics, 46(5), 323-351.

[8] Clauset, A., Shalizi, C. R., & Newman, M.E. (2009). Power-law distributions in empirical data. SIAM review, 51(4),661-703.


最近国内外关于幂律分布是否广泛存在于真实世界的讨论非常热烈,具体可参考集智俱乐部发表的两篇文章:

理论危机 | 无标度网络遭到史上最严重质疑

Love is All You Need | 无标度网络理论之父Barabási回应史上最严重质疑

集智AI学园组织了一次题目为 “解读幂律(Power Law)分布与无标度(Scale Free)网络 ——贫穷限制了我们的想像力” 网络直播课程,旨在介绍幂律分布和无标度网络的基本知识。本文由音频改编润色形成,部分图片和文字进行了调整,有删节。

推荐 1