3 幂律分布研究: 当前许多领域(像生物学、计算机科学)的进展都面临着要处理一些复杂系统问题[31],自然界和社会中的系统的复杂性可归因于一个个交织的网络(像生态网、因特网)的复杂性,通过这些复杂网络,系统的各个组成部分相互之间发生着各种线性的、非线性的作用。复杂网络[32-35]的研究应运而生,它是近年来刚刚兴起的一个研究方向,隶属复杂性科学,教导我们从网络的观点来看待整个世界,甚至我们人类都可看成是复杂网络中的一个个小小的节点。钱学森[36]给出了复杂网络的一个较严格的定义:具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络称为复杂网络。目前,这个新领域已聚集了一大批杰出的物理学家、生物学家、计算机网络专家、数学家和社会学家。 从统计物理学来看,网络是一个包含了大量个体及个体之间相互作用的系统。近年来在对复杂网络的研究过程中,科学家们亦发现了众多的幂律分布,虽然这些网络在结构及功能上是如此的千变万化,相差迥异。复杂网络中节点的度值k*相对于它的概率P(k)满足幂律关系,且幂指数多在大于2小于3的范围内[31,32];这一现象是如此的普遍,如此地令人惊叹不已,以至于人们给具有这种性质的网络起了一个特别的名字——无标度网络[37]§。这里的无标度是指网络缺乏一个特征度值(或平均度值),即节点度值的波动范围相当大。
------------------------------------------
* 节点的度定义为与该节点相连接的节点的个数。
§ 可能地,Price[17] (Science, 1965)所研究的索引网络是第一个被发现的无标度网络。
------------------------------------------
无标度网络在自然界和现实生活中的实例举不胜举**,像Internet[38]、WWW[39,40]这样的技术性网络,电子邮件网络[41]、电影演员合作网络[42]、引文关系网络[43]这样的社会性网络,甚至细胞代谢网络[44]、蛋白质调控网络[45]、食物链网络[46]等之类的生物网,都是典型的无标度网络。在过去的40多年里,科学家们一直想当然地认为现实中的网络都是随机的,随机图论[47]就是专门为了研究随机网络而发展起来的一门数学学科,但无标度特性的发现打破了这种构想。随机网络的度分布是泊松分布,度值比平均值高许多或低许多的节点,都十分罕见,是一种高度“民主”的网络,而无标度网络的度分布则是幂律分布,节点度值相差悬殊,往往可以跨越几个数量级,是一种极端“专制”的网络,二者之间有本质的区别。这两种网络的一个形象化的比较如图3[48]所示。
------------------------------------------
** 存在一些指数型度分布的复杂网络[37],如高速公路网,电力网。
------------------------------------------
图3 具有相同节点数和边数的随机网络(左)和无标度网络(右)
度分布满足幂律的无标度网络还有一个奇特的性质——“小世界”特性[49],虽然WWW中的页面数已超过80亿,但平均来说,在WWW上只需点击19次超链接,就可从一个网页到达任一其它页面。“小世界”现象在社会学上也称为“六度分离”,它来源于1967年,美国哈佛大学的社会心理学家Milgram的一个实验[50-52],这个实验证实,世界上任何两个人,不论他(她)是中国的藏民,非洲的难民,还是美国的政界高层,好莱坞的明星,甚至北极的爱斯基摩人,美洲的土著印第安人,都可通过熟人找熟人的方式建立联系,而两者之间的平均最少“中介”数是6,如此看来,整个地球确实是一个小小的世界。
图4[53]是Internet的拓扑图,它具有很强的自相似性,跟河流网之类的分形图非常类似。分形理论的创始人Mandelbrot[54]曾说过,“当你看到一个非整数指数关系,就应想到分形。不过你应当小心从事”。可以说,幂律分布与分形、非线性、复杂性密切相关,它支配了所有自然演化的具有自相似特性的无标度网络。无标度网络的度分布是一个非整数指数关系,这种网络的拓扑图呈现分形特征也在情理之中。近年来,物理工作者们日渐对无标度网络的拓扑结构产生了浓厚的兴趣,并构建了多种物理定义,从不同的角度研究了无标度网络的分形维问题[55-57]。
简单性一向是现代自然科学、特别是物理学的一条重要的指导原则[58]。许多科学家相信自然界的基本规律是简单的,爱因斯坦就是这种观点的突出代表者,他曾说过,“要使我们的理论尽可能得简单——但不是更简单。”从普适简单的幂律,我们似乎可以说,大自然是如此的复杂,而支配它的物理定律却又是如此的简洁优雅。
4 幂律分布的形成机制
如此广泛的幂律是怎样形成的呢?这是目前许多学者关注的焦点,毕竟一味地到处寻找幂律关系并没有多大的意义,而支配它形成的最根本的动力学原因才是最重要的。从现象到本质的探索一直是物理学的使命,十几年来,或者几十年来,为了解释幂律分布的形成原因,科学家们提出了几种机制,包括增长与优先连接[42, 59]、自组织临界[60, 61]、HOT理论[62, 63]、渗流模型[8,64-66]及一些随机过程[7, 8, 67]等。
一些解释幂律形成原因的机制是相当复杂的,甚至动用了“临界现象理论”和“重正化群”[68,69]等工具。其实,一些简单的代数方法——像“指数组合”[7,8]、“变量替换”[70]——亦能产生幂律分布,比如,Miller[71]曾用“指数组合”的方法解释了英文单词频率的幂律分布,Reed和Hughes[7]利用该机制,并结合随机过程,解释了城市人口分布、生物物种数分布等幂律分布。
图4 Internet在自治系统层次上的拓扑图
4.1 优先连接
Barabási与Albert针对复杂网络中普遍存在的幂律分布现象,提出了网络动态演化的BA模型[42,59],他们解释,成长性和优先连接性是无标度网络度分布呈现幂律的两个最根本的原因。所谓成长性是指网络节点数的增加,像Internet中自治系统或路由器的添加,以及WWW中网站或网页的增加等,优先连接性是指新加入的节点总是优先选择与度值较高的节点相连,比如,新网站总是优先选择人们经常访问的网站作为超链接。随着时间的演进,网络会逐渐呈现出一种“富者愈富,贫者愈贫”的现象。社会学家所说的“马太效应”[72],《新约》圣经所说的“凡有的,还要加给他,叫他有余”,同优先连接也有某种相通之处。
“优先连接性”的思想并不是BA模型的原创,早在1925年,Yule[73]在解释每类植物物种数的分布满足幂律分布的原因时就已经提出了类似的思想,虽然当时研究的对象不是复杂网络。1955年,Simon[74]对优先连接性作了进一步深入的研究***,他对网络中可能存在的幂律不怎么感兴趣,但他列举了五种可以用他的理论解释的幂律分布:文献中单词频率的分布,科学家撰写的科技文献数量的分布,城市人口的分布,收入的分布及每类生物中物种数的分布。
------------------------------------------
***
在Simon的工作之前,Champernowne[75]就提出了一个类似于“乘法过程”的数学模型,解释了个人收入分布的幂律现象。实际上,Simon的工作只是Champernowne模型的推广。
------------------------------------------
“优先连接”并不适用于所有出现幂律分布的情况,即便是对于某些无标度网络,用它解释幂律的成因也显得很不合理。以生态系统中的食物链为例,认为被捕食者最有可能被猎物广泛的杂食性捕食者吃掉,确实是一件很荒唐的事。还有像Internet、航空网等网络,流量或容量的限制可以在一定程度上抑制优先连接性,电影演员的合作网络中,节点(演员)的衰老或隐退也能起到类似的作用。
4.2 自组织临界
自组织临界理论[61]是一个影响深远的理论,在复杂系统的研究领域中,该模型曾一直被认为是产生幂律分布的动力学原因,幂律亦可作为自组织临界的证据。它认为,由大量相互作用的成分组成的系统会自然地向自组织临界态发展;当系统达到这种状态时,即使是很小的干扰事件也可能引起系统发生一系列灾变。布鲁克海文实验室的Bak、加州大学圣巴巴拉分校的汤超和佐治亚理工学院的Wiesenfeld等人用著名的“沙堆模型”[61,
76]形象地说明了自组织临界态的形成和特点(如图5[76]):设想在一平台上缓缓地添加沙粒,一个沙堆逐渐形成。开始时,由于沙堆平矮,新添加的沙粒落下后不会滑得很远。但是,随着沙堆高度的增加,其坡度也不断增加,沙崩的规模也相应增大,但这些沙崩仍然是局部性的。到一定时候,沙堆的坡度会达到一个临界值,这时,新添加一粒沙子(代表来自外界的微小干扰)就可能引起小到一粒或数粒沙子,大到涉及整个沙堆表面所有沙粒的沙崩。这时的沙堆系统处于“自组织临界态”,有趣的是,临界态时沙崩的大小与其出现的频率呈幂律关系。这里所谓的“自组织”是指该状态的形成主要是由系统内部各组成部分间的相互作用产生,而不是由任何外界因素控制或主导所致,这是一个减熵有序化的过程;“临界态”是指系统处于一种特殊的敏感状态,微小的局部变化可以不断被放大、进而扩延至整个系统。
图5 “沙堆模型”
幂律分布是自组织临界系统在混沌边缘,即从稳态过渡到混沌态的一个标志,利用它可以预测这类系统的相位及相变。自组织临界理论可以解释诸如火山爆发、山体滑坡、岩层形成、日辉耀斑、物种灭绝、交通阻塞、以及金融市场中的幂律分布现象。这种理论的启示是小事件和大事件可能有相同的起因,这为地震、恐龙灭绝、森林火灾等复杂大系统的突变提供了新的解释。以恐龙灭绝为例,古生物学家经过对化石的研究指出,这一重大事件不是经历了数万年或者几年,而是在20多天的突变中“一朝覆灭”的。恐龙的灭绝可以被看作是处于临界状态下的生态系统发生的一次“大雪崩”。
4.3 HOT理论
另一种解释幂律分布形成原因的重要理论是HOT[62, 63, 77],由加州大学圣巴巴拉分校的Jean Carlson以及加州理工学院的John Doyle提出。他们宣称,对于由许多子系统连结成的复杂系统, 不管是自然演化还是人为设计的,当该系统可以有效地容忍某些不确定因素时(具强健性),将对其它未被考虑到的不确定因素变得更敏感。也就是说,强健性和敏感度具有相互递换的效果。这里的不确定因素包含系统内部的不确定因素以及外在环境的干扰。以生态系统为例,如果它可以容忍气温变化、湿度、养分等巨幅变化,那么这生态系统却可能无法容忍一些意料之外的小干扰,如基因突变、外来族群迁入、或新的病毒,这些干扰可能会造成生态环境的巨大改变。
当一复杂系统处于HOT状态时,该系统将满足幂律,也就是说,全局性的优化过程可导致幂律分布:具有特征尺度的输入经过一个全局性的系统“产量”优化过程后,可产生具有幂律分布特性的输出。全局性优化在生态系统、航空航天与汽车系统、林业系统、因特网、交通运输及电力系统中具有广泛的应用,HOT理论可以解释上述系统中出现的幂律分布现象,比如可以解释林业系统中火灾规模所呈现的幂律分布。
4.4 随机过程
一些随机过程也可以产生幂律分布:“随机行走”模型可以解释物种寿命所呈现的幂律分布[78];“Yule过程”[21,73]是一个生成幂律的比较通用的机制,通过调节它的某些参数,可以产生幂指数范围相当宽广的幂律分布,并可与实际观测值相一致。
产生幂律分布的机制是相当多的,是否存在某个单一的、通用的理论可以解释所有的性质迥异的幂律分布呢?有一部分学者,特别是自组织临界理论的支持者,声称他们的理论可以,但大多数科学家认为[79],幂律分布是许多不同的过程或作用导致的结果,这就像经典力学,牛顿的经典力学固然很伟大,但它仅适用于宏观低速的情形。
5 幂律分布的动力学影响
幂律分布的动力学影响主要是对复杂网络而言的。网络动力学性质的基本研究对象是动力学模型在不同网络上的性质与相应网络的度分布的联系,在一定程度上说,这是一种关于网络的结构与功能关系的研究。
幂律特性的度分布对无标度网络的动力学性质有着极其深刻的影响。以疾病或病毒在网络中的传播这一物理过程为例,以前的基于规则网络及随机网络的研究表明[80-82],疾病的传染强度存在一个阈值,只有传染强度大于这个阈值时,疾病才能在网络中长期存在,否则感染人数会呈指数衰减。但对无标度网络上传染病模型的研究结果表明,不存在类似的阈值[83-86],只要传染病发生,就将长时间存在下去,这一特性表明,要想在Internet这样的无标度网络上彻底消灭病毒,即使是已知的病毒,也是不可能的[37]。
另外,度分布的幂律特性对网络的容错性和抗攻击能力也有很大的影响,对网络的攻击分为随机攻击和选择性攻击两种类型[87],分别称为网络的容错能力与抗攻击能力。研究表明[87,88],无标度网络具有很强的容错性,但是对基于节点度值的选择性攻击抗攻击能力相当差。比如对万维网或因特网中集散节点的攻击,有可能造成整个网络的瘫痪,对于某些微生物来说,它们体内度值很高的蛋白质通常掌握着细胞的生死(如图6[37]所示)。度分布满足泊松分布的随机网络,其容错性和抗攻击能力则是基本相当的[87]。可见,网络的结构稳定性是与网络的度分布特性紧密联系在一起的。
图6 酵母菌体内蛋白质的相互作用关系图
对于幂律分布对网络的其它动力学方面的影响,比如对网络上Ising模型[89,90]、XY模型[91]、临界现象[92]及沙堆模型[93]等的影响,限于篇幅,本文不再赘述,有兴趣的读者可以参考相关文献。幂律分布对现实中无标度网络的动力学性质影响深刻,这在相当程度上改变了我们对原有物理世界的看法,并进一步显示了幂律分布的重要性。
6 结束语
幂律分布已有超过一百年的研究历史了,即使在现在,仍然是众多学科研究的热点。它那简洁优雅的形式,可以将许多似乎毫不相干的事物联系在一起,这种独特的魅力吸引了一大批杰出的物理学家、生物学家、天文学家、地质学家、数学家和社会学家,并不断有新的研究者加入到该领域。但即便如此,要真正从本质上把握驱动系统呈现幂律分布的物理过程与机制,仍然有许多试验或理论性的工作要做。另外,不同类型的幂律分布幂指数有很大的不同,究竟是什么原因导致了这种不同?这仍然是一个尚未完全解决的问题。不过,我们相信,不久的将来,在众多科学家的共同努力下,人类最终将根本性地破解幂律分布之谜,为物理世界的简洁之美再谱华章。
参考文献
[1] http://www.guinnessworldrecords.com/gwr5/content_pages/record.asp?recordid=48409, 2005
[2] http://www.guinnessworldrecords.com/content_pages/record_category_a.asp, 2005
[3] http://www.worldbank.org/data/databytopic/GDP.pdf, 2004
[4] http://www.worldbank.org/data/databytopic/POP.pdf, 2004
[5] http://www.hpl.hp.com/research/idl/papers/ranking/ranking.html, 2000
[6] 张济忠.分形.北京:清华大学出版社,1997. 348[ Zhang J Z. Fractal. Beijing: Tsinghua
University Press, 1997. 348 (in Chinese) ]
[7] Reed W J, Hughes B D. Phys. Rev. E, 2002, 66: 067103
[8] Newman M E J. arXiv: cond-mat/0412004 v2
[9] Gutenberg B, Richter R F. Bulletin of the Seismological Society of
America, 1944, 34:185
[10] Neukum G, Ivanov B A. Crater size distributions and impact
probabilities on Earth from lunar, terrestrial planet, and asteroid
cratering data. In: Gehrels T (ed.). Hazards Due to Comets and Asteroids.
Tucson: University of Arizona Press, 1994. 359
[11] 张济忠.分形.北京:清华大学出版社,1997. 326[ Zhang J Z. Fractal. Beijing: Tsinghua
University Press, 1997. 326 (in Chinese) ]
[12] Lu E T, Hamilton R J. Astrophysical Journal, 1991, 380: 89
[13] Crovella M, Bestavros A. IEEE/ACM Transactions on Networking, 1997,
5(6):835
[14] Roberts D C, Turcotte D L. Fractals, 1998, 6: 351
[15] Zanette D H, Manrubia S C. Physica A, 2001, 295: 1
[16] Lotka A J. J. Wash. Acad. Sci, 1926, 16: 317
[17] Price D J de S. Science, 1965, 149: 510
[18] Adamic L A, Huberman B A. Quarterly Journal of Electronic Commerce,
2000, 1: 5
[19] Cox R A K, Felton J M, Chung K C. Journal of Cultural Economics,
1995, 19: 333
[20] Kohli R, Sah R. Working paper, Harris School of Public Policy,
University of Chicago, 2003, 04.01
[21] Willis J C, Yule G U. Nature, 1922, 109: 177
[22] http://www.collisiondetection.net/mt/archives/001136.html, 2005
[23] http://news.xinhuanet.com/newmedia/2005-03/17/content_2710396.htm, 2005
[24] Teslyuk A B, Krashakov S A, Shchur L N. arXiv: cs.NI/0404010
[25] 张宇,张建玮,王正行.物理,2004, 33(10): 734[ Zhang Y, Zhang J W, Wang Z X.
Wuli(Physics), 2004, 33(10): 734 (in Chinese) ]
[26] http://staff.science.nus.edu.sg/~parwani/c1/node87.html, 2002
[27] Montemurro M A. arXiv:cond-mat/0104066 v2
[28] 张济忠.分形.北京:清华大学出版社,1997. 350[ Zhang J Z. Fractal. Beijing: Tsinghua
University Press, 1997. 350 (in Chinese) ]
[29] Colander D C. Microeconomics 4th ed. Boston: McGraw-Hill, 2001. 428
[30] Hu H B, Wang L. Advances in Complex Systems, 2005, 8(1): 159
[31] Barabási A-L. Emergence of scaling in complex networks. In: Bornholdt
S, Schuster H G (Eds.). Handbook of Graphs and Networks: From the Genome
to the Internet. Berlin: Wiley-VCH, 2002. Chapter 3