第３卷第３期２００６年９月
复杂系统与复杂性科学
ＣＯＭｐＬＥＸＳＹＳＴＥＭＳＡＮＤＣＯＭＰＬＥＸｒＩＹＳＣＩＥＮＣＥ
Ｖ０１．３
Ｓｅｐ．
Ｎｏ．３
２００６
文章编号：１６７２—３８１３（２００６）０３—００５６—３９
原文取自：ＰｈｙｓｉｃｓＲｅｐｏｒｔｓ，２００６，４２４（４，５）：１７５—３０８
ＣｏｍｐｌｅｘＮｅｔｗｏｒｋｓ：ＳｔｒｕｃｔｕｒｅａｎｄＤｙｎａｍｉｃｓ
Ｓ．Ｂｏｃｃａｌｅ￡ｔｊｌ，Ｖ．Ｌａ￡ｏｒａ２一，Ｙ．Ｍｏｒｅｎ０４一，Ｍ．Ｃｈａｖｅｚｆ６，Ｄ．．Ｕ．Ｈｗａｎ９１
（１．ＣＮＲ—ＩｓｔｉｔｕｔｏｄｅｉＳｉｓｔｅｍｉＣｏｍｐｌｅｓｓｉ，ＬａｒｇｏＥ．Ｆｅ珊ｉ，６５０１２５Ｆｌｏｒｅｎｃｅ，Ｉｔａｌｙ；
２．ＤｉｐａｒｔｉｍｅｎｔｏｄｉＦｉｓｉｃａｅＡｓｔｒｏｎｏｍｉａ，Ｕｎｉｖｅｒｓｉ话ｄｉＣａｔａｎｉ８，ＶｉａＳ．Ｓｏｆｉａ，６４９５１２３Ｃａｔａｎｉａ，Ｉｔａｌｙ；
３．ＩｎｓｔｉｔｕｔｏＮａｚｉｏｎａｌｅｄｉＦｉｓｉｃａＮｕｃｌｅａｒｅ，ＳｅｚｉｏｎｅｄｉＣａｔａｎｊａ，ＶｉａＳ．Ｓｏｆｉａ，６４９５１２３Ｃ８ｔａｎｉａ，Ｉｔａｌｖ；
４．ＩｎｓｔｉｔｕｔｏｄｅＢｉｏｃｏｍｐｕｔａｃｉ６ｎ
ｙ
ＦｉｓｉｃａｄｅＳｉｓｔｅｍａｓＣｏｍｐｌｅｊｏｓ，Ｕｎｉｖｅｒｓｉｄａｄｄｅｚａｒａｇｏｚａ，ｚａｒａｇｏｚａ５０００９，Ｓｐａｉｎ；
５．ＤｅｐａｒｔａｍｅｎｔｏｄｅＦｉｓｉｃａＴｅ６ｒｉｃａ，ＵｎｉｖｅｒｓｉｄａｄｄｅＺａｒａｇｏｚａ，Ｚａｒ８９０ｚａ５０００９，Ｓｐａｉｎ；
６．ＬａｂｏｒａｔｏｉｒｅｄｅＮｅｕｒｏｓｃｉｅｎｃｅｓＣｏｇｎｉｔｉｖｅｓｅｔＩｍａｇｅｒｉｅＣ６ｒ６ｂｒａｌｅ（ＬＥＮＡ）ＣＮＲＳＵＰＲ一６４０，Ｈ６ｐｉｔａｌｄｅ
ｌａＳａｌｐｅｔｒｉ电ｒｅ．４７Ｂｄ．ｄｅｌ’Ｈ６ｐｉｔａｌ，７５６５ｌＰａｒｉｓＣＥＤＥＸ１３，Ｆｒａｎｃｅ）
复杂网络：结构和动力学
方爱丽，赵继军，译
（青岛大学复杂性科学研究所，山东青岛２６６０７１）
摘要：耦合的生物化学系统、神经网络、相互作用的群居物种、互联网和万维网只是由大量高度相互连接的动态个体组成的系统的少数几个例子。获取这类系统的全局特征的首选方法是建立图模型——图中的点代表动态个体，边代表个体间的相互作用。一方面，科学家们需要处理结构问题如刻画一个复杂连线体系的拓扑结构、揭示建立在现实网络基础上的统一原理，以及完善模型从而模拟网络的增长和复制网络结构特性；另一方面，在研究复杂网络动力学时会产生许多相关问题，例如研究一个大的动态系统如何通过复杂连接的相互作用来表现集体行为的。我们回顾了近来在研究复杂网络的结构和动力学方面的主要概念以及取得的结果，总结了这些思想在许多不同学科包括从非线性科学到生物学、从统计力学到医药学以及工程学等领域的有关应用。
目录
１引言
１．１自然界的网络方法
１．２文章框架
２复杂网络的结构
２．１定义和符号
２．１．１点的度数、度分布和相关性
２．１．２最短路长、直径和介中性
２．Ｉ．３聚类
２．１．４模体
２．１．５社团结构
２．１．６图谱
２．２现实世界网络的拓扑结构
第３卷第３期方爱丽，等译：复杂网络：结构和动力学
２．２．１小世界特性
２．２．２无标度分布
２．２．３一些例子
２．３网络模型
２．３．１随机图
２．３．２广义随机图
２．３．３小世界网络
２．３．４静态无标度网络
２．３．５演化的无标度网络
２．４加权网络
２．４．１加权网络的测度
２．４．２现实世界的加权网络
２．４．３加权网络建模
２．５空间网络
２．５．１欧几里得空间的小世界行为
２．５．２欧几里得空问的无标度网络
２．５．３现实地理网络建模
３静态和动态鲁棒性
３．Ｉ网络对错误与攻击的静态耐受性
３．１．１数值分析结果
３．１．２无关联网络中的网络弹性
３．１．３关联网络中的网络弹性
３．１．４网络对于攻击的耐受性
３．２动态效应
３．２．１相继故障的建模
３．２．２通讯网络的拥阻
４传播过程
４．１传染病传播
４．１．１均匀混合假设
４．１，２无相联网络
４．１．３关联网络
４．１．４疾病波动
４．２谣言传播
５同步与集体动力学
５．１同步导论
５．２主稳定函数方法
５．３网络同步倾向
５．３．１加权网络同步：实数特征谱的耦合矩阵
５．３．２加权网络同步：具有复杂特征谱的耦合矩阵
５．４耦合振子同步
５．５混沌动力学同步
５．６常微分方程组网络中的其它集体行为
复杂系统与复杂性科学２００６年９月
６应用
６．１社会网络
６．１．１结构
６．１．２动力学Ｉ：意见形成
６．１．３动力学Ⅱ：策略博弈
６．２互联网和万维网
６．２．１互联网结构
６．２．２万维网结构
６．２．３动力学
６．３代谢、蛋白质和基因网络
６．３．１结构
６．３．２动力学
６．４大脑网络
６．４．１结构
６．４．２动力学
６．４．３开放性问题
７其他问题
７．１发现社团结构的算法
７．１．１谱图分割
７．１．２分级聚类
７．１．３Ｇｉｖａｎ和Ｎｅｗｍａｎ算法
７．１．４ＧＮ算法的变型和拓展
７．１．５基于模块化的快速方法
７．１．６基于谱分析的其它方法
７．１．７其他算法
７．２导航和搜索
７．２．１局域信息搜索
７．２．２网络的可导航性
７．３自适应及动态连接
致谢
附加证明
参考文献
１引言
１．１自然界的网络方法
我们的周围，网络无处不在。就拿我们自己来说是各种社会关系网络的基本单位；作为生物系统，我们是生化系统反应的精妙结果。网络可以是欧几里得空间的真实物体，如电力网、因特网、高速公路或地铁系统及神经网络；也可以是定义在抽象空间的实体，如朋友关系网和个体合作网。
历史上，网络的研究主要是离散数学的分支一图论的的范畴。自从１７３６年瑞士数学家欧拉（ＬｅｏｎｈａｒｄＥｕｌｅｒ）发表哥尼斯堡（Ｋｂｎｉｇｓｂｅｒｇ）桥问题（找一个经过普鲁士哥尼斯堡城的每一座桥回到起点的回路，且每座桥只走一次）的解，图论已经取得了很大的进展，并且为一系列的实际问题提供了答案，比如：单位时问内从起点到终点经过管道网络的最大流是多少；怎样能用最少种类的颜色给地图涂色以保证相邻区域的颜色
第３卷第３期方爱丽，等译：复杂网络：结构和动力学
不同；怎样给ｎ个人安排凡项工作以取得整体最大效用。除了数学方面图论的发展，网络的研究还在一些专门的领域比如社会科学取得了重大成就。社会网络分析从１９世纪２０年代早期开始发展，主要研究社会实体之间的关系，如组内成员的交流、国家之间的贸易、或者是公司之间的经济交易。
过去的１０年，复杂网络的研究在兴趣和研究方面有了新的发展，例如，对那些复杂的结构上不规则且随时间动态演化的网络，研究重点从分析小网络转向研究包含成千上亿个节点的网络系统，重新关注由动态个体组成的网络的属性。这一转变是由两篇具有开创性的文章引起来的，一篇是ｗａｔｔｓ和ｓｔｒｏｇａｔｚ于１９９８年在Ｎａｔｕｒｅ上发表的关于小世界网络的文章，另一篇是Ｂａｒａｂ矗ｓｉ和Ａｌｂｅｒｔ于１９９９年在ｓｅｉｅｎｃｅ上发表的关于无标度网络的文章。这股飓风主要由物理学界人士参与，并且日益增强的计算机计算能力为研究实际网络的大量数据的属性提供了可能。这些实际网络既包括：交通网络、电信网络、因特网、万维网、电影资料库里的演员合作网、科学引文目录里的合著，也包括生物和医药系统的网络如神经网络、基因网络、新陈代谢网和蛋白质网。
来自不同领域的关于网络的大量比较分析产生了一系列意想不到的戏剧性结果。面对的首要问题当然是结构上的问题。对复杂网络的研究是从定义新概念和测度来刻画真实网络的拓扑结构开始的。主要成果是对所研究的大多数真实网络确定了一系列共有的统一原理和统计学属性。一个有关的属性是点的度数即与其他点的直接连接数目。在实际网络中，度分布ｐ（后）被定义为随机均匀选择的点具有南度的概率，或者等价地定义为图中具有矗度的点所占的比例。ｐ（蠡）明显地偏离随机图所期望的泊松分布，许多情况下呈现出幂指数值介于２～３之间的幂律尾（无标度）分布。另外，实际网络是由点的度相关性、两个点之间相对短路径（小世界属性）、存在的大量短回路和特定模体来刻画的。
人们发现由数学上图论提供的网络模型与实际需要有很大差距，于是这些实际的发现引发了网络建模的复兴。科学家不得不开发新的模型来模拟网络的增长和再现实际观察到的拓扑结构属性。真实网络的结构是由其组成因素不断演化形成的结果，当然也就影响系统的功能。因此在这一阶段的研究，学者们期望通过理解和建模复杂网络的结构，来进一步更好地了解网络的演化机制，及其动态和功能上的表现。
事实表明耦合结构对于网络功能的鲁棒性以及网络对随机故障或有目的的攻击等外部扰动的反应有着重要影响。同时首次有研究由动态系统组成的大集合体动态特性的可能，而这些动态系统则是通过复杂拓扑相互作用的。因此网络拓扑在确定集体动态行为的涌现中起了重要作用。举例来说，涌现可以是同步或者说是对发生在复杂网络上的有关过程主要特性的管控，如流行病、信息、流言的传播。
文献中已出现了许多对读者有参考意义的复杂网络的综述性文章¨。。和书＂书。。ｗａｔｔｓ的文章是关于处理小世界网络的结构和动力学问题的先驱作品¨。；Ｓｔｒｏｇａｔｚ发表在Ｎａｔｕｒｅ有关复杂网络专刊上的文章讨论了由动态个体组成的网络¨ｏ；Ａｌｂｅｒｔ和Ｂａｒａｂｄｓ∥１、Ｄｏｒｏｇｏｖｔｓｅｖ和Ｍｅｎｄｓ¨’刊的综述着重于从统计力学的角度上研究的增长网络模型。Ｎｅｗｍａｎ的综述文章Ｈ１是这个领域的重要的记述，包含精确的参考文献目录，详尽地回顾了结构属性、度量和模型，最后一章还致力于对发生在网络上的过程的研究。在这值得一提的还有４篇参考文献，即由Ｂｏｒｎｈｏｌｄｔ和Ｓｃｈｕｓｔｅｒ编辑整理的文集¨１、Ｐａｓｔｏｒ?Ｓａｔｏｒｒａｓ等编辑的文集”。、Ｂｅｎ—Ｎａｉｍ等编辑的文集¨０。、Ｐａｔｏｒ—ｓａｔｏｒｒａｓ和Ｖｅｓｐｉｇｎａｎｉ的关于因特网的分析与建模的书籍¨。。市场上还为外行的读者提供了许多关于复杂网络的流行书¨。”。。例如看了Ｂｕｃｈａｎａｎ的文章…１就会拥有这个领域学者的观点。另外许多在特定研究领域有关网络的相关书籍已经出版。Ｂｏｌｌｏｂｄｓ¨４’”１，ｗｅｓｔ¨刮和ＨａｒａｒｙⅢ１的关于图论的书籍也值得参考。由Ｗａｓｓｅｒｍａｎ和Ｆａｕｓｔ编写的教科书¨引和由Ｓｃｏｔｔ编写的文献［１９］在社会网络分析方面为人们所熟知。参考文献［２０—２２］描述了标准图算法。
激发我们关于这个题目另外再做一个报告的原因有如下３条：
第一个原因是新的研究方向已经出现，涵盖网络结构方面的新的题目和问题。一个例子是对于加权网络兴起的研究，加权网络是指网络中的每一条边都赋予一个实数。大多数真实的复杂拓扑结构通常在连接的容量和强度上有大的异质性，这激发了对加权网络的研究。在社会系统中个体之间存在着弱连接和强连接；在神经网络中存在传送电子信号的容量不同；因特网上存在非平衡流量；这都是实际加权网络的的例子。忽略
复杂系统与复杂性科学２００６年９月
了这些相互作用的多样性，将意味着丢失很多复杂网络上的信息，而这些信息对于刻画网络是非常有用的。另一个新的题目是关于空间网络。复杂网络早期工作集中于刻画拓扑结构属性，空问方面很少得到关注，甚至被忽略。然而，拓扑结构可能被地理上的嵌入所制约，这一点也不奇怪。例如空间网络的长程连接由欧几里德距离约束，这对于网络的统计属性有重要的影响。并且因为能连接到单个点的边的数量由点的物理位置限制，所以点的度数是有限制的。这在平面网络特别明显（任两条边相交得到网络的顶点），就像城市街道，在一个十字路口仅有一小部分街道穿过。即便是在非平面空间网络，比如航线网，连接的数目是由机场的可利用空间所限制。这些事实都说明空间网络与其他复杂网络不同。除了对结构属性的充分论述，本文还包括所有这些新的内容以及它们在相应具体情况下的应用。
第二个原因是最近这个题目的主要兴趣转向研究网络的动态行为，尤其是对网络的结构如何影响其动态属性的研究。例如对复杂网络的集体同步动力学的研究，就是将拓扑结构与耦合的动态系统局部特性之间的相互影响与网络的同步联系在一起。事实上在许多相关情况下这种现象表现了一个至关重要的特征。例如有证据表明一些脑疾病是大量神经元反常、有时突然同步引起的结果，因此研究癫痫的产生、持续和传播的网络机理是当今神经系统科学的前沿课题。同样在社会学领域，较好地理解形成社会集体行为（如新的习惯、流行时尚、主流观点的突然涌现）的机理与同步现象非常相关。本文的第二章的大部分内容概述了迄今为止取得的关于复杂网络中集体行为的主要成果，回顾了已有的主要观点和概念，对现有的严格的结论也作了评价。
最后我们给出当前吸引科学界关注的一系列课题，其中包括建立寻求社团结构的可操作的算法的问题、复杂网络内搜索问题、适应网络的建模问题。
社团结构是复杂网络的一个重要属性。例如：社会网络中紧密相连的若干组点代表属于社会团体的个体；在万维网中表示关于共同标题的网页。而在细胞和基因网中社团则与某种功能性模块有关。因此，在网络内部找到社团是理解网络功能的有力的工具，也有助于识别复杂结构内部的连接层次。
另一个有关问题是在没有全局结构信息的情况下如何通过网络导航由网络中的一个点到达另一个点，或者说仅仅基于网络拓扑结构的一些局部信息如何优化搜索程序。
对本身是动态实体的那些网络来说，适应和动态连接是它们的特性。这意味着拓扑结构不是固定的、成熟的、也不是一成不变的。相反由于外部作用的驱使或者内部元素的作用或者遵循明确的预先确定的演化规则，允许它随时问演化和调节。这一进步是由于要为一些特殊案例（如基因调整网络、生态系统、金融市场）恰当建模的需要而推动的，也是由于要适当地刻画一系列科技有关问题（如移动的无线连接的个体）的出现的需要而推动的。有一些研究工作刚刚起步，尽管结果不是很完善，但是我们相信未来会有进展。
１．２论文大纲
本文组织如下：
第２章讨论网络的结构。描述从实际网络拓扑结构观察得到的一些共同的属性，以及如何度量。然后简要地回顾了这些年来提出的主要模型，侧重于随机图、小世界模型和无标度网络。最后特别强调对于加权网络和具有空间结构的网络的研究和建模。
第３章讨论对一些组员的外部干扰或者故意破坏造成故障的情况下的网络的鲁棒性，回顾了静态的和动态的方法，特别是描述了发生在相关联和非相关联网络上的渗流过程、相继故障、交通和通讯网络的拥阻现象。
第４章探讨了复杂拓扑结构的元胞自动机，分析了一系列传染病和流言扩散模型。
第５章是关于复杂网络的集体同步动力学的涌现。在这里我们回顾了使同步倾向最大化的网络拓扑结构条件下，以主稳定方程方法为代表的最重要的成果。我们进一步考虑了非线性演化的动态个体组成的网络，并且回顾了在混沌映射网络、混沌系统网络和周期性震荡网络研究方面取得的主要结果。
第６章总结了实际网络的一些应用，如因特网、万维网、社会网、描述细胞成分相互作用的网络和神经网络。这一章包含了关于这些网络的结构和动力学两方面的问题。
第３卷第３期方爱丽，等译：复杂网络：结构和动力学
最后，第７章探讨了近来在学术界引起极大兴趣的三个主题。首先讨论了将一个大的网络分成社团结构的算法，然后回顾了在寻求快速可靠的复杂网络的搜索与导航方面的最新成果，最后讨论了适应动态连接网络。２复杂网络的结构
本章的目的是简要介绍对网络特性的表征和建模的最新进展。首先介绍定义和符号、论述用于描述网络拓扑结构的基本量，进而分析观测到的实际网络的属性，并为读者提供所得模型的简要回顾。本章最后综述了在加权网络和空间网络研究方面取得的最新成果。
２．１定义和符号
图论¨４一¨是复杂网络精确数学处理的自然框架，且形式上复杂网络可以用图表示。无向（有向）图Ｇ＝（Ｎ，多）由集合Ｎ和西组成，且Ｎ≠咖，集合垂是由集合Ｎ中元素的无序（有序）对构成的集合。集合Ｎ；｛ｎ。，孔：，…，ｎ。｝中的元素是图Ｇ的节点（又称为顶点或点），集合圣ｓ｛ｆ。，ｚ。，…，ｆ。｝中的元素是图的连接（又称为边或线）。集合Ｎ和少中元素的个数分别由Ⅳ和Ｋ表示。以后文中，当必须强调图中的点和边的数量时，我们将图表示为Ｇ（Ⅳ，Ｋ）＝（Ｎ，痧），简记为Ｇ（Ⅳ，Ｋ）或Ｇ眦。
（ａ）（ｂ）（ｃ）
（ａ）无向图；（ｂ）有向图；（ｃ）加权无向图，其中点数』ｖ＝７，边数置＝１４。有向图中相邻点
用表示方向的箭头连接。加权图中，”“表示边的权重，用边的粗细来体现权重大小。
图２．１无向图、有向图及加权无向图
通常按在集合Ⅳ中的次序ｉ来提及点。无向图中每条边是由一对点ｉ和＿『来定义，表示为（ｉ，Ｊ）或ｚ。边可以说是关联点ｉ和ｊ，或者说连接这两个点；点ｉ和ｊ称作边（ｉ，Ｊ）的端点。通过边相连的两点称为邻接活邻居。有向图中，两个点的顺序很重要：ｚ。ｉ表示一条由点ｉ指向点．『的边且ｆｉｉ≠Ｚ。。通常是这样描绘图的：画圆点表示点，如果两点之间有连接就在相应的两点之问画一条线。怎样画这些圆点和线都无关紧要，重要的是哪两个点连成边，哪两个点没有。图２．１（ａ）和（ｂ）分别是无向图和有向图的例子，图中Ⅳ＝７，Ｋ＝１４。注意到图形不含有环，即两端点相同的边，也不含有多重边即两点之间不止一条边相连，因为这些都不符合上面给出的图的标准定义。含有环或多重边的图称为多重图¨５’懈３。本文重点讨论的不包括多重图，如果不特别说明，图指无向图。加权图将在２．４节详细讨论。
＾，，＾，１、
对于大小为Ⅳ的图Ｇ，边数Ｋ至少为ｏ，至多为坐上≯（这时所有点两两相邻接）。如果Ｋ《Ⅳ２则称图
上
＾ｒ，＾ｒ１、、
Ｇ是稀疏图；如果Ｋ＝ｏ（Ⅳ２）则称图Ｇ是稠密图。如果Ｋ＝《＝尘业≯则称图Ｇ川为Ⅳ阶完备图，表
Ｚ
示为Ｋ。。疋称作三角形。
满足Ｎ’∈Ｎ且空’∈中的图Ｇ’＝（Ｎ７，西’）称为图Ｇ＝（Ｎ，西）的子图。如果图Ｇ中连接集合Ｎ７中点的所有边都在图Ｇ’中，则称Ｇ７为由Ｎ’导出的子图，记为Ｇ’＝Ｇ［Ｎ’］。对于某一给定的属性来说如果一个子图在不丢失该属性的前提下不能再扩展，那么该子图就是最大子图。与后面章节相关的定义是给定点ｉ的邻居子图，记为Ｇ；。Ｇ；定义为Ｎｉ的导出子图即Ｇｉ＝Ｇ［Ｎｊ］，其中Ｎｉ为点ｉ的邻居点集合。
复杂系统与复杂性科学２００６年９月
图论的一个重要概念是图中两个不同点的可达性。实际上，即便不相邻的两个点也可以由一个到达另一个。从点ｉ到点．『的路是从ｉ开始到，的点边交替序列。序列中的边数定义为路的长度。各边相异的路称为迹（ｔｒａｉｌ），各点相异的道路称为路径（ｐａｔｈ）。两点之间长度最短的路称为最短路。环是封闭的路，至少要有３个点并且边不重复。长度为Ｊｊ｝的环通常叫做后一环记为ｃ。。ｃ，是三角形（ｃ，＝玛），Ｃ。是四边形，Ｃ，是五边形等等。如果每一对不同的点ｉ和，，都有一条路径，我们就说图是连通的，否则就称不连通的。最大连通导出子图称为组元，巨组元是阶次与Ⅳ相同的组元。
图的矩阵表示是经常用到的。图Ｇ＝（Ⅳ，妒）可由邻接矩阵Ａ完全描述。给定邻接矩阵Ａ是一个Ⅳ×Ⅳ的方阵，其元素为口＂（ｉ，．『＝１，２，…，Ⅳ），若边ｆ；ｆ存在则ｏｉｉ＝１，否则口ｉｆ＝Ｏ。邻接矩阵的对角线上的元素都是０，从而无向图的邻接矩阵是对称的。另外一种表示方法是关联矩阵曰，曰是Ⅳ×Ｋ矩阵，其元素为６∽若点ｉ连接于边２。则６诂＝ｌ，否则６诸＝０。
２．１．１点的度数、度分布和相关性
点ｉ的度数七ｉ是与该点连接的边数，用邻接矩阵Ａ定义为：
后：＝∑口ｕ（２．１）
ｉＥＮ
如果是有向图，点的度数包括两部分：从ｉ出发的连接边数＂‘＝＞’口。（记为出度），指向ｉ的连接边数＂＝
７‘
＞’ｏ“记为人度），ｉ点的总度数定义为忌；＝Ｉ｜｝ｒ＋Ｆ。一个图的点的度数列表称为度数序列。
度分布ｐ（．｜｝）定义为随机均匀选择的点具有而度的概率或者说图中具有．｜｝度的点所占的比例，根据ｐ（五）可以获得图Ｇ的最基本的拓扑特征。度分布也可以记作ｐ。，其中南取非负整数值。
对于有向网络，需要考虑两种分布，ｐ（扩）和ｐ（尼”‘）。要得到无向网络的各点的度数分布信息可以通过绘制ｐ（Ｊｊ｝）图，也可以通过计算分布的矩。ｐ（Ｊ｜｝）的乃阶矩定义为：
（１｜｝“）＝∑唧（１｜｝）（２．２）
Ａ
一阶矩（七）是图Ｇ的平均度数。二阶矩衡量连接分布的波动性，而且我们将在第３章和第４章看到，当图的大小无穷大时，（七２）发散，从根本上改变了发生在图上的动力学行为。
度分布完全决定了非关联网络的统计属性。然而我们将看到，许多真实网络是相关联的，具有而度的点与具有后’度的点相连的概率取决于后。在这种情况下，有必要引进条件概率ｐ（七’Ｉ尼），定义为从后度的点出发的一条边指向矗’度的点的概率，满足归一化条件＞ｌｐ（尼’Ｉ庇）＝１和平衡条件如（南７Ｉ南）ｐ（后）＝露’ｐ（矗Ｉ
下
尼’）ｐ（矗７）‘２耶４｜。对于无关联图，由于ｐ（七’Ｊ矗）不依赖于｜ｊ｝，由平衡条件和归一化条件得到ｐ（｜｜｝’Ｉ七）＝掣。
＼盯，虽然度相关性形式上由ｐ（矗’Ｉ｜ｊ｝）刻画，然而由于大多数实际网络来说Ⅳ的大小是有限的，所以直接计算条件概率会得到噪声很大的结果。这个问题可以通过定义点￡最近邻平均度来解决，即：
ｋ，ｉ＝奄砖＝击扣ｔ（２．３）这里将所有属于点ｉ的第一邻居集合Ｎｉ的点的度数求和。利用定义（２．３），可以计算具有詹度的点的最近邻的平均度数，记为｜ｊ｝。。（后），得到隐含的对尼的依赖关系拉５｜。事实上，这个量可以用条件概率表示为：
庇。。（矗）＝＞‘矗’ｐ（后７１愚）（２．４）
节
／Ｌ２＼
如果不存在度相关性，公式［２．４］写为：ＪｊＩ。（蠡）：号＊即知。（后）独立于．｜｝。相关联图分为两类：同类匹配图和
＼托／
非同类匹配图。如果矗。。（｜ｊ｝）是＿ｊ｝的增函数，则此关联图是同类匹配的；如果忍。。（后）是矗的减函数则此关联图是非同类匹配的旧…。换句话说，在同类匹配网络中点趋于连接和它们相关联的点，而在非同类匹配网络中度数低的点更可能与度数高的点相连。度相关性通常用作为｜｜｝的函数的后。。（后）的斜率ｙ的值来量化，或者通过
第３卷第３期方爱丽，等译：复杂网络：结构和动力学
计算边的任一顶点的度数的皮埃逊相关系数来量化＂６’２７｜。在２．２节将通过讨论实际网络的例子来展示这两类相关性。
２．１．２最短路长度、直径和介中性
最短路在网络内交通和通讯方面起着重要作用。假设需要通过因特网从一个计算机向另一个计算机传送数据包，最短路提供了一个最优的路径从而可以快速传送并且节省系统资源¨］。同样道理最短路在刻画图的内部结构方面也起着重要作用¨８’悖］。我们可将图Ｇ的所有最短路长表示成矩阵Ｄ，其元素ｄ。表示点ｉ到点，的最短路的长度。ｄ。的最大值称作图的直径，以下将用Ｄｉ口ｍ（Ｇ）表示。度量图中两个点问典型间隔由平
卜而ｕ萎；，＿。（２?５）均最短路长给出，也称作特征路长，定义为所有顶点对之间的最短路长的平均值∞’２８｜：
此定义存在一个问题就是当图中有不连通的组元时，Ｌ发散。一种可能避免无穷大就是公式（２．５）只限于对属于最大连通组中顶点对求和心８１。在许多情况下（见３．１．１节）另一种有用的方法是考虑最短路长的调和平均值心＂，定义图Ｃ的所谓的效率‘３叩１３为：肌赤磊≠，壶＠?６）
该量是网络的通行能力的一个指标，并且避免了公式（２．５）可能出现的发散结果，这是由于图中非连通顶点对÷＝ｏ，在公式（２．６）的求和中不起作用。效率Ｅ数学性质的研究见参考文献［３２］，效率Ｅ的最新应用见文。玎
献［３３—３５］，公式（２．６）的扩展见文献［３２，３６］。
两个不相邻点Ｊ和忌之间的通讯，依赖于连接＿『和而路径上的其它点。所以度量一个给定点的关联性可以通过计算经过该点的最短路的数量来得到，定义为点的介数。和点的度数、紧密性（定义为从所有点到达该点的平均距离的倒数）一样，介数是点的中心性的标准测度之一，最初应用在社会网络中量化个体的重要性‘１８’伸驯，更准确地说点ｉ的介数６ｉ有时也指负载…Ｊ９’３８’３９１，定义为：
６：：ｙ丝盟（２．７）
‘ｕ氧≠ｋ‰
这里ｎ琅是连接点．『和忌的最短路径的数量，而ｎ。（ｉ）是连接点＿『和后且经过点ｉ最短路的数量。文献［２０一２２］给出找到最短路的标准算法（如７．２节的Ｄｉｊｋｓｔｒａ算法或广度优先搜索），文献［４０，４１］给出了最近推出的计算介数的快速算法。文献［４２—４７］研究了介数的分布。文献［４２］和文献［４８—５０］分别研究了介数与介数相关性和介数与度数相关性。
介数的概念可以推广到边的介数，定义为通过该边的顶点对的最短路数量＂１｜。后者广泛应用于第５．３节和７．１．３节。
２．１．３聚类
聚类也称传递性，是朋友关系网络的典型属性，在这个网中两个人共同的朋友很可能互相认识¨８ｉ。对于一般的图Ｇ，传递性意味着存在很多三角形。可以用图的传递性Ｔ来量化，定义为传递三元组的相对数即顶点关联三元组构成三角形的比例¨’５２’５３。：
３×图中的三角形数ｒ，¨
个一
ｐ一７
１一图中顶点关联三元组数
分子上乘以３是因为每一个三角形都含有三个以其一个点为中心的顶点关联三元组，确保０≤ｒ≤１。对瓦图，丁＝１。
另一个办法是利用ｗａｔｔｓ和ｓｔｒｏｇａｔｚ在文献［２８］中提到的图的聚集系数。首次引入点ｉ的局域聚集系数ｃｉ来表示点ｉ的两个邻居＿『和ｍ有多大可能使ｎ胁＝１，ｃｉ的值可以通过对图Ｃ；（２．１节定义的点ｉ的子图）中的实际边数（记为ｑ）计数而得到。注意到Ｇｉ有时候是不连通的。局域聚集系数ｃ。定义为８ｉ与蔓掣的比
?６４?复杂系统与复杂性科学２００６年９月值，掣为Ｇ。中可能的最多边数”，２８Ｊ。
～＝（２．９）
２ｅ
‘
计算ｃ。的快速算法见文献［５４］ｏ图的聚集系数是Ｇ的所有点的ｃ。的平均值：
１
ｃ＝（ｃ）＝亩∑ｃ；（２．１０）
‘’ｌ∈“
根据定义有０≤ｃ。≤ｌ且０≤Ｇ≤ｌ。Ｃ和ｒ的区别见文献［４，３１］。有时用到Ｋ级连通的聚集系数ｃ（惫），ｃ（南）定义为所有具有露度的点的ｃ。的平均值。
近几年人们提出各种高阶聚集系数，其中具有后阶邻居的知阶聚集系数¨￡５６３；基于四阶环的内部结构‘５７３或一般阶次的环的数量¨８１的度量方法。文献［５９，６０］给出无偏度相关情况下的聚集系数定义，文献［６１］给出有向图中三元组的概念，文献［３３］给出平面图的聚类定义（见２．５节）。图Ｇ的聚类属性的另一个测度是局部效率阳０’３“，定义为：
１
Ｅｋ＝亩∑Ｅ（Ｇ；）（２．１１）
４。ｌＥ“
其中层（Ｇ？）是图Ｇ。的效率，可由公式（２．６）计算。
２．１．４模体‘
模体肘是有向图或无向图Ｇ中点的相互连接模式，出现频率比在随机图中明显要高。随机化图具有和原图形相同的点数、边数、度分布，但是边的分布是随机的。作为一种相互连接模式，Ｍ通常意味着Ｇ的一个含ｎ个顶点的连通（有向或无向）的子图。一个所有３个点的有向连通图的例子见图示２．２。
＞＞＞卜》
）．）．）ｆ＼．１）．
ｒ、丫。■圹、－、ｋｙｓ
》＞＞》
ｐ谚≯ｐ
》》》》
图２．２所有含有３个点的有向连通子图的１３类模体
模体的概念最早由Ａ１０ｎ和他的同事们提出，见文献［６２—６６］，他们研究生物和其他网络中的小儿模体。图Ｇ的有效模体的研究是基于匹配算法，数～下原图和随机化以后图中ｎ点子图Ｍ出现的次数。肘的统计显著性是用ｚ分数来描述的，定义为旧删：ｚ肝：掣盯“Ⅳ（２．１２）
其中ｎ村是Ｇ中子图肘出现的次数，（ｎ嚣以）和盯嚣。分别是在随机化图中肘出现次数的平均值和方差。
第３卷第３期方爱丽，等译：复杂网络：结构和动力学
２．１．５社团结构
历史上，社团的概念及其首次网络形式定义出现于社会科学¨“。给定图Ｇ（Ｎ，中），社团（群或粘着子图）是一个各点紧密相连（粘着）的子图Ｇ’（Ｎ’，痧７）。由于Ｇ’各点之间结构的凝聚可以用不同的方法来量化，因此对社团结构有不同的定义。
条件最强的定义要求所有社团成员对之间都相连，这就引出派系的概念。派系是至少３个点的最大完全子图，即图中点的子集满足：子集内的所有点两两相邻且再没有其他点与子集内的所有点相邻，这样的子集就构成一个派系。将条件“相邻”削弱为“可达”此定义可以扩展为：忍一派系。儿一派系是一个最大子图，其中任何两点之间的最短路长的最大值小于等于ｎ。当ｎ＝１时此定义与原定义相符，２一派系是所有点不必相邻但是必须通过至多～个中点可达的子图，３一派系要求所有点通过至多２个中间点可达，依此类推。然而，ｎ一派系的概念使得允许路径长度的增加，另一种是放松派系的强假设条件的方法是，将每个点必须连接的其他顶点数量减少。Ｋ一丛是包含ｎ个点的最大子图，其中每个点与子图中的至少ｎ一七个点相邻。
对社团结构的另一类不同定义是基于边的相对频率。这种情况下社团可以看成是若干群，群内的点连接紧密，群之间的点联系稀疏Ｍ＿６８』。例子见图２．３。这类最简单的形式定义见文献［６９，７０］。一个不是很严格的定义如下：如果Ｇ’内的度数和比与Ｇ７外其它点连接的度数和大，那么Ｃ’就是一个社团＂“。并非只有上述列出的定义方法，可能还有在某种情况下更适合的一些其它定义，见文献［１８］。
２．１．６图谱
图谱是图的邻接矩阵Ａ的特征值的集合¨“。
图Ｇ舭有Ⅳ个特征值肛ｉ（ｉ＝ｌ，２，…，Ⅳ），Ⅳ个相
应特征向量ｙ；（ｉ＝ｌ，２，…，Ⅳ）。当Ｇ是无环且无
多重边的无向图时，Ａ是实对称矩阵，因此图Ｇ有
实特征根，ｐ。≤肛：≤…≤ｐ。，对应于不同特征值
的特征向量是正交的。当Ｇ是有向图时，特征值可
能含有虚部，例如有３点的遍历图。所以特征值和
特征向量的阶和性质就更加复杂。适当时候将对
后者详细描述。
Ｐｅｒｒｏｎ—Ｆｒｏｂｅｎｉｕｓ定理说明图（可以是有向图）存在一实特征值弘Ⅳ及其对应的实的非负特社团定义为点的群，群内部连接紧密，而外部稀疏。上图中，用虚线圈表示出三个社团。本图取自文献［５１］。
图２．３社团结构图
征向量，对任意特征值ｐ，有ｌ肛ｌ≤肛。。如果图是连通的，ｐⅣ具有多重１，对所有不同于肛Ⅳ的特征值肛都有Ｉ弘Ｉ＜弘。。当点和边从图中移走时，ｐ。的值就减小。对一个连通的无向图，这意味着最大特征值是非退化的，相应的特征向量矿。中的每个元素都是非负的。所有其他特征向量中的元素同时具有正值和负值，因为它们
与矽．Ⅳ正交。同一定理说明在连通图中有后。；。＜（后）＜ｐ。＜后一，或矗幽＝（七）＝肛Ⅳ＝七一。
对大型图，定义谱密度为¨２’”。：
１兰
Ｐ（肛）＝专＞：６（肛一肛；）（２．１３）
』Ｖ互一
当Ⅳ一∞时，ｐ（肛）逼近一个连续函数。图的特征值及相应的特征向量与其重要的拓扑特征密切相关，如：图的直径，图中环的数量和图的连通属性等。
例如：因为Ｔｒ（Ａ）＝０，所以所有特征值之和为０，两两特征值之积相加等于一Ｋ，任３个特征值之积相加等于Ｇ中三角形的个数的２倍，高阶乘积相加分别与长度为４，５…的环的个数有关¨”４’７５。。此性质是基于这样一个事实：矩阵Ａ‘的第ｉ行第，列元素等于经过Ｉ｜｝步从点ｉ到达点＿『的路径的个数¨引，因此Ａ‘的迹给出了图中某点经过＿｜｝步回到自身的路径的总和。由于Ａ‘的特征值是Ａ的特征值的Ｉ｜｝次幂，Ａ‘的迹可以由Ａ的特征
ＮＨ
．
值获得，两不必进行矩阵乘法运算。由Ｔｒ（４‘）＝芝：ｐ；和（ｙ弘；）５＝ｏ可以推得上述性质。
复杂系统与复杂性科学２００６年９月这也意味着公式２．１３的谱密度ｐ（ｐ）的第１ｊ；阶矩膨。，定义为艏。＝专＞：肛：＝÷Ｔｒ（Ａ‘），等于图中的点
』’■，．』Ｖ
经过．｜｝步回到起点的所有路径数的总和除以ⅣＬ＿７２Ｊ。特征值也给出图的直径的一系列范围。例如：普通图的Ｄ沱ｍ（Ｇ）比不同特征值个数少。而在座～规则图（图中点的度数都等于尼）中，由于Ｄ；ｍ（Ｇ）≤ｉ丽￡等萤瓦赫，比较好的上限估计可以由第二大特征值肛¨得到。
１ｎ／＾，１、
从正规矩阵和拉普拉斯矩阵的谱中可以提取图的连通性质的重要信息。正规矩阵定义为Ⅳ＝Ｄ—Ａ，其
中Ｄ是对角线上元素为Ｄ。＝＞’口。＝店ｉ的对角矩阵。组合Ｌａｐｌａｃｅ矩阵／ｉ，也称为Ｋｉｒｃｈｈｏｆｆ矩阵（最早由
７‘
Ｋｉｒｃｈｈｏｆｆ提出），定义为／Ｉ＝Ｄ—Ａ。／ｌ是一个对称半正定矩阵，因为Ａ可以用关联矩阵表示为Ａ＝曰曰“”１，所以Ａ的所有特征值都是非负实数，／ｌ具有Ⅳ个实的正交特征向量。由于Ａ每行元素和都为Ｏ，所以／ｌ总有最小特征值Ａ．＝ｏ，对应特征向量ｐ，＝（１，１，…，１）。很容易证明特征值。的个数等于Ｇ的组元的数量。一般地，第二最小的特征根Ａ：是非平凡的，一系列图谱理论证明：Ａ：越大，图越难切分。
Ａ的特征值和特征向量、矩阵／土和Ⅳ已经用于描述真实网络以及模型＂２’７３’７６。７引，也用于揭示粘连子群和其他区域特征的存在，７．１．１节将详细介绍。关于谱方法在网络分析及可视化方面的作用见文献［７４］。
２．２实际网络的拓扑结构
自然和技术中的许多系统是由大量高度关联的动态个体组成的。撙］。耦合生化系统、神经网络、相互作用的群居物种、互联网和万维网仅仅是其中的几个例子。取得这类系统的全局特征的首选方法是建立图模型——图中的点代表动态个体（如大脑的神经元或社会中的个人），边代表个体间的相互作用。当然，这只是一种近似表达，因为这意味着将依赖予时间、空间、和其他许多因素的两动态个体的相互作用转化为两相应点之间是否存在边的一个简单的二进制数。不过，许多情况下，这是整个系统的简单而又信息齐全的表现。
过去的１０年，大量增长的有效数据、计算设备的优化以及强大可信的数据分析工具已经为研究现实世界的网络的拓扑属性提供了越来越好的条件，我们才可以研究各种系统内的相互作用如：通讯阳’２５’８０］、社会心８１８卜８４１和生物系统∞５娟８１。主要研究结果表明，大多数实际网络内在不同，但是具有相同的拓扑属性，如较短的特征路径、较高的聚集系数、度分布的胖尾形状、度相关性、模体和社团结构。实际网络的所有这些特征与规则网格和随机图（数学上图论的标准模型）绝然不同。这引起了人们对理解形成网络拓扑结构的演化机制、设计体现实际网络最重要特征的网络模型的极大关注。我们将在２．３节回顾各种模型。这里我们简要讨论网络的最重要属性：小世界效应、无标度分布、度相关性和聚类特征。一些实际网络的更完整描述见第６章。２．２．１小世界属性
对一些实际网络上的动态过程的研究已经表明捷径的存在。连接网络不同区域的桥可以加快远距离点之间的通讯。
在Ｄ维空间超立方体网格上，一个点要到达任意选定的点需要经过的点的平均数量随着网格的大小按ⅣⅣ４增长。相反，大多数实际网络尽管规模很大，但任两点之间有相对较短的路径。这种特征被称为“小世界属性”，在数学上用平均最短路径长Ｌ来刻画，￡由等式（２．５）定义，且与网络的大小Ⅳ呈对数关系＂’２引。这条属性是２０世纪６０年代首先由Ｍｉｌｇｒａｍ在社会网络中发现的，Ｍｉｌｇ豫ｍ做了一系列实验来估计熟人网络中一个人到达另一个人的实际步数¨Ｅ”４“。
开始实验时，Ｍｉｌｇｒａｍ要求被随机选取的住在内布拉斯加（Ｎｅｂｒａｓｋａ）的一些人将信件送给一个Ｂｏｓｔｏｎ的人，只知道此人的名字、工作和大概位置。信的当前持有者只能把信传给知道名且估计离目标人较近的人手中。Ｍｉｌｇｒａｍ跟踪了这些信件的传送路径，分析了传送者的熟人关系动力学特性。一般我们会猜想信件最终到达目的地会经过上百步，但是Ｍｉｌｇｒａｍ得到惊人的结论：到达目标人平均只需要６步。最近，Ｄｏｄｄｓ等人冲引成功地重复了Ｍｉｌｇｒａｍ的实验，不过是关于全球因特网范围内的电子邮件的传递。事实上，邮件完成传递信息任务的链接数是服从统计特征的。
第３卷第３期方爱丽，等译：复杂网络：结构和动力学
在许多其他实际网络如生物网、技术网中也发现了小世界属性”’２８’４０’５２ｏ，并且是某些网络（如随机网）的
明显的数学属性。和随机网不同的是，小世界属性在实际网络中经常伴随着聚类现象，表现为由公式（２．１０）计算得到的高的聚集系数值（见表２．１）。因此，ｗａｔｔｓ和Ｓｔｒｏｇａｔｚ的具有开创性的论文中提议将小世界网络定义为：既具有象随机网一样小的￡，又具有象规则网一样大的聚集系数ｃ的网络∽８【。基于效率公式，这样定义的网络具有高的全局效率Ｅ幽。（公式２．６），和高的局域效率Ｅｋ（公式２．１１），也就是说，这样的网络不管是在全局还是局域范围信息交换效率都很高∞０’”１。
２．２．２无标度分布
几年前ｓｃｉｅｎｃｅ杂志上研究的通常是均质网络。有相互作用的结构中的均质性意味着几乎所有的点在拓
＾ｒ，＾ｒ１、扑意义上是相当的，就像规则网和随机图。例如对随机网来说，生坐掣个可能连接中的任一个连接存在的
Ｚ
概率相同，因此度分布为二项分布，或者当图的规模无穷大时趋于泊松分布（见第２．３．１节）。因此，难怪科学家利用实际网络数据进行研究时，有理由认为度总是分布在均值周围，具有明确的二次波动平均。与期望的相反，人们发现大多数实际网络服从幂律形状的度分布ｐ（后）～Ａ＿｜｝～，指数ｙ的变化范围为２＜ｙ＜３。因此网络的平均度（后）可以定义且有一定限制，方差盯２＝（后２）一（后）２由分布的二阶矩决定，二阶矩：
一…．．
（后２）＝Ｉ
后２ｐ（后）ｄ七～后：：：（２．１４）
Ｊ＊…随积分上限发散。这样的网络称作无标度网络心’９引，因为幂律在所有标度上都具有同样性质。事实上，除了乘数因子外，幂律是唯一满足当自变量石乘以因子变化后自身能保持不变的函数八∞），是方程，（ａｘ）＝阿（菇）的唯一解。由于与相变一４。和分形印副的关系，幂律在统计物理中具有重要的地位。以后提到无标度网络，即指度分布是幂律分布的一类图。当然，这并不意味着这类图对于网络结构的其他度量属性是无标度的一…。这类网络具有高度非均匀度分布，同时有少数点与其他很多点连接，而大多数点的连接很少。
对于有限规模网络，胖尾度分布有着自然的分界旧３｜。分析实际网络时，由于样本的有限性，可能数据会出现相当强的内在噪声。因此，当系统规模小、度分布ｐ（后）是胖尾时，建议测量累积度分布Ｐ…（后）＝ｙｐ（矗’）。事实上，将原分布ｐ（七）求和，表现在尾部的统计震荡一般就会平滑。从而若ｐ（后）～后一，指数ｙ可
，未以由双对数坐标下Ｐ…（七）的斜率加上１得到，即’，＝ｌ＋ｙ。。。另一种方法是将数据按指数级分区间旧。。２．２．３例子
表２．１给出了一些已发表的网络的主要拓扑性质，这些网络属于以下３种不同种类：信息（通讯）、生物和社会系统。关于它们及其他实际网络的问题更详细的内容见第６章。
表２．１现实世界的一些信息（通讯）、生物和社会网络的基本特征
１１．１７４２２８．２６３７０９。２×１０８２．１１５７７８５７．５１６２２５．２２６５９．８１２上表中量包括：顶点数Ⅳ，特征路径长Ｌ，聚集系数ｃ，平均度（＾），度分布指数ｙ，相关性类型。除了万维网、新陈代谢网（埃希氏
菌）和邮件网络，其他所有网络都是无向的。对于有向网络，两个指数ｙ的值分别代表出度和人度分布的指数。
龇默，，２
３５５；
８８２２Ｏｌ，，Ｏ０６５ｌ８４
８８ｌｌ８８８２８ｎｎｏｏｏ叫ｏｏｏｏｗ＜＞＜ｈ＜＜＞＞＿呈ｎｎＵＵ７ｌＯ８８９儿儿７尼３１１ｌ４２４３５２２２２２２２２ｌ４
Ｍ∞叭¨昕，”∞∞ＯＯ０ＯＯ０Ｏ０Ｏ眈
５
３坨∞铂酪
孵３９４６２７８３４坶∞６５鲫２∞鼯４２３７
６３５叭２ｌ｜一删？一一删罴＝篡＝一
复杂系统与复杂性科学２００６年９月
最先考虑的信息／通讯网络是因特网的两个例子旧一￡８０ｊ。这两个网络中点表示主机，边表示它们之间的物理连接。ＡＳ２００ｌ代表２００１年４月１６日自治系统层次的因特网”引，而Ｒｏｕｔｅｒｓ表示路由器层次的因特网归８｜。Ｇｎｕｔｅｌｌａ是由ｃｌｉｐ２分布搜索法¨叫提供的点对点的网络∽９１，作为一种连接成千上万台电脑的方式越来越受欢迎，它使得局域的或者是更广区域内的用户间能共享文件（如音乐或录像）。最后，由不同网页间的超连接组成的万维网，含有多于１０８个点，是当今研究的最大的网络。与前面提到的网络不同的是，万维网是有向的，每个网页有一些人边，也有一些指向其他网页的出边。所有的这些图都是稀疏的且具有小的平均度（后）。它们都呈现小世界属性，即就有相比于网络规模来说很小的特征路径长。它们都具有大的ｃ值，都表现为幂律度分布（幂指数见表）即它们是无标度的。图２．．４画出自治系统层次的因特网在不同３年的累积度分布图形。新的点不断出现，旧点不断移除，
从这个意义上讲因特网是一个动态实体，
尽管如此，我们看到网络仍然保持着无标
度属性。然而上面所提的网络在最近邻点
之间的度相关性上有所不同。ＡＳ和
Ｇｎｕｌｅｌｌａ网络表现出不相称度相关性，即
点趋于和不相近度数的点相连，由表中ｙ的符号表示。相反，Ｒｏｕｔｅｒ网络展示了相称的度相关性，即点趋于和相近度数的点建立连接。最近在一些包括技术网络的网络应用方面，有人指出距离ｄ≥１的点之间的度度相关性的重要性¨…。这种相关性可以由距离为ｄ的相邻点的平均度（Ｋ“’）。来刻画，＜Ｋ¨’）。受到起点度数．ｊ｝的约束，是克的函数。ｄ＝１时描述的是普通的最近邻点的度相关性。图２．５ａ给出Ａｓ层次的因特网的（足Ⅷ’）。，图２．５ｂ给出
越
０
钆
不同三年的Ａｓ因特网的累积度分布，很明显的幂律分布，而且，尽管因特网是动态的，指数＇，不随时间而变化。引用图彳导到文献［２５］的允许。
图２．４Ａｓ层次因特网的累积度分布图
Ｒｏｕｔｅｒ层次的因特网的（Ｋ‘４’）。。图２．５ａ中，距离为ｄ的邻居点的平均度（Ｋ‘。’）。当ｄ＞１时服从和（Ｋ‘１’）。相同的趋势，ｄ越大，相关性越小（也可见图２．５ａ中斜率∥关于ｄ的函数图）。而在图２．５ｂ一直到ｄ＝２度相关性都是相称的，ｄ＞２开始不相称。最后，ｄ＞６时，与不相称网络比较而言，网络的度相关有相同的趋势。
＾
名
Ⅺ
Ｖ
（ａ）Ａｓ因特网、（ｂ）Ｒｏｕｔｅｒ因特网中与☆度点的距离为ｄ的最近邻点的平均度图。其中插图给出曲线斜
率与ｄ的函数依赖关系，表明：离起点的距离增加时度相关性的变化。引用该图得到文献［１０２］的允许。
图２。５与量度点的距离为ｄ的最近邻点的平均度图
第３卷第３期方爱丽，等译：复杂网络：结构和动力学
表２．１的第二部分给出两类生物网络（酵母中的蛋白质相互作用网＂钊和新陈代谢反应网旧５’”纠）的主要拓扑属性。第一类网的点是蛋白质，如果两蛋白质之间有相互物理作用（例如两氨基酸链互相粘合）那么两点之间用边相连。此网络表现为高度的异质拓扑结构，同技术网络观测到的一样，大多数蛋白质参与少数的相互作用，而少数蛋白质与其他许多蛋白质相互作用。特别地，蛋白质有五个相互作用的概率ｐ（七）可由具有指数分界的幂律分布拟合。在幽门螺旋杆菌的蛋白质相互作用网中也发现了相同的无标度现象。”…。因此，蛋白质相互作用网和基因网近几年得到了彻底的研究旧６’１０５—０８Ｊ，人们相信如上所述的研究有助于找到特效药或者完成蛋白质作用图¨０８’蛐引。新陈代谢反应网是有向网，其点是化学物质，通过它们之间的代谢反应相连旧５’１０３｜。同时，参与七次代谢反应的酶作用物的出度入度都服从相同指数的幂律分布。令人惊讶的是，这种特征是普遍的。不管从生命领域哪方面来考虑，无标度特征都是相同的旧５｜。新陈代谢网还有吸引人的地方就是高度等级性和模块性¨∞Ｊ。特别是模块性（即存在共同作用以完成某种功能的互相连接的分子集合）看来是基本的图形特征。第６．３节将继续讨论新陈代谢网、蛋白质网和基因网。在高层次的生物组织中也有高度异质网络，一个例证就是食物网。其中点代表生态系统的物种，有向边代表捕食者二被捕食者关系。现有的几个有关食物网拓扑结构的¨７＇明’１１０—１３１的统计研究没有最终下结论是否所有的食物网都可以看作无标度网络。然而，所有食物网的研究结果表明这样的网络具有小世界属性，至少是高度的异质性，至于是否是无标度，其强分界可能是由所分析的生态网很小而产生的。
表２．１最后给出３个社会网络的例子。从历史上讲，社会系统是最早从网络的视角研究的系统之一【８９’１１４｜。社会网络正式定义为一些个体或社会实体通过他们之间的某种相互关系连接在一起的网络。相互关系有不同种类，如友谊、合作、性接触或商业关系。这里我们讨论由合作论文关系定义的数学家合作网、建立在互联网电影资料库的电影演员合作网（在同一部电影中扮演角色的演员组成的网络）以及邮件交换网隅４｜。后者网络中的点表示邮件地址，有向边表示信件从一个地址传向另一个地址。尽管此网络通过通讯网（因特网）工作，人们通常认为这是社会网络，因为它反映了终端用户的不同社会关系。正如表中所见，３个网络都有幂律分布特征，小的Ｌ值，大的聚类系数。尽管在数据的收集过程中可能有不精确之处，但是许多现代网络理论是由社会人际学¨扎１９１得出来的，由于该系统为新观念和工具提供好的平台；激励了近来社会网络研究的发展。例如：检测社团结构的算法通常在社会网络中进行测试（见７．１节），这是由于这类系统天生的倾向是有各种大小的社团结构和派系。
２．３网络模型
对第２．２节实例的观察，无疑推动了新概念和模型的引进。本节，我们着重介绍网络数学建模，从动机、构建程序和重要属性方面探讨一些简单一般模型。更细致介绍见文献［２—４，７］。
２．３．１随机图
对随机图的系统研究是由Ｅｒｄ６ｓ和Ｒ６ｎｙｉ在１９５９年开始的，起初的目的是用概率论方法研究图的属性怎样随着随机连接数目的增多而变化。随机图指不同点之间连接的无序特征。Ｅｒｄ６ｓ和Ｒ６ｎｙｉ在第一篇论文中提出了一个能产生了Ⅳ个点Ｋ条边的随机图模型，我们称之为ＥＲ随机图，记为Ｇ恐。从Ⅳ个不连接的点开始，通过连接随机选择的顶点对（禁止多重连接），直到边数为Ｋ，就形成了ＥＲ随机图…“。我们强调所获得的图是许多可能结果中的一个，是所有可能的连接组合之一。对Ｇ恐的完整刻画需要描述所有可能实现的统计总体，即用全体邻接矩阵表示…“。另一ＥＲ随机图模型是由每对顶点以概率Ｏ＜ｐ＜１连接形成，此程序定义了一个不同的集合，记为Ｇ：：，包含了具有不饲边数的图，五条边的图出现的概率为ｐ‘（１一ｐ）州肚¨儿“［１４，１１５，１１７｜。这两个模型在统计力学的正则系综和巨正则系综上非常相似‘１１８｜，当Ⅳ一∞时
，＇矿
是一致的¨６｜。值得注意的是对固定的（１ｊ｝）令Ⅳ＿＋∞取极限，在第一个模型中对应着等不变，，在第二个模型
』Ｖ
中对应着ｐ（Ⅳ一１）不变。尽管看起来第一个模型更实用，但是第二个模型用来进行解析运算更简单些。
ＥＲ随机图是所有图模型中研究得最好的，尽管他们没有再现２．２节讨论的实际网络的大部分属性。ＥＲ
复杂系统与复杂性科学２００６年９月
随机图的结构属性随着ｐ而变化，特别是在临界概率ｐ。＝专出现很大的变化，相应的临界平均度为（南）。：１。Ｅｒｄ６ｓ和Ｒ６ｎｙｉ证明了㈨１６］：
（１）如果｜ｐ＜ｐ，，当Ⅳ一∞肘，几乎可以肯定（概率接近１）图中没有大于Ｄ（１ｎⅣ）的组元，并且任何组元中不能含有多于一个环。
（２）如果ｐ＝ｐ。，几乎可以肯定最大组元大小为０（Ⅳ２／３）。
（３）如果ｐ＞ｐ。，图中有一个大小为Ｄ（Ⅳ）且含有Ｄ（Ⅳ）个环的组元，除此之外没有任何其他组元具有多于０（１ｎⅣ）个点和多于１个环。
在ｐ。处的变化具有二阶相变的典型特征，特别是如果把最大组元的大小看成有序参数，那么这种相变同平均场渗流相变属于广义上的同一类。Ｅｒｄ６ｓ和Ｒ６ｎｙｉ研究了随机图的最大和最小度¨”３，后来由Ｂ０１ｌｏｂ６ｓ推导出全部度分布ｎ１９３。点ｉ上连有矗＝七ｉ条边的概率服从二项分布ｐ（．｜｝；＝后）＝ｃ：一。ｐ‘（１一ｐ）肛卜‘，其中ｐ‘是连有后条边的概率，（１一ｐ）肛卜‘是其余（Ⅳ一ｌ—Ｉ｜｝）条边不连的概率，ｃ：一。表示选择后条边的端点的不同方法。由于随机图中所有点统计上是等价的，因此都有相同的分布，且随机均匀选择的点具有．ｊｉ度的概率有相同形式ｐ（五；＝．｜｝）。对于大的Ⅳ和固定的（南），度分布近似于泊松分布ｐ（１｜｝）＝型半，因此有时称ＥＲ随机图为泊松随机图。由于边与点的连接与他们的度数无关，所以根据定义ＥＲ随机图是不相关图。因此ｐ（而’Ｉ矗）和后。。（Ｊ｝）与七无关。
关于连通属性，当ｐ≥警时，集合Ｇ纛中几乎所有图是完全连通的…５ｌ，直径在ｄｉ口巩＝ｉ等斋＝妄％
的一个小范围内变化¨４?１２０］。平均最短路长Ｌ与直径一样是Ⅳ的函数，Ｌ一器。ＧＥＲ图的聚集系数
１＾ｒ５．１４，２８，５３１
等于ｃ：ｐ：粤，由于ｐ是图中任意两点之间相连的概率，所以点的邻居中将有趔掣条边具有庇度，
其最大可能边数为丛鱼÷旦Ⅲ１。因此随机图的ｃ随系统的无限增大而消失。
加）：』笔糕群毗Ｉ＜２厕矿可（２．１６）对大的Ⅳ和ｐ＞ｐ。，ＥＲ随机图的谱密度收敛于分布心’７引：
ｐ（ｐ）＝｛２仃Ⅳｐ（１一ｐ）ＶＪｐＩ、。。“，、１，７
【
ｏｏｔｈｅｒｗｉｓｅ
这同ｗ唔ｎｅｒ半圆律对称不相关随机矩阵的预测结果一致＂８｜。最大特征值肛。孤立于大多数谱，且随着网络规模增大而增加。对ｐ＜ｐ。，谱密度偏离半圆律，奇数阶矩幔川等于Ｏ，这表明返回起始点的唯一方法是每条边通过偶数次。
２．３．２一般随机图
为了更好地表达实际网络，特别是其非泊松分布的简单属性，ＥＲ模型可以通过不同的方式扩展。文献中多次探讨了具有任意度分布的随机图。
由Ｂｅｎｄｅｒ和Ｃａｎ“ｅｌｄｍｌ３引入的配置模型可根据度序列建立图‘１２２’１２３｜。度序列是Ⅳ个整数列Ｄ＝｛后，，七：，…，后。｝，且＞Ｉｊｃｉ＝２Ｋ，其中Ｋ是图中的边数。在配置模型中，Ｄ满足当Ⅳ很大时，具有七度的点所占的比例趋于理想分布ｐ（南）。模型以等概率考察了所有含有Ⅳ个点且度序列为Ｄ的图的集合（记为Ｇ怨）。给于每个点ｉ配置＿ｌ｝。条半边，并以均匀概率随机将两个半边组对成边，这就是Ⅳ个点、度序列为Ｄ的随机配置。这个程序以相等的概率产生与序列Ｄ相符的任意图№＇１２２｜。事实上，因为点ｉ的南。条不同半边有庇ｉ！种的排列数，所以每个配置图的取得有ｎ（｜ｊ｝ｉ！）种不同方法。注意到Ｇ恐可以看作Ｇ怨的特例。另外，能产生多图、可能含有
第３卷第３期方爱丽，等译：复杂网络：结构和动力学
环的另一种不同方法见文献［１２２，１２３］。
配置模型的简单性使得它成为很好的分析方法。Ｍｏｌｌｙ和Ｒｅｅｄ证明了：当
Ｑ＝ｙ矗（后一２）ｐ（七）＞ｏ（２．１７）
乍且图中最大度七…不太大时，随机图中肯定会以ｐ（后）的概率出现巨组元。相反，当Ｑ＜０且．｜｝。。。不太大时最大巨组元的大小为Ｄ（．｜｝：。；ｌｎⅣ）¨２２｜。我们将在３．１２节探讨上述推导，在２．３．４节探讨当ｐ（后）为幂律分布时的应用。ＥＲ随机图，公式（２．１７）产生临界平均度（．｜｝），＝１，这将在２．３．１节讨论。同样作者在文献［１２３］中研究了巨组元的大小和当删掉这样巨组元后形成的图的结构。
Ｎｅｗｍａｎ等提出一个略微不同的方法来产生具有给定度分布的图，其中点的度是服从独立同分布ｐ（七）的随机整数。用这种方法，考虑的不只是一个度序列，而是度序列的集合，并且集合的统计属性包括组元大小及距离给定点为ｍ的点的数目，可以利用概率生成函数这个有力的工具来计算Ｈ，１２４｜。Ｎｅｗｍａｎ等发现一个平均最短路的近似公式，即
当Ⅳ《＝ｉ，＝２《彳ｌ时，
其中＝。是相距ｍ的邻居点数的平均数。在特殊情况ＥＲ随机图中，这个公式化简为２．３．１节的表达式，其中ｚ。＝（矗），彳。＝（．｜｝）２。最近，ｃｈｕｎｇ和Ｌｕ提出一个给定期望度序列的随机图模型，严格证明了￡与等同阶，其中ａ等于度的平方和的加权平均ｕ２５｜。
配置模型的聚集系数Ⅲ’幢ｑ为：ｃ＝等［警】２＝等［（南）２＋等手】２ｃ２．ｔ９，即ＥＲ随机图的聚集系数值乘以另外一个因子，这个因子可以特别大，因为它的首项是—羔的４次方，所以当Ⅳ一∞时，ｃ逐渐消失，尽管在实际观察中高度倾斜的度分布和图大小有限时它不能被忽略（见２．３．４节）。在文献［６，５９］中简单探讨了随机图的一般属性，包括其聚集属性。
２．３．３小世界网络
ｗａｔｔｓ和ｓｔｒｏｇａｔｚ（ｗｓ）模型是构建图的一种方法，记为Ｇ：★，同时具有小世界属性和高的聚集系数口８｜。模型的建立是以概率ｐ将边重连得到，开始于Ⅳ个点的环，其中每个点对称地与他的２ｍ个近邻相连，共有Ｋ＝ｍⅣ条边，然后，对每个点的每条连接于顺时针方向邻居的边按照概率ｐ与随机选择的点重连，保持不变的概率为１一ｐ。注意到，ｐ＝０时得到规则网，ｐ＝１时得到每个点的最小度后砌＝ｍ的随机图。对于介于０和ｌ之间的＿ｐ值，以上程序产生的图具有小世界属性和非平凡聚集系数。另外文献［１２６—１２８］提出了基于增加边而不重连的构建小世界网络的程序。
ｗｓ模型激发了学者试图理解作为重连概率ｐ和网络大小Ｊ７＼，的函数的网络属性＂３’１２８“圳。文献［２８］中，小世界属性表现为当ｐ略大于０时，￡（ｐ）立刻下降。这是由于边的重连产生了连接远距离点的长程连接（捷径）。重连对的ｆ影响是高度非线性的，不仅影响最近邻结构，而且与其它邻居也可建立新的最短路径。相反，一条边从聚类中的点连向聚类以外的点对Ｃ至多有一个线性的影响，即从线性到对数的转变￡（ｐ）较Ｃ（ｐ）快得多。这导致了出现一小的ｐ值（但非Ｏ）使得网络中同时具有短的路径和高的聚集系数。
Ｌ（ｐ）的变化很快激发人们做了大量的数值和解析工作口３＇１２８’１圳，目的是检查是否在确定的ｐ值时出现小世界现象，或者在ｐ＝０和有限』ｖ时是否有交叉现象，结果说明后者是对的。让我们看一下Ｂａｒｒａｔ和ｗｅｉｇｔ∞川以及Ｎｅｗｍａｎ和Ｗａｔｔ［１２引的论点。假设ｐ保持不变，我们观察￡（Ⅳ，ｐ）的变化。对小的系统，平均最短路数小于１，￡（Ⅳ，ｐ）随系统大小线性变化。然而，对较大的Ｊ７、ｒ，平均最短路数变大（大于１）并且三（Ⅳ，ｐ）随
ｈ—ｈ
复杂系统与复杂性科学２００６年９月
ｌｏｇ（Ⅳ）变化。与传统统计物理中的相关长行为相似，在某些中间系统Ⅳ＝￡时，出现我们期望的转变三一ｐ一。另外，在转折点附近，Ｌ（Ⅳ，ｐ）服从关系＂３’１２８１：
￡（Ⅳ，ｐ）～ｐ一０ＩⅣｐ７）（２．２０）其中／（ｚ）是服从：当戈《１时以并）一戈；当戈》１时，八菇）～１ｎ戈的通用比例函数。现在假设丁＜１，ａ＜ｒ＜１，由方程（２．２０）得出：
当Ⅳ卜∥“》１时，有Ｌ（Ⅳ，Ｊ７＼，＿１几）一Ⅳ∥？厂（Ⅳ１＿∥“）～Ⅳ７儿ｌｎ（Ⅳ１－∥４）（２．２１）另一方面，平均重连数为ｍⅣ卜∥“，随着Ⅳ的增大逐渐消失。因此，Ｂａｒｒａｔ和ｗｅｉｇｔ导出ｒ≥１并且数值模拟也证实了这一点。Ｎｅｗｍａｎ和Ｗａｔｔｓ利用重整化群方法分析证实了此结果，并证明实际丁＝１［１２引。总起来讲，当最短路的密度趋于０，同时特征长度随着ｐ。发散时，模型经历一个连续的相变过程。确切的比例函数八菇）表达式见文献［１２９，１３１］。
Ｂａｒｒａｔ和ｗｅ唔ｔ得到一个Ｃ（ｐ）的简单公式，与ｗＳ模型的数值模拟吻合得很好¨３｜。公式是基于当ｐ＝０时，ｃ（ｏ）＝舌警∑＿六。由于边以１一ｐ的概率不重连，在ｐ＝ｏ时已连接的两个点将以（１一ｐ）３的概率保持二ｔ二ｍ—ｌＪ
连接，因此得到：ｃ（ｐ）～ｏ（ｐ）＝主黼（１一ｐ）３（２?２２）
其中０（ｐ）被重新定义为邻居点之间的平均边数与所有可能的平均边数之比。
对于度分布，当ｐ＝０时，为以２ｍ为中心的６函数，ｐ＝１时类似于ＥＲ网络。对于０和１之间的值，度分布由文献［５３］给出：对于Ｊ｜｝≥ｍ有ｐ（蠡）＝薹ｃ：Ｉｌ（１一ｐ）＿一‘丽芝三｝二－两ｅｌｍ，对于南＜ｍ，ｐ（Ｊｉ｝）＝ｏ。
Ｆａｒｋａｓ等数值模拟研究了Ｓｗ模型的谱特征，结果表明当ｐ增大时，分布逐渐趋于随机图分布¨２｜，Ｍｏｎａｓｓｏｎ从解析和数值两个方面研究了拉普拉斯算子的谱特征¨２引。
２．３．４静态无标度网络
大量的关于实际网络的拓扑属性的研究激发人们构建服从幂律分布的图。具有幂律分布的图可以由第２．３．２节讨论的方法，作为一个具有给定分布的随机图的例子而得到。我们定义此类图为静态无标度图，以区别于将在第２．３．５节讨论的演化图模型。
Ａｉｅｌｌｏ等研究了仅含有两个参数ａ和ｙ的模型，模型设计所有具有五度的点的数目为Ⅳ（矗）＝ｅ“矗叫¨３２１。由于一旦ａ和７给定，所有点数Ⅳ和边数Ｋ就固定不变了，所以此模型记为Ｇ…。注意到当南＝１时晓是点数的对数值，而ｅ“７是图中的最大度。Ａｉｅｌｌｏ等的研究表明Ｍｏｌｌｏｙ和Ｒｅｅｄ准则可预测当ｙ＜ｙ。＝３．４７８７５…时Ｇ。含有一个巨组元；并且证明第二大组元的大小在２＜ｙ＜Ａ。时为０（１０９Ⅳ），在ｌ＜７＜２时，为０（１）；当０＜７＜１时，图几乎是全连通的。
利用公式（２．１９），Ｎｅｗｍａｎ计算了幂律分布的聚集系数，发现：ｃ～Ⅳ。Ｐ７Ⅳｈ。１’。这样当ｙ＞÷时，ｃ趋于ｏ；当ｙ＜÷时，由于与某点共邻的两点之间平均来说会有多于１条边，所以ｃ随系统的大小增大而增大”３。
ｃｈｕｎｇ和Ｌｕ研究了具有幂律分布的随机图的平均距离，证明了若７＞３则￡与ｌｏｇⅣ同阶；若２＜ｙ＜３，则Ｌ与０（１０９ｌｏｇⅣ）同阶，这时直径与Ｄ（１０９Ⅳ）同阶‘１２５１。Ｃｏｈｅｎ和Ｈａｖｌｉｎ得到同样的结论…引。最近，Ｃｈｕｎｇ等指出随机幂律图的邻接矩阵的谱服从幂律分布，其标准化拉普拉斯矩阵的特征向量服从半圆律¨３４１。
在点具有某些内在属性的假设基础上，物理界人士提出其他一些构建无标度网络的方法。Ｇｏｈ等提出模型¨２。：每个点ｉ具有权重（或适应度）ｔ１７。＝ｉ～，其中ｉ＝１，２，…，Ⅳ是点序列，ａ是区间［０，１）内的可调参数。两个点ｉ和点歹分别以概率当和｛｝选取，如果两点之间没有边，则将两点连接。此程序重复下去直到系
艺埘ｆ艺１‘’‘
第３卷第３期方爱丽，等译：复杂网络：结构和动力学
统中生成ｍⅣ条边，所以（｜ｊ｝）＝２ｍ。当理＝ｏ时得到ＥＲ随机图。当ａ≠０时，得到的图度分布为幂律分布ｐ（７）～＿ｊ｝一，幂指数ｙ＝１＋二。这样，通过改变理在［Ｏ，１）内的取值，可得到指数７（２，∞）范围内的值。对２＜ｙ＜３范围内的任意ｙ，介数分布服从指数为６＝２．２的幂律分布㈤’４“。
Ｃａｌｄａｒｅｌｌｉ等研究了一个类似的适应度模型¨”１。模型开始于Ⅳ个孤立的点，每个点ｉ具有适应度叩。，叼ｉ是一个服从分布ｐ（＇７）的实数。每对点ｉ和点，之间按照概率八７７；，叼ｉ）连边以叼；，＇７，）是对称函数。对不同的适应度分布和连接原则，此模型产生了幂律分布ｐ（局），当对于任意ｉ，，如果以’７ｉ，＇７ｉ）＝ｐ，则得到ＥＲ随机图。最近，Ｍａｓｕｄａ等研究阀值图模型，是前面模型的子类，特别适用于解析处理。模型中两点之间的连接是由这两点的适应度之和是否超过一个阀值９来确定，即若田ｉ＋仇≥ｐ则八田ｉ，叩ｉ）＝ｌ，否则以＿，７；，叼ｆ）＝０¨３６１。
最后提一下梯度网络，即由分布在点上的区域梯度导出有向图¨”。１３引。在最简单模型中，Ｔｏｒｏｃｚｋａｉ和Ｂａｓｓｌｅｒ考虑了一个给定的基网ｓ和与点ｉ相关联的非退化量＾ｉ，＾。用以刻画点ｉ的潜力。然后，从每个点出发指向他的邻居节点中潜力最大的点的有向边的集合就构成了梯度网络¨”Ｊ。可以看到梯度网络仅仅由树构成。另外，如果基网Ｓ是无标度的，＾。是独立同分布的随机变量，得到的梯度网络是无标度的且具有相同指数。更有趣的是，如果Ｊｓ是随机图（＾ｉ是独立同分布的随机变量），得到的梯度网络是无标度的，且入度分布ｐ（矿）是指数ｙ讯＝１的递减的幂律分布ｎ３７’１３引。
２．３．５演化的无标度网络?
在网络生长过程对网络结构属性不重要的情况下，静态的无标度网络是不错的模型。相反，实际网络的许多例子说明结构的改变是由系统的动态演化决定的。这里我们探讨一系列模型，主要目的是再现发生在实际网络中的生长过程。原因是通过模拟生成网络的动力学机制，我们能够再现今天我们所看到的系统的结构属性。我们主要讨论由Ｂａｒａｂａｓｉ和Ａｌｂｅｒｔ于１９９９年提出的网络生长模型以及各种变形。
Ｂａｒａｂａｓｉ和Ａｌｂｅｒｔ（ＢＡ）模型是由构建万维网中得到灵感的生长网络模型，包含两个基本因素：生长和择优连接∽３｜。基本思想是：在万维网中，度数高的点得到新连接的概率比度数低的点高。更确切地讲，有向网络ＧＺ。是这样构成的：起始于ｍ。各孤立的点，每一时间步￡＝１，２，…，Ⅳ一ｍ。，网络中引入一个具有ｍ≤ｍ。条边的新点．『。点－『与已有的点ｉ连接的概率与点ｉ的实际度数成线性比例：
Ｈ２轰㈦２３，
广＋‘，儿’
由于每个新点有ｍ条边，则ｔ时刻网络中将有Ｊ７、，＝ｍ。＋ｆ个点和Ｋ＝ｍｆ条边，在大￡值情况下，相应的平均度为（尼）＝２ｍ。ＢＡ模型和１９７６年Ｐｒｉｃｅ提出的模型¨４叫有许多共性，Ｐｒｉｃｅ的模型用于解释６０年代在引文网络中发现的幂律方面的问题（包括出度和入度分布）¨４１｜。在Ｐｒｉｃｅ模型中，新发表的论文引用以前的论文的概率与忌。＋１成比例，其中矗。。是这篇论文已经被引用的次数。从网络增长方面看，Ｐｒｉｃｅ模型是ｓｉｍｏｎ在１９５５年提出的模型的发展，Ｓｉｍｏｎ模型解释了大量实际数据所表现出来的幂律分布例如：一篇散文中单词出现次数的分布或城市人口的分布¨４２ｏ（Ｓｉｍｏｎ模型在生长的万维网中的应用见［１４３］）。关于Ｐｒｉｃｅ模型的详细讨论见Ｎｅｗｍａｎ的综述Ｈ。。这里仅简单提及与ＢＡ模型的两大主要区别：它是有向图，新点添加的边数不是固定的数目。
ＢＡ模型已经利用平均场近似∽３’¨４ｌ、或更精确地说利用率方程¨４５１和主方程¨４６１方法得到解，当￡一∞
时，得到度分布ｐ（Ｊｊ２）～后一，指数ｙ＝３。在不变选择概率ｌＩ＝—＿＿ｊ的增长网络情况下得到度分布
；０ｍｏ十‘一１
＿ｐ（矗）＝二ｅ““。这意味着择优连接是ＢＡ模型的重要因素。
Ｋｒａｐｉｖｓｋｙ和Ｒｅｄｎｅｒ考虑了有向的ＢＡ模型。他们研究了点ｉ的年龄ｏ（定义为点ｉ以后的点与其连接的数目）和它的度数的关系，以及邻近点度数的相关性¨４７｜，发现年龄为口具有局度的点的数目Ⅳ。（七）等于：
复杂系统与复杂性科学２００６年９月
几（忍）２√１一号（１一√ｌ一号）（２?２４）这样，固定年龄的点的度分布随度数呈指数衰减，特征度√１一号当口一ｏ。时发散。他们还说明邻居节点的度具有相关性，因此相同度数的点更可能连接¨４“，这与标准的ＢＡ模型中没有度度相关性形成鲜明的对比。另一种在ＢＡ无标度网络（或一般无向无关联网络）中产生度相关性的方法见文献［１４８］，是基于以下迭代算法：每一时步，随机选择网络的两条边，４个端点根据其度数排序。然后，以概率ｐ将一条边连接两个度数较小的端点，另一条边连接度数较大的端点；以概率ｌ—ｐ将便随机重连。当一条或两条边都已存在于网络中时，停止这一步。重复上述重连步骤，会出现一个不改变原有度分布的相称匹配网络。改变概率ｐ，可以构建不同度分布的相称匹配网络。
数变量有一个双对数修正，Ｌ～蒜‘１４９。。聚集系数随系统增大而减小，ｃ～Ⅳ加７５。这个衰减的速度比在对于同样大小的Ⅳ和Ｋ，ＢＡ模型的平均路径比ＥＲ随机图的短，随着Ⅳ呈对数增长拉３。解析结果预言对随机图中观察到的ｃ～Ⅳ。要慢，但是仍然与小世界模型不同，在小世界模型中，ｃ是一个与Ⅳ无关的常数。
ＢＡ模型的图谱是三角形的，与ＥＲ随机图的圆形分布不同。在中心区域，ｐ（ｐ）指数递减，而在尾部呈幂律衰减＂２’７３｜。对于大的Ⅳ，最大特征值肛Ⅳ随系统大小变化为ⅣⅣ４，相应的特征向量强烈依附于度数最大的点‘７引。
ＢＡ模型得到出乎意料的关注，除了本身的解析和数值研究以外，许多作者提出修正和一般化模型，使得更能表示真实世界的网络∞１。各种一般化模型，比如具有非线性择优连接模型、动态边重连模型、适应度模型以及分级和确定增长模型等都可以在文献中找到。这些模型产生了更具弹性的７的值，而在最初的ＢＡ模型中严格有７＝３。另外，一些修正模型考虑了增强聚集性，而这是ＢＡ模型所缺乏的。这里我们讨论几个这样的模型。
Ｄｏｒｏｇｏｖｔｓｅｖ．Ｍｅｎｄｅｓ．ｓａｍｕｋｈｉｎ（ＤＭｓ）模型考虑了线性择优连接形式为：
兀：—生坐Ｌ（２．２５）
斟ｙ（孟。＋后。）、
其中一ｍ＜‰＜∞【１４…。这是一个比式（２．２３）更一般的形式，因为常数座。表示点的初始优势。根据此连接概率得到指数为７＝３＋竺的幂律度分布。因此，当初始优势后。从一ｍ增长到无穷大时，ｙ从２增长到无穷大。当ｋ＝０时，就得到ＢＡ模型‘４７’Ｈ引。
Ｋｒａｐｉｖｓｋｙ等研究了非线性连接概率模型，形式为：
Ⅱ２蔷㈦２６，
ｉ＿Ｉ７托ｆ
证明了线性是产生幂律分布的必要条件。事实上，如果ｄ＜１，根据规则（２．２６）将产生拉长的指数度分布；而当ｄ＞ｌ，一个点将与其他所有点相连ｎ４５’１４７｜。
文献［１５０］提出加速增长模型，其中每一时步增加的新边ｍ随网络大小按照ｍ～胪（ｚ）增加。
文献［１５ｌ，１５２］考虑了波动的择优连接规则，Ｇａｒｄｅｎｅｓ和Ｍｏｒｅｎｏ通过将择优连接规则仅应用于邻居中新加入的点，研究了择优连接规则的全局特征在ＢＡ模型中重要性程度¨”。。
ＢＡ模型中，网络形成后不允许变化。然而，实际网络如ｗｗｗ或者社会网络中，连接可以被增加或删除。Ａ１ｂｅｒｔ和Ｂａｒａｂａｓｉ（ＡＢ）基于以下３个规则对他们的初始模型提出了一般化模型¨５４１。每一时步，以概率ｐ，选择一个已有的点，从该点添加ｍ条边与择优选择的ｍ个点相连；然后以概率ｇ，重连ｍ条任选边；最后以概率１一ｐ—ｑ，添加一个新点到网络并择优连接到ｍ个已有的点上。模型给出一种体制生成ｐ（露）幂律分布，幂指
第３卷第３期方爱丽，等泽：复杂网络：结构和动力学
数由ｐ和ｇ的值决定。
Ｄｏｒｏｇｏｖｔｓｅｖ和Ｍｅｎｄｅｓ‘”引，Ｔａｄｉｃ‘１５６ｔ”引，Ｋｒａｐｉｖｓｋｙ等‘”８１以及其他作者们‘”９－１６２｜，研究了类似的模型，其中边可以出现或消失或移动，或者边加入后在网络中运动。根据参数的不同，这些模型表现为幂律或者指数度分布。
实际网络中，新的网页能得到比旧网页更多的连接，最近的有趣的文章比旧的更容易被引用，从这些例子可以概括出：相对年轻的点由于他们内在的属性可以吸引许多连接。Ｂｉａｎｃｏｎｉ—Ｂａｒａｂ丘ｓｉ（ＢＢ）模型将点的
内在适应度添加到原始ＢＡ模型规则中。ＢＢ模型基于以下连接概率¨６３，Ｍ引：
丌：堕（２．２７）
埘∑＇７，也
ｉ＿’７。ｌ｜｜Ｋ’
这里田。是点ｉ的适应度，服从给定分布ｐ（田）。特殊情况，当ｐ（田）为常数，研；在区间［０，１］内时，得到ｐ（｜ｊ｝）一
Ｌ一２２６
音两和度相关性后。。“而１（ｐ＞ｏ）。Ｂｉａｎｃ。ｎｉ和Ｂａｒａｂａｓｉ还指出演化网络和均衡玻色气体之间有趣的联系，这时适应度叩ｉ由占。＝一卢一１１０９刀。代替，卢代表温度的倒数Ⅲ４３。
Ｒａｖａｓｚ．Ｂａｒａｂｄｓｉ（ＲＢ）模型旨在再现一些实际网络中观察到的等级组织ｎ６５１。模型结合了无标度属性和高聚类性，在不同标度上重复同样的构造规则，将在６．２节关于互联网的建模中讨论ＲＢ模型的细节和属性。文献［１０３，１６６—１６８］讨论了等级和确定性的增长网络模型。
文献还考虑了ＢＡ模型中缺少的聚类属性的加强，最简单的解决方案是将三角增长协议¨２６１嵌入ＢＡ模型［１６９—１７１］。Ｈｏｌｍｅ—Ｋｉｍ（ＨＫ）模型和ＢＡ模型一样，每次增加一个新点和ｍ条边，或者将他们与先前连接的点的邻居相连，或者遵循择优连接的原则。ＨＫ模型产生了无标度分布，当ｍ＝３时，聚集系数可以变化至Ｏ．５［１６９］。
Ｊｉｎ．Ｇｉｒｖａｎ．Ｎｅｗｍａｎ模型¨＂１是受社会网络动力学的启发基于３条简单的机制产生了一个高聚集系数的网络。３条机制为：
（１）拥有共同朋友的两个个体相遇的可能性大。
（２）极少相遇的个体之间的关系随时间推移逐渐减弱。
（３）个体拥有友谊的容量有限。
点的惰化程序也增加聚类¨７２，１７３１。Ｋｌｅｍｍ—Ｅｇｕｉｌｕｚ（ＫＥ）模型也称为结构无标度模型，描述了在点的有限记忆基础上拥有向边网络的增长动力学¨７川。网络中的每个点可分为两个状态：活动的和非活动的。模型开始于具有ｍ个活动的点的完全图，在每一时步，增加具有ｍ条出边的新点．『，ｍ个活动的点中的每一个点从点，获得一个人边，新点，就成为活动的点，原来ｍ个活动的点中的某个点成为不活动的点。点ｉ为不活动的点的概率为：
ｒ）２忐暖士）１（２－２８）其中豇：是点ｉ的入度，口是一个正的常数，上式是对当前所有活动点的集合Ⅳ。。求和。此程序重复迭代，直到达到所要的网络规模。该模型产生了无标度网络（ｙ＝２＋兰）和与ＢＡ模型相比大的聚集系数，如当口＝ｍ时，ｃ＝导。然而，由于特征路径长度与网络大小成比例即ｚ～Ⅳ¨７引，网络并没有呈现小世界特征。增加边的重连可能复原小世界属性¨７“。值得注意的是，上述过程的结果强烈依赖于增加点和使点成为不活动点的顺序㈣３。
另一类模型是由蛋白质相互作用启发的演化网络。Ｓ０１６一Ｐａｓｔｏｒ—Ｓａｔｏｒｒａｓ—Ｓｍｉｔｈ—Ｋｅｐｌｅｒ（ＳＰＳＫ）模型基于以下３条机理‘＂５’：
（１）复制：将任意选择的一个点及其连接复制。