博文
涌现之三：分形与幂律
||
涌现之三：分形与幂律
计算士
分形结构
幂律的起源有很多，构造出幂律分布的方法也有很多，但最早让幂律变得这么“出名”，并与复杂系统产生密切联系的，却是分形结构。
分形(Fractal)一词的创始人，美国数学家Mandelbrot1967年在Science上发表了著名的文章《英国海岸线有多长》（how Long Is The Coast Of Britain），从此使“分形”的概念变得十分流行。什么是分形呢？简单地说，就是说自然中存在的线、面、体，并不像古希腊人和欧氏几何期望的那样是光滑平整的，而是“坑坑洼洼”的。Mandelbrot有一句名言：“云彩不是球体，山岭不是锥体，海岸线不是圆周，树皮并不光滑，闪电更不是沿着直线传播的。”
Mandelbrot在《英国海岸线有多长》中指出，这个问题对实际生活造成的困扰之一就是，按照传统的方法，我们实际上是无法精确测量像海岸线这样的自然对象的测度的。因为对于海岸线这样的结构，用愈小的尺子，就能测出愈多的“坑坑洼洼”，得到的长度也越长。
那么，如何去描述这样的结构呢？我们需要用到“分数维”的思路。经典的欧式几何只使用了一二三等“整数维”，而“分形几何”则谈论那些具有分数维的对象。直观地说，一条拉直的线是一维的，而如果它像海岸线一样变得歪歪扭扭，就可能介于1维到2维之间。以此类推，一个像榴莲壳一样极不平整的面的维度就介于2和3之间，一个由各种毛细管道构成的生物体的维度就介于3和4之间···
|
生命的第四维 等等，如何想象第4维呢？我们先不对这个问题做过多深究，在这个问题上，我们可以向数学家学习，他们是如此自如地谈论几十维的空间，好像那些怪物真的存在似地。实际上，由于毛细管道的复杂分形构造，生物体具有接近4的维度的观点，已经被圣塔菲的West和新墨西哥大学的Brown用于解释生物体的异速增长率（Allometric）中的指数3/4，这个内容在“涌现之二”已经由张江介绍，相关的文献可参考Geoffrey B. West, James H. Brown, Brian J. Enquist, The Fourth Dimension of Life: Fractal Geometry and Allometric Scaling of organisms, Science 284, 1677(1999)。 |
分数维的测量
测量分数维有很多种方法，这里集中讨论其中最常用的一种：盒子维（box dimension，在Mandelbrot的原文中被称为Hausdorff Dimension）。盒子维，顾名思义，就是用一个个“小盒子”去量对象的测度。这种方法抓住了分形结构“用来量的尺子越短，得到的长度越长”的特点，先用布满空间的大盒子去套对象，被“装到”的部分记为1，没“装到”的部分记为0，去数有多少个记为1的盒子；然后再一步一步使用越来越小的盒子，由此对对象的测量渐趋精细。用个比喻的说法，这个测量过程就好比从飞机上带着降落伞往下跳，一开始看见的海岸线比较平滑，随着高度下降，距离拉近，看到的结构越来越复杂，得到的信息也越来越多，测得的长度也越来越接近真实值。
把在这个过程中每一步的“盒子”的在一维尺度上的缩小倍数画在X轴上，数得的相应的抓到对象的盒子数画在Y轴上，每一步得到一个点，把这些点连起来，在双对数坐标轴中，就会形成一条直线，这条直线的斜率就是对象的分形盒子维。
|
英国海岸线的分数维 实际上，我们可以测出西英国海岸线的维度大概为1.25，而与之比较，南非海岸线的维度为1.02（参见Richard的研究结果），所以，英国西海岸要比南非海岸更“坑坑洼洼”一点。 |
这里面还有个细节，因为分形结构有着不同的维度，因此“盒子”的维度也要恰当选取。一般来说，盒子的维度就是这个分形对象在传统的欧式几何中表达出来的维度。比如测海岸线就用一维的盒子，测出来测一幅画则要用二维盒，测一只猪则要三维盒子···另外，什么是盒子“在一维尺度上的缩小倍数”呢？如果我们把刚好覆盖全图的盒子拿过来，不管这个盒子究竟是几维的，取其一维规模为1，随着盒子的整体size变小，盒子在一维上规模缩小的程度就是这个“缩小倍数”（或者说，盒子在一维尺度上缩小比例的倒数，但这样就太绕口了···）。
规则图的分数维
以上图中的第二个小图为例，这个图是分型几何中有名的谢宾斯基（Sierpinski）三角形，就是把一个正常的等边三角形不断“镂空”的过程。我们设可以一口气包下整个三角形的正方形盒子的边长为1，用1/2边长的正方形去套该三角形可以得到三个三角形，用1/4的边长去套可以得到9个···因此，我们总结出个规律，当盒子的一维尺度成倍压缩时，包含对象的盒子数也成倍增长，把这个规律写成log(N)/log(n)的格式，取n为无穷大表示这个过程不断进行下去，可以求得log(N)/log(n)即为分形盒子维。这个结果，几何地表示出来，就是每一步的点在双对数坐标系下的连线的斜率。
|
自相似结构与标度不变性 人们发现，许多自然界的结构，在这种“坑坑洼洼”中，又存在着“自相似”的现象：半径长达几公里的台风大气旋，在几米的尺度上看，也是由一个个小气旋构成的；一块磁铁被任意地切割，总会形成新的有南北两极的小磁铁。这种现象也可以称为“标度不变性”，指的是无论在什么样的尺度下，这个分形结构的形状都是一样的。我们在这里提出一种猜想，有着“自相似”分形结构的对象，在按照上述方法绘制的双对数坐标系下的直线是过原点的。但这个猜想目前还没有被证实。 |
不规则图的分数维
在上图的第三个小图中，我们处理一个不规则图形。值得注意的是我们这里的全图不是一个正方形，因此图中的s，指的是长方形的长上的格子的缩小比例，第一步的缩小倍数为6，得到19个被填充的盒子；第二步缩小倍数为12，得到54个被填充的盒子；坐标系中X轴上的两点之差是log12-log6，Y轴上的两点差是log54-log19，最后得到的线的斜率为(log54-log19)/( log12-log6)=log(54/19)/log2=1.507。
我们发现，如果不用长方形的长，而是用宽的话，得到第一步的倍数是4，第二步的倍数是8，X轴上的差是log8-log4=log12-log6=log2，Y轴不变，因此斜率也不变。从这里我们看到，只要我们保持盒子是正方形（立方体、四维立方体···），使用原图的任意一方向上的缩放比例来计算，结果都是一样的。有趣的是，不使用任何一个方向上的缩放比例，而直接使用盒子的个数，结果也是一样的，因为log8-log4=log12-log6= log8 *12-log4*6=log2。由于这个指标更易懂，因此我们在维度较低的时候提倡这个指标的使用，但是在分析高维对象的时候，这个指标就会带来不必要的计算量。
另外，还有一个问题，我们知道在谢宾斯基三角形中，这个盒子的缩小过程可以被写成一个表达式，这也意味着如果将其几何过程表达为一条由许多点连起来的线，这些点都在一条线上，而且这条线是过原点的，因此，其实只要有一个点就可以画出这条线并求出斜率。对于不规则图，我们可以看出这条线未必是过原点的，因此求出斜率至少要有两个点。那么，如果有更多点，这些点在一条线上吗？
答案是否定的。实际上，对不规则图的分形盒子维计算，是通过回归拟合一系列点得到的。举一个例子，http://www.mathworks.com/matlabcentral/fileexchange/15918给出了一个简易的程序，可以使用Matlab来计算1-2维之间的分形盒子维。其程序的思想是将一个图以象素的方式读入Matlab，成为矩阵，并以01赋值的方式将要分析的曲线在矩阵中表达出来，随后把这个矩阵切割成等分的blocks，计算抓住待分析曲线的blocks的个数。如下图所示，随着blocks数的不断增多，对曲线分数维的描述也越来越精确。需要注意的是本处的图的X轴上标的就是经过对数处理的盒子的个数，而不是盒子在一维上的缩小倍数，不过正如我们已经分析过的那样，这两个指标的区别对计算结果是没有影响的。
分数维与幂律
通过思考盒子维的计算过程，我们可以这样总结分数维的：随着测量尺度的缩小，量得的分形对象的测度（长度、面积、体积）增加的速度。分数维也能用于代表对象的结构复杂性，对象的结构越复杂，分数维越大。如果我们直接用测量尺度的大小做X轴，这个斜率就会变成负的，如下图所示（该图的坐标不具备参考意义）：
对所有研究复杂系统的人来说，这个图是十分熟悉的，这是一个典型的幂律（Power Law）分布图。在幂律中，最“有名”的幂律是Zipf定律与Pareto定律。实际上,幂律分布广泛存在于物理学，地球与行星科学，生物学，人口统计学，经济学等众多领域中。
目前经实证研究指出分布为幂律的有：地震规模大小的分布（古登堡-里希特定律）、月球表面上月坑直径的分布、行星间碎片大小的分布、太阳耀斑强度的分布、计算机文件大小的分布、战争规模的分布、、大多数国家姓氏的分布、科学家撰写的论文数及论文被引用的次数的分布、网页被点击次数的分布、书籍及唱片的销售册数或张数的分布、每类生物中物种数的分布、甚至电影所获得的奥斯卡奖项数的分布等。
幂律分布的现象的一个重要特征是无标度（Scale free）：系统中个体的尺度相差悬殊，缺乏一个具有代表性的规模。按照Barabasi在Link一书中的说法，诸如正态分布这样的分布，我们可以找到一个mean，用于代表大部分的个体，但像幂律却不存在这样的一个具有代表性的size，因此，是难以用某个固定规模的标度（scale）来描述系统个体的分布的。
我们发现，在分形结构和复杂网络等研究领域中，都出现了无标度和幂律的概念，那么，在这些领域中的幂律和无标度，说的是不是一件事呢？这是有可能的。在所有出现幂律分布的地方，我们都在处理同一个问题：尺度变化与获得信息的关系。
以复杂网络为例，上图引自Barabasi1999年发表在Science上的“成名作”Emergence of Scaling in Random Networks（Albert-Laszlo Barabasi and Reka Albert., Science 286, 509（1999））。其中A 是演员合作网，B是互联网，C是电力网，三张图均是在双对数坐标系下的度分布图。也就是X轴代表一个节点存在直接联系的邻居数，Y轴代表拥有该数量的直接邻居数的节点个数。如果我们使用上文的视角来看，也可以将度分布图视为，随着测量度的尺度的不断减小，得到网络的越来越精确的结构的过程。实际上，信号处理中的“小波多分辨率理论”（wavelet multi-resolution theory，又称“多尺度小波分解”），就是这个过程在信号处理和图像处理方面的应用。
既然网络节点度分布、财富分布、词频分布等幂律分布的形状和原理与分形维的计算原理一致，那这些幂律分布在双对数坐标系下的斜率是不是也是“分形维”呢？如果说对复杂网络，“分形维”是有意义的，可以直接用于表示网络复杂的程度，那对于财富分布、词频分布等，“分形维”的意义又是什么呢？
这就回到了“结构”和“流”的关系上。我们将继续在探索的道路上前进。
|
单变量幂律与双变量幂律 我们这里举的大部分例子，从分形维的计算到财富分布，都是单变量幂律：X轴代表该单变量的尺度变化，Y轴代表该变量的数量变化。而之前提到的生物学中的3/4率，则是双变量幂律：X轴代表一个变量的尺度变化，Y轴代表另一个变量的尺度变化。单变量幂律与双变量幂律之间存在着什么样的关系？两个单变量幂律分布在什么样的条件下可以被表示为双变量幂律分布呢？ |
https://blog.sciencenet.cn/blog-284004-252105.html
上一篇：涌现之一：最可能者生存？应用热力学定律解释自然选择
下一篇：复杂系统研究的第谷与牛顿
