从统计物理学看复杂网络研究

从统计物理学看复杂网络研究第24卷第1期2004年3月物理学进展PROGISSINPHYSICSV01.24.No.1Mar.,2004文章编号:1000-0542(200401-001829从统计物理学看复杂网络研究吴金闪,一,狄增如(1.北京师范大学管理学院系统科学系,北京1008752.北京师范大学物理系,北京100875)摘要:从统计物理学来看,网络是一个包含了大量个体及个体之间相互作用的系统.本文从统计物理学的角度整理与总结了复杂网络目前的主要研究结果,并对将来的研究工作傲了一个展望.文章把网络分为三个层次无向网络,有向网络与加权网络,对不同网络的静态几何量研究的现状分别做了综述,并结合网络机制模型设计与评价的需要,提出了新的有待研究的静态几何量;对网络机制模型做了总结与分析,提出了有待解决的关于双向幂律网络的机制模型的问题;部分地概括了网络演化性质,网络的结构稳定性以及网络上的动力学模型的研究.然后,以我们目前正在进行的两个方面的工作科学家网络和产品生产关系网络一为例,粗略地介绍了网络研究在一些实际问题中的应用.最后,作为一个简单的补充和索引,我们整理了复杂网络研究中部分常用的解析与数值计算的方法.关键词:统计物理学;复杂网络;综述;随机图;幂律;无标度网络中图分类号:O414.2文献标识码:A0引言近年来,关于复杂网络的研究正处于蓬勃发展的阶段Ll3J.其研究者来自图论,统计物理学,计算机网络,生态学,社会学以及经济学等各个不同领域.网络研究的文章主要发表于Phys.Rev.Lett.,Phys.Rev.E,PhysicaA,PNAS等物理类期刊,Nature,Science等综合期刊,以及EcologyLetter,ACM等专业期刊.2002年Rev.Mod.Phys.的综述文章复杂网络的统计物理学L1在历史,基础与前沿等各个方面都写的非常之好,得到了非常高的引用率,已经在SIS被评为由突出影响的文章之一L4J.但是这一年多以来,网络研究的飞速发展,新的理论研究,新的应用领域的发展和开辟,使得我们有必要重新整理与总结这一领域的研究,以促进复杂网络研究的发展.同样是网络的统计物理学,本文更多的从复杂网络研究的不同方向进行总结,在保证一定的广度的基础上突出深度,阐述不同方向之间的联系,并据此提出新的研究问题.收稿日期:200310-25基金项目:国家自然科学基金(No.79990580)和(No.6o0o3o18)资助1期吴金闪等:从统计物理学看复杂网络研究19网络可以用来描述人与人之间的社会关系,物种之间的捕食关系,词与词之间的语义联系,计算机之间的网络联接,网页之间的超链接,科研文章之间的引用关系,以及科学家之间的合作关系,甚至产品的生产与被生产关系.网络还可以作为现象的背景舞台,例如在社会关系网络上讨论舆论的传播,接触关系网络上讨论传染病的传播,计算机病毒在Internet网络或邮件网络上的传播,在引文网络上研究新思想的提出与传播,在科学家网络上研究科学家之间的相互影响等.网络与现象结合还可以用来讨论网络的稳定性等结构与功能关系,例如在食物链网络上讨论个别或部分物种灭绝对整体生态系统的影响,在不同的网络上讨论传染病传播的控制,在科学家网络中讨论某个领域中不同的科学家的影响力对网络演化的影响.此外,网络本身的演化过程也是一个有趣的问题,例如Internet网络的形成被认为是无限定原则的,但是它却展现了一些重要而普适的结构特征与稳定性,再比如,对于某一个学科内的引文网络与科学家网络的演化机制的研究,有可能给出促进科学发展的新的方案与模式.每一个系统中的网络都有其自身的特殊性质,有其紧密联系在一起的独特现象,有其自身的演化机制,但是由于都可以使用网络分析的方法,所以有其共性.例如关于顶点度值,介数的分析方法以及大量不同网络中存在的相同的统计特征,再如随机去点与选择性攻击对网络结构的影响及其分析方法.研究网络的几何性质,网络的形成机制,网络演化的统计规律,网络上的模型性质,以及网络的结构稳定性,并把它与具体系统结合起来是复杂网络研究的中心内容.统计物理与图论都是研究这种共性的有力工具.网络G=(,E)作为图论的概念是指由一个点集(G)和一个边集E(G)组成的一个图,且E(G)中的每条边ei有V(G)的一对点(U,)与之对应.记顶点数为N=I,I,边数为L=IEI.如果任意(U,)与(,U)对应同一条边,则称为无向网络,否则为有向网络;如果任意IeI=1,则称为无权网络,否则为加权网络.从统计物理学的角度来看,网络是一个包含了大量个体以及个体之间相互作用的系统,是把某种现象或某类关系抽象为个体(顶点)以及个体之间相互作用(边)而形成的用来描述这一现象或关系的图.统计物理学是从微观到宏观的桥梁.研究网络中顶点与边的度值与权值等微观性质与网络的几何性质,效率与稳定性等宏观性质之间的关系正是复杂网络研究的核心内容.因而,与图论的研究有所不同,统计物理学研究网络更侧重于从各种实际网络的现象之上抽象出一般的网络几何量,并用这些一般性质指导更多实际网络的研究,进而通过讨论实际网络上的具体现象发展网络上模型的一般方法,最后讨论网络本身的形成机制.统计物理学在模型研究,演化机制与结构稳定性方面的丰富的研究经验是统计物理学在复杂网络研究领域得到广泛应用的原因;而图论5与社会网络分析提供的网络静态几何量及其分析方法是复杂网络研究的基础,并得到了充分的发展.我们把个体与相互作用直接抽象为顶点与边的系统称为网络,例如www网络,合作者网络【66,67】,并把网络的统计性质称为网络静态几何量;把关于实际网络演化的统计规律的分析称为网络演化性质的研究,例如www网络中网页数量的时间演化规律,而把关于具有特定几何性质的网络的形成机制的探索称为网络演化机制模型,例如探讨ScaleFree网络的形成;把建立在网络上的其他模型,例如传染病挖J,渗流模型【DJ的动态物理学进展24卷过程称为网络上的动力学性质;把网络的各种攻击方式与响应称为网络的结构稳定性,例如选择性隔离对于传染病流行的控制作用.本文是按照前面所述的逻辑来组织的,首先我们对三种网络的静态几何量研究的现状做了总结,并提出了一些新的研究对象;接着我们同样对网络机制模型做了回顾和展望,提出了有待解决的问题;随后部分地概括了网络演化性质与网络上的动力学性质的研究,并探讨了它们与网络研究的关系;接着总结了网络的结构稳定性研究,尤其是基于网络的传染病控制与食物链网络的鲁棒性的研究.最后,由于其特殊的重要地位,我们用科学家网络为例,做了一个包含以上几个方面的研究思路,并提出了产品生产关系网络(PION)的研究思路与计划.研究产品生产关系网络可以不仅把握经济学领域大量现象与关系,并且,由于这种网络结构有其特殊性,还可望促进网络研究的发展.最后一节,我们整理了在解析和数值计算中经常使用的一些技术,便于大家参考以及查找相应的文献.1网络上的静态几何量在本节中我们将对网络的静态几何性质做一小结,并按照为网络机制模型的研究服务的思想提出了新的静态几何量.静态几何量指的是给定网络G=(,E)的微观量的统计分布或者宏观统计平均值.由于有向网络与加权网络有其特有的几何量,我们将分开讨论无向网络,有向网络与加权网络.1.1无向网络目前已得到研究的典型无向网络包括:Intemet网络,电影演员合作网络,科学家合作网络,人类性关系网络,蛋白质互作用网络,语言学网络,蛋白质折叠关系网络.无向网络的基本几何量l1.2有:度及其分布特征,度的相关性,集聚程度及其分布特征,最短距离及其分布特征,介数(Betweenness)及其分布特征,连通集团的规模分布.一个顶点的度是指与此顶点连接的边的数量,即d=(1)其中记号取值为1当路径l包含顶点q,否则为零,即=dn;同时为了以后表述方便,我们定义其他两种类型的记号,与分别表示顶点相邻与边相连,对于有向网络,推广为,.对于加权网络用记号w代替就可以完整地描述.VV我们都可以得到其度d.度值的分布特征是网络的重要几何性质.规则网络各顶点度值相同,因而符合分布,随机网络符合泊松分布(见(2.1)节),大量实际网络存在幂律形式的度分布l1.2J,称为无标度网络(ScaleFreeNetworks),包括Intemet网络43,44,电影与电视剧演员合作网络17,31,45,科学家合作网络66,67,人类性关系网络,蛋白质互作用网络47,语言学网络48等,同时还存在高斯型,如蛋白质折叠网1期吴金闪等:从统计物理学看复杂网络研究21络L4,和指数衰减型的幂率分布,如电视剧演员合作网络45.进一步的问题是,是否度分布可以完备地描述网络的特征呢?如果度分布与网络一一对应,我们就说度分布可以完整地描述网络,网络也只需要用度分布来描述.试想对于一给定的度分布,通过抽样,我们可以给对应网络的每一个顶点一个度值,保持度值的任意一种连接方式都构成一种网络.如果任意一种连接对应的其他几何量都一样,则我们认为实际上为同一网络.但是显然不能保证其他几何量也都一样.那么,保持度值不变的随机连接,即度与度之间没有相关性,是否可以成为大多数网络的代表呢?所以度分布之间的相关性是另一个重要的几何量.Newman把它称为匹配模式5_,意思是考察度值大的点倾向于和度值大的点连接,还是倾向于和度值小的点连接.具体的方法是,通过任意一条边都可以找到两个顶点,进而得到两个度值,这样通过所有的边我们就得到了两个序列,分析这两个序列的相关性即可.研究表明实际网络存在一定程度上的匹配模式,有的网络正向匹配,也有的网络反向匹配.但是,由于是无向网络,把哪一个顶点的度放人序列口,把哪一个顶点的度放人序列b是任意的,这一点对于相关性分析的影响并没有得到研究.实际网络的分析表明,不同的网络存在不同的匹配模式,有正相关也有负相关.集聚程度的意义是网络集团化的程度,即考察连接在一起的集团各自的近邻之中有多少是共同的近邻.一种定义是对于每一个顶点,找到其近邻集合N,记=INI,N中存在的边的数量为M=(3)zE,yE则=M(4)于是我们可以得到所有顶点的集聚程度,它的统计分布是刻画网络的一个重要几何量,其平均值称为平均集聚程度C.两点的最短路径z定义为所有连通(i,)的通路中,所经过的其他顶点最少的一条或几条路径.记(i,)之间最短路径的集合为s相应的路径长度为d:I.如果(,)之间不存在通路,那么记df=N.于是我们可以得到一个NN的矩阵(d).其分布特征是一个重要的全局几何量,其平均值称为平均最短路径d.另一个重要的全局几何量是介数(Betweenness)16.顶点的介数含义为网络中所有的最短路径之中,经过U的数量.它反映了顶点的影响力.记(i,)之间最短路径的集合为S顶点U的介数定义为B=(5)由此可以得到每一个顶点的介数B.实证研究表明,大量实际网络的介数分布也拥有共同的统计特征16_.类似地,可以定义边的介数,Newman等人发现,边的介数可以用于分析顶点的聚类.其基本思想是在包含不同集团的网络中所有最短路径经过次数最多的边,也就是介数最大的边,必然是联接两个集团之间的边.当然,建立在联接赋权基础物理学进展24卷上的HierarchicalClustering聚类算法也能给出网络上顶点的分类.连通集团是指G的一个子图,在这个子图内,任意两点之间都存在通路.一个网络可能存在多个相互独立的连通集团.在渗流模型中,当系统处于临界状态时,连通集团的规模呈现出幂律分布.实证研究表明,对于大量的Scalefree网络,连通集团的规模也存在幂律分布1l.关于无向网络的度分布还存在另外一种形式.计算近邻顶点的数目得到度值,然后把所有顶点的度值归一化后再把近邻顶点的度值相加得到顶点的二次度值,重复这一过程,直到得到稳定的度值J.这样得到的每一个顶点的度值实际上是邻接矩阵的最大本征值对应的本征向量,上述过程实际上就是矩阵本征值的最速下降法.但是这样的度分布具有的几何意义目前没有得到研究.1.2有向网络目前已得到研究的典型有向网络包括:wWw网络,细胞内化学反应网络,食物链网络,引文网络,电力网络,神经网络.当我们忽略边的方向的时候,或者反过来看认为任何一条边都是双向的时候,有向网络就成为无向网络.因此,关于无向网络的所有几何量都可以在有向网络中研究.有向网络的特殊静态几何量包括:In度和Out度的分布特征,基于顶点的In-Out度关联性,基于边的(In-Out,In-In,OutIn,OutOut)度关联性,双向比,In集团和Out集团的集聚程度.把无向网络的度推广为In度和Out度,dt=(6)y以及d:,(7)y可分别研究In度和Out度的分布特征.实证研究表明,有向网络中存在In度和Out度的双向幂律分布,如wWw网络25,49,26,细胞内化学反应网络50,51;但是也存在只有In度幂律分布的网络,如引文网络65;以及符合指数衰减的网络,如电力网络与神经网络45;此外,由于受顶点数规模限制,食物链网络的度分布特征仍然没有确定5.由于每一个有向网络的顶点都存在In与Out两个度值,研究这两个度值之间的关联将是有向网络的另一个重要特征.与无向网络的度相关类似,我们可以研究有向网络基于边的度相关.任意选取一条边,在边的两端存在4个度值,起点的In度和Out度,终点的In度和Out度,所以存在4种关联性,分别是In-In,In-Out,OutIn,Out-Out关联.尽管关联性复杂了,可是同时去掉了上一小节所提到的无向网络度相关分析的任意性.那么这样的度度相关的研究是否仅仅是无向网络中度关联性分析的平庸推广呢?不是.我们提到,所有新提出的几何量都是为了网络机制模型服务的,在下一节中大家可以看到在机制模型中,反馈机制是一个重要的因素,而有向网络的度相关性正是建立反馈机制的重要参考.边的双向比,即双向的边占所有边的比例,也是一个重要的概念,可以为设计双向幂1期吴金闪等:从统计物理学看复杂网络研究律分布的机制模型提供参考.1.3加权网络目前,关于加权网络的实证研究不多,只有在Newman的工作66中提到了一点关于科学家加权合作网络的研究.首先,我们需要讨论加权网络的加权的必要性与方式.把一个实际问题抽象为加权网络的过程并不都是平庸的.当然,对于邮递员问题等包含距离关系的网络,直接把距离作为权就可以了,但是对于其他包含相似关系,亲密程度等社会关系的网络,如何加权就值得讨论了.尤其是,当系统当中包含多个层次的同一属性的关系的时候,就必须仔细研究其加权方式了.以下,我们以某一学术领域内的科学家网络66,68为例,介绍加权网络.为了研究某一学术领域的发展变化,某一个新的思想在此领域内的产生,传播,我们构造了一个科学家之间通过文献相互联系影响的网络.我们认为,对于研究此问题而言,科学家之间的合作关系66,引文关系65,68以及讨论或书信交往(经常体现在致谢中)属于同一属性的关系,但是所起作用的程度有所不同.对于交流思想而言,合作是最直接的影响,其次是引文,再次为致谢.而且,在同为合作的关系内,合作的次数的不同,对于交流思想的影响也是不一样的.因此,在这个科学家网络中,每一条边代表了综合考虑了以上三个方面两个层次的相互作用以后的影响力程度.并且由于引文和致谢的有向性,此网络是一个加权有向网络.加权网络的静态几何量包括:度及其分布特征,权及其分布特征,权的相关性,权与度的相关性,最短距离及其分布特征,介数及其分布特征与隧道现象,与相应无权网络的对比,距离关系与类聚分析,以及在加权网络上集聚程度的定义及其统计性质.首先加权并不改变度与集聚程度等局域几何量,所以无权网络的局域几何量分析都可以在加权网络上实现.权的分布反映的是本领域内学术交流的活性,如果我们认为所有学术研究都将表现为文献发表与学术交流的话,那么它反映的是此领域内学术研究的活跃程度.类似于无向网络的度相关性,权的相关性考察的内容是是否活跃的科学家倾向于和其他活跃的科学家合作,还是倾向于提携后进.一种可行的方法是把某一个点的权定义为从该点出发的所有的边的权重之和,即t=wout(8)=w(8)以及所有到达该点的边的权重之和,即w=W(9)其中,合作关系作为无向部分同时记人w与w.权与度的相关性研究,考察的是科学家合作交流的广泛性与深入性的关系.用上一小节有向网络的度的定义,每一格点的有两个度值d,d,两个权值,w.m,存在四种相关性一d,w,wmd,Wndm.忽略有向性,可以定义Wu=+.wIll(1o)【d=dOUt+d物理学进展24卷也可以讨论无向化网络的权与度相关性.加权网络另一个有意思的特征量是单位权,即=)它表示顶点每一个连接的平均权重.有关单位权的统计分布以及关联性的研究将是一个有趣的问题.加权网络中的最短路径是指在两点之间所有连通的路径中,权数之和最小的一条或几条路径.在科学家网络中,它和新的思想在网络上的传播密切相关.与无权网络的顶点数最小相比,加权会改变最短路径.而且由于最短路径的改变,介数也将发生变化.在科学家网络中,介数反映了在本领域内,某位科学家影响力的大小.某一顶点的近邻顶点介数分布的两极分化性质称为隧道现象,全部顶点的介数分布反映的是科学家影响力的层次.边的介数反映的是不同科学家之间的交流对学科发展的影响力的不同.同时,利用边的介数也可以对科学家做聚类分析.所有以上局域或全局几何量都需要与相应的无向网络或无权网络做对比研究.最后,我们可以用两两顶点之间的距离来度量由于加权带来的顶点之间的亲密程度的不同.并且有了距离关系以后,我们就可以做聚类分析,给出科学家之间的交流集团.这种聚类分析还可以和基于边的介数的聚类分析对比.加权网络目前仍然是一块有待开发的沃土.2网络机制模型上一节我们主要总结了对于实际网络的静态性质的统计研究,这一节我们去看一看什么样的网络模型会展现这些特定的统计性质.这是研究网络上的动力学模型的基础.如考虑不同网络上的传染病模型,用来描述接触性传染病的传播,谣言在人群中的传播等现象,或者不同网络上的渗流模型.对于这些问题,我们可以选择用微分方程来描述.例如以下Logistic模型,=一z)z(12)我们把看成是健康人与受感染人之间发生接触并获得传染的几率.所以在此模型中,所有个体是均匀混合的,没有局域近邻的概念,就好像是溶液中发生的化学反应一样.或者我们这样来理解,把疾病看作只要接触就传染,那么的意义是平均来看每一个体的近邻数目占所有人口的比例.因此,可见Lostic模型的背景是完全随机网络.作为补充,我们可以在规则网络上用模拟或者重整化群的方法来研究同一问题.而作为模型真实背景的是人的社会交往的网络,这样一些网络可以通过实证研究获得对其静态性质一定的认识.但是对于研究这些网络上的动力学模型来说,更加广泛的研究还需要网络模型,而不仅仅是实际网络数据.例如,人类相互认识的网络是SmallWorld网络,那么当我们研究这样的网络上的动力学模型的时候,我们就需要一个相应特征的网络来作为我们的背景.当然,我们可以收集这个网络的实际信息,然后在这个实际网络上进行分析.1期吴金闪等:从统计物理学看复杂网络研究但是这有很大的局限性,尤其对于理论研究.如果我们能够设计一个具有这些性质的网络演化机制模型,那么我们进一步对网络上动力学模型的研究就可以以这些机制模型为基础.当然,如果发现现有的机制模型不能展现已有的几何性质,我们就需要修改模型.本节中,我们将分别介绍规则网络和完全随机网络5(以下简称随机网络),Smallwlorld网络与ScaleFree网络17的机制模型.2.1规则网络与随机网络我们把一维链,二维正方晶格等称为规则网络.规则网络是指平移对称性晶格,任何一个格点的近邻数目都相同.当然这只是一个习惯用法,不是下定义,比如CarleyTree显然不是随机网络,但是也没有规定说它属于规则网络.随机网络是另一个极端,由N个顶点构成的图中,可以存在c条边,我们从中随机连接M条边所构成的网络就叫随机网络.还有一种生成随机网络的方法是,给一个概率P,对于c2中任何一个可能连接,我们都尝试一遍以概率P的连接.如果我们选择M=pc2,这两种随机网络模型就可以联系起来.对于如此简单的随机网络模型,其几何性质的研究却不是同样的简单.随机网络几何性质的研究是由PaulErd6s,Alfr6dR6nyi和B61aBollobs在五十年代到六十年代之间完成的.为了强调随机网络研究与统计物理学的联系,我们从系综理论的角度重新表述了随机网络统计性质的研究结果.但是,为了在这一节中突出模型的统计性质而不是处理方法,我们把这一表述放在最后专门介绍方法与技术的一节中.规则网络与随机网络的典型几何性质包括:度分布,平均集聚程度与平均最短距离.规则网络所有顶点都相同,因此其度值相同,度分布为(k一惫0),其平均集聚程度也只需要在一个点计算C:(>=,其最短距离可以也只从某一个顶点开始计算从它到所有lrvr其他顶点之间的距离之和LN2,然后计算其平均值d=N.对于随机网络G乙-N(N,P),包含了从空图到完全图的所有可能情况,因此随机图的几何性质需要对每一种可能图做平均,例如我们计算每一种可能图的最短距离,然后按照各自出现的几率做平均.一般公式与详细的计算见第7节.研究结果表明随机网络顶点的度值符合平均值为N的泊松分布,其集聚程度约等于P,最短距离dln(N).对比规则网络与随机网络,我们发现,平均集聚程度与平均最短距离,这两个静态几何量能够很好地反映规则网络与随机网络的性质及其差异.规则网络的特征是平均集聚程度高而平均最短距离长,随机网络的特征是平均集聚程度低而平均最短距离小.规则网络的平均最短距离dN,而其集聚程度可以通过改变近邻数目k0来调整,例如在如1图1所示的规则网络中,k0=4,集聚程度分别为寺.而在随机网络中,平均集聚程度非常的小,在图1所示的随机网络中,顶点数与边数都与规则网络相同,但集聚程度为0.02.然而正是由于其集聚程度非常地小,所以其平均最短距离小.考察一个顶点的近邻,假设其近邻数为a,那么在a个近邻的近邻之中相互重复的个数非常少,所以从出发经过两次近邻关系我们可以找到正比于a的新顶点,最多经过logan个近邻关系,我们就可以穷尽整个网络.所以,其最短距离满足dInN.可见,对于规则网络,也正是由物理学进展24卷图1SmallWorld网络模型.图中所示的SmallWorld网络是在左图的规则网络基础上通过边的重连得到的.当P:0时,成为规则网络,P=1.0时成为随机网络.本图取自文献7于其集聚程度高,重复率很大,所以平均最短距离大.如此看来好像这是一对相互矛盾的几何量.那么,是否存在一个同时具有高集聚程度,小最短路径的网络呢?对于传染病模型,平均集聚程度对应于传播的广度,平均最短距离代表的是传播的深度.因此,如果实际网络同时存在宽的广度和大的深度的话,在这样的网络上的传染病传播显然将大大高于规则网络与随机网络.watt和Strogatz为我们找到了这样的网络模型一&nauWorld网络3.7.2.2SmallWorld网络watt和Strogatz发现,只需要在规则网络上稍作随机改动就可以同时具备以上两个性质.改动的方法是,对于规则网络的每一个顶点的所有边,以概率P断开一个端点,并重新连接,连接的新的端点从网络中的其他顶点里随机选择,如果所选的顶点已经与此顶点相连,则再随机选择别的顶点来重连.当P:0时就是规则网络,P=1则为随机网络,对于0<P<1的情况,存在一个很大的P的区域,同时拥有较大的集聚程度和较小的最小距离.一个典型的SmallWorld网络见图1中间的示意图,其几何性质如图2所示.图2Smallw0rld网络的几何性质.同时有大集聚程度而小最短距离是SmallWorld网络的重要特征,而且此性质在P略大于0到小于1的很大范围内存在.本图取自文献E71期吴金闪等:从统计物理学看复杂网络研究27实证研究发现,大量的实际网络存在在这种Smallw0rld现象,见表1.在Watts和Strogatz的工作之后,不同的作者做了许多Smallworld网络上的动力学模型的研究14,36-38,60-63,体现了平均集聚程度和平均最短距离的深刻的表现能力.我们将在网络的动力学性质一节对此做一小结.表1实际网络的SmallWorld现象列表中包括所研究网络的实际对象(Network),大d(size),平均度值(<>),平均最短距离(f),按随机网络计算的最短距离(f1),平均集聚程度(C),按随机网络计算的集聚程度(C1).通过对比实际网络与相应(相同顶点数和边数)随机网络的性质,可以发现网络的SmallWorld特征.此表在文献Ill的基础上收集确认其他文献编辑而成,感谢作者R.Albert提供.2.3scaleFree网络在SmallWorld网络的研究兴起之后,越来越多的科学家投入到复杂网络的研究中去.大家发现其实更多的其他几何量的特征也具有很大程度上的普适性和特定的结构功能关系.ScaleFree网络就是其中的一个重要方面.ScaleFree网络指的是网络的度分布符合幂律分布,由于其缺乏一个描述问题的特征尺度而被称为无标度网络.我们都知道幂律在统计物理学相变与临界现象,以及在自组织临界性(SOC)中的特殊地位J.这种度分布的无标度性是否也会带来网络上动力学模型的特殊性质呢?我们也将在下一节网络的动力学性质加以总结.实证研究发现,大量的实际网络可以被认为是ScaleFree网络1,见表2.28物理学进展24卷列表中包括所研究网络的实际对象(Network),大d,(Size),平均度值(<>),Out度幂律分布指数(.y),In度幂律分布指数(),平均最短距离(f),按随机网络计算的最短距离(fand).可见,ScaIeFree网络一般具有SmallWorld特征.此表在文献1的基础上收集确认其他文献编辑而成.感谢作者R.Albert提供.现在我们来看看ScaleFree网络的形成机制.目前对于无向ScaleFree网络,普遍认为偏好依附(PreferentialAttachnlent)【17是一个很好地形成ScaleFree网络的机制.具体模型如下.取初始m0个顶点任意连接或完全连接.每一步在原网络G(t一1)的基础上加上一个新的顶点,同时加上从此顶点出发的m条边,形成新的网络G(t).其中新加边的另一个端点按照正比于顶点度数的分布一南(13随机选取.重复以上新加点的过程足够多步所形成的网络的各顶点的度满足幂律分布P()k,见图3.而且,指数y=3与模型的参数m0,m无关.进一步的数值模拟表明,当m取某一范围内的随机数时,指数也不变.鉴于实际网络的幂指数并不都是y=3,有的作者发展了Barahsi和Albert的原始偏好依附模型,使得幂指数可以用模型参数来调整.在偏好依附模型中,顶点的度值k可以认为是其吸引力的度量.那么,随着时间的推移,除去少数精品之外,大多数的顶点的吸引力会随着时间减弱.一个考虑了顶点的历史模型22可以改变幂指数y.更多的可调参数模型甚至是破坏幂律分布的模型可以通过考虑更一般的网络演化过程得到.另外一个要改动偏好依附模型的要求是偏好依附模型并不能复现所有的认为是ScaleFree网络的静态特征.对于大多数实际ScaleFree网络的SmallWorld现象,模型给1期吴金闪等:从统计物理学看复杂网络研究29101010k图3偏好依附模型生成网络的度分布.(a)度分布不随着m或m0的改变而改变,从左到右m0:m分别取值为1,3,5,7;(b)在不同时刻,N=100000,150000,2OOOOO,取m0:m=5得到的度分布曲线完全重合,插入的小图是其中两个顶点的度值的演化曲线,与方程(29)相符.本图取自文献20,感谢Albert提供出了较好的结果,但是模型的度度相关性为零,这与实际网络中存在的匹配模式不相符合【l5l.更多的其他几何量的实际与模型的对比,以及在对比基础上对模型的修改工作还有很多值得做的地方.比如Goh和Oh等给出了模型上的介数的分布规律16,但是更广泛的实证分析仍然有待完成.这些相符的或者不相符的现象都给出了模型推广与修改的方向.作为一个一般的网络演化的框架有哪些现象是可以进入模型来考虑的呢?一个一般的网络演化包含五种现象:加点,加边,重连,去边,去点.所谓加点就是t时刻在图G(t1)上加上新的顶点,并且加上若干从此顶点出发的边;加边指的是t时刻在G(t1)原有顶点之间新加入若干连接;去边与去点则是以上过程的逆;而先去边后加边和起来就是重连,但是只有当加边和去边发生在同一顶点上的时候才刚好是重连,所以鉴于重连事件的几率有可能大大大于去边和加边发生几率之乘积,所以把重连独立出来.目前绝大多数网络演化模型都在这五种事件的范围内讨论.在这样一个框架下来看,我们看到偏好依附模型只考虑了加点的行为,只是对于加点以后建立的从新加点出发的连接做了偏好性假定.从Barabhsi和Albert提出此模型以后,许多作者讨论了此模型的变例.Dorogovtsev,Mendes和Samukhin的模型【l8J讨论了新加点加入之后,m条新加边可以不从此点出发的模型,维持偏好性不变.模型还区分了In和Out边,并且基于In度提出了吸引力的概念,认为顶点的吸引力就是A=A+志.岫.此模型也能呈现幂律的度分布,并且幂指数可调y:2+.其实我们可以看到,实际上,此模型相当于考虑了加点和加边两件事情,只是由新加点引起的边不是一个确定数,内部原有点之间的新加边也不是确定数,但是仍然都维持偏好性.当我们只考虑In度分布的时候,可以忽略新加边Out端点的选择而只考虑In端点的偏好性.有两个试验可以探讨加点和偏好性在模型中的不同地位.第一个试验是只考虑加物理学进展24卷点,但是从新点出发的边的端点的选择不满足偏好性,而是随机选取.模型给出了指数衰减的分布u.另外一个试验是只考虑加边.从一个非常稀疏的N顶点M边的随机网络开始,每一步就是随机选一个顶点,然后按照偏好性选择另一个顶点,如果不存在已连接的边,连之.或者是同时考虑活性偏好与连接偏好,即第一端点的选择和第二端点的选择都按照偏好依附的形式.当然,随着重复的次数增加,模型将趋向于完全网络,所以这样的模型的稳态显然不是幂律分布的.但是,是否存在着一个演化区间,在此范围内,网络呈现幂律分布呢?我们知道如果两个端点都随机选择就是随机网络模型,顶点的度符合泊松分布,那么按照偏好方式选择的随机网络模型呢?如果在一定时间段出现了幂律分布的话,那说明偏好性是其决定性因素,所谓引入新加点只是使得网络取得某种平衡,不至于发展为完全网络而已.Barabsi等人就研究了这样一个模型20,发现在演化的初期确实存在幂律形式的度值分布,但是随着时间的演化逐渐过渡到高斯分布.这说明偏好依附是ScaleFree网络的核心机制,但是新加点也不可或缺.Albert和Barabhsi的第二个关于ScaleFree网络的机制模型31考虑了加点,加边,重连三种事件.每一时刻这三个操作分别以某一概率(1一Pq,P,q)发生,任何一种事件发生都遵循偏好性.理论分析与模拟的结果表明幂律分布与指数分布都可以在网络中出现,取决于P,q的值:q<q一为幂律形式的度分布,否则为指数形式.当然,这样的结果肯定是不完全的,因为当p0.5的时候,加边占统治地位,必然使网络趋向于完全图.所以关于P也存在某一个阈值.无向网络模型的一个比较全面的探索是由Cooper和Frieze完成的L33,他们考虑了加边和加点两件事情,并且探讨了有无偏好性对模型的影响.其演化过程如下,在任一时刻t,以a的几率加边发生在图G(t一1)的原顶点之间,以1一a的几率加入新顶点.如果加入新顶点,则按照某一分布P产生一个随机数i表示从此顶点出发的边数,然后以p的几率在原顶点中随机选择另一个端点,以1一p的几率按照偏好性选择另一端点.如果是在原顶点中加边,则按照某一分布产生一个随机数i表示新加的边数.然后,以的几率在原顶点中均匀选择第一端点,以1一的几率按照偏好性选择第一端点,接着以),的几率在原顶点中均匀选择第二端点,以1一),的几率按照偏好性选择第二端点.文章对于各个参数对于模型的影响都做了理论分析,包括分布形式的显式结果或上下界分析.再用这个框架去看引入顶点年龄历史的模型,我们发现可以认为考虑活性与年龄的关系相当于在一定程度上考虑去点或去边的行为.那么,一个关键性机制突出,又能最大程度上复现相关几何性质,包含一般的网络演化五种现象的机制模型,将是无向ScaleFree网络模型的最终目标.从有向网络的角度来看,无向网络的偏好依附模型可以认为是只存在In度幂律分布.Out度为(out一/n)分布或某种平庸随机分布的演化模型.既然实证研究表明了双向幂律网络的普遍性,那么机制模型的研究工作就需要对此做出回答.对于双向幂律分除了以偏好依附为基础的这一大类模型之外,还存在一类特殊的确定性scaIeF网络二_星结,见Ba臆li等人的文章Bl.对于实证研究而言,有一个静态统计量能够很好地区分这两类模型:顶点集聚程度的分布规律p(c).1期吴金闪等:从统计物理学看复杂网络研究31布模型,如果在单向幂律分布模型的基础上把所有的单向边都换成双向边,那自然就有了双向幂律分布.所以双向比双向边占所有边的比例对于有向网络来说是一个重要静态几何量.还有一种实现双向幂律模型的方式是独立地构造ln和Out边的机制,例如类比于按照偏好性建立的ln边的反馈机制,我们也可建立Out边的反馈机制.基于以上想法,键立了以下模型【0.从m0顶点M边的随机网络开始,在t时刻,以口的几率加入一个新的顶点,并带来从此顶点出发的m条边,以1一口的几率从原有网络的顶点内产生m条边.从新加顶点出发的边的终点按照偏好性选择,即Ain+易inP(U)=_(14)v(A+惫)而从原有顶点出发的边按照Out度的偏好性选择起点,即Aout+易out(),(15)V然后再按照P(u)来选择其终点.当然这样的模型肯定会展现双向幂律分布.还有一个因素也可以在单向幂律的基础上产生双向幂律一ln度与Out度的高度相关性.考察每一个顶点的(d.m,d)之间的相关性,如果存在高度正相关说明,对外联系活跃(Out)的顶点也常常是获得外界联系多(In)的顶点.于是,自然也可以得到双向幂律分布了.那么真实有向网络的双向幂律结构是否能够由以上这些因素来解释呢?这有待于实证分析来回答,尤其是关于度相关性的实证分析及其与理论模型的对比在这一点的判定上就有重要价值.如果以上因素都不能够代表实际网络双向幂律结构的形成机制的话,那么研究者就不得不面对一个包含混合反馈机制的有向网络模型了,比如,ln边可以同时受ln度和Out度的反馈来影响,以及Out边.最后,我们谈谈加权网络的机制模型.由于加权网络的静态几何量与动力学性质没有得到广泛的研究,所以也就很难对其形成机制进行深入探讨了O从机制模型的角度来看,加权网络的演化既包含连接的演化又包含权重的演化,而且两者可能相互影响,看来要复杂得多了.3网络的演化性质在设计网络机制模型的时候,我们主要关1,5静态几何量统计性质的再现,而忽略网络演化过程的统计特征,尽管机制模型设计的就是演化行为.然而,实际上,真实网络的演化性质也是可做实证分析的,尽管网络演化的时间序列包含大量的数据而且难以获得相关纪录.我们把关于实际网络演化的统计性质的研究单独列出来做为动态网络的研究,以区别于静态统计性质的研究.而两者都将为网络机制模型的研究提供启发和标准.目前,动态演化性质的研究比较多的网络是合作者网络【6J与www网络J.物理学进展24卷5.1时间演化性质在Barabgsi等人关于合作者网络的动态演化性质的研究工作67中,他们选择了数学和神经科学领域的研究者网络作为研究对象.首先文章以年为时间单位讨论了顶点(即研究者)数的时间演化,总文章数的时间演化.然后讨论了度分布的时间演化稳定性以及平均度值随时间的变化.接着统计了不同时间点的网络的平均最短距离和平均集聚程度,做了演化曲线.随后对网络最大集团的相对大小也做了随时演化行为的分析.例如图4一a所示为每一年的新加入研究者随时间变化曲线,图4一b为每一年发表的文章数量随时间变化曲线.图4发表文章数量与科学家数量随时间的变化.(a)数学与神经科学发表的文章数量,插图为每一年新发表的文章;(b)两领域内研究者的数量,插图为每一年新增加的研究者.本图取自文章E67除了顶点数和联接数的时间演化性质以外,网络上特定动力学过程的演化性质也应该是复杂网络?