复杂网络简介

小世界效应对于传播动力学行为的影响小世界效应对于传播动力学行为的影响.Moore 等发现,少量的长程边也可以明显增加网络中 疾病易于传染的性质57.如果把疾病得以传播开去的传染率下限（称为传播阈值）和传播时 间特性（感染者数量和传播持续时间之间的关系）视作网络传播动力学中最重要的可观测 量,则相比规则网络,小世界网络的传播阈值小,传播速度快.另外,很早人们就观察到在大规模 的种群中,疾病的流行常常具有某种周期的特性58,59,Kuperman 等60最早讨论了小世界网络 中的疾病传播的周期振荡,他们发现,当长程边数目慢慢增大时,感染个体数量的时间序列将 逐步从在一个不动点上下波动变成明显的周期振荡.熊等通过在小世界网络的 SIR 模型中引 入潜伏期,在不同参数设置下,分别得到短时和长时的振荡行为61.类似地,Verdasca 等从儿童 传染病麻疹和百日咳的致病机理出发,系统讨论了带有潜伏期的 SIR 模型（SEIR 模型）在小 世界网络上的传播行为,也发现了明显的周期振荡62. 汪小帆, 李翔, 陈关荣, 复杂网络理论及其应用, 清华大学出版社, 2006 S. P. Borgatti, A. J. Mehra, D. J. Brass, G. Labianca, Network Analys is in the Social Sciences, Science 323 (2009) 892-895. 感受：学海无涯，还有很多知识都还未掌握。 Barabasi A L;Albert R Emergence of scaling in random networks 1999 Watts, D.J. and Strogatz, S.H. (1998) Collective Dynamics of “Small-World” Networks. Nature, 393, 440-442. 什么是复杂网络？ 对普通人而言，在媒体上看到复杂网络，首先想到的是互联网，实际上网络已经成为 Internet 的代名词，确实 Internet 从只有几个结点的简单的网络，发展到今天 Internet 的用户已经数以亿计，即使不考虑终端用户，路由器的用户也是几万人，确实是复杂的网 络，而且对互联网我们缺少统一的行政管理机构，可以说到今天已经没有任何一个人能够 知道互联网上所有的路由器到底是怎么联结在一起，就是没有互联网联结一张很完整的清 晰的地图。 世界上除了互联网以外，复杂网络的例子在我们生活中比比皆是，比如说我们把一个万维 网做为一个结点，可以说至少和我们人类的数目相当的，所以万维网也是极其复杂的网络。 就拿我们人体而言，我们人体当中实际上有各种各样的复杂网络，我们大脑当中的神经网 络，实际上就是有数量高于十次方以上大量的神经源互相连接在一起，我们人体还有各种 各样的新陈代谢网络。那么一条江河里面食物链构成的食物链也是网络，甚至大型软件系 统都可以看成是小的对象类通过互相调用构成的复杂网络，因此可以说绝大部分的事物都 可以看成是复杂网络。 1.2 复杂性的表征 复杂网络的复杂性到底体现在哪些方面？ 1）直观而言，就是网络的结构非常复杂，比如说互联网、路由器和路由器怎么连接，我们 没有很清晰、很规则的概念； 2）网络是不断演化的，以互联网而言，网络上我们可以说路由器是不断地增加，路由器与 路由器之间的连接也是不断增长的； 3）连接的多样性。就像人类朋友的关系，朋友也有亲密和疏远之分；还有网络动力学的复 杂性，互联网每一个路由器的动力行为，实际上都是在不停地变化，而且不同的结点都有 不同的动力行为，这些都是网络复杂的因素。 那么我们说一个网络复杂，它的复杂性到底体现在哪些方面？首先第一直观而言，就是网 络的结构非常复杂，比如说互联网、路由器和路由器怎么连接，我们没有很清晰、很规则 的概念；其次网络是不断演化的，以互联网而言，网络上我们可以说路由器是不断地增加， 路由器与路由器之间的连接也是不断增长的；还有一个就是连接的多样性。就像人类朋友 的关系，朋友也有亲密和疏远之分；还有网络动力学的复杂性，互联网每一个路由器的动 力行为，实际上都是在不停地变化，而且不同的结点都有不同的动力行为，这些都是网络 复杂的因素。今天我想跟大家交流的是关于网络结构上的复杂性。那么在研究网络结构的 复杂性之前，我们首先想要关心的一个问题就是我们为什么要研究网络的结构？一个最主 要的理由一个系统的结构、一个网络的结构与它的功能密切相关。我们大家可以想象一下， 我们要想解决一个城市里面的道路交通堵塞的问题，我们首先必须要对现有的城市交通道 路的布局有一个非常清晰、完整的了解，否则的话很难想象我们能够很好解决道路堵塞的 问题。像时尚病毒在我们人类自身构成的网络当中的传播，也与我们人类社会的日益网络 化相关的，病毒的传播也是与互联网的网络化相关的，所以我们之所以研究网络结构，就 是结构与功能之间有着密切的关系。 复杂网络的描述语言 描述这种不同类型复杂网络的共同语言，这样一种共同的语言，应该说是由伟大的数学家 欧拉在十八世纪就给我们建立了 用规则的图来表示复杂网络的结构 关于复杂网络突破结构性质的研究，进展有很多，但重要的方面，可以归为以下这三个方面： 1、网络的聚类特性。 2、尽管网络结点很多，但是是不是真的很大，它到底有多小。 3、网络当中的结点与结点是否平等。事实上可以归为这三个问题。 聚类特性 用一句成语就是网络物以类聚、人以群分的关系，以朋友关系网络而言的话，那么我的朋 友圈的聚类系数是什么？就是我在我的朋友圈当中，任意随机找两个朋友，我看这两个朋 友他们两个人之间也互相是朋友的概率是多大。我们根据我们日常经验来看，事实上我的 朋友大部分都是我的同事、同学、邻居，所以他们相互为朋友的概率事实上也是不小的， 而一个网络如果它真的是完全随机的，那么我的朋友当中两个人互相为朋友的概率应该是 很小的，所以说实际的复杂网络，它并不是完全随机的，而是具有比完全随机网络高得多 的聚类的特性，这是最近几年来人们通过对许多大型的实际的复杂网络的数据做统计分析 得到的结论，就是与完全随机的网络相比，我们的网络具有高得多的聚类效应，确实是物 以类聚，人以群分，这是一个特性。 小世界特征 对以下的例子，我们可以发现小世界这样一种特征，是不同类型的复杂网络所共有的一种 特征，也就是说这些不同类型的复杂网络，尽管他们的规模都很大，但是两个结点之间的 距离比我们想象得要小得多。 另外一个特性，这些网络看上去都很大，那么我们从反方面来说，它到底有多小呢？我们 要看它有多小，我们就要有具体的概念来刻划，一个网络当中两个结点之间的距离我们定 义为从这个结点到那个结点所需要的最小的边数，我们就称为这两个结点之间的距离。一 个网络的平均距离就是网络所有的结点距离，我们取平均值，过去几年来人们对众多不同 的复杂网络进行分析发现这些网络虽然大，但是实际上这些网络都是惊人的小，同样以人 类自身的网络为例的话，实际上在二十世纪六十年代美国一个社会科学家就通过一系列的 实验发现在我们地球上随机找两个人，这两个人之间，从平均的意义上来讲，这两个人通 过六层朋友关系就能拉上关系，这就是社会学上的所谓六度分割原理，这样的六度分割原 理，我想绝大部分的人都有这样的体验。比如说我们有的时候在一起吃饭的时候，原来这 两个人是互相不认识的，但是大家聊一聊、谈一谈就发现你认识甲先生，而甲先生是我的 好朋友，聊一聊就会拉上关系，大家都会有这个体会，常常说这个世界真小，这实际上就 是反映我们人类社会小世界的特征。那么事实上具有这种小世界特征的网络绝不是人类社 会本身这个网络一个。在前几年，美国的科学家们把好莱坞所有老的电影演员拿来做实验， 比如说一个演员是一个结点，两个演员他们合作在同一部电影演出，划一个边，通过所有 演员分析表明，平均来讲两个演员之间的距离比 6 还小，也就是 3 至 4 的样子。 以万维网为例，万维网在 1999 年统计大概是 10 亿的数量级，那么美国一些物理学家就设 计了一种软件，通过这个软件对万维网做数据采集分析发现，万维网中的平均距离是 19 个 连接，这是什么概念？就是说你在互联网上随机任意取两点，不断 点这上面的超级链节按 19 次鼠标就能到达另一点，这就是万维网小世界特征。 以互联网为例，我们路由器的数量已经是数以几十万计，但是平均两个路由器之间的距离 也就是 10 左右。 以食物链为例子，科学家发现，对食物链网络而言，两个物种的距离只有 2， 以我们生物体当中的新陈代谢网络而言，科学家发现，大量的新陈代谢网络都是小世界网 络，它们平均距离都是 3 左右，惊人得小。通过一个很小的动物，就是鲁虫，这个动物的 神经源距离是 14、 我们人类的语言，我们每天都在使用不同的语言讲话，也许大家没有想到过我们人类的语 言也可以看作是一个复杂的网络。以英语为例，我们可以把每一个单词看做是一个结点， 如果两个单词它们在同一个句子当中出现过，我们就认为这两个单词之间是直接关联的， 就加一个边，这样我们可以把语言看作是一个复杂的网络。通过对英语的统计分析，两个 单词之间的平均距离，实际上只有 2 至 3。 以我们电子线路为例，我们一块电路板上往往都有很多的元件，如果两个元件之间有两个 联线相连，就画一条边，我们发现电路板上的平均距离也只有 4。 回到我们科研人员本身，我们谈一下科研合作网络，实际上在对 SARS 病毒的研究方面，我 们之所以能够在这么短的几个月里面，对 SARS 的研究方面，应该说还是取得了很大的进展， 很大的程度上应该归功于我们能够迅速组织起来的科研合作网络，在这里我们可以看到一 个科研合作网络的每一个科学家、每一个科研人员，我们把他们看作一个结点，如果两个 科学家、两个科研人员合作发表过一篇文章的话，我们就把这两个结点画一条边，这样我 们就可以得到一个科学合作网络，研究人员通过对不同学科、不同领域的科学合作网络所 做的统计分析发现，这些科学合作网络都具有小世界的特征，也就是说两个科学家之间平 均距离也是在 4 至 9 之间，也是很惊人得小。 比如说在数学史上，最多产的一个科学家，二十世纪最著名的科学家阿尔多斯，他一生发 表过一千多篇文章，我查到我和他的平均距离，实际上惊人得小，只有 3。 为什么实际的复杂网络都具有这样一种小世界的特征？这方面突破性的进展，是在 1998 年 美国康乃尔大学的导师和学生提出来小世界模型。他们小世界模型首先是从一个规则的， 但是局部连接的网络开始的，如果我们把这个网络看成是朋友关系网络的话，就是说左边 局部规则的网络，就是假设每个人的朋友都在我的周围，如果我们的朋友关系真是这样的 网络的话，那么这样的网络具有很高的聚类特性，但是它是大世界，就是全世界人口有 70 亿的话，从这个顶点到另外一个顶点的距离，跟我们人类的数量是相等的，所以这是一个 大世界。那么他们通过研究发现，我们只要在这样一个局部连接网络当中，引入非常少量 的长城连接，就可以使原来大世界的网络，变成一个小世界的网络，也就是说可以使两个 人之间的距离变得非常小。以朋友关系为例，就是说我们只要有少量的人，他具有少量远 在异国他乡的朋友的话，就能使我们整个人类变成一个小世界的网络。 我们前面谈到了实际网络具有比较高的聚类效应，而且实际网络尽管它们的规模都很大， 但是其实它们也有很小的方面。下面我们看一看实际的网络当中，结点与结点之间在地位 上是否平等呢？要表述这个问题就要引出另外一个概念，就是度分布的概念，所谓一个网 络结点分布的话，就是你有多少个朋友，这个 K 就是你的度，那么什么叫做度分布的概念？ 就是说我们以朋友网络关系而言，我们随机找一个人看看他有 K 个朋友的概率是多大，这 个概率就是这个网络的度分布。那么我们研究人员在过去几年里面，在对复杂网络的度分 布上面，发现了什么样的特征呢？我们学过概率统计的朋友可能都知道，我们最常用的分 布，就是我们科研人员最常用的分布就是正态分布，具有这种分布的网络，它具有一个明 显的特征长度 K，就是以我们这个城市。 以我们高速公路网为例，那么通过每一个大城市的高速公路数目应该来说差别都不太大， 就是不可能说一个城市有几百条高速公路都穿过这个城市，那么航空交通网就大不一样， 右边是美国航空交通网的图，很多机场实际上都是不大的，每天的航班数目都不太多，但 是有少量的大的机场它几乎每分钟都有飞机不停地在升起降下，比如说芝加哥、亚特兰大、 纽约等等，对网络连接起很重要的作用，就是把这几个大机场关闭，整个航空交通网络就 会瘫痪。那么我们只是关掉小的机场的话，可以说对整个航空交通网络是没有影响的，所 以航空交通网跟城市的高速公路交通网是有很大的区别。 那么研究人员通过对许多实际网络的研究，就发现许多实际网络都具有像航空交通网的性 质，就是这种网络它的连接度分布是一种我们称之为 PK 的分布，就是 K 的幂次方，具有 这种幂度的分布网络，由于没有明显的特征长度，所以我们称之为五次度网络。 以互联网为例，就是五次度网络，大量的路由器只有少量的路由器连接，但是大量的互联 网路由器与众多的其他的路由器相连接。对这种互联网的五次度网络特征发现，也影响到 了我们对互联网突破结构发生器的研究工作，大家知道，我们互联网的规模发展到今天这 么大，我们有了一种新的想法，我们是不可能立即在实际的网络上面做实验，我们往往都 要做大量的仿真实验，而这些仿真实验效果怎么样，很大程度上取决于我们互联网仿真模 型是否与实际的互联网相符合。 运行在互联网上的万维网，也是具有五次度特性的网络。那么万维网实际上是一种有向的 网络，为什么称为是有向的网络？就是说万维网就像我的主页上有一些超级链节，比如说 我有一个指向新浪网的主页，但是新浪网上面没有指向我的主页，所以我们可以画出两张 地图，就是只考虑每一个出去的网络，另外一个就是只考虑有多少个外面的指向它，通过 对两张地图的统计发现，都具有五次度特征。这种五次度特征表示万维网什么特性？就是 不规则的特性。像我的个人主页很少有别的主页能够加上我的个人主业的超级链接，而成 千上万能够指向新浪网的超级链接。很多新陈代谢的网络也具有这种五次度特征，有一篇 文章提到在癌症上面非常重要的网络叫 P53 网络，就提到这样一个观点，我们理解 P53 网 络一种方式就是把它与互联网相比较，细胞和互联网一样也具有五次度的特征。我们科学 引用网络而言，即我们把每发表的一篇文章当做一个结点，文章后面参考文献，就构成了 文章与文章之间相互引用关系，组成了科学引用网络，研究人员发现，对不同学科而言， 这种科学引用网络都具有这种五次度特征。 通过这些例子，我们就要问，像复杂网络当中哪些少量大的结点是怎么产生的？为什么这 些复杂网络它们的连接分布具有这种分布的特性？在 1999 年的时候，二个物理学家发表了 一篇文章，就提出五次度网络模型，他们认为之所以复杂网络会产生这种五次度特性，是 有两个很重要的机理：一个是网络不断增长的特性，也就是我们万维网上每天都有新的站 点产生，以科研人员为例，就是有不同的科研成果加进来；第二就是网络结点优先连接特 点，就是富的人更富这样的特性。这是什么意思？比如说以万维网为言，我在建立我个人 主页的时候，我在我个人主页建立超级链接，主要先想到新浪、雅虎这样著名的站点，越 具有高知名度的结点，后面的结点越想跟他们连接，就是富的人越富。发表文章我们参考 的时候，越是著名的文章我们大家越想引用它，就是这两个机理使得复杂网络具有五次度 特性。这几年还有大量的研究，我们就不详细介绍了。 总的来看，关于复杂网络结构特征的研究，我们看到许多的实际网络尽管规模很大，但是 还是比较紧密的联系在一起的，而且尽管它的规模很大，实际上结点与结点之间的距离远 比我们想象的小得多，也就是世界上也很小的，尽管网络规模很大，但是网络当中结点与 结点之间的地位是不平等的，就是我们的网络世界实际上也是不平等的，就是归纳起来就 是这样三种主要的特性。 3.3 鲁棒性 研究网络的这些结构上的特征本身并不是我们的目的，我们的目的是想看看这些结构上的 特征与网络的行为之间到底有什么样的关系，或者说网络的结构是怎么样影响网络的行为 的？这里我们简单谈一下三个方面：网络的脆弱性；网络上的统分化行为；网络上的病毒 传播机制。 一个系统，一个网络，它的某个脆弱的方面，我们在科学方面通常也把它称为这个系统的 阿基尼斯的脚后跟，为什么称为阿基尼斯脚后跟，阿基尼斯是古希腊出生的一个英雄，他 的母亲把他放在禁河里，所以就力大无穷，他母亲是抓着他的脚后跟放入禁河，只有脚后 跟是凡人，别人就射他的脚后跟，所以我们称之为阿基尼斯的脚后跟。Internet 的阿基尼 斯脚后跟，在这期发表的文章当中，就研究了具有五次度特征的复杂网络，它的鲁棒性和 脆弱性，就是把这个网络的一些结点去掉，这个网络是否还是一个完整的网络。以互联网 为例，我们互联网的前身是具有几个结点的网络演变而来的，美国国防部当时在设计这个 网络的时候，一个很重要的因素就是希望我这个网络在受到苏联攻击的时候，它仍然能够 保持通信的畅通，互联网现在发展成为这样巨大的网络，是否还具有鲁棒性，对数据仿真 研究发现，确实我们的互联网它对随机性的鼓掌具有非常高的鲁棒性，这实际上也是与我 们今天的现实相符合，我们每天都在使用互联网，也许我们没有注意到在互联网上每天都 有数以百计的路由器在发生故障，而我们普通用户都没有感觉到这些故障，我们还能在互 联网上冲浪，这就是互联网高度容忍的随机性和鲁棒性，为什么互联网有这样的鲁棒性？ 研究认为互联网路由器具有的五次度特征有关系，也就是互联网上有少量的路由器，它们 与其他众多的路由器相关联，这些少量的路由器只要能正常运行，就能保证整个 Internet 能够正常运行。但是从另外一个方面来讲，正是由于少量的结点，它对整个网络运行所起 的重要的作用，也使得我们互联网对恶意的攻击具有很强的脆弱性，也就是说如果我要使 我们的互联网陷入瘫痪的话，我只要对哪些少量的连接度很高的结点，只要使不超过 5 的结点瘫痪的话，就可以使 Internet 瘫痪，这也是它不利的一个方面。那篇文章的观点就 认为这种复杂网络对随机性故障的鲁棒性和对恶意攻击的脆弱性是五次度特征的共性。而 事实上，近些年不同领域的科学家对不同事物进行研究分析，鲁棒当同时脆弱是复杂网络 最重要的特征，比如说航天飞机，我们设计航天飞机的时候，显然我们总是失望，对我们 能够想到的各种干扰，我们希望航空飞机能够顺利回到地面，但是我们还是不幸出现了哥 伦比亚号的灾难，就是实际的复杂系统既具有鲁棒性，也具有脆弱性的一面。 3.4 网络同步 实际上同步化现象是宇宙当中最朴实的现象，对同步化在科学上做研究，可以追溯到十九 世纪一个科学家，他发现两个挂钟在一个地方，一个时期以后就会是同步，而以前是不同 步的。 比如说夏天有一棵树上有很多的萤火虫，可能一开始闪灭的时间都不同，但是一段时间以 后就可以同时闪灭，就像手电筒一开一关一样。 窗外蟋蟀叫响的声音是不同的，但是过一段时间就会听到蟋蟀同时叫，同时不叫。 演讲的时候，观众都要给以掌声，但是最初几秒钟大家的掌声比较杂乱，但是很快过了几 秒钟我们的掌声就会非常整齐一致。 2001 年发表的一篇文章就是探讨议会中这些观众的掌声一开始不同步，几秒钟以后就会同 步。 在高科技领域也有很多同步化的现象，比如说路由器振荡的同步。 激光之所以有可能产生，就是因为数以万以计的原子，它们同时释放出具有同样的分子产 生的。 同步并不都是有利的，在很多场合同步也是有害的，比如说英国在为了迎接新千年的到来， 建立了一座千年大桥，开放后不久有一天晚上，这个大桥上面人数众多，大家走路又产生 了某种共振，使千年大桥发生了剧烈的晃动，迫使工作人员不得不把这座大桥关闭，这就 是同步化造成的危害。 以互联网为例，普通公众没有意识到互联网上有多少同步化的危害，比如说互联网上的路 由器，每一个路由器都要周期性的发布路由消息，而尽管各个路由器它都是自己来决定它 什么时候发布路由消息的，但是研究人员发现不同路由器它们发送路由消息，最终会达到 同步化现象，也就是大家要不同时发布路由消息，要不发布，这显然对网络的拥塞，这都 是不利的行为。 前面谈到同步化的行为，科学家就想到这些不同类型的复杂网络为什么会产生这些同步化 的现象，就是在不同类型的同步化现象背后共同的特征是什么？特别是近几年人们也把同 步化现象产生与复杂网络突破结构结合起来，在这方面通过研究，我们就发现如果一个复 杂网络当中，任何两个结点之间，都是直接相连的话，那么只要这个网络的规模足够大的 话，这个网络之间的结点必然会产生同步化现象。而对于一个只有局部相连的规则网络而 言，对这个网络而言，不管两个结点之间的连接强度有多大，只要网络规模足够大的话， 这样的网络是不可能达到同步的。 而我们关于小世界网络的研究，我们发现只要在原来局部规则网络的基础上，引入少量的 几个长城链接，就能够显著改善网络同步化的能力。 对五次度网络同步化的实验表明，由于网络的非均匀特性，就是少量结点在五次度网络的 作用，相当于几个结点起作用，这样使得五次度网络与新型网络类似同步化的能力也是非 常强的，所以说这就在一定程度上解释了为什么许多复杂网络它都具有一种同步化的趋势。 3.5 网络传播 复杂网络传播现象，也就是最初一个局部的小的故障，小的扰动是怎么在网络当中传播的， 怎么样最终影响整个网络系统行为的。 例如，由于狂风暴雨，使得某一个地方的电线杆倒了，这就有可能在很短时间内导致一片 城区都断电，这就是电力网中的连锁故障。 经济活动为例，最简单的例子就是亚洲金融危机，在 1997 年亚洲金融危机发生之前，那些 发生危机的国家它们的经济建