复杂网络稀疏性的统计物理研究综述

朱陈平, 张永梅, 刘小廷, 王荣芳, 王新光

(南京航空航天大学应用物理系,南京 210016)

复杂网络稀疏性的统计物理研究综述

朱陈平, 张永梅, 刘小廷, 王荣芳, 王新光

(南京航空航天大学应用物理系,南京 210016)

大多数实际存在的复杂网络是稀疏的,即网络平均度远小于节点数:k—≪N.到目前为止,关于这一性质的起源,它对于网络功能与网络上动力学过程的影响,可能的应用价值的研究还都远远不足.实际上,稀疏性与网络的其它拓扑性质密切相关.近几年来,人们对复杂网络稀疏性的相关效应从理论和实验两个方面都做了深入的研究,但是,还缺乏原理性的探讨.从统计物理的视角出发,稀疏性应当被看作复杂系统中个体之间相互作用的涌现性质,而不应当是现有模型中先验的前提.本文拟就复杂网络稀疏性的统计物理研究作一综述.

复杂网络;稀疏性;统计物理

1 大多数实际存在的大型网络都具有稀疏性[5-8］

大多数实际存在的大型网络都具有稀疏性[5-8],满足k—≪ln N≪N,或者k—～ln N的网络就是稀疏网络,其中k—为平均度,它是平均每个节点连边数目的两倍.在系统生物学[9]中,也常常定义在一对给定的节点之间在给定方向上的连边概率p= E/N2,E为总边数.当p≪1时,网络就是稀疏的.

绝大多数生物网络都是稀疏的,这一性质已经引起生物界(特别是新近兴起的系统生物学界)的广泛重视.基因调控网络(GRN)[9-10]是典型的稀疏网络.已被详细研究过的一些典型GRN的平均每基因连边数(平均度的一半)在(2,10)的范围.其入度大致为泊松型的,出度近似为幂律分布,Kundu[11]将单一蛋白质的结构信息分亲水和疏水两种类型记录在氨基酸残基之间相互作用的网络中,把这两种氨基酸网络分开来分析.结果表明,两种网络都具有小世界性质,平均度大致介于(2.72,7.58)的范围,两个网络的长程相互作用的度分布都是有指数截断的幂律形式,疏水网络具有比亲水网络更大的平均度.

一些技术网络也具有稀疏性,电力网[12]是其中的典型例子.Krapivski等[13]在给出描写Internet和WWW的拓扑性质的log网络模型时指出,Internet 和WWW展示出与log网络的某种相似性.例如:在WWW网中,边的总数超过节点总数一个数量级,与Internet(尤其是自治系统的AS图)相似,每个节点的平均边数也系统地随时间缓慢增长.但是,它们也是比较稀疏的.在下一代综合通讯系统的热点课题—-移动ad hoc通讯网络(MANET)的研究中,实验和理论都表明,MANET可以工作在稀疏连通的状态[14-16].最近,笔者的研究发现,工作在临界渗流状态附近的纳米碳管网络是相当稀疏的[17].这种网络独特的电导、热导与透明性质正在成为热点研究课题.

一批交叉科学研究者们发现,语言的概念网络也是稀疏的[18],它具有小世界性质,同时还有指数开头的幂律度分布.Krapivski等[13]对《Physical Review》系列杂志引文网的实证统计也表明,从1997年到2001年,对于PR的长期出版数据,平均每篇文章参考文献的数目,出度随总的文献规模缓慢增长,与他们模型预测的对数增长相吻合.

2 稀疏性与网络的其它拓扑性质密切相关[4］

3 复杂网络稀疏性的统计物理研究新进展

Watts[21]很早就指出:由于搜集信息和建立关系都是耗费精力的操作,连边需要付出代价,所以相互作用和影响的网络都倾向于是稀疏的.这是一个出现在真实网络中的一般的性质,所以仅考虑具有≪N的系统的网络.当人与人之间互相影响的网络足够稀疏,级联作用的传播会受限于网络的全局连通率；而当它足够密集时,级联作用的传播则决定于个体节点的稳定性.Boguñá和Pastor-Satorras[7]认为,必须考虑两种不同类型网络的可能性:具有准确定义的平均度的热力学极限的稀疏网络,与平均度随网络尺寸发散的非稀疏网络.在稀疏网络情况下,边的数目随着系统尺寸线性增长,联合分布是一个精确描写的与尺寸无关的量.在相反的情况下,非稀疏网络的连边数目比线性更快地增长,这会引起热力学极限的破坏而且会有边凝聚现象的涌现.为了区分稀疏和非稀疏网络,必须考虑平均度的数值.如果密度r(h)与系统尺寸无关,唯一得到稀疏网络的可能性由连接概率的一个标度关系来刻画.这个标度行为会具有很强的应用价值.Reichardt 等[22]则发现,网络的群落(community)结构,可以解释为自旋玻璃的能量最小化自旋位形,其中自旋态就是群落的指标.他们在大规模ER随机图上的数值实验还表明,稀疏网络中群落的数目倾向于随平均度的降低而增加.Ehrhardt等[23]在研究自主体的相互作用网络与知识的扩散和积累的耦合演化过程中发现,大数目N的稀疏网络比小数目的网络更加稳定,更能够承受大的涨落.他们用特征量ξ描写系统的成网作用.只要ξ小,只有稀疏网络的稳态是可能的,随着成网效应ξ的增长,全局的形势没有多大改善,因为由于技术水平的差别太大,大多数企图产生新连边的努力还是归于失败.然而,当ξ变得足够大,这种情形变得不稳定,密集网络以一种突然的方式形成,网络的形成是一个随机事件,而且它会对稍微不同的ξ值发生.在具有大数目N自主体的典型的社会中,稀疏网络比具有小的N的社会中更加稳定.这是因为,从稀疏相到密集网络相的翻转是由大的涨落引发的.这在小的系统中相对容易地发生,当成网作用ξ掉到阈值ξ1以下的时候,密集网络翻转回到稀疏网络.Bornholdt[24-25]等人提出了自组织临界性与网络稀疏性的模型,采用活跃点失去连边,惰性点得到连边的规则,使得网络能够自组织演化到平均度小于3的稀疏网络.Meisel 等[26]分别采用HSP(体内平衡的突触可塑性)和STDP(与放电时间相关的突触可塑性)两种规则,根据节点之间的状态关联,决定加边或者去边,同样得到了自组织临界性下网络稀疏性的结果.2008年, Vazquez等[27]总结前人的选举人模型结果,给出了复杂网络上耦合演化的选举人模型；通过建立主方程,结合平均场近似求出解析解；发现了与平均度相关的破碎相变,划分出冻结相与活跃相两种网络状态.Nowak小组[28]在网络中的几种博弈中发现,稀疏的网络上的演化稳定性并不意味着在比较均匀的网络上的稳定性.在实验方面,值得注意的是,一个高度精巧的脑磁图实验揭示了大脑功能区之间的稀疏网络连接与动力学态的关系.Bassett等[29]利用对脑磁图时间序列的小波分解,来描写大脑功能网络中在具体频率下同步的拓扑结构,他们报告的网络在静息和运动两个状态都是稀疏地连接的,其平均连接密度为0.095.此外,在所有尺度上和状态中的网络同步性是接近于阈值0.01,这给出在耦合振子系统中,从全局的有序到无序行为的转变区的下界.

我国学者对稀疏网络的研究也作出了突出贡献.中科院自动化所的刘勇(Liu Yong)等[30]在权威杂志《Brain》上报道说,人类大脑已经被描述为一个大型的稀疏的由高效的小世界性质刻画的复杂网络,这些性质确保大脑以较高的效率产生和整合信息.以前的许多神经成像研究,提供了在精神分裂症的大脑区域之间功能失调连接的牢固证据.然而,人们并不知道功能失调连接会引起大脑功能网络拓扑性质的破坏.为此,他们通过静息状态下的功能核磁成像,研究了人类大脑功能网络的拓扑性质.他们获取了31个病人和31个健康对象的数据,由部分关联分析和阈值估计得到90个皮层区及亚皮层区之间的功能连接,从而建立了一组无向图.他们的发现表明,健康对象的大脑功能网络具有高效的小世界性质,而精神分裂病人大脑的这些性质已被破坏.大脑功能网络的高效小世界性质能够以相对低的代价确保高效的信息传输,更重要的是,精神病人的大脑中前额、颞叶等地方的小世界性质被显著的改变了.这些发现,与这种病的大脑中功能失调整合的假说相吻合.特别地,他们发现,这些改变的拓扑测度与精神分裂症的病程相关联.探测与估计这些改变,有助于理解病理学机制和度量精神病严重性的程度.小的连通度(即稀疏性)和低的功能连接强度,不仅表明稀疏的连接,也指明了精神分裂症的功能关联脑区之间同步性的降低.这不仅具有明显的实用价值,还在实验上支持了前人[6]的理论结果,即连边密集的振子的集合比连边稀疏的集合更加容易同步化.

中科院章祥荪小组[31-36]系统地研究了一些生物网络与稀疏性相关联的性质.复旦大学章忠志小组[37-38]解析研究了一批伪分形图形的稀疏拓扑性质.杨孔庆[39]研究组对与地理距离有关的复杂网络曾进行系统性地概述.中科大谢彦波等[40]在综合考虑节点度和节点之间几何距离的综合效应的模型中,找到了无标度网络新的生成机制.陈力军小组[41]提出了平均度约束的传感器网络控制策略.最近,吕凌媛等[8]定义了一个用于网络链路预测的局部路径指标,并指出,对于巨大而稀疏的网络,也就是有大的N和小的平均度k—的网络,这一指标的优越性是突出的.北京大学的Jiang Mi和Ma Ping[42]指出,在稀疏的神经元网络中比较容易维持由重连诱导的相干共振.方锦清[43]负责的重点项目组提出了部分同步判据,并且把它运用到具有稀疏连接的同步时空系统中.最近,中科大姜罗罗等[44]在具有去边的博弈模型中发现,当网络变得稀疏,合作的小团体会以孤立岛群的方式形成.戴俊与何大韧[45]报导了对BA(barabasi-albert)网络中与距离相关的I-sing模型的研究结果,节点间相互作用的强度随着几何距离指数衰减,数值模拟求出了铁磁-顺磁的相变点.李翔[46]分别研究了小世界和无标度网络中长程衰减耦合边对随机稀疏网络的相同步的影响,指出它与网络的一致性相关.当耦合指数小于临界值,长程边的密度增加会改善同步性能.

4 网络稀疏性研究中的两个热点问题

当前,对网络稀疏性探讨最多的问题之一是基因调控网络的稀疏重建算法.

一个生物组织的信息储存在它的基因组中,所有复杂器官的基因组由长的DNA分子组成,这些DNA具有双螺旋的核苷酸结构.基因组的基本功能单位就是基因.分子生物学的中心法则指出,信息储存于DNA中,存储在DNA中给定基因的信息被转录成为mRNA,然后再被翻译成为蛋白质.蛋白质是细胞中基本的结构和功能单元.每个蛋白质专门承担许多不同重要角色中的一个,例如一个结构单元,酶催化剂或者抗体.蛋白质组的一个大的子集就是起调控作用的转录因子(TF),它们决定什么时候、在什么地方、以多大数量将特定的基因表达为蛋白质.因为调控蛋白质自身也是基因表达的产物,它们自身也受到调控,这就产生了相互作用基因之间的复杂网络.转录基因调节是细胞发育和分化的基础,它们构成从蛋白质水平到基因向mRNA的转录的重要反馈机制；而且,能够产生从同样的遗传信息出发实现分化的基因表达方式,即同样的基因型可以产生不同的表现型.转录因子最简单的作用就是对基因表达的抑制或者激活,即作为阻遏蛋白,或者作为激活蛋白.转录因子的作用,也受到其它转录因子的调节.所有基因相互作用的集合被称为基因调控网络(GRN),这是复杂系统的一个典型的例子.GRN具有以下的一般性质:a.它是稀疏的.与细胞中大的基因数目相比,每个基因只受到有限数量的其它基因的调控,远小于所有基因的总数目.b.基因网络是单向的.c.基因受到集体活动机制的调节,一个基因的表达水平经常依赖于不同调控蛋白质的集体活动.

目前,根据实验数据进行分析处理来确定GRN是极为复杂的.这一工作受到以下几个方面的制约: a.表达模式的数目M一般是远小于测量到的基因的数目N,可得到的信息是不完整的.b.数据包含噪声.c.微阵列(microarray,生物芯片)实验不是测量单个细胞的表达形貌,而是一群相似的细胞的形貌,这样的平均过程会掩盖单一细胞的调节过程的细节特征.d.非调控机制不能被考虑到基于表达的算法上.目前,研究者们设计了各种各样的预测算法,如迭代贪婪算法[47]、贝叶斯推断[48]、核-重加权的逻辑斯蒂递归[49],进行GRN的稀疏重建.系统生物学、数学、计算机、物理、自动控制领域的研究人员花费了大量的人力物力来建立模型[50]与设计算法,取得了丰富的成果.但是,这类方法本身要精确推断出GRN的结构乃至具体的单向边调控关系,本质上是非常困难的.统计物理学应当能够发挥基本作用,尤其是理解不涉及具体调控细节的共同的基本性质,如稀疏性的来源以及入度和出度分布,集群系数等.另一个值得关注的课题是移动ad hoc通讯网络(MANET).它是各国通信、计算机、自动控制与系统科学研究者开发下一代综合通讯系统的共同课题.MANET可以以手提电脑、手机、传感器等作为无线通讯节点.它不设置基站,每个节点通过多跳无线连接,以确定的通讯半径平等地同时担负发射、接

收和转发控制等功能,特别适用于抢险救灾、沙漠、草原、战场等恶劣环境的群体通讯.当前,一系列新问题有待解决:可变拓扑结构的连通性、媒体接入控制(MAC)机制(当一个节点正在向外发送信息,在它的通讯半径内的其它节点不能同时发出信息)、节能策略、路由策略和保密性等.近年来,物理学界开始在统计物理的思路下建立MANET的复杂网络模型[51],寻求新的算法、策略、原理与技术.

5 网络稀疏性的研究具有突出的统计物理意义

网络的平均度与系统的有效维数直接关联[52],而维度是统计物理中确定相变普适类的关键参数之一.此外,自组织临界性也与平均度即稀疏性密切相关.在同时存在拓扑无序(如复杂网络)与节点状态无序的系统中,小的稀疏的网络不大能够耐受较大的涨落,容易发生动力学的失稳及转变.稀疏性普遍存在于绝大数生物系统以及其它领域的真实网络中,平均场理论在这里的适用性是值得检验的,因为它对于较高的维度才是准确的.另外,由于网络中不存在平移对称性和旋转对称性,以往常用于大块均匀物质系统的方法一般就不能照搬使用,这是对传统统计物理的挑战.所以,研究网络的稀疏性有希望探索出新的方法、技术乃至原理.

在前人的经典复杂网络模型[1-3]中,平均度经常是作为给定的条件出现的,即事先假定每个节点必须和给定数量的其他节点相连,如WS(wattsstrogatz)小世界网络和BA网络,而不去探讨为什么这样.在BA模型中,新加点具有相同的出度.在NW(newman-watts)小世界模型中,加边过程是随机选择两点,不涉及加边的原因,即与节点的性质或者状态有什么关系.后来的一些改进模型,特别是耦合演化网络模型[25,53-69],逐渐有意识地克服这一缺陷.但是,完全由局域信息、近邻的相互作用确定最终稳态网络平均度的模型仍然不多,特别是,能够同时再现无标度性质和大的集群系数[70],又能自组织再现稀疏性质的模型为数更少.这就使人不得不思考稀疏性的来源问题.笔者认为,它不应当是先验的、作为前提给出的,而应当是由个体相互作用的机制导出的,或者是由耦合演化过程自发涌现的.统计物理思想和方法对于理解这类涌现性质具有天然的优势.

网络稀疏性相关效应的分析已经有丰富的结果,但是,大多数是非物理领域的研究者的贡献.根据目前对scholar.google.com网站的检索,有关网络稀疏性的论文数目已达约4 460篇.但是APS (The American Physical Society)期刊至今所发表的8 920多篇复杂网络论文中,只有93篇是与稀疏网络相关的,而权威期刊《Phys.Rev.Lett.》上只发表了8篇[71-78].虽然已经有重要进展,但是,一般分别侧重于个别问题,原理性的探讨和总结还不多见.从2002年到现在,国家自然科学基金委已经资助与复杂网络相关的项目约219个,极大地推动了我国科技界在网络模型和网络动力学等方面的研究进展.但是,到目前为止,还没有发现一个基金课题是明确表明针对网络稀疏性开展研究的.显然,从本文的综述可见,稀疏性问题貌似简单,也被许多人忽视,然而,其重要性无疑是不容小觑的.可以预期,对网络稀疏性起源与效应的深入探讨,会拓展人们认识复杂系统的视角,导出更具有统计物理色彩的新的研究范式.

参考文献:

[1] ALBERT R,BARABÁSI A.Statistical mechanics of complex networks[J].Reviews of Modern Physics, 2002,74(1):47-97.

[2] BARABÁSI A,ALBERT R.Emergence of scaling in random networks[J].Science,1999,286(5439): 509-512.

[3] WATTSD J,STROGATZ S H.Collective dynamics of small-world networks[J].Nature,1998,393(6684): 440-442.

[4] 何大韧,刘宗华,汪秉宏.复杂系统与复杂网络[M].北京:高等教育出版社,2009.

[5] ANDRECUT M,HUANGS,KAUFFMANSA.Heuristic approach to sparse approximation of gene regulatory networks[J].Journal of Computational Biology,2008, 15(9):1173-1186.

[6] ARENASA,DIAZ-GUILERA A,PEREZ-VICENTECJ. Synchronization reveals topological scales in complex networks[J].Physical Review Letters,2006,96 (11):114102.

[7] BOGUÑÁM,PASTOR-SATORRASR.Class of correlated random networks with hidden variables[J].Physical Review E,2003,68(3):36112.

[8] LÜL Y,JIN C H,ZHOU T.Similarity index based on local paths for link prediction of complex networks [J].Physical Review E,2009,80(2):46122.

[9] ALON U.An Introduction to Systems Biology:Design Principles of Biological Circuits[M].Boca Raton:CRC Press,2007.

[10] HEARD E,TISHKOFF S,TODD J A,et al.Ten years of genetics and genomics:What have we achieved and where are we heading[J].Nature Reviews Genetics, 2010,11(10):723-733.

[11] KUNDU S.Amino acid network within protein[J]. Physica A:Statistical Mechanics and its Applications, 2005,346(1/2):104-109.

[12] OVERBYE T J,WEBER J D.Visualizing the electric grid[J].IEEE Spectrum,2002,38(2):52-58.

[13] KRAPIVSKY P L,REDNER S.Network growth by copying[J].Physical Review E,2005,71(3):36118.

[14] CABREROS,PAÑEDA X G,PLAGEMANN T,et al.O-verlay solution for multimedia data over sparse MANETs[C]∥Proceedings of the 2009 International Conference on Wireless Communications and Mobile Computing:Connecting the World Wirelessly.New York:Association for Computing Machinery,2009: 1056-1061.

[15] LI Zhuo-qun,SUN Ling-fen,IFEACHOR E C.Rangebased relative velocity estimations for networked mobile devices[J].IEEE Transactions on Vehicular Technology,2009,58(4):2095-2099.

[16] WANG Li,ZHU Chen-ping,GU Zhi-ming,et al.Modeling mobile ad hoc communication networks on two-dimensional square lattice[J].Frontiers of Physics in China,2009,4(4):556-560.

[17] 贾龙涛,朱陈平,陈昌东.随机纳米碳管网络及其渗流性质[J].复杂网络与复杂性科学,2011,8(3):13-18.

[18] MOTTER A E,DE MOURA A P,LAI Ying-cheng,et al.Topology of the conceptual network of language [J].Physical Review E,2002,65(6):65102.

[19] LIU Zong-hua,LAI Ying-cheng,YE Nong,et al.Connectivity distribution and attack tolerance of general networks with both preferential and random attachments[J].Physics Letters A,2002,303(5/6): 337-344.

[20] WU Xiao-yan,LIU Zong-hua.How community structure influences epidemic spread in social networks[J]. Physica A:Statistical Mechanics and its Applications, 2008,387(2/3):623-630.

[21] WATTS D J.A simple model of global cascades on random networks[J].Proceedings of the National Academy of Sciences of the United States of America,2002, 99(9):5766-5771.

[22] REICHARDT J,BORNHOLDT S.Statistical mechanics of community detection[J].Physical Review E,2006, 74(1):16110.

[23] EHRHARDT G,MARSILI M,VEGA-REDONDO F.Diffusion and growth in an evolving network[J].International Journal of Game Theory,2006,34(3): 383-397.

[24] BORNHOLDT S,RÖHL T.Self-organized critical neural networks[J].Physical Review E,2003,67 (2):66118.

[25] BORNHOLDT S,RÖHL T.Topological evolution of dynamical networks:Global criticality from local dynamics[J].Physical Review Letters,2000,84(26): 6114-6117.

[26] MEISEL C,GROSS T.Adaptive self-organization in a realistic neural network model[J].Physical Review E, 2009,80(6):61917.

[27] VAZQUEZ F,EGUÍLUZ V M,MIQUEL M S.Generic absorbing transition in coevolution dynamics[J].Physical Review Letters,2008,100(10):108702.

[28] OHTSUKI H,NOWAK M A.Evolutionary stability on graphs[J].Journal of Theoretical Biology,2008,251(4):698-707.

[29] BASSETT D S,MEYER-LINDENBERG A,ACHARD S,et al.Adaptive reconfiguration of fractal small-world human brain functional networks[J].Proceedings of the National Academy of Sciences,2006,103(51): 19518-19523.

[30] LIU Yong,LIANG Meng,ZHOU Yuan,et al.Disrupted small-world networks in schizophrenia[J].Brain, 2008,131(4):945-961.

[31] ZHANGShi-hua,JIN Guang-xu,ZHANG Xiang-sun,et al.Discovering functions and revealing mechanisms at molecular level from biological networks[J].Proteomics,2007,7(16):2856-2869.

[32] ZHANGShi-hua,LIU Hong-wei,NING Xue-mei,et al. A graph-theoretic method for mining functional modules in large aparse protein interaction networks[C]∥Proceedings of the Sixth IEEE International Conference on Data Mining-Workshops,2007:130-135.

[33] ZHANGShi-hua,LIU Hong-wei,NING Xue-mei,et al. A hybrid graph-theoretic method for mining overlapping functional modules in large sparse protein interaction networks[J].International Journal of Data Mining and Bioinformatics,2009,3(1):68-84.

[34] ZHANGShi-hua,NING Xue-mei,DING Chris,et al. Determining modular organization of protein interaction networks by maximizing modularity density[J]. BMCSystems Biology,2010,4(2):S10.

[35] ZHANGShi-hua,NING Xue-mei,ZHANG Xiang-sun,et al.Graph kernels,hierarchical clustering,network community structure:Experiment and comparative analysis[J].The European Physical Journal B,2007,57 (1):67-74.

[36] ZHANGShi-hua,WANG Rui-sheng,ZHANG Xiang-sun. Uncovering fuzzy community structure in complex networks[J].Physical Review E,2007,76(4):46103.

[37] ZHANGZhong-zhi,COMELLAS F,FERTIN G,et al. High-dimensional apollonian networks[J].Journal of Physics A:Mathematical and General,2006,39 (8):1811.

[38] ZHANG Zhong-zhi,ZHOU Shui-geng,FANG Lu-jun,et al.Maximal planar scale-free sier pinski networks with small-world effect and power law strength-degree correlation[J].Europhysics Letters,2007,79(3):38007.

[39] YANG Kong-qing,YANG Lei,GONGBai-hua,et al.Geographical networks:Geographical effects on network properties[J].Frontiers of Physics in China,2008,3 (1):105-111.

[40] HU Bo,JIANG Xin-yu,DING Jun-feng,et al.A model of weighted network:The student relationships in a class[DB/OL].[2004-08-06].http:∥arxiv.org/ abs/cond-MAT/0408125

[41] 陈力军,毛莺池,陈道蓄,等.平均度约束的无线传感器网络拓扑控制[J].计算机学报,2007,30(9): 1544-1550.

[42] JIANG Mi,MA Ping.Coherence resonance induced by rewiring in complex networks[J].Chaos:An Interdisciplinary Journal of Nonlinear Science,2009,19 (1):013115.

[43] 方锦清,汪小帆,郑志刚.非线性网络的动力学复杂性研究[J].物理学进展,2009,29(1):1-74.

[44] JIANG Luo-luo,MATJAŽP,WANG Wen-xu,et al.Impact of link deletions on public cooperation in scalefree networks[J].Europhysics Letters,2011,93 (4):40001.

[45] DAI Jun,HE Da-ren.Phase transition of a distance-dependent ising model on the barabasi-albert network [J].Chinese Physics Letters,2007,24(12):3355.

[46] LI Xiang.Phase synchronization in complex networks with decayed long-range interactions[J].Physica D: Nonlinear Phenomena,2006,223(2):242-247.

[47] ANDRECUT M,KAUFFMAN S A.On the sparse reconstruction of gene networks[J].Journal of Computational Biology,2008,15(1):21-30.

[48] HUSMEIER Dirk.Sensitivity and specificity of inferring genetic regulatory interactions from microarray experiments with dynamic bayesian networks[J]. Bioinformatics,2003,19(17):2271-2282.

[49] AHMED A,XING E P.Recovering time-varying networks of dependencies in social and biological studies [J].Proceedings of the National Academy of Sciences, 2009,106(29):11878.

[50] SONG L,KOLAR M,XING E P.KELLER:estimating time-varying interactions between genes[J].Bioinformatics,2009,25(12):128-136.

[51] WANG Li,ZHU Chen-ping,GU Zhi-ming.Scaling of critical connectivity of mobile ad hoc networks[J]. Physical Review E,2008,78(6):066107.

[52] NEWMAN M.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America, 2002,99(12):7821-7826.

[53] BARRAT A,BARTHELMY M,VESPIGNANI A.Weighted evolving networks:Coupling topology and weight dynamics[J].Physical Review Letters,2004,92 (22):228701.

[54] CASTELLANOC,FORTUNATOS,LORETO V.Statis-tical physics of social dynamics[J].Reviews of Modern Physics,2009,81(2):591-646.

[55] EGUILUZ V M,ZIMMERMANN M G.Transmission of information and herd behavior:An application to financial markets[J].Physical Review Letters,2000,85 (26):5659-5662.

[56] EHRHARDT G C,MARSILI A,VEGA-REDONDO F. Phenomenological models of socioeconomic network dynamics[J].Physical Review E,2006,74 (3):036106.

[57] FRONCZAK P,FRONCZAK A,HOLYST J A.Self-organized criticality and coevolution of network structure and dynamics[J].Physical Review E,2006, 73:046117.

[58] GROSS T,SAYAMA H.Understanding Complex Systems[M].Berlin:Springer,2009:73-106.

[59] HOLME P,NEWMAN M.Nonequilibrium phase transition in the coevolution of networks and opinions[J]. Physical Review E,2006,74(5):056108.

[60] ITOJ,KANEKO K.Spontaneous structure formation in a network of chaotic units with variable connection strengths[J].Physical Review Letters,2001,88 (2):028701.

[61] ITOJ,KANEKO K.Spontaneous structure formation in a network of dynamic elements[J].Physical Review E,2003,67(4):046226.

[62] LIU M,BASSLER K E.Emergent criticality from coevolution in random Boolean networks[J].Physical Review E,2006,74(4):041910.

[63] PACHECOJ M,TRAULSEN A,NOWAK M A.Coevolution of strategy and structure in complex networks with dynamical linking[J].Physical Review Letters, 2006,97(25):254103.

[64] WANG Ru,CAI Xu.The strong consensus opinion dynamics on adaptive networks[J].International Journal of Modern Physics C,2008,19(12):1939-1947.

[65] XIE Yan-bo,WANG Wen-xu,WANG Bing-hong.Modeling the coevolution of topology and traffic on weighted technological networks[J].Physical Review E, 2007,75(2):026111.

[66] ZHOU C,KURTH J.Dynamical weights and enhanced synchronization in adaptive complex networks[J]. Physical Review Letters,2006,96(16):164102.

[67] ZHU Chen-ping,XIONG Shi-jie,TIAN Ying-jie,et al. Scaling of directed dynamical small-world networks with random responses[J].Physical Review Letters, 2004,92(21):218702.

[68] ZIMMERMANN M,EGUILUZ V,MIGUEL S M.Cooperation,adaptation and the emergence of leadership [M]∥KIRMAN A,ZIMMERMANN J B.Economics with Heterogeneous Interacting Agents.Berlin: Springer,2001:73-86.

[69] ZIMMERMANN M,EGUILUZ V,MIGUEL S M.Coevolution of dynamical states and interactions in dynamic network[J].Physics Review E,2004,69(6):065102.

[70] ZHU Chen-ping,LIU Xiao-ting,GU Zhi-ming.Flathead power-law,size-independent clustering,and scaling of coevolutionary scale-free networks[J].Frontiers of Physics,2011,6(3):337-341.

[71] DAS M,MACKINGTOSH F,LEVINE AJ.Effective medium theory of semiflexible filamentous networks[J].Physical Review Letters,2007,99(3):038101.

[72] DOROGOVTSEV S N,GOLTSEV A,MENDES J F F. K-core organization of complex networks[J].Physical Review Letters,2006,96(4):040601.

[73] GALLOS L K,ARGYRAKIS P.Absence of kinetic effects in reaction-diffusion processes in scale-free network[J].Physical Review Letters,2004,92 (13):138301.

[74] JAHNKE S,MEMMEISHEIMER R M,TIMME M.Stable irregular dynamics in complex neural networks [J].Physical Review Letters,2008,100(4):048102.

[75] LUCCOLI S,POLITI A.Irregular collective behavior of heterogeneous neural networks[J].Physical Review Letters,2010,105(15):158104.

[76] PEIXOTO T P.Redundancy and error resilience in boolean networks[J].Physical Review Letters,2010, 104(4):048101.

[77] RANGAN A V.Three-dimensional visualization of a human chromosome using coherent x-ray diffraction [J].Physical Review Letters,2009,102(1):018101.

[78] REICHARDT J,LEONE M.(Un)detectable cluster structure in sparse networks[J].Physical Review Letters,2008,101(7):078701.

A review on statistical physics for the sparsity of complex networks

ZHUChen-ping, ZHANGYong-mei, LIU Xiao-ting, WANGRong-fang, WANGXin-guang
(Departmemt of Applied Physics,Namjimg Umiversity of Aeromautics amd Astromautics,Namjimg 210016,Chima)

Most practically existing complex networks are sparsely connected,namely,the average degrees of them are much smaller than their total numbers of nodes:k—≪N.Up till now,the research on the origin of this property,its effects on functions of networks and dynamic processes on networks,and its possible applications have been still far less than adequate.Actually,sparsity is closely related with other topological properties.In recent years,much progress has been made on sparseness of complex networks from both theoretic and experimental aspects.However,principle conclusion is still anticipated.From the view point of statistical physics,it is believed that the sparsity of networks should be accounted as an emergent property of interactions between individuals in complex systems,instead of a priori prerequisite for existing models.In the present paper,we attempt to review previous investigations with statistical physics on the sparseness of complex networks.

complex metwork；sparsity；statistical physics

N 94文献标示码：A

1007-6735(2011)05-0425-08

2011-09-12

朱陈平(1958-),男,副教授.研究方向:统计物理与复杂性科学.E-mail:chenpingzhu@yahoo.com.cn