复杂网络概述课件

《复杂网络概述课件》由会员分享，可在线阅读，更多相关《复杂网络概述课件（42页珍藏版）》请在金锄头文库上搜索。

1、复杂网络概念 复杂网络含义 大量真实复杂系统的拓扑抽象； 在感觉上比规则网络和随机网络复杂； 大量复杂系统得以存在的拓扑基础。 复杂网络的研究历史 哥尼斯堡七桥随机图论小世界和无标度网络,复杂网络,2,复杂网络研究简史,格尼斯堡七桥问题,Euler（17071783），瑞士数学家 ，图论之父,一笔画问题,1736年， 七桥游戏,3,随机图理论 20世纪60年代，由两位匈牙利数学家Erds和Rnyi建立的随机图理论（random graph theory）被公认为是在数学上开创了复杂网络理论的系统性研究。,Erds和Rnyi的最重要的发现是：ER随机图的许多重要性质都是突然涌现的。也就是说，对于

2、任一给定的概率p，要么几乎每一个图都具有某个性质Q（比如说，连通性），要么几乎每一个图都不具有该性质。 在20世纪的后40年中，随机图理论一直是研究复杂网络的基本理论。,4,小世界实验 20世纪60年代美国哈佛大学的社会心理学家Stanley Milgram通过一些社会调查后给出的推断是：地球上任意两个人之间的平均距离是6。这就是著名的“六度分离”（six degrees of separation）推断。,为了检验“六度分离”的正确性，小世界实验Bacon数。美国Virginia大学计算机系的科学家建立了一个电影演员的数据库，放在网上供人们随意查询。网站的数据库里目前总共存有近60万个世界各

3、地的演员的信息以及近30万部电影信息。通过简单地输入演员名字就可以知道这个演员的Bacon数。,一个有趣的数学家故事：Erds数证明小世界实验。,小世界实验- 六度分离,米尔格伦的实验过程是：他计划通过人传人的送信方式来统计人与人之间的联系。 首先把信交给志愿者A，告诉他信最终要送给收信人S。如果他不认识S，那么就送信到某个他认识的人B手里，理由是A认为在他的交集圈里B是最可能认识S的。但是如果B也不认识S，那么B同样把信送到他的一个朋友C手中，就这样一步步最后信终于到达S那里。这样就从A到B到C到最后到S连成了一个链。斯坦利米尔格伦就是通过对这个链做了统计后做出了六度分离的结论。 然而在这个

4、实验中，实际上只有三分之一的信送到了收信人那里，因此实验的完成率很低。,小世界实验六度分离,我们或许有过这样的经历：偶尔碰到一个陌生人，同他聊了一会后发现你认识的某个人居然他也认识，然后一起发出”这个世界真小”的感叹。那么对于世界上任意两个人来说，借助第三者、第四者这样的间接关系来建立起他们两人的联系平均来说最少要通过多少人呢？ 美国社会心理学家斯坦利米尔格伦(Stanley Milgram)在1967年通过一些实验后得出结论：中间的联系人平均只需要5个。他把这个结论称为“六度分离”。 六度分离: 平均只要通过5个人，你就能与世界任何一个角落的任何一个人发生联系。这个结论定量地说明了我们世界的

5、”大小”，或者说人与人关系的紧密程度。 30多年来，六度分离理论一直被作为社会心理学的经典范例之一。 尽管如此，实际上这个理论并没有得到严格的证实。美国心理学教授朱迪斯克兰菲尔德(Judith Kleinfeld)对米尔格伦最初的实验提出不同意见，因为她发现实验的完成率极低。,小世界实验- Bacon数,截止到几天前，世界电影史上共产生了大约23万部电影，78多万名电影演员（参见互联网电影库 ）. Kavin Bacon在许多部电影中饰演小角色。 几年前,Virginia 大学的计算机专家Brett Tjaden设计了一个游戏，他声称电影演员Kevin Bacon是电影界的中心。 在游戏里定

6、义了一个所谓的Bacon数：随便想一个演员，如果他（她）和Kavin Bacon一起演过电影，那么他（她）的Bacon数就为1；如果他（她）没有和Bacon演过电影，但是和Bacon数为1的演员一起演过电影，那么他的Bacon数就为2；依此类推。 发现: 在曾经参演的美国电影演员中，没有一个人的Bacon数超过4。,小世界实验- Bacon数,在网上有一个网页http:/www.cs.virginia.edu/oracle/。网站的数据库里总共存有有783940个世界各地的演员的信息以及231,088部电影信息。 通过简单地输入演员名字就可以知道这个演员的bacon数。目前比如输入Stephe

7、n Chow（周星驰）就可以得到这样的结果：周星驰在1991年的豪门夜宴(Haomen yeyan) 中与洪金宝(Sammo Hung Kam-Bo)合作；而洪金宝又在李小龙的最后一部电影，即1978年的死亡的游戏 （Game of Death） 中与 Colleen Camp 合作；Colleen Camp 在去年的电影Trapped 中与Kevin Bacon 合作。这样周星驰的Bacon数为3。 对78万个演员所做的统计：演员的最大Bacon数仅仅为8，平均Bacon数仅为2.948。,小世界实验-Erdos数,Paul Erdos(1913-1996)：是出生于匈牙利的犹太籍数学家，被

8、公认为20世纪最伟大的天才之一。 Erdos毕生发表的论文超过1500篇（在数学史上仅次于欧拉(Euler ，1707-1783)，超长的合作者名单,合作者超过450位。但若加上别人所做但曾获他关键性提示之论文，则他的论文应有数万篇。 他的研究领域主要是数论和组合数学，但他的论文中涵盖的学科有逼近论、初等几何、集合论、概率论、数理逻辑、格与序代数结构、线性代数、群论、拓扑群、多项式、测度论、单复变函数、差分方程与函数方程、数列、Fourier分析、泛函分析、一般拓扑和代数拓扑、统计、数值分析、计算机科学、信息论等等。 “Mathematical Reviews“ 曾把数学划分为大约六十个分支，

9、Erdos的论文涉及到了其中的40%.,小世界实验-Erdos数,Erdos从来没有一个固定的职位，从来不定居在一个地方，也没有结婚，带着一半空的手提箱，穿梭于学术研讨会，浪迹天涯，颇富传奇色彩。有人称他为流浪学者(wande ring scholar)。 他效忠的是科学的皇后， 而非一特定的地方。各地都有热心的数学家提供他舒适的食宿，安排他的一切，他则对招待他的主人，给出一些挑战性的数学难题，或给予研究上的指导做为回馈。 他可以和许多不同领域的数学家合作。数学家常将本身长久解决不了的问题和他讨论，于是很快地一篇论文便诞生了。,小世界实验-Erdos数,数学家以下述方式来定义Erdos数(Er

10、dos number) : Erdos本人之Erdos 数为0，任何人若曾与Erdos合写过论文， 则其Erdos数为1。任何人若曾与一位 Erdos数为l(且不曾与有更少的Erdos数) 的人合写过论文， 则他的Erdos数为2 几乎每一个当代数学家都有一个有限的Erdos数，而且这个数往往非常小，小得出乎本人的预料。比如说证明Fermat大定理的Andrew Wiles，他的研究方向与Erdos相去甚远，但他的Erdos数只有3，是通过这个途径实现的：Erdos-Andrew Odlyzko-Chris M.Skinner-Andrew Wiles.,小世界实验-Erdos数,Fields

11、奖得主的Erdos数都不超过5，（只有Cohen和Grothendieck的Erdos数是5，） Nevanlinna奖得主的Erdos数不超过3，（只有Valiant的Erdos数是3） Wolf数学奖得主的Erdos数不超过6，（只有V.I.Arnold是6，且只有Kolmogorov是5，） Steele奖的终身成就奖得主的Erdos数不超过4. 在具有有限Erdos数的人名单中往往还能发现一些其他领域的专家，如: 比尔盖兹(Bill Gates)， 他的Erdos数是4，通过如下途径实现：Erdos-Pavol Hell-Xiao Tie Deng-Christos H. Papadi

12、mitriou-William H. (Bill) Gates. 爱因斯坦的Erdos数是2.,13,有两篇开创性的文章可以看作是复杂网络研究新纪元开始的标志： 一篇是美国康奈尔（Cornell）大学理论和应用力学系的博士生Watts及其导师、非线性动力学专家Strogatz教授于1998年6月在Nature杂志上发表的题为“小世界”网络的集体动力学（Collective Dynamics of Small-World Networks）的文章； 另一篇是美国Notre Dame大学物理系的Barabsi教授及其博士生Albert于1999年10月在Science杂志上发表的题为随机网络中标度

13、的涌现（Emergence of Scaling in Random Networks）的文章。 这两篇文章分别揭示了复杂网络的小世界特征和无标度性质，并建立了相应的模型以阐述这些特性的产生机理。,复杂网络的结构,四种结构模型： 规则网络 随机网络 小世界网络 无标度网络,规则网络,系统中节点及其与边的关系是固定的。 （a）全局耦合网络； （b）最近邻耦合网络； （c）星形网络 全局耦合网络具有最小的平均路径长度Lgc =1和最大的聚类系数Cgc =1；,最近邻耦合网络:包含N个围成一个环的点，其中每个节点都与它左右各K/2个邻居点相连（K为偶数），对于较大的K值，最近邻耦合网络的聚类系数为

14、因此，这样的网络是高度聚类的。对于固定的K值，网络平均路径长度为 星形耦合网络：有一个中心点，其余N-1个点都只与这个中心点连接，其平均路径长度为 聚类系数为,随机图,随机图是与规则网络相反的网络，一个典型模型是Erdos和Renyi于40多年前开始研究的随机图模型。 假设有大量的纽扣（N1）散落在地上，并以相同的概率p给每对纽扣系上一根线。这样就会得到一个有N个节点，约pN(N-1)/2条边的ER随机图的实例。,18,1998，Watts和Strogatz：WS小世界网络,D. J. Watts, and S. H. Strogatz, Nature, 393, 440-442 (1998)

15、.,C(p) : 平均聚集系数 L(p) : 平均最短路径,WS小世界模型 NW小世界模型,小世界网络,作为从完全规则网络向完全随机图的过渡，Watts和Strogtz于1998年引入了一个小世界网络模型，称为WS小世界模型。其构造算法如下： 从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各K/2个节点相连，K是偶数。 随机化重连：以概率p随机地重连网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同节点之-间至多只能有一条边，并且每一个节点都不能有边与自身相连。 P=0对应于完全规则网络，p

16、=1对应于完全随机网络。,小世界网络,具有较短的平均路径长度又具有较高的聚类系数的网络就称为小世界网络。 Newman和Watts提出了NW小世界模型，用“随机化加边”取代WS小世界模型构造中的“随机化重连”。算法如下： 从规则图开始：含有N 个节点的最近邻耦合网络。 随机化加边：以概率P在随机选取的一对节点之间加上一条边。 NW小世界模型中，p=0对应于原来的最近邻耦合网络，p=1对应于全局耦合网络。,无标度网络模型,研究发现许多复杂网络的连接度分布函数具有幂律形式，由于这类网络的节点的连接度没有明显的特征长度，故称为无标度网络。 Barabasi 和Albert 提出了一个无标度网络模型，称为BA模型。该模型考虑到了实际网络的两个重要特性： 增长特性；优先连接特性。 基于这两个特性，BA无标度网络模型构造算法如下： 增长：从一个具有m0个节点的网络开始，每次引入一个新的节点，并且连到m个已存在的节点上，这里