复杂网络_结构和动力学-1

第3卷第3期 2006年9月 复杂系统与复杂性科学 COMpLEXSYSTEMSANDCOMPLEXrIYSCIENCE V01．3 Sep． No．3 2006 文章编号：1672—3813(2006)03—0056—39 原文取自：PhysicsReports，2006，424(4，5)：175—308 ComplexNetworks：StructureandDynamics S．Boccale￡tjl，V．La￡ora2一，Y．Moren04一，M．Chavezf6，D．．U．Hwan91 (1．CNR—IstitutodeiSistemiComplessi，LargoE．Fe珊i，650125Florence，Italy； 2．DipartimentodiFisicaeAstronomia，Universi话diCatani8，ViaS． Sofia，6495123Catania，Italy； 3．InstitutoNazionalediFisicaNucleare，SezionediCatanja，ViaS．Sofia，6495123C8tania，Italv； 4．InstitutodeBiocomputaci6nyFisicadeSistemasComplejos，Universidaddezaragoza，zaragoza50009，Spain； 5．DepartamentodeFisicaTe6rica，UniversidaddeZaragoza，Zar890za50009，Spain； 6．LaboratoiredeNeurosciencesCognitivesetImagerieC6r6brale(LENA)CNRSUPR一640，H6pitalde laSalpetri电re．47Bd．del’H6pital，7565lParisCEDEX13，France) 复杂网络：结构和动力学 方爱丽，赵继军，译 (青岛大学复杂性科学研究所，山东青岛266071) 摘 要：耦合的生物化学系统、神经网络、相互作用的群居物种、互联网和万维网只是由大量高度相 互连接的动态个体组成的系统的少数几个例子。获取这类系统的全局特征的首选方法是建立图模 型——图中的点代表动态个体，边代表个体间的相互作用。一方面，科学家们需要处理结构问题如 刻画一个复杂连线体系的拓扑结构、揭示建立在现实网络基础上的统一原理，以及完善模型从而模 拟网络的增长和复制网络结构特性；另一方面，在研究复杂网络动力学时会产生许多相关问题，例 如研究一个大的动态系统如何通过复杂连接的相互作用来表现集体行为的。我们回顾了近来在研 究复杂网络的结构和动力学方面的主要概念以及取得的结果，总结了这些思想在许多不同学科包 括从非线性科学到生物学、从统计力学到医药学以及工程学等领域的有关应用。 目录 1 引言 1．1 自然界的网络方法 1．2 文章框架 2复杂网络的结构 2．1定义和符号 2．1．1点的度数、度分布和相关性 2．1．2最短路长、直径和介中性 2．I．3 聚类 2．1．4模体 2．1．5社团结构 2．1．6 图谱 2．2现实世界网络的拓扑结构 万方数据万方数据 第3卷第3期 方爱丽，等译：复杂网络：结构和动力学 2．2．1小世界特性 2．2．2无标度分布 2．2．3一些例子 2．3 网络模型 2．3．1随机图 2．3．2广义随机图 2．3．3小世界网络 2．3．4静态无标度网络 2．3．5演化的无标度网络 2．4加权网络 2．4．1加权网络的测度 2．4．2现实世界的加权网络 2．4．3加权网络建模 2．5 空间网络 2．5．1欧几里得空间的小世界行为 2．5．2欧几里得空问的无标度网络 2．5．3现实地理网络建模 3静态和动态鲁棒性 3．I 网络对错误与攻击的静态耐受性 3．1．1数值分析结果 3．1．2无关联网络中的网络弹性 3．1．3关联网络中的网络弹性 3．1．4网络对于攻击的耐受性 3．2动态效应 3．2．1相继故障的建模 3．2．2通讯网络的拥阻 4传播过程 4．1传染病传播 4．1．1均匀混合假设 4．1，2无相联网络 4．1．3关联网络 4．1．4疾病波动 4．2谣言传播 5 同步与集体动力学 5．1 同步导论 5．2主稳定函数方法 5．3网络同步倾向 5．3．1加权网络同步：实数特征谱的耦合矩阵 5．3．2加权网络同步：具有复杂特征谱的耦合矩阵 5．4耦合振子同步 5．5混沌动力学同步 5．6 常微分方程组网络中的其它集体行为 万方数据万方数据 复杂系统与复杂性科学 2006年9月 6 应用 6．1 社会网络 6．1．1结构 6．1．2动力学I：意见形成 6．1．3动力学Ⅱ：策略博弈 6．2互联网和万维网 6．2．1互联网结构 6．2．2万维网结构 6．2．3动力学 6．3代谢、蛋白质和基因网络 6．3．1 结构 6．3．2动力学 6．4大脑网络 6．4．1 结构 6．4．2动力学 6．4．3开放性问题 7 其他问题 7．1发现社团结构的算法 7．1．1谱图分割 7．1．2分级聚类 7．1．3Givan和Newman算法 7．1．4GN算法的变型和拓展 7．1．5基于模块化的快速方法 7．1．6基于谱分析的其它方法 7．1．7其他算法 7．2导航和搜索 7．2．1局域信息搜索 7．2．2网络的可导航性 7．3 自适应及动态连接 致谢 附加证明 参考文献 1 引言 1．1 自然界的网络方法 我们的周围，网络无处不在。就拿我们自己来说是各种社会关系网络的基本单位；作为生物系统，我们 是生化系统反应的精妙结果。网络可以是欧几里得空间的真实物体，如电力网、因特网、高速公路或地铁系 统及神经网络；也可以是定义在抽象空间的实体，如朋友关系网和个体合作网。 历史上，网络的研究主要是离散数学的分支一图论的的范畴。自从1736年瑞士数学家欧拉(Leonhard Euler)发表哥尼斯堡(Kbnigsberg)桥问题(找一个经过普鲁士哥尼斯堡城的每一座桥回到起点的回路，且每 座桥只走一次)的解，图论已经取得了很大的进展，并且为一系列的实际问题提供了答案，比如：单位时问内 从起点到终点经过管道网络的最大流是多少；怎样能用最少种类的颜色给地图涂色以保证相邻区域的颜色 万方数据万方数据 第3卷第3期 方爱丽，等译：复杂网络：结构和动力学 不同；怎样给n个人安排凡项工作以取得整体最大效用。除了数学方面图论的发展，网络的研究还在一些专 门的领域比如社会科学取得了重大成就。社会网络分析从19世纪20年代早期开始发展，主要研究社会实 体之间的关系，如组内成员的交流、国家之间的贸易、或者是公司之间的经济交易。 过去的10年，复杂网络的研究在兴趣和研究方面有了新的发展，例如，对那些复杂的结构上不规则且随 时间动态演化的网络，研究重点从分析小网络转向研究包含成千上亿个节点的网络系统，重新关注由动态个 体组成的网络的属性。这一转变是由两篇具有开创性的文章引起来的，一篇是watts和strogatz于1998年 在Nature上发表的关于小世界网络的文章，另一篇是Barab矗si和Albert于1999年在seience上发表的关于 无标度网络的文章。这股飓风主要由物理学界人士参与，并且日益增强的计算机计算能力为研究实际网络 的大量数据的属性提供了可能。这些实际网络既包括：交通网络、电信网络、因特网、万维网、电影资料库里 的演员合作网、科学引文目录里的合著，也包括生物和医药系统的网络如神经网络、基因网络、新陈代谢网和 蛋白质网。 来自不同领域的关于网络的大量比较分析产生了一系列意想不到的戏剧性结果。面对的首要问题当然 是结构上的问题。对复杂网络的研究是从定义新概念和测度来刻画真实网络的拓扑结构开始的。主要成果是 对所研究的大多数真实网络确定了一系列共有的统一原理和统计学属性。一个有关的属性是点的度数即与 其他点的直接连接数目。在实际网络中，度分布p(后)被定义为随机均匀选择的点具有南度的概率，或者等价 地定义为图中具有矗度的点所占的比例。p(蠡)明显地偏离随机图所期望的泊松分布，许多情况下呈现出幂指 数值介于2～3之间的幂律尾(无标度)分布。另外，实际网络是由点的度相关性、两个点之间相对短路径(小 世界属性)、存在的大量短回路和特定模体来刻画的。 人们发现由数学上图论提供的网络模型与实际需要有很大差距，于是这些实际的发现引发了网络建模 的复兴。科学家不得不开发新的模型来模拟网络的增长和再现实际观察到的拓扑结构属性。真实网络的结构 是由其组成因素不断演化形成的结果，当然也就影响系统的功能。因此在这一阶段的研究，学者们期望通过 理解和建模复杂网络的结构，来进一步更好地了解网络的演化机制，及其动态和功能上的表现。 事实表明耦合结构对于网络功能的鲁棒性以及网络对随机故障或有目的的攻击等外部扰动的反应有着 重要影响。同时首次有研究由动态系统组成的大集合体动态特性的可能，而这些动态系统则是通过复杂拓扑 相互作用的。因此网络拓扑在确定集体动态行为的涌现中起了重要作用。举例来说，涌现可以是同步或者说 是对发生在复杂网络上的有关过程主要特性的管控，如流行病、信息、流言的传播。 文献中已出现了许多对读者有参考意义的复杂网络的综述性文章¨。。和"书。。watts的文章是关于处 理小世界网络的结构和动力学问题的先驱作品¨。；Strogatz发表在Nature有关复杂网络专刊上的文章讨论了 由动态个体组成的网络¨o；Albert和Barabds∥1、Dorogovtsev和Mends¨’刊的综述着重于从统计力学的角度 上研究的增长网络模型。Newman的综述文章H1是这个领域的重要的记述，包含精确的参考文献目录，详尽 地回顾了结构属性、度量和模型，最后一章还致力于对发生在网络上的过程的研究。在这值得一提的还有4 篇参考文献，即由Bornholdt和Schuster编辑整理的文集¨1、Pastor·Satorras等编辑的文集”。、Ben—Naim等编 辑的文集¨0。、Pator—satorras和Vespignani的关于因特网的分析与建模的书籍¨。。市场上还为外行的读者提 供了许多关于复杂网络的流行书¨。”。。例如看了Buchanan的文章⋯1就会拥有这个领域学者的观点。另外 许多在特定研究领域有关网络的相关书籍已经出版。Bollobds¨4’”1，west¨刮和HararyⅢ1的关于图论的书籍 也值得参考。由Wasserman和Faust编写的教科书¨引和由Scott编写的文献[19]在社会网络分析方面为人们 所熟知。参考文献[20—22]描述了图算法。 激发我们关于这个题目另外再做一个的原因有如下3条： 第一个原因是新的研究方向已经出现，涵盖网络结构方面的新的题目和问题。一个例子是对于加权网络 兴起的研究，加权网络是指网络中的每一条边都赋予一个实数。大多数真实的复杂拓扑结构通常在连接的容 量和强度上有大的异质性，这激发了对加权网络的研究。在社会系统中个体之间存在着弱连接和强连接；在 神经网络中存在传送电子信号的容量不同；因特网上存在非平衡流量；这都是实际加权网络的的例子。忽略 万方数据万方数据 复杂系统与复杂性科学 2006年9月 了这些相互作用的多样性，将意味着丢失很多复杂网络上的信息，而这些信息对于刻画网络是非常有用的。 另一个新的题目是关于空间网络。复杂网络早期工作集中于刻画拓扑结构属性，空问方面很少得到关注，甚 至被忽略。然而，拓扑结构可能被地理上的嵌入所制约，这一点也不奇怪。例如空间网络的长程连接由欧几里 德距离约束，这对于网络的统计属性有重要的影响。并且因为能连接到单个点的边的数量由点的物理位置限 制，所以点的度数是有限制的。这在平面网络特别明显(任两条边相交得到网络的顶点)，就像城市街道，在 一个十字路口仅有一小部分街道穿过。即便是在非平面空间网络，比如航线网，连接的数目是由机场的可利 用空间所限制。这些事实都说明空间网络与其他复杂网络不同。除了对结构属性的充分论述，本文还包括所 有这些新的内容以及它们在相应具体情况下的应用。 第二个原因是最近这个题目的主要兴趣转向研究网络的动态行为，尤其是对网络的结构如何影响其动 态属性的研究。例如对复杂网络的集体同步动力学的研究，就是将拓扑结构与耦合的动态系统局部特性之间 的相互影响与网络的同步联系在一起。事实上在许多相关情况下这种现象表现了一个至关重要的特征。例如 有证据表明一些脑疾病是大量神经元反常、有时突然同步引起的结果，因此研究癫痫的产生、持续和传播的 网络机理是当今神经系统科学的前沿课题。同样在社会学领域，较好地理解形成社会集体行为(如新的习 惯、流行时尚、主流观点的突然涌现)的机理与同步现象非常相关。本文的第二章的大部分内容概述了迄今 为止取得的关于复杂网络中集体行为的主要成果，回顾了已有的主要观点和概念，对现有的严格的结论也作 了评价。 最后我们给出当前吸引科学界关注的一系列课题，其中包括建立寻求社团结构的可操作的算法的问题、 复杂网络内搜索问题、适应网络的建模问题。 社团结构是复杂网络的一个重要属性。例如：社会网络中紧密相连的若干组点代表属于社会团体的个 体；在万维网中表示关于共同标题的网页。而在细胞和基因网中社团则与某种功能性模块有关。因此，在网络 内部找到社团是理解网络功能的有力的工具，也有助于识别复杂结构内部的连接层次。 另一个有关问题是在没有全局结构信息的情况下如何通过网络导航由网络中的一个点到达另一个点， 或者说仅仅基于网络拓扑结构的一些局部信息如何优化搜索程序。 对本身是动态实体的那些网络来说，适应和动态连接是它们的特性。这意味着拓扑结构不是固定的、成 熟的、也不是一成不变的。相反由于外部作用的驱使或者内部元素的作用或者遵循明确的预先确定的演化规 则，允许它随时问演化和调节。这一进步是由于要为一些特殊案例(如基因调整网络、生态系统、金融市场) 恰当建模的需要而推动的，也是由于要适当地刻画一系列科技有关问题(如移动的无线连接的个体)的出现 的需要而推动的。有一些研究工作刚刚起步，尽管结果不是很完善，但是我们相信未来会有进展。 1．2 论文大纲 本文组织如下： 第2章讨论网络的结构。描述从实际网络拓扑结构观察得到的一些共同的属性，以及如何度量。然后简 要地回顾了这些年来提出的主要模型，侧重于随机图、小世界模型和无标度网络。最后特别强调对于加权网 络和具有空间结构的网络的研究和建模。 第3章讨论对一些组员的外部干扰或者故意破坏造成故障的情况下的网络的鲁棒性，回顾了静态的和 动态的方法，特别是描述了发生在相关联和非相关联网络上的渗流过程、相继故障、交通和通讯网络的拥阻 现象。 第4章探讨了复杂拓扑结构的元胞自动机，分析了一系列传染病和流言扩散模型。 第5章是关于复杂网络的集体同步动力学的涌现。在这里我们回顾了使同步倾向最大化的网络拓扑结 构条件下，以主稳定方程方法为代表的最重要的成果。我们进一步考虑了非线性演化的动态个体组成的网 络，并且回顾了在混沌映射网络、混沌系统网络和周期性震荡网络研究方面取得的主要结果。 第6章总结了实际网络的一些应用，如因特网、万维网、社会网、描述细胞成分相互作用的网络和神经网 络。这一章包含了关于这些网络的结构和动力学两方面的问题。 万方数据万方数据 第3卷第3期 方爱丽，等译：复杂网络：结构和动力学 最后，第7章探讨了近来在学术界引起极大兴趣的三个主题。首先讨论了将一个大的网络分成社团结构的 算法，然后回顾了在寻求快速可靠的复杂网络的搜索与导航方面的最新成果，最后讨论了适应动态连接网络。 2 复杂网络的结构 本章的目的是简要介绍对网络特性的表征和建模的最新进展。首先介绍定义和符号、论述用于描述网络 拓扑结构的基本量，进而分析观测到的实际网络的属性，并为读者提供所得模型的简要回顾。本章最后综述 了在加权网络和空间网络研究方面取得的最新成果。 2．1 定义和符号 图论¨4一¨是复杂网络精确数学处理的自然框架，且形式上复杂网络可以用图表示。无向(有向)图G= (N，多)由集合N和西组成，且N≠咖，集合垂是由集合N中元素的无序(有序)对构成的集合。集合N； {n。，孔：，⋯，n。}中的元素是图G的节点(又称为顶点或点)，集合圣s{f。，z。，⋯，f。}中的元素是图的连接(又 称为边或线)。集合N和少中元素的个数分别由Ⅳ和K表示。以后文中，当必须强调图中的点和边的数量时， 我们将图表示为G(Ⅳ，K)=(N，痧)，简记为G(Ⅳ，K)或G眦。 (a) (b) (c) (a)无向图；(b)有向图；(c)加权无向图，其中点数』v=7，边数置=14。有向图中相邻点 用表示方向的箭头连接。加权图中，”“表示边的权重，用边的粗细来体现权重大小。 图2．1 无向图、有向图及加权无向图 通常按在集合Ⅳ中的次序i来提及点。无向图中每条边是由一对点i和_『来定义，表示为(i，J)或z。边可 以说是关联点i和j，或者说连接这两个点；点i和j称作边(i，J)的端点。通过边相连的两点称为邻接活邻居。 有向图中，两个点的顺序很重要：z。i表示一条由点i指向点．『的边且fii≠Z。。通常是这样描绘图的：画圆点表示 点，如果两点之间有连接就在相应的两点之问画一条线。怎样画这些圆点和线都无关紧要，重要的是哪两个 点连成边，哪两个点没有。图2．1(a)和(b)分别是无向图和有向图的例子，图中Ⅳ=7，K=14。注意到图形 不含有环，即两端点相同的边，也不含有多重边即两点之间不止一条边相连，因为这些都不符合上面给出的 图的标准定义。含有环或多重边的图称为多重图¨5’懈3。本文重点讨论的不包括多重图，如果不特别说明，图 指无向图。加权图将在2．4节详细讨论。 ^，，^， 1、对于大小为Ⅳ的图G，边数K至少为o，至多为坐上≯(这时所有点两两相邻接)。如果K《Ⅳ2则称图 上 ^r，^r 1、 、G是稀疏图；如果K=o(Ⅳ2)则称图G是稠密图。如果K=《=尘业≯则称图G川为Ⅳ阶完备图，表 Z 示为K。。疋称作三角形。 满足N’∈N且空’∈中的图G’=(N7，西’)称为图G=(N，西)的子图。如果图G中连接集合N7中点 的所有边都在图G’中，则称G7为由N’导出的子图，记为G’=G[N’]。对于某一给定的属性来说如果一个子 图在不丢失该属性的前提下不能再扩展，那么该子图就是最大子图。与后面章节相关的定义是给定点i的邻 居子图，记为G；。G；定义为Ni的导出子图即Gi=G[Nj]，其中Ni为点i的邻居点集合。 万方数据万方数据 复杂系统与复杂性科学 2006年9月 图论的一个重要概念是图中两个不同点的可达性。实际上，即便不相邻的两个点也可以由一个到达另一 个。从点i到点．『的路是从i开始到，的点边交替序列。序列中的边数定义为路的长度。各边相异的路称为迹 (trail)，各点相异的道路称为路径(path)。两点之间长度最短的路称为最短路。环是封闭的路，至少要有3个 点并且边不重复。长度为Jj}的环通常叫做后一环记为c。。c，是三角形(c，=玛)，C。是四边形，C，是五边形等 等。如果每一对不同的点i和，，都有一条路径，我们就说图是连通的，否则就称不连通的。最大连通导出子图 称为组元，巨组元是阶次与Ⅳ相同的组元。 图的矩阵表示是经常用到的。图G=(Ⅳ，妒)可由邻接矩阵A完全描述。给定邻接矩阵A是一个Ⅳ×Ⅳ的 方阵，其元素为口"(i，．『=1，2，⋯，Ⅳ)，若边f；f存在则oii=1，否则口if=O。邻接矩阵的对角线上的元素都是 0，从而无向图的邻接矩阵是对称的。另外一种表示方法是关联矩阵曰，曰是Ⅳ×K矩阵，其元素为6∽若点i 连接于边2。则6诂=l，否则6诸=0。 2．1．1 点的度数、度分布和相关性 点i的度数七i是与该点连接的边数，用邻接矩阵A定义为： 后：=∑口u (2．1) iEN 如果是有向图，点的度数包括两部分：从i出发的连接边数"‘=>’口。(记为出度)，指向i的连接边数"= 7‘ >’o“记为人度)，i点的总度数定义为忌；=I|}r+F。一个图的点的度数列表称为度数序列。 度分布p(．|})定义为随机均匀选择的点具有而度的概率或者说图中具有．|}度的点所占的比例，根据p(五) 可以获得图G的最基本的拓扑特征。度分布也可以记作p。，其中南取非负整数值。 对于有向网络，需要考虑两种分布，p(扩)和p(尼”‘)。要得到无向网络的各点的度数分布信息可以通过 绘制p(Jj})图，也可以通过计算分布的矩。p(J|})的乃阶矩定义为： (1|}“)=∑唧(1|}) (2．2) A 一阶矩(七)是图G的平均度数。二阶矩衡量连接分布的波动性，而且我们将在第3章和第4章看到，当图 的大小无穷大时，(七2)发散，从根本上改变了发生在图上的动力学行为。 度分布完全决定了非关联网络的统计属性。然而我们将看到，许多真实网络是相关联的，具有而度的点 与具有后’度的点相连的概率取决于后。在这种情况下，有必要引进条件概率p(七’I尼)，定义为从后度的点出发 的一条边指向矗’度的点的概率，满足归一化条件>lp(尼’I庇)=1和平衡条件如(南7I南)p(后)=露’p(矗I 下 尼’)p(矗7)‘2耶4|。对于无关联图，由于p(七’J矗)不依赖于|j}，由平衡条件和归一化条件得到p(||}’I七)=掣。 ＼盯， 虽然度相关性形式上由p(矗’I|j})刻画，然而由于大多数实际网络来说Ⅳ的大小是有限的，所以直接计算 条件概率会得到噪声很大的结果。这个问题可以通过定义点￡最近邻平均度来解决，即： k，i=奄砖=击扣t (2．3) 这里将所有属于点i的第一邻居集合Ni的点的度数求和。利用定义(2．3)，可以计算具有詹度的点的最近邻 的平均度数，记为|j}。。(后)，得到隐含的对尼的依赖关系拉5|。事实上，这个量可以用条件概率表示为： 庇。。(矗) = >‘矗’p(后71愚) (2．4) 节 ／L2＼ 如果不存在度相关性，[2．4]写为：JjI。(蠡)：号*即知。(后)独立于．|}。相关联图分为两类：同类匹配图和 ＼托／ 非同类匹配图。如果矗。。(|j})是_j}的增函数，则此关联图是同类匹配的；如果忍。。(后)是矗的减函数则此关联图 是非同类匹配的旧⋯。换句话说，在同类匹配网络中点趋于连接和它们相关联的点，而在非同类匹配网络中度 数低的点更可能与度数高的点相连。度相关性通常用作为||}的函数的后。。(后)的斜率y的值来量化，或者通过 万方数据万方数据 第3卷第3期 方爱丽，等译：复杂网络：结构和动力学 计算边的任一顶点的度数的皮埃逊相关系数来量化"6’27|。在2．2节将通过讨论实际网络的例子来展示这两 类相关性。 2．1．2 最短路长度、直径和介中性 最短路在网络内交通和通讯方面起着重要作用。假设需要通过因特网从一个计算机向另一个计算机传 送数据包，最短路提供了一个最优的路径从而可以快速传送并且节省系统资源¨]。同样道理最短路在刻画 图的内部结构方面也起着重要作用¨8’悖]。我们可将图G的所有最短路长表示成矩阵D，其元素d。表示点i到 点，的最短路的长度。d。的最大值称作图的直径，以下将用Di口m(G)表示。度量图中两个点问典型间隔由平 均最短路长给出，也称作特征路长，定义为所有顶点对之间的最短路长的平均值∞’28|： 卜而u萎；，_。 (2·5) 此定义存在一个问题就是当图中有不连通的组元时，L发散。一种可能避免无穷大就是公式(2．5)只限于对 属于最大连通组中顶点对求和心81。在许多情况下(见3．1．1节)另一种有用的方法是考虑最短路长的调和平 均值心"，定义图C的所谓的效率‘3叩13为： 肌赤磊≠，壶 @·6) 该量是网络的通行能力的一个指标，并且避免了公式(2．5)可能出现的发散结果，这是由于图中非连通顶点 对÷=o，在公式(2．6)的求和中不起作用。效率E数学性质的研究见参考文献[32]，效率E的最新应用见文 。玎 献[33—35]，公式(2．6)的扩展见文献[32，36]。 两个不相邻点J和忌之间的通讯，依赖于连接_『和而路径上的其它点。所以度量一个给定点的关联性可以 通过计算经过该点的最短路的数量来得到，定义为点的介数。和点的度数、紧密性(定义为从所有点到达该 点的平均距离的倒数)一样，介数是点的中心性的标准测度之一，最初应用在社会网络中量化个体的重要 性‘18’伸驯，更准确地说点i的介数6i有时也指负载⋯J9’38’391，定义为： 6：：y丝盟 (2．7) ‘ u氧≠k‰ 这里n琅是连接点．『和忌的最短路径的数量，而n。(i)是连接点_『和后且经过点i最短路的数量。文献[20一22] 给出找到最短路的标准算法(如7．2节的Dijkstra算法或广度优先搜索)，文献[40，41]给出了最近推出的计 算介数的快速算法。文献[42—47]研究了介数的分布。文献[42]和文献[48—50]分别研究了介数与介数相 关性和介数与度数相关性。 介数的概念可以推广到边的介数，定义为通过该边的顶点对的最短路数量"1|。后者广泛应用于第5．3 节和7．1．3节。 2．1．3 聚类 聚类也称传递性，是朋友关系网络的典型属性，在这个网中两个人共同的朋友很可能互相认识¨8i。对于 一般的图G，传递性意味着存在很多三角形。可以用图的传递性T来量化，定义为传递三元组的相对数即顶 点关联三元组构成三角形的比例¨’52’53。： 个一 3×图中的三角形数 r，¨ 1一图中顶点关联三元组数 p一7 分子上乘以3是因为每一个三角形都含有三个以其一个点为中心的顶点关联三元组，确保0≤r≤1。对瓦 图，丁=1。 另一个办法是利用watts和strogatz在文献[28]中提到的图的聚集系数。首次引入点i的局域聚集系数 ci来表示点i的两个邻居_『和m有多大可能使n胁=1，ci的值可以通过对图C；(2．1节定义的点i的子图)中 的实际边数(记为q)计数而得到。注意到Gi有时候是不连通的。局域聚集系数c。定义为8i与蔓掣的比 万方数据万方数据 ·64· 复杂系统与复杂性科学 2006年9月 值，掣为G。中可能的最多边数”，28J。 2e ‘～= (2．9) 计算c。的快速算法见文献[54]o图的聚集系数是G的所有点的c。的平均值： 1 c=(c)=亩∑c； (2．10) ‘’l∈“ 根据定义有0≤c。≤l且0≤G≤l。C和r的区别见文献[4，31]。有时用到K级连通的聚集系数c(惫)，c(南) 定义为所有具有露度的点的c。的平均值。 近几年人们提出各种高阶聚集系数，其中具有后阶邻居的知阶聚集系数¨￡563；基于四阶环的内部结构‘573 或一般阶次的环的数量¨81的度量方法。文献[59，60]给出无偏度相关情况下的聚集系数定义，文献[61]给 出有向图中三元组的概念，文献[33]给出平面图的聚类定义(见2．5节)。图G的聚类属性的另一个测度是 局部效率阳0’3“，定义为： 1 Ek=亩∑E(G；) (2．11) 4。lE“ 其中层(G?)是图G。的效率，可由公式(2．6)计算。 2．1．4 模体 ‘ 模体肘是有向图或无向图G中点的相互连接模式，出现频率比在随机图中明显要高。随机化图具有和原 图形相同的点数、边数、度分布，但是边的分布是随机的。作为一种相互连接模式，M通常意味着G的一个含n 个顶点的连通(有向或无向)的子图。一个所有3个点的有向连通图的例子见图示2．2。 >>>卜》)． )． ) f＼． 1)．r、 丫。■圹、 - 、kys 》>>》p谚≯p 》》》》 图2．2 所有含有3个点的有向连通子图的13类模体 模体的概念最早由A10n和他的同事们提出，见文献[62—66]，他们研究生物和其他网络中的小儿模体。 图G的有效模体的研究是基于匹配算法，数～下原图和随机化以后图中n点子图M出现的次数。肘的统计显 著性是用z分数来描述的，定义为旧删： z肝：掣 盯“Ⅳ (2．12) 其中n村是G中子图肘出现的次数，(n嚣以)和盯嚣。分别是在随机化图中肘出现次数的平均值和方差。 万方数据万方数据 第3卷第3期 方爱丽，等译：复杂网络：结构和动力学 2．1．5 社团结构 历史上，社团的概念及其首次网络形式定义出现于社会科学¨“。给定图G(N，中)，社团(群或粘着子 图)是一个各点紧密相连(粘着)的子图G’(N’，痧7)。由于G’各点之间结构的凝聚可以用不同的方法来量 化，因此对社团结构有不同的定义。 条件最强的定义要求所有社团成员对之间都相连，这就引出派系的概念。派系是至少3个点的最大完全 子图，即图中点的子集满足：子集内的所有点两两相邻且再没有其他点与子集内的所有点相邻，这样的子集 就构成一个派系。将条件“相邻”削弱为“可达”此定义可以扩展为：忍一派系。儿一派系是一个最大子图，其中 任何两点之间的最短路长的最大值小于等于n。当n=1时此定义与原定义相符，2一派系是所有点不必相邻 但是必须通过至多～个中点可达的子图，3一派系要求所有点通过至多2个中间点可达，依此类推。然而，n一 派系的概念使得允许路径长度的增加，另一种是放松派系的强假设条件的方法是，将每个点必须连接的其他 顶点数量减少。K一丛是包含n个点的最大子图，其中每个点与子图中的至少n一七个点相邻。 对社团结构的另一类不同定义是基于边的相对频率。这种情况下社团可以看成是若干群，群内的点连接 紧密，群之间的点联系稀疏M_68』。例子见图2．3。这类最简单的形式定义见文献[69，70]。一个不是很严格的 定义如下：如果G’内的度数和比与G7外其它点连接的度数和大，那么C’就是一个社团"“。并非只有上述列 出的定义方法，可能还有在某种情况下更适合的一些其它定义，见文献[18]。 2．1．6 图谱 图谱是图的邻接矩阵A的特征值的集合¨“。 图G舭有Ⅳ个特征值肛i(i=l，2，⋯，Ⅳ)，Ⅳ个相 应特征向量y；(i=l，2，⋯，Ⅳ)。当G是无环且无 多重边的无向图时，A是实对称矩阵，因此图G有 实特征根，p。≤肛：≤⋯≤p。，对应于不同特征值 的特征向量是正交的。当G是有向图时，特征值可 能含有虚部，例如有3点的遍历图。所以特征值和 特征向量的阶和性质就更加复杂。适当时候将对 后者详细描述。 Perron—Frobenius定理说明图(可以是有向 图)存在一实特征值弘Ⅳ及其对应的实的非负特 社团定义为点的群，群内部连接紧密，而外部稀疏。上 图中，用虚线圈表示出三个社团。本图取自文献[51]。 图2．3 社团结构图 征向量，对任意特征值p，有l肛l≤肛。。如果图是连通的，pⅣ具有多重1，对所有不同于肛Ⅳ的特征值肛都有 I弘I<弘。。当点和边从图中移走时，p。的值就减小。对一个连通的无向图，这意味着最大特征值是非退化的， 相应的特征向量矿。中的每个元素都是非负的。所有其他特征向量中的元素同时具有正值和负值，因为它们 与矽．Ⅳ正交。同一定理说明在连通图中有后。；。<(后)：6(肛一肛；) (2．13) 』V互一 当Ⅳ一∞时，p(肛)逼近一个连续函数。图的特征值及相应的特征向量与其重要的拓扑特征密切相关，如：图 的直径，图中环的数量和图的连通属性等。 例如：因为Tr(A)=0，所以所有特征值之和为0，两两特征值之积相加等于一K，任3个特征值之积相加 等于G中三角形的个数的2倍，高阶乘积相加分别与长度为4，5⋯的环的个数有关¨”4’75。。此性质是基于这 样一个事实：矩阵A‘的第i行第，列元素等于经过I|}步从点i到达点_『的路径的个数¨引，因此A‘的迹给出了 图中某点经过_|}步回到自身的路径的总和。由于A‘的特征值是A的特征值的I|}次幂，A‘的迹可以由A的特征 N H ． 值获得，两不必进行矩阵乘法运算。由Tr(4‘)=芝：p；和(y弘；)5=o可以推得上述性质。 万方数据万方数据 复杂系统与复杂性科学 2006年9月 这也意味着公式2．13的谱密度p(p)的第1j；阶矩膨。，定义为艏。=专>：肛：=÷Tr(A‘)，等于图中的点 』’■，． 』V 经过．|}步回到起点的所有路径数的总和除以ⅣL_72J。特征值也给出图的直径的一系列范围。例如：普通图的 D沱m(G)比不同特征值个数少。而在座～规则图(图中点的度数都等于尼)中，由于D；m(G)≤ 1n／^， 1、i丽￡等萤瓦赫，比较好的上限估计可以由第二大特征值肛¨得到。 从正规矩阵和拉普拉斯矩阵的谱中可以提取图的连通性质的重要信息。正规矩阵定义为Ⅳ=D—A，其 中D是对角线上元素为D。=>’口。=店i的对角矩阵。组合Laplace矩阵／i，也称为Kirchhoff矩阵(最早由 7‘ Kirchhoff提出)，定义为／I=D—A。／l是一个对称半正定矩阵，因为A可以用关联矩阵表示为A=曰曰“”1， 所以A的所有特征值都是非负实数，／l具有Ⅳ个实的正交特征向量。由于A每行元素和都为O，所以／l总有 最小特征值A．=o，对应特征向量p，=(1，1，⋯，1)。很容易证明特征值。的个数等于G的组元的数量。一般 地，第二最小的特征根A：是非平凡的，一系列图谱理论证明：A：越大，图越难切分。 A的特征值和特征向量、矩阵／土和Ⅳ已经用于描述真实网络以及模型"2’73’76。7引，也用于揭示粘连子群和 其他区域特征的存在，7．1．1节将详细介绍。关于谱方法在网络分析及可视化方面的作用见文献[74]。 2．2 实际网络的拓扑结构 自然和技术中的许多系统是由大量高度关联的动态个体组成的。撙]。耦合生化系统、神经网络、相互作用 的群居物种、互联网和万维网仅仅是其中的几个例子。取得这类系统的全局特征的首选方法是建立图模 型——图中的点代表动态个体(如大脑的神经元或社会中的个人)，边代表个体间的相互作用。当然，这只 是一种近似表达，因为这意味着将依赖予时间、空间、和其他许多因素的两动态个体的相互作用转化为两相 应点之间是否存在边的一个简单的二进制数。不过，许多情况下，这是整个系统的简单而又信息齐全的表现。 过去的10年，大量增长的有效数据、计算设备的优化以及强大可信的数据分析工具已经为研究现实世 界的网络的拓扑属性提供了越来越好的条件，我们才可以研究各种系统内的相互作用如：通讯阳’25’80]、社 会心818卜841和生物系统∞5娟81。主要研究结果表明，大多数实际网络内在不同，但是具有相同的拓扑属性，如较 短的特征路径、较高的聚集系数、度分布的胖尾形状、度相关性、模体和社团结构。实际网络的所有这些特征 与规则网格和随机图(数学上图论的标准模型)绝然不同。这引起了人们对理解形成网络拓扑结构的演化机 制、

设计

领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计

体现实际网络最重要特征的网络模型的极大关注。我们将在2．3节回顾各种模型。这里我们简要讨论 网络的最重要属性：小世界效应、无标度分布、度相关性和聚类特征。一些实际网络的更完整描述见第6章。 2．2．1 小世界属性 对一些实际网络上的动态过程的研究已经表明捷径的存在。连接网络不同区域的桥可以加快远距离点 之间的通讯。 在D维空间超立方体网格上，一个点要到达任意选定的点需要经过的点的平均数量随着网格的大小按 ⅣⅣ4增长。相反，大多数实际网络尽管规模很大，但任两点之间有相对较短的路径。这种特征被称为“小世界 属性”，在数学上用平均最短路径长L来刻画，￡由等式(2．5)定义，且与网络的大小Ⅳ呈对数关系"’2引。这条 属性是20世纪60年代首先由Milgram在社会网络中发现的，Milg豫m做了一系列实验来估计熟人网络中一 个人到达另一个人的实际步数¨E”4“。 开始实验时，Milgram要求被随机选取的住在内布拉斯加(Nebraska)的一些人将信件送给一个Boston 的人，只知道此人的名字、工作和大概位置。信的当前持有者只能把信传给知道名且估计离目标人较近的人 手中。Milgram跟踪了这些信件的传送路径，分析了传送者的熟人关系动力学特性。一般我们会猜想信件最 终到达目的地会经过上百步，但是Milgram得到惊人的结论：到达目标人平均只需要6步。最近，Dodds等 人冲引成功地重复了Milgram的实验，不过是关于全球因特网范围内的电子邮件的传递。事实上，邮件完成传 递信息任务的链接数是服从统计特征的。 万方数据万方数据 第3卷第3期 方爱丽，等译：复杂网络：结构和动力学 在许多其他实际网络如生物网、技术网中也发现了小世界属性”’2 8’40’52 o，并且是某些网络(如随机网)的 明显的数学属性。和随机网不同的是，小世界属性在实际网络中经常伴随着聚类现象，表现为由公式(2．10) 计算得到的高的聚集系数值(见表2．1)。因此，watts和Strogatz的具有开创性的论文中提议将小世界网络定 义为：既具有象随机网一样小的￡，又具有象规则网一样大的聚集系数c的网络∽8【。基于效率公式，这样定义 的网络具有高的全局效率E幽。(公式2．6)，和高的局域效率Ek(公式2．11)，也就是说，这样的网络不管是在 全局还是局域范围信息交换效率都很高∞0’”1。 2．2．2无标度分布 几年前science杂志上研究的通常是均质网络。有相互作用的结构中的均质性意味着几乎所有的点在拓 ^r，^r1、扑意义上是相当的，就像规则网和随机图。例如对随机网来说，生坐掣个可能连接中的任一个连接存在的 Z 概率相同，因此度分布为二项分布，或者当图的规模无穷大时趋于泊松分布(见第2．3．1节)。因此，难怪科学 家利用实际网络数据进行研究时，有理由认为度总是分布在均值周围，具有明确的二次波动平均。与期望的 相反，人们发现大多数实际网络服从幂律形状的度分布p(后)～A_|}～，指数y的变化范围为2 < h < < > > _呈 n n U U 7 l O 8 8 9 儿 儿 7 尼 3 1 1 l 4 2 4 3 5 2 2 2 2 2 2 2 2 l 4 M ∞ 叭 ¨ 昕 ， ” ∞ ∞ O O 0 O O 0 O 0 O 眈 5 3 坨 ∞ 铂 酪 孵 3 9 4 6 2 7 8 3 4 坶 ∞ 6 5 鲫 2 ∞ 鼯 4 2 3 7 6 3 5 叭 2l|一删?一一一一删罴=篡=一 万方数据万方数据 复杂系统与复杂性科学 2006年9月 最先考虑的信息／通讯网络是因特网的两个例子旧一￡80j。这两个网络中点表示主机，边表示它们之间的 物理连接。AS200l代表2001年4月16日自治系统层次的因特网”引，而Routers表示路由器层次的因特 网归8|。Gnutella是由clip2分布搜索法¨叫提供的点对点的网络∽91，作为一种连接成千上万台电脑的方式越 来越受欢迎，它使得局域的或者是更广区域内的用户间能共享文件(如音乐或录像)。最后，由不同网页间的 超连接组成的万维网，含有多于108个点，是当今研究的最大的网络。与前面提到的网络不同的是，万维网是 有向的，每个网页有一些人边，也有一些指向其他网页的出边。所有的这些图都是稀疏的且具有小的平均度 (后)。它们都呈现小世界属性，即就有相比于网络规模来说很小的特征路径长。它们都具有大的c值，都表现 为幂律度分布(幂指数见表)即它们是无标度的。图2．．4画出自治系统层次的因特网在不同3年的累积度分 布图形。新的点不断出现，旧点不断移除， 从这个意义上讲因特网是一个动态实体， 尽管如此，我们看到网络仍然保持着无标 度属性。然而上面所提的网络在最近邻点 之间的度相关性上有所不同。AS和 Gnulella网络表现出不相称度相关性，即 点趋于和不相近度数的点相连，由表中y 的符号表示。相反，Router网络展示了相称 的度相关性，即点趋于和相近度数的点建 立连接。最近在一些包括技术网络的网络 应用方面，有人指出距离d≥1的点之间 的度度相关性的重要性¨⋯。这种相关性 可以由距离为d的相邻点的平均度 (K“’)。来刻画，1时服从和(K‘1’)。相 同的趋势，d越大，相关性越小(也可见图2．5a中斜率∥关于d的函数图)。而在图2．5b一直到d=2度相关 性都是相称的，d>2开始不相称。最后，d>6时，与不相称网络比较而言，网络的度相关有相同的趋势。 ^ 名 Ⅺ V (a)As因特网、(b)Router因特网中与☆度点的距离为d的最近邻点的平均度图。其中插图给出曲线斜 率与d的函数依赖关系，表明：离起点的距离增加时度相关性的变化。引用该图得到文献[102]的允许。 图2。5 与量度点的距离为d的最近邻点的平均度图 万方数据万方数据 第3卷第3期 方爱丽，等译：复杂网络：结构和动力学 表2．1的第二部分给出两类生物网络(酵母中的蛋白质相互作用网"钊和新陈代谢反应网旧5’”纠)的主要 拓扑属性。第一类网的点是蛋白质，如果两蛋白质之间有相互物理作用(例如两氨基酸链互相粘合)那么两 点之间用边相连。此网络表现为高度的异质拓扑结构，同技术网络观测到的一样，大多数蛋白质参与少数的 相互作用，而少数蛋白质与其他许多蛋白质相互作用。特别地，蛋白质有五个相互作用的概率p(七)可由具有 指数分界的幂律分布拟合。在幽门螺旋杆菌的蛋白质相互作用网中也发现了相同的无标度现象。”⋯。因此， 蛋白质相互作用网和基因网近几年得到了彻底的研究旧6’105—08J，人们相信如上所述的研究有助于找到特效 药或者完成蛋白质作用图¨08’蛐引。新陈代谢反应网是有向网，其点是化学物质，通过它们之间的代谢反应相 连旧5’103|。同时，参与七次代谢反应的酶作用物的出度入度都服从相同指数的幂律分布。令人惊讶的是，这种 特征是普遍的。不管从生命领域哪方面来考虑，无标度特征都是相同的旧5|。新陈代谢网还有吸引人的地方就 是高度等级性和模块性¨∞J。特别是模块性(即存在共同作用以完成某种功能的互相连接的分子集合)看来 是基本的图形特征。第6．3节将继续讨论新陈代谢网、蛋白质网和基因网。在高层次的生物组织中也有高度 异质网络，一个例证就是食物网。其中点代表生态系统的物种，有向边代表捕食者二被捕食者关系。现有的 几个有关食物网拓扑结构的¨7'明’110—131的统计研究没有最终下结论是否所有的食物网都可以看作无标度网 络。然而，所有食物网的研究结果表明这样的网络具有小世界属性，至少是高度的异质性，至于是否是无标 度，其强分界可能是由所分析的生态网很小而产生的。 表2．1最后给出3个社会网络的例子。从历史上讲，社会系统是最早从网络的视角研究的系统之 一【89’114|。社会网络正式定义为一些个体或社会实体通过他们之间的某种相互关系连接在一起的网络。相互 关系有不同种类，如友谊、合作、性接触或商业关系。这里我们讨论由合作论文关系定义的数学家合作网、建 立在互联网电影资料库的电影演员合作网(在同一部电影中扮演角色的演员组成的网络)以及邮件交换 网隅4|。后者网络中的点表示邮件地址，有向边表示信件从一个地址传向另一个地址。尽管此网络通过通讯网 (因特网)工作，人们通常认为这是社会网络，因为它反映了终端用户的不同社会关系。正如表中所见，3个网 络都有幂律分布特征，小的L值，大的聚类系数。尽管在数据的收集过程中可能有不精确之处，但是许多现代 网络理论是由社会人际学¨扎191得出来的，由于该系统为新观念和工具提供好的平台；激励了近来社会网络 研究的发展。例如：检测社团结构的算法通常在社会网络中进行测试(见7．1节)，这是由于这类系统天生的 倾向是有各种大小的社团结构和派系。 2．3 网络模型 对第2．2节实例的观察，无疑推动了新概念和模型的引进。本节，我们着重介绍网络数学建模，从动机、 构建程序和重要属性方面探讨一些简单一般模型。更细致介绍见文献[2—4，7]。 2．3．1 随机图 对随机图的系统研究是由Erd6s和R6nyi在1959年开始的，起初的目的是用概率论方法研究图的属性