复杂网络简介

小世界效应对于传播动力学行为的影响.Moore等发现,少量的长程边也可以明显增加网络中疾病易于传染的性质[57].如果把疾病得以传播开去的传染率下限（称为传播阈值）和传播时间特性（感染者数量和传播持续时间之间的关系）视作网络传播动力学中最重要的可观测量,则相比规则网络,小世界网络的传播阈值小,传播速度快.另外,很早人们就观察到在大规模的种群中,疾病的流行常常具有某种周期的特性[58,59],Kuperman等[60]最早讨论了小世界网络中的疾病传播的周期振荡,他们发现,当长程边数目慢慢增大时,感染个体数量的时间序列将逐步从在一个不动点上下波动变成明显的周期振荡.熊等通过在小世界网络的SIR模型中引入潜伏期,在不同参数设置下,分别得到短时和长时的振荡行为[61].类似地,Verdasca等从儿童传染病麻疹和百日咳的致病机理出发,系统讨论了带有潜伏期的SIR模型（SEIR模型）在小世界网络上的传播行为,也发现了明显的周期振荡[62].汪小帆,李翔,陈关荣,复杂网络理论及其应用,清华大学出版社,2006S.P.Borgatti,A.J.Mehra,D.J.Brass,G.Labianca,NetworkAnalysisintheSocialSciences,Science323(2009)892-895.感受：学海无涯，还有很多知识都还未掌握。BarabasiAL;AlbertREmergenceofscalinginrandomnetworks1999Watts,D.J.andStrogatz,S.H.(1998)CollectiveDynamicsof“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，就是以我们这个城市。以我们高速公路网为例，那么通过每一个大城市的高速公路数目应该来说差别都不太大，就是不可能说一个城市有几百条高速公路都穿过这个城市，那么航空交通网就大不一样，右边是美国航空交通网的图，很多机场实际上都是不大的，每天的航班数目都不太多，但是有少量的大的机场它几乎每分钟都有飞机不停地在升起降下，比如说芝加哥、亚特兰大、纽约等等，对网络连接起很重要的作用，就是把这几个大机场关闭，整个航空交通网络就会瘫痪。那么我们只是关掉小的机场的