明日线上公开课预告

想要更好地了解幂律分布

下面这节免费公开课怎么能错过?!

10月10日 19:00-20:30 带你启程

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

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

将围绕以下4个问题展开:

  1. 什么是幂律分布

  2. 什么是无标度网络

  3. 如何产生幂律分布

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

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

全文概念地图 | 本文约10000字,建议阅读时间30分钟。

1.什么是幂律分布

1.1 正态分布

(normal distribution)

目前,幂律分布还没有进入概率论和数理统计的教材。为了便于大家理解,从大家熟知的、教材上讲得比较多的分布开始说起。

1.1.1身高分布

设想一个情况,如果要估计某个人的身高,如果你对这种人种不清楚,想必你一定难以回答。但如果给你足够多的这种人人给你观测,你就会有信心进行预测。为了方便预测,你会将这些人按身高区间进行统计,然后做出频率图,不出意外,这个频率应该如图1种红色所示,呈现出中间高两边低的特征,像一个钟的形状。

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

图1 某一些人口的身高分布特征图。红色为实际样本,绿色为正态分布的拟合

红色的是实际数据,而理论上是绿色图形,这个理论分布就是著名的正态分布,又名高斯分布(Gaussian distribution),可以看出这和实际的分布非常一致。

从这个估计出的期望和标准差,你就可以回答只要是这种人种的成年男性,他的身高95%的可能性应该在解读幂律分布与无标度网络 | 长文综述-集智俱乐部这个区间,其中解读幂律分布与无标度网络 | 长文综述-集智俱乐部为期望,解读幂律分布与无标度网络 | 长文综述-集智俱乐部为标准差。

例如中国华东地区成年男子的平均身高为171.38厘米,标准差为6.97厘米,大部分人应该在1米71左右,绝大多数人在157.72厘米-185.04厘米范围之内,只有5%的人会超过这个范围,像姚明这样长到229厘米的人实在凤毛菱角,偏离期望达到解读幂律分布与无标度网络 | 长文综述-集智俱乐部倍的标准差的可能性会小于1亿分之一(很抱歉拿不到准确的数字,从标准正态分布表没有查到)。如果身高确实服从这个分布的,我们基本上不可能看到身高超过5米的人。

1.1.2智商分布

还可以举一个例子,就是人的智商,如果大家用有钱又有闲的话,找来足够多的人测量一下他们的智商,然后也画出智商的分布,你也会发现它也是服从这样一个中间比较高,两边迅速衰减的分布图(图2)。

从图上可以看出,大家的平均智商在一百,只有很少的人能跑很远,据说莫扎特(Wolfgang Amadeus Mozart),爱因斯坦(Alfred Einstein)的智商很高,达到160以上,但只有千分之一的人才能有资格如此骄傲!进一步,我们可以讨论这样一个问题——智商达到1000的人存在吗?答案是,如果这个分布是对的,那么人类不可能达到,不可能在偏离期望那么远的地方找到正态分布随机数样本。

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

图2 人类智商分布示意图

虽然在这儿没有什么用,我们还是写一下正态分布的数学形式,如下

解读幂律分布与无标度网络 | 长文综述-集智俱乐部(1)

其中解读幂律分布与无标度网络 | 长文综述-集智俱乐部为期望,解读幂律分布与无标度网络 | 长文综述-集智俱乐部为标准差,都是有限的数值。

正态分布确实非常广泛存在,包括学生的成绩,某一人种成年男人或者女人的体重,行星轨道的偏差,以及一些实验上的误差等等,都是具有这种分布特征的。那么为什么这种分布普遍存在?

1.1.3中心极限定理

那么这个问题实际上在概率论和数理统计的教学中已经获得了解答。这就是中心极限定理,中心极限定理讨论了一些随机变量的和作为新的随机变量具有的性质。这儿有三个中心极限定理——

  • 棣莫佛-拉普拉斯(de Moivre - Laplace)定理,是中央极限定理的最初版本,讨论了服从二项分布的随机变量序列。它指出,n 个参数为 p的二项分布的和将以np为均值、np(1-p)为方差的正态分布为极限。

  • 林德伯格-列维(Lindeberg-Levy)定理,是棣莫佛-拉普拉斯定理的扩展,讨论独立同分布随机变量序列的中央极限定理。它表明,独立同分布、且数学期望和方差有限的随机变量序列的标准化和以标准正态分布为极限。

  • 林德伯格-费勒(Lindeberg-Feller)定理,是中央极限定理的高级形式,是对林德伯格-列维定理的扩展,讨论独立,但不同分布的情况下的随机变量和。它表明,满足一定条件时,独立,但不同分布的随机变量序列的标准化和依然以标准正态分布为极限。李雅普诺夫也研究讨论了这个问题,有些材料上标明是李雅普诺夫(Lyapunov)中心极限定理。

可以用高尔顿(Francis Galton)钉板实验获得对中心极限定理的理解。下图是一个实验装置。我们把一些钢珠放到上面的地方,然后它就会从上面中间的这个孔的落下。落下的过程中,它会碰到一个一个的钉子,碰到每个钉子的时候,小球都会做一个选择,要么往左边滚下去,要么往右边滚下去。经过第一层的选择后,小球会进入第二层,同样它也会面临这样的两个选择,到底是往左边走呢还是往右边走?

假设这些钉子的设计比较均匀的,小球每一次路径的选择都是等概率事件,向左走的概率为0.5,向右走的概率也是0.5,这是一个等概率的二项分布。小球经过一层是一个二项分布的选择,是一个二项分布的随机数,其结果是+1还是-1,而一层一层经过很多层后,它对于中心位置的偏差实际上是这些二项分布随机数的和,从实验结果上看,这是一个正态分布。

大家可以想,如果我们要小球滚到图中到最右边的地方,它一定要是经过多次的往右的选择才会到达这个,比较困难的,所以概率比较低。而最后滚到中间的路径选择比较多,概率也会大一些。

这个钉板实验实际上就是说明棣莫佛-拉普拉斯定理。扩展到其他分布,同分布的累加效果可以由林德伯格-列维定理来确定,这儿也有一些计算机模拟的图形[1],表明一些独立的同样分布的随机变量,它们和最后都会成一个正态分布,甚至包括U型的分布,从单个分布来看中间低两边高,但多个独立的这种变量加起来,最后也会呈现一个正态分布。

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

图3 高尔顿钉板实验装置

1.2 幂律分布

(power law distribution)

1.2.1幂律分布的几个例子

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

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

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

图1.标普500指数的收益率分布(红线为正态分布的拟合)

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

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

图2 美国家户收入分布和富豪的资产

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

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

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

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

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

图3 富人的富裕程度会超出我们的想象

图片来源:https://www.huliwenku.com/p/ac9aqgdo.html

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

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

解读幂律分布与无标度网络 | 长文综述-集智俱乐部 (1)

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

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

图4 幂律分布随机数的频数统计直方图(在线性坐标和双对数坐标下)

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

解读幂律分布与无标度网络 | 长文综述-集智俱乐部 (2)

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

1.2.3 地震的能量

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

图5 地震的能量/震级和发生频率的关系

图像来源:Christensen, K., Danon, L., Scanlon, T., & Bak, P. (2002).Unified scaling law for earthquakes.Proceedings of the National Academy of Sciences,99(suppl 1), 2509-2513.

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

1.2.4 城市规模

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

图6 城市规模的分布

图像来源:Newman, M. E. (2005). Power laws, Pareto distributions and Zipf's law.Contemporary physics,46(5), 323-351.

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

1.2.5 回信的时间间隔

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

图7 达尔文和爱因斯坦的回信时间间隔分布

图像来源:Oliveira, J. G., & Barabási, A. L.(2005). Human dynamics: Darwin and Einstein correspondence patterns.Nature,437(7063),1251.

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

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

1.2.6 幂律分布的期望和方差

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

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

1.2.7 幂律分布的标度不变性

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

图8 幂律分布的标度不变性

幂律分布的期望和方差让人意外,它还有一个让人意外特征,被称为标度不变性(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律的数学表达是

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

图9 语言中的Zipf律

解读幂律分布与无标度网络 | 长文综述-集智俱乐部 (3)

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

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

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

可以定义广义的Pareto法则,p份额的人口占据总财富1-p的份额。并且这个规律是可以迭代的,如p^2份额的人口占据总财富的份额,份额(1-p)^2的人口占据总财富的份额,则可以得到Pareto分布

解读幂律分布与无标度网络 | 长文综述-集智俱乐部 (4)

这是一个累计分布函数,表示大于某个量的人口份额正比于这个量的一个幂次函数,为Pareto指数,对于广义的Pareto法则,具有关系[1]

解读幂律分布与无标度网络 | 长文综述-集智俱乐部(5)

Pareto法则和帕累托分布是等价的。Pareto分布在双对数坐标下是负的斜率的直线,如图10的右图。

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

图10 幂律分布和Pareto分布

数据来源:Newman, M. E. (2005). Power laws, Pareto distributions and Zipf's law.Contemporary physics,46(5),323-351.

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律,斜率互为倒数。综上,这三者是同一个数据的不同展示形式,在双对数坐标下均为负斜率的直线,且满足关系

解读幂律分布与无标度网络 | 长文综述-集智俱乐部 (6)

2.复杂网络

无标度网络

2.1 复杂网络

(complex network)和度(degree)

世界很复杂,特别是人的参与会增加其不确定性和更为复杂的关系。复杂的系统会呈现诸多属性和特征,各个属性之间的关联错综复杂,从复杂的系统抓住最核心的因素和作用机制是能成功分析系统应用系统的必由之路。

复杂网络是人类认识复杂世界的一个典型工具。

在研究一些具体的例子时,可以做一些简化,复杂网络就是对于真实系统简化得来的。例如研究消息在社会中的传播,假如个体不掌握诸如CCTV这样的媒体信息,那么很多消息是通过社会关系(特别是朋友关系)传递出去的,所以朋友关系就是消息传播的重要载体。在研究消息传播时,我们不用考虑他们穿什么衣服,也可以简化性别差异的影响,最后发现最核心的影响传播行为的就是这个社会关系网,在这个网络中个体被抽象为节点,关系被抽象为连边,个体的生物功能等完全不用考虑,节点的唯一功能就是通过连边传递信息。

图11是一个社会关系网络的示意图,左边表示一个非常局部的网络,个人为节点而具有朋友关系就会在相应的节点之间连一条边。节点的连边数量称为度(degree),图11(b)中的两个人(在其他的人都只有2-3个度的时候)的度是5,在这个局部区域的信息传递中一定会起到重要的作用。

整个社会关系网可能如图11(b)一样,很多的节点的度会很小,而一些节点的度很大,微博上一些大V的粉丝惊人地多,他们在消息的传递上具有相当高的话语权。这种度的分布(均衡程度)对于网络的功能具有重要影响。

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

图11社会关系网

图像来源:https://business-networksw.org/page/30/?pages-list

2.2 无标度网络

2.2.1 无标度网络的定义

无标度网络(scalefree network)是复杂网络大牛A.-L. Barabasi在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点对无标度网络的运行起着主导的作用。

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

图12一些实际网络中的度分布可以近似由幂律分布表示

图像来源:Barabási, A. L., & Albert, R. (1999). Emergence ofscaling in random networks.science,286(5439),509-512.

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

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

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

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

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

图13 一些实际网络中的度分布可以近似由幂律分布表示

图片来源:Albert, R., Jeong, H.,& Barabási, A. L. (2000). Error and attack tolerance of complex networks.nature,406(6794), 378.

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

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

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

图14无标度网络对于随机失效的鲁棒性和对于有目的攻击的脆弱性

图片来源:Albert, R., Jeong, H.,& Barabási, A. L. (2000). Error and attack tolerance of complex networks.nature,406(6794), 378.

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

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

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

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

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

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

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

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

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

图15 流行病在无标度网络上的存活概率

数据来源:Pastor-Satorras, R., & Vespignani, A.(2001). Epidemic spreading in scale-free networks.Physical review letters,86(14), 3200.

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

3.如何产生幂律分布

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

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

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

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

3.1偏好依附

(Preferential Attachment)模型

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

解读幂律分布与无标度网络 | 长文综述-集智俱乐部 (7)

表示连接到度为的节点的概率。后续已经有一些类似的机制产生不同指数的无标度网络。在这儿要强调一下这个偏好依附的思想实际上是有很深的意义,马太效应说的也是这个意思,正反馈也是这个意思。现实上能找到很多正反馈的例子来说明幂律分布,例如有一篇文章提到,对于名字的偏好使用造成名字的分布呈现幂律特征

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

图16 偏好依附网络的形成过程

数据来源:http://barabasi.com/publications/1/review-articles

3.2 货币转移模型

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

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

图17 货币转移模型示意图

假如时刻的两个个体手中的货币分别为,若二人的存储率分别为,就是自己保留下来不用于交易的部分,则下一时刻二人的货币持有量变为

解读幂律分布与无标度网络 | 长文综述-集智俱乐部(8)

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

3.3最小值限制

随机乘数模型

随机乘数模型如下所示

解读幂律分布与无标度网络 | 长文综述-集智俱乐部 (9)

表示个体的大小是在迭代过程中每次乘以一个随机数产生的,例如

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

对(9)取对数并考虑到长期作用,可得

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

根据中心极限定理,lnX的极限行为是正态分布,即X的极限行为是对数正态分布。如果对随机乘数模型增加一个小的调整,设定一个最小的值,即如果

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

这种带有最小反射的随机乘数模型可以得到幂律分布随机数[4]。

3.4 猴子

随机打字模型

一些很简单的机制可以产生幂律分布的随机数。叫一个猴子来用一个有n个字母键和一个空格键的键盘随机打字,假设它以概率p敲击空格键,以1-p的概率等可能的敲击n个字母键。则随机得到一个长度为c的单词,它必须连续敲击c次字母键,然后按一次空格键,整个过程实现的概率为

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

如果我们按出来的词频从大到小排序,随机出来的短的词肯定概率大一些,会排前面(空格是一个特殊单词,占据位置1),则有长度为j的词占据的位置范围是

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

而排序位置大概在解读幂律分布与无标度网络 | 长文综述-集智俱乐部的词长度为j,频率为

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

代入解读幂律分布与无标度网络 | 长文综述-集智俱乐部,就可以得到

解读幂律分布与无标度网络 | 长文综述-集智俱乐部(10)

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

4.如何估计

和判断幂律分布

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

4.1回归与决定系数

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

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

图18 对幂律分布的非线性回归

非线性拟合的计算难度比较大,更广泛的使用是对数线性回归。即

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

回归后同样得到参数的估计和决定系数。如果只是知道大小和排序的关系,可以用

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

来进行回归得到估计,然后根据关系折算过去解读幂律分布与无标度网络 | 长文综述-集智俱乐部。但一些研究发现直接这样回归在样本量不多的时候容易出现偏差,而建议使用

解读幂律分布与无标度网络 | 长文综述-集智俱乐部 (11)

作者[6]认为对于排序调整0.5后的估计值更加可靠,此时的标准差为解读幂律分布与无标度网络 | 长文综述-集智俱乐部,n为样本数量。

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/。

参考文献

[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.

编辑:王怡蔺


解读幂律分布与无标度网络 | 长文综述-集智俱乐部

集智俱乐部QQ群|877391004

商务合作及投稿转载|swarma@swarma.org

搜索公众号:集智俱乐部

加入“没有围墙的研究所”

解读幂律分布与无标度网络 | 长文综述-集智俱乐部

让苹果砸得更猛烈些吧!

原文始发于微信公众号( 集智俱乐部 ):集智