复杂网络理论及其应用.ppt

《复杂网络理论及其应用.ppt》由会员分享，可在线阅读，更多相关《复杂网络理论及其应用.ppt（66页珍藏版）》请在三一文库上搜索。

1、简介: 复杂网络理论及其应用,王继民 2006年5月21日,outline,小世界实验 六度分离、Erdos数、bacon数等 一些实际的复杂网络系统 Web、科学家合作网络、经济网络、交通网络、疾病传播等 复杂网络的静态几何量 度分布、聚类系数、平均路径长度等 网络拓扑的基本模型及其性质 随机网络、Small World网络、Scale Free网络等 近几年的研究态势 发展历程、会议、论文、软件、实证等,小世界实验- 六度分离,我们或许有过这样的经历：偶尔碰到一个陌生人，同他聊了一会后发现你认识的某个人居然他也认识，然后一起发出”这个世界真小”的感叹。那么对于世界上任意两个人来说，借助第三

2、者、第四者这样的间接关系来建立起他们两人的联系平均来说最少要通过多少人呢？ 美国社会心理学家斯坦利米尔格伦(Stanley Milgram)在1967年通过一些实验后得出结论：中间的联系人平均只需要5个。他把这个结论称为”六度分离”(six degrees of separation)。 六度分离: 平均只要通过5个人，你就能与世界任何一个角落的任何一个人发生联系。这个结论定量地说明了我们世界的”大小”，或者说人与人关系的紧密程度。 30多年来，六度分离理论一直被作为社会心理学的经典范例之一。 尽管如此，实际上这个理论并没有得到严格的证实。美国心理学教授朱迪斯克兰菲尔德(Judith Klei

3、nfeld)对米尔格伦最初的实验提出不同意见，因为她发现实验的完成率极低。,小世界实验- 六度分离,米尔格伦的实验过程是：他计划通过人传人的送信方式来统计人与人之间的联系。 首先把信交给志愿者A，告诉他信最终要送给收信人S。如果他不认识S，那么就送信到某个他认识的人B手里，理由是A认为在他的交集圈里B是最可能认识S的。但是如果B也不认识S，那么B同样把信送到他的一个朋友C手中，就这样一步步最后信终于到达S哪里。这样就从A到B到C到最后到S连成了一个链。斯坦利米尔格伦就是通过对这个链做了统计后做出了六度分离的结论。 然而在这个实验中，实际上只有三分之一的信送到了收信人哪里，因此实验的完成率很低。

4、,小世界实验-Erdos数,Paul Erdos(1913-1996)， 出生于匈牙利的犹太籍数学家，被公认为本世纪最伟大的天才之一。 Erdos毕生发表的论文超过1500篇（在数学史上仅次于欧拉(Euler ，1707-1783)，超长的合作者名单,合作者超过450位。但若加上别人所做但曾获他关键性的提示之论文，则他的论文应有数万篇。 他的研究领域主要是数论和组合数学，但他的论文中涵盖的学科有逼近论、初等几何、集合论、概率论、数理逻辑、格与序代数结构、线性代数、群论、拓扑群、多项式、测度论、单复变函数、差分方程与函数方程、数列、Fourier分析、泛函分析、一般拓扑和代数拓扑、统计、数值分析

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

6、讨论，于是很快地一篇论文便诞生了。,小世界实验-Erdos数,数学家以下述方式来定义Erdos数(Erdos number) : Erdos本人之Erdos数为0，任何人若曾与Erdos合写过论文，则其Erdos数为1。任何人若曾与一位Erdos数为l(且不曾与有更少的Erdos数) 的人合写过论文， 则他的Erdos数为2 几乎每一个当代数学家都有一个有限的Erdos数，而且这个数往往非常小，小得出乎本人的预料。比如说证明Fermat大定理的Andrew Wiles，他的研究方向与Erdos相去甚远，但他的Erdos数只有3，是通过这个途径实现的：Erdos-Andrew Odlyzko-C

7、hris M.Skinner-Andrew Wiles.,小世界实验-Erdos数,Fields奖得主的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，通过如下途径实现：E

8、rdos-Pavol Hell-Xiao Tie Deng-Christos H. Papadimitriou-William H. (Bill) Gates. 爱因斯坦是2.,小世界实验- Bacon数,截止到几天前，世界电影史上共产生了大约23万部电影，78多万名电影演员（参见互联网电影库 ）. Kavin Bacon在许多部电影中饰演小角色。 几年前,Virginia 大学的计算机专家Brett Tjaden设计了一个游戏，他声称电影演员Kevin Bacon是电影界的中心。 在游戏里定义了一个所谓的Bacon数：随便想一个演员，如果他（她）和Kavin Bacon一起演过电影，那么他

9、（她）的Bacon数就为1；如果他（她）没有和Bacon演过电影，但是和Bacon数为1的演员一起演过电影，那么他的Bacon数就为2；以此类推。 发现: 在曾经参演的美国电影演员中，没有一个人的Bacon数超过4。,小世界实验- Bacon数,小世界实验- Bacon数,在网上有一个网页http:/www.cs.virginia.edu/oracle/。网站的数据库里总共存有有783940个世界各地的演员的信息以及231,088部电影信息。 通过简单地输入演员名字就可以知道这个演员的bacon数。目前比如输入Stephen Chow（周星驰）就可以得到这样的结果：周星驰在1991年的豪门夜宴

10、(Haomen yeyan) 中与洪金宝(Sammo Hung Kam-Bo)合作；而洪金宝又在李小龙的最后一部电影，即1978年的死亡的游戏 （Game of Death） 中与 Colleen Camp 合作；Colleen Camp 在去年的电影Trapped 中与Kevin Bacon 合作。这样周星驰的培根数为3。 是对所有这将近78万个演员所做的统计。结果如下页所示: 左边是Bacon数，右边是拥有这个Bacon数的演员个数。可以看到最大的培根数仅仅为8。平均培根数仅为2.948。,小世界实验- Bacon数,小世界实验- Bacon数,Kavin Bacon图 有明确的定义（顶点

11、和边） 数据库中90%的演员被归入到一个单独的连通分支 最高的有限Bacon数为8 平均Bacon数为2.9 注：少数演员承担了将多数演员联系在一起的工作。,小世界实验-用E-mial传递,检验六度分离的假说,D. watts 2001年开始, 18名目标对象, 166个国家共 6万多志愿者, 平均转发57次,outline,小世界实验 六度分离、Erdos数、bacon数等 一些实际的复杂网络系统 Web、科学家合作网络、经济网络、交通网络、疾病传播等 复杂网络的静态几何量 度分布、聚类系数、平均路径长度等 网络拓扑的基本模型及其性质 随机网络、Small World网络、Scale Fre

12、e网络等 近几年的研究态势 发展历程、会议、论文、软件、实证等,网络的拓扑性质,网络是一个包含了大量个体及个体之间相互作用的系统. 任何一个网络可以抽象为一个图.（最早可追溯到Euler对Konogsberg七桥问题的研究） 网络的拓扑性质：网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质。 图的分类: 无向图, 有向图,加权图, 混合图 简单图是指: 无向,无权,无重边,无自环的图. 目前关于简单网络的研究结果较多,一些实际的复杂网络系统,Web Internet 网络, 电影演员合作网络, 科学家合作网络, 论文引用网络 电话呼叫网络 语言学网络, 电力网络 经济网络, 交通网络

13、 疾病传播 神经网络 人类性关系网络, 蛋白质互作用网络, 蛋白质折叠关系网络 ,Complex Network Example: WWW - (K. C. Claffy) 有向网络， 结点：web页面，边：超链,Complex Network Example: Internet (William R. Cheswick) 无向网络， 结点：路由器和计算机， 边：通讯设备（如电缆等）,Complex Network Example: Telecomm Networks (Stephen G. Eick),Complex Network Example: Routes of Airlines,C

14、omplex Network Example: Usenet (Naveen Jamal),Complex Network Example: VLSI Circuits, CNN,Complex Network Example: Biological Networks,Complex Network Example: Arts ,一些实际的复杂网络系统,Web 有向网络， 结点：web页面，边：超链 Internet 网络 无向网络， 结点：路由器和计算机， 边：通讯设备（如电缆等） 电影演员合作网络 无向网络， 结点：电影演员， 边：两个电影演员一起演过电影 科学家合作网络 无向网络， 结点

15、：科学家， 边：两个科学家一起发表过一篇论文 论文引用网络 有向网络， 结点：论文，有向边：论文引用 电话呼叫网络 有向网络， 结点：电话号码，有向边：电话呼叫 语言学网络 无向网络， 结点：单词， 边：两个词相邻，（或出现在同一个句子中，或相同语义） 电力网络 无向网络， 结点： 发电厂，电站，接转站。 边：高压线 经济网络, 交通网络 疾病传播 神经网络 人类性关系网络, 蛋白质互作用网络, 蛋白质折叠关系网络 ,outline,小世界实验 六度分离、Erdos数、bacon数等 一些实际的复杂网络系统 Web、科学家合作网络、经济网络、交通网络、疾病传播等 复杂网络的静态几何量 度分布、

16、聚类系数、平均路径长度等 网络拓扑的基本模型及其性质 随机网络、Small World网络、Scale Free网络等 近几年的研究态势 发展历程、会议、论文、软件、实证等,复杂网络的静态几何量,度分布（degree distribution） 聚类系数 (clustering coefficient) 平均路径长度(average path length) 无向网络的基本几何量有: 度及其分布特征,度的相关性,集聚程度及其分布特征,最短距离及其分布特征,介数(Betweenness) 及其分布特征,连通集团的规模分布 有向网络的特殊静态几何量包括: In 度和Out 度的分布特征,基于顶点的

17、In-Out 度关联性,基于边的( In-Out , In- In ,Out- In ,Out-Out) 度关联性,双向比, In 集团和Out 集团的集聚程度。 加权网络的静态几何量包括: 度及其分布特征,权及其分布特征,权的相关性,权与度的相关性,最短距离及其分布特征,介数及其分布特征与隧道现象,与相应无权网络的对比,距离关系与类聚分析,以及在加权网络上集聚程度的定义及其统计性质。,平均路径长度(average path length),网络中两个顶点i，j之间的最短路径定义为所有连通(i,j) 的通路中, 所经过的其他顶点最少的一条或几条路径。 两个顶点i，j之间的距离dij定义为i，j

18、之间最短路径上的边数。 网络的直径(diameter),定义为网络中任意两个顶点之间距离的最大值。 网络的平均路径长度(average path length), 定义为网络中任意两个顶点之间距离的平均值。即：,聚类系数 (clustering coefficient),在朋友关系网中，你的两个朋友很可能彼此也是朋友。这种属性称为网络的聚类特性。 用数学化的语言来说，对于某个节点i，它的聚类系数Ci被定义为它所有相邻节点之间连的数目占可能的最大连边数目的比例。 整个网络的聚类系数C则是所有节点聚类系数的平均值。 在随机网络中，C=p, （由于边的分布是随机的）,度分布（degree distr

19、ibution）,一个顶点的度是指与此顶点连接的边的数量。 在有向网络中，分为：出度，入度 研究包括：度及其分布特征，度的相关性。 度值的分布特征是网络的重要几何性质。 规则网络各顶点度值相同，因而符合delta分布 随机网络符合泊松分布 大量实际网络存在幂律(power-law)形式的度分布，即无标度网络（Scale Free Networks）。 无标度网络包括Internet网络，电影与电视剧演员合作网络，科学家合作网络，人类性关系网络，蛋白质互作用网络，语言学网络等，同时还存在高斯型，如蛋白质折叠网络和指数衰减型的概率分布。 度的相关性：Newman把它称为“匹配模式”，意思是考察度值

20、大的点倾向于和度值大的点连接，还是倾向于和度值小的点连接。实际网络的分析表明，不同的网络存在不同的匹配模式，有正相关也有负相关。（有向网络中）基于顶点的In-Out 度关联性。,outline,小世界实验 六度分离、Erdos数、bacon数等 一些实际的复杂网络系统 Web、科学家合作网络、经济网络、交通网络、疾病传播等 复杂网络的静态几何量 度分布、聚类系数、平均路径长度等 网络拓扑的基本模型及其性质 随机网络、Small World网络、Scale Free网络等 近几年的研究态势 发展历程、会议、论文、软件、实证等,网络拓扑的基本模型及其性质,规则网络 随机网络 Small World

21、网络 Scale Free网络 等级网络,规则网络,规则网络是指平移对称性晶格,任何一个格点的近邻数目都相同。 各个节点的具有相同的度值 如图为最近邻耦合网络：每个节点都与它左右的K/2个节点相连。 对大的N, K, 有：聚类系数C3/4, 平均路径长度L无穷大 一般地，规则网络具有大的簇系数和大的平均距离,随机网络,ER随机图模型：顶点的度值服从 Poisson distribution，也称Poisson随机图 如：pajek的生成 平均度：kp*N 平均路径长度Lln(N)/ln(k) 聚类系数: C=p 1 (由于极度稀疏) 一般地，随机网络具有小的簇系数和小的平均距离。,Small

22、World模型,是否存在一个同时具有高的集聚程度,小的最短路径网络呢? 对于传染病模型, 平均集聚程度对应于传播的广度,平均最短距离代表的是传播的深度。 因此,如果实际网络同时存在宽的广度和大的深度的话,在这样的网络上的传染病传播显然将大大高于规则网络与随机网络。 1998年Watts和Strogatz 为我们找到了这样的网络模型Small World 网络（发表在Nature上）. 现在常称为：WS model,Small World模型,方法：Watts和Strogatz 发现,只需要在规则网络上稍作随机改动就可以同时具备以上两个性质。 改动的方法是,对于规则网络的每一个顶点的所有边,以概

23、率p 断开一个端点,并重新连接,连接的新的端点从网络中的其他顶点里随机选择,如果所选的顶点已经与此顶点相连,则再随机选择别的顶点来重连。 当p = 0 时就是规则网络, p = 1 则为随机网络,对于0 p 1 的情况,存在一个很大的p 的区域,同时拥有较大的集聚程度和较小的最小距离。 形成机制：规则网络，以概率p 断开一个端点，随机连接）,NW模型,WS model的构造过程有可能破坏网络的连通性 1999年Newman and Watts提出了NW模型：用“随机化加边”替代“随机化重连” 还有许多改进的模型：加点，加边，去点，去边， 以及不同形式的交叉，产生多种形式的小世界模型,实际的Sm

24、all World网络,Scale Free网络,节点度服从幂律分布，就是说具有某个特定度的节点数目与这个特定的度之间的关系可以用一个幂函数近似地表示。 幂函数曲线是一条下降相对缓慢的曲线，这使得度很大的节点可以在网络中存在。 对于随机网络和规则网络，度分布区间非常狭窄，几乎找不到偏离节点度均值较大的点，故其平均度可以被看作其节点度的一个特征标度。在这个意义上，我们把节点度服从幂律分布的网络叫做无标度网络（scale-free networks），并称这种节点度的幂律分布为网络的无标度特性。,Scale Free网络,1999年，Barabsi 和Albert给出了构造无标度网络的演化模型。

25、形成机制：生长和择优连接 取初始m0个顶点任意连接或完全连接。每一步在原网络G( t - 1) 的基础上加上一个新的顶点,同时加上从此顶点出发的m 条边, 形成新的网络G ( t ) 。其中新加边的另一个端点按照正比于顶点度数的分布。 随机选取。重复以上新加点的过程足够多步所形成的网络的各顶点的度满足幂律分布p ( k) k( -) 。而且,指数= 3 与模型的参数m0 , m 无关。 进一步的数值模拟表明,当m 取某一范围内的随机数时,指数也不变。 现在常称为： BA Model,Scale Free网络,等级网络(Hierarchical network),以模块生成等级网络实例 具有:

26、scale-free特征,outline,小世界实验 六度分离、Erdos数、bacon数等 一些实际的复杂网络系统 Web、科学家合作网络、经济网络、交通网络、疾病传播等 复杂网络的静态几何量 度分布、聚类系数、平均路径长度等 网络拓扑的基本模型及其性质 随机网络、Small World网络、Scale Free网络等 近几年的研究态势 发展历程、会议、论文、软件、实证等,复杂网络研究简史,过去讲究较小规模的网络,国内外的研究情况,从2002年起，国内不同学科的研究人员和青年学者对复杂网络研究的兴趣越来越浓，至今国内已召开过多次以复杂网络为主题的学术会议和论坛 2004年4月在无锡组织了有4

27、0余人参加的首届全国复杂动态网络学术论坛。 武汉大学在国内率先成立了校级复杂网络研究中心并于2005年春季组织了全国复杂网络学术会议 2005年10月在北京召开的由中国高等学术研究中心组织的第二届全国复杂网络学术论坛 一些国际著名大学（如MIT，哥伦比亚大学和密歇根大学等）已相继开设了有关复杂网络的课程，汪小帆教授也在上海交通大学为研究生开设了复杂网络课程。 2006年10月武汉会议,2006全国复杂网络学术会议,复杂网络中理论及其应用-book,复杂网络中理论及其应用-book,复杂网络的主要研究内容,实证研究 结合应用的研究 简单的如： Library And Information Sc

28、ience Abstracts(LISA)图书馆与信息科学文摘库中1996年2005年所有的英文论文数据，共109249条 教育网数据,教育网数据: 对xzm搜集的edu数据,网页数量1000，有376个，链接关系图,教育网数据-input,50个（入度大小. 按网络影响因子核心站点？ ）,教育网数据-output,34个（按出度大小）,情报学报,Papers: Complex Networks,SCI papers EI papers,Papers: Small-World Networks,SCI papers EI papers,Papers: Scale-Free Networks,S

29、CI papers EI papers,面临的挑战性课题,20世纪美国最有影响的五十人物之一E. O. Wilson指出: “今天最大的挑战性,不仅是细胞生物学和生态学,而是科学的所有方面,特别是如何精确地和完全地描述复杂系统.科学家已经认识了许多类型的复杂系统.他们认为已经知道系统中大多数元素和受力况.下一步的任务就是怎么综合起来,至少在数学模型方面必须抓住整个系综的关键性质.“ 如下为中国原子能科学研究院 方锦清列举: 挑战性问题之一,从理论上急待深入探索复杂动态网络的数学物理模型,建立精确的理论框架,例如,统一混合择优理论,六度分离理论,无标度特性,多标度特性和超家族特性,以及量子信息网

30、络等, 这是网络发展面临的一大课题. 挑战性问题之二,探索从随机方法,确定性方法, 到多种混合方法, 以及不同网络特性的互相转变关系, 从而构造符合实际要求和工程应用的复杂网络. 挑战性问题之三,复杂网络是否存在普遍动力学性质,是否存在更多的统计分布规律和非统计规律, 大规模复杂网络是否存在富标度特性, 它们之间有什么内在联系 挑战性问题之四,研究非线性动态复杂网络中动力学过程的时空复杂性及其主要表现形式, 包括: 相同和不同的结点动力学下,分叉,混沌,阵发混沌等及其各种广义同步.同步的产生机制分析,控制和同步问题.,面临的挑战性课题,挑战性问题之五,探索不同类型网络的非线性演化和时空斑图的涌

31、现产生的 挑战性问题之六,如何描述复杂物理机制, 为什么社会网络与技术网络和生物网络的拓扑特性差异很大 挑战性问题之七,动态网络基本性质的特征量 如何发展定量与定性分析方法,不仅需要几何描述,而且需要物理和信息等更多的描述,以便有效地刻画复杂动态网络的主要特性. 挑战性问题之八,进一步研究和发展广义随机与确定论相结合理论,交叉理论方法,非平衡统计理论方法,相变理论方法,玻色-爱因斯坦凝聚理论方法,等等,推进整体复杂动态网络研究的深入. 挑战性问题之九,复杂动态网络的应用研究,如何把复杂网络的研究成果尽快地实应用于我国实际工程,国防领域(例如无线特设通信网络等) 中去,这正是该领域深入研究的迫切

32、要求和进一步发展的推动力所在. 挑战性问题之十,生物复杂网络的研究.,software,Software,Softwarepajek (处理近千万个顶点),复杂寓于简单,在不同领域许多系统都呈自相似结构,即局部与总体相似。例如国家、河流、行星系等都是这样。 “分形”是研究自相似结构的。分形的构成常遵循一种法则:复杂的分形外形是由简单的规则重复迭代生成的。 以Koch曲线为例:将一直线三等分,中间的1 /3用一等边三角形取代。直线变为4段等长折线。每段直线再按此规则变化,一直重复下去,即生成Koch曲线,outline,小世界实验 六度分离、Erdos数、bacon数等 一些实际的复杂网络系统 Web、科学家合作网络、经济网络、交通网络、疾病传播等 复杂网络的静态几何量 度分布、聚类系数、平均路径长度等 网络拓扑的基本模型及其性质 随机网络、Small World网络、Scale Free网络等 近几年的研究态势 发展历程、会议、论文、软件、实证等,Thank you!,911,