复杂网络 PPT课件.pptx
- 文档编号:13089974
- 上传时间:2023-06-11
- 格式:PPTX
- 页数:109
- 大小:10.30MB
复杂网络 PPT课件.pptx
《复杂网络 PPT课件.pptx》由会员分享,可在线阅读,更多相关《复杂网络 PPT课件.pptx(109页珍藏版)》请在冰点文库上搜索。
,复杂网络ComplexNetwork,为什么研究复杂网络?
二十一世纪涌现的新现象,互联网是怎样“链”接的?
从一个页面到另一个页面,平均需要点击多少次鼠标?
美国航空网,城市公共交通网,为什么两者结构差异如此之大?
这种差异是必然还是偶然的?
城市交通涌堵的原因是什么?
非典发现在广州,为什么却在北京爆发呢?
传染病是怎样扩散和消失的?
互联网,病毒传播网计算机病毒是怎样传播的?
为什么“好事不出门,坏事行千里”呢?
神经网络,生态网络,电力网络,电信网络,社交网络,航空网络,Facebook全球友谊图,二十一世纪科学研究的特点,二十世纪科学研究方法:
分析、还原论;当分析为主要的研究方法时,人类关注如何将系统“分析”、“分解”,揭开系统的细部,了解是什么元素或部件组成了系统;忽视或破坏了这些元素是如何组合成系统的。
二十一世纪(二十世纪末),系统成为主要的研究对象,整合成为主要方法;整合的方法在于了解细部以后,研究“如何组合”的问题,这导致复杂网络结构的研究;如:
普列高津的耗散结构理论、哈肯的协同学、混沌和复杂系统理论、系统生物学、,复杂系统与复杂网络,复杂系统与复杂网络的概念系统:
集合(具体元素)+结构+功能系统的结构是什么?
一切系统的基础结构都是网络;一切系统的核心结构都是逻辑网络;复杂系统的结构就是复杂网络。
复杂网络是构成复杂系统的基本结构,每个复杂系统都可以看作是单元或个体之间的相互作用网络;复杂网络在刻画复杂性方面的重要性是由于结构决定功能的;复杂网络是研究复杂系统的一种角度和方法,它关注系统中因子相互关联作用的拓扑结构,是理解复杂系统性质和功能的基础。
具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络称为复杂网络。
钱学森,复杂系统与复杂网络的主要特性,1)开放性与环境和其它系统进行相互作用,交换物质、能量、信息,保持和发展系统内部的有序性与结构稳定性;在这种交换中,系统经历着从低级向高级、从简单到复杂、从无序向有序的不断优化的动态发展过程;虽然开放性是所有真实系统的基本属性,但这里的开放非指一般意义上的相互作用与交流,而开放的度量、性质、强度对复杂系统的性态、演化具有决定性的意义。
例:
人、城市网络簇。
2)涌现性即内部元素通过非线性相互作用,在宏观层次上产生出新的、元素不具有的整体属性;虽然涌现同样是所有系统都具有的,但这里涌现意味着新的整体属性的产生。
“整体大于部分之和”,如:
大脑的神经网络系统3)演化性(不可逆性)即通过与所在环境中的其它系统的相互作用和内部的自组织,使系统发展到新的阶段,表现出阶段性、临界性,完成系统演化的生命周期。
社会网络中的人、生物群体的自组织系统(鸟群),4)复杂性结构复杂性:
表现为多元性,非对称性,非均匀性,非线性分岔(Bifurcation)、混沌(Chaos)、分形Fractal;行为复杂性:
表现为学习,自适应性,混沌同步,混沌边沿,随机性等等;认识复杂性:
又称为主观复杂性,它表现为不确定性,描述复杂性与计算复杂性等等。
例:
神经网络中的突触有强有弱,可抑制也可兴奋网络复杂性:
即系统内部和系统之间的相互作用可以看成由节点、边(连接)构成的体系,出现网络复杂性、小世界特征与无标度特征等。
网络系统的复杂性,
(1)结构复杂性网络连接结构错综复杂、极其混乱,同时又蕴含着丰富的结构:
社区、基序、聚集性、生成规律性等等,而且网络连接结构可能是随时间变化的。
包括:
静态结构的复杂性和结构动态演化的复杂性。
例如:
互联网上每天都不停地有页面和链接的产生和删除。
例:
神经系统由神经元互连形成,连接以“突触连接结构”实现,突触有强弱、兴奋与抑制、不同的神经递质;连接不断改变,形成连接结构变化。
(重边,加权等),
(2)节点复杂性节点的独立或固有特性网络中的节点可能是具有分岔和混沌等复杂非线性行为的动力系统;例如:
基因网络中每个节点都具有复杂的时间演化行为;一个网络中可能存在多种不同类型的节点,比如控制哺乳动物中细胞分裂的生化网络就包含各种各样的基质和酶。
关联引发的节点特性当关联失去时这类特性会在节点处消失或改变;例如:
耦合神经元重复地被同时激活,那么它们之间的连接就会加强,这被认为是记忆和学习的基础。
(3)复杂网络之间相互影响的复杂性实际的复杂网络会受到各种各样因素的影响和作用。
例如:
电力网络故障会导致Internet网速变慢,运输系统失控等一系列不同网络间的连锁反应。
(4)网络分层结构的复杂性行政管理网络是具有层结构的,多数网络都有节点的分层结构,只是在许多网络中没有意识到是一种造成复杂性的重要结构。
对复杂网络的理解,复杂网络是二十一世纪科学研究的思想和理念,它启发我们用什么观点理解这个世界:
整个世界以及组成世界的任何细部都是由网络及其变化形成的;复杂网络也是研究复杂系统的一种技术和方法,它关注系统中个体相互作用的拓扑结构,是理解复杂系统性质和功能的基本方法。
复杂网络研究简史,格尼斯堡七桥问题,Euler(17071783),瑞士数学家,图论之父,一笔画问题,随机图理论,20世纪60年代,由两位匈牙利数学家Erds和Rnyi建立的随机图理论(randomgraphtheory)被公认为是在数学上开创了复杂网络理论的系统性研究。
Erds和Rnyi的最重要的发现:
ER随机图的许多重要性质都是突然涌现的。
即:
对于任一给定的概率p,要么几乎每一个图都具有某个性质Q(比如说,连通性),要么几乎每一个图都不具有该性质。
在20世纪的后40年中,随机图理论一直是研究复杂网络的基本理论,小世界实验,大多数人都过这样的经历:
碰到一个陌生人,同他聊了一会后发现你认识的某个人居然他也认识,然后一起发出“这个世界真小”的感叹;那么对于世界上任意两个人来说,借助第三者、第四者这样的间接关系来建立起他们两人的联系平均来说最少要通过多少人呢?
哈佛大学美国社会心理学家斯坦利米尔格伦(StanleyMilgram)在1967年实验后得出结论:
中间的联系人平均只需要5个,他把这个结论称为“六度分离”(SixDegreesofSeparation);六度分离:
平均只要通过5个人,你就能与世界任何一个角落的任何一个人发生联系。
这个结论定量地说明了我们世界的”大小”,或者说人与人关系的紧密程度;六度分离理论一直被作为社会心理学的经典范例之一。
小世界实验,米尔格伦的实验过程:
他计划通过人传人的送信方式来统计人与人之间的联系;首先把信交给志愿者A,告诉他信最终要送给收信人S;如果他不认识S,那么就送信到某个他认识的人B手里,理由是A认为在他的交集圈里B是最可能认识S的;但是如果B也不认识S,那么B同样把信送到他的一个朋友C手中,就这样一步步最后信终于到达S那里;这样就ABCS连成了一个链;斯坦利米尔格伦通过对这个链做了统计后做出了六度分离的结论。
尽管如此,实际上这个理论并没有得到严格的证实;美国心理学教授朱迪斯克兰菲尔德(JudithKleinfeld)对米尔格伦最初的实验提出不同意见,因为她发现实验的完成率极低(实际上只有三分之一的信送到了收信人那里)。
小世界实验-Bacon数,截止到最近,世界电影史上共产生了大约23万部电影,78多万名电影演员,KavinBacon在许多部电影中饰演小角色;Virginia大学的计算机专家BrettTjaden设计了一个游戏,他声称电影演员KevinBacon是电影界的中心,定义了Bacon数:
一个演员如果和KavinBacon一起演过电影,那么他(她)的Bacon数就为1;如果他(她)没有和Bacon演过电影,但是和Bacon数为1的演员一起演过电影,那么他的Bacon数就为2;依此类推。
小世界实验-Bacon数,网站http:
/www.cs.virginia.edu/oracle/的数据库里总共存有有783,940个世界各地的演员的信息,以及231,088部电影信息;通过简单地输入演员名字就可以知道这个演员的bacon数;比如输入StephenChow(周星驰)就可以得到这样的结果:
周星驰在1991年的豪门夜宴(Haomenyeyan)中与洪金宝(SammoHungKam-Bo)合作;而洪金宝又在李小龙的最后一部电影,即1978年的死亡的游戏(GameofDeath)中与ColleenCamp合作;ColleenCamp在去年的电影Trapped中与KevinBacon合作;这样周星驰的Bacon数为3。
对78万个演员所做的统计:
演员的最大Bacon数仅仅为8,平均Bacon数仅为2.948。
小世界实验-Erdos数,PaulErdos(1913-1996):
出生于匈牙利的犹太籍数学家,被公认为20世纪最伟大的天才之一;Erdos毕生发表的论文超过1500篇(在数学史上仅次于欧拉),超长的合作者名单,合作者超过450位,若加上别人所做但曾获他关键性提示之论文,则数万篇;他的研究领域主要是数论和组合数学,但他的论文中涵盖的非常多的学科;MathematicalReviews曾把数学划分为大约六十个分支,Erdos的论文涉及到了其中的40%.,小世界实验-Erdos数,定义Erdos数(Erdosnumber)的定义:
Erdos本人之Erdos数为0;任何人若曾与Erdos合写过论文,则其Erdos数为1;任何人若曾与一位Erdos数为l(且不曾与有更少的Erdos数)的人合写过论文,则他的Erdos数为2几乎每一个当代数学家都有一个有限的Erdos数,而且这个数往往非常小,小得出乎本人的预料;证明Fermat大定理的AndrewWiles,他的研究方向与Erdos相去甚远,但他的Erdos数只有3,是通过这个途径实现的:
Erdos-AndrewOdlyzko-ChrisM.Skinner-AndrewWiles.,小世界实验-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;其他领域的专家:
比尔盖兹(BillGates),他的Erdos数是4,通过如下途径实现:
Erdos-PavolHell-XiaoTieDeng-ChristosH.Papadimitriou-WilliamH.(Bill)Gates;爱因斯坦的Erdos数是2。
复杂网络研究,两篇开创性的文章可以看作是复杂网络研究新纪元开始的标志:
美国康奈尔(Cornell)大学理论和应用力学系的博士生Watts及其导师、非线性动力学专家Strogatz教授于1998年6月在Nature杂志上发表的“小世界”网络的集体动力学(CollectiveDynamicsofSmall-WorldNetworks);美国NotreDame大学物理系的Barabsi教授及其博士生Albert于1999年10月在Science杂志上发表的随机网络中标度的涌现(EmergenceofScalinginRandomNetworks)。
这两篇文章分别揭示了复杂网络的小世界特征和无标度性质,并建立了相应的模型以阐述这些特性的产生机理。
1998,Watts和Strogatz:
WS小世界网络,D.J.Watts,andS.H.Strogatz,Nature,393,440-442(1998).,60个节点组成的一个环每个节点与相邻的两个节点相连,计算网络的平均路径长度,即网络中所有节点对之间的路径长度的平均值。
规则网络的平均路径长度为15,面对面的两个点之间的信息交流会需要较长时间。
将规则网络中少量与相邻节点连接的边改成长距离连接,对图中5%的边(3条)进行重连后得到的网络,重连时3条边的一端被解开,重新连接到一个随机选择的节点上;重连后的网络与原来的规则网络的边数量一样多,但平均路径长度降到了9左右;节点数量越多,这个效应越明显。
如果是有1000个节点的规则网络,平均路径长度是250,如果5%的边重连,平均路径长度会降到20。
小世界性一个网络如果只有少量的长程连接,相对于节点数量来说平均路径却很短,则为小世界网络;自然、社会和技术演化产生的许多生物、群体和产品似乎都具有这种结构;这是为什么呢?
有人认为至少有两种相互矛盾的选择压力导致了这种结果:
在系统内快速传播信息的需要,以及产生和维持可靠的远程连接的高成本;小世界网络具有较短的平均路径长度,同时又只需相对较少的长程连接,从而解决了这两个问题。
反映到人类社会网络中,就是有一类人特别擅长交往,他们认识很多人,正是由于他们的存在,才使得六度分隔成为可能。
无标度网络(Scale-freenetwork),一种网络聚集现象,六度分隔告诉我们,人与人建立链接不是一个完全随机的过程;“人以类聚,物以群分”,复杂网络中的节点往往也呈现出集群特性:
例如,社会网络中总是存在熟人圈或朋友圈,其中每个成员都认识其他成员。
集群程度的意义是网络集团化的程度,这是一种网络的内聚倾向;连通集团反映的是一个大网络中各集聚的小网络分布和相互联系的状况。
例如,它可以反映这个朋友圈与另一个朋友圈的相互关系。
每个人认识的人数分布符合二八定律,无标度网络(Scale-freenetwork),现实世界的网络大部分都不是随机网络,少数的节点往往拥有大量的连接,而大部分节点却很少,一般而言他们符合zipf(其普夫)定律,(即:
80/20马太定律);现实中的交通网,电话网和Internet都是无标度网络;在这种网络中,存在拥有大量连接的集散节点,比如交通枢纽就是这样的节点。
人们给具有这种性质的网络起了一个特别的名字无标度网络。
这里的无标度是指网络缺乏一个特征度值(或平均度值),即节点度值的波动范围相当大。
在一般的随机网络(如ER模型)中,大部分的节点的度都集中在某个特殊值附近,形成泊松分布。
无标度网络(Scale-freenetwork),真实社会化网络的建立是一个什么过程呢?
Barabsi,Albert-Lszl提出了他们的方法,为了构造出符合幂律(PowerLaw)分布(即二八定律)的网络,他们给出了一个网络的构建过程,并把这种网络称之为无尺度网络:
网络是动态增长的,不断有新的节点加入,而不是随机网络中那样所有节点都已给出,仅仅是随机建立连接;优先情结,新增的点并不是如随机网络中那样和其他点有相同的概率建立建立连接,它会有更大的概率和已有很多连接的节点建立连接。
从最初的两个点开始,每次新增的一个绿色节点有更高的概率和已经有很多连接的节点建立连接;,优先情节在现实中也是存在的,大多数的普通人总是期望和少数的活跃用户建立间接。
一个随机网络和一个无尺度网络,右边的黑色点就是活跃用户。
无标度网络的定义按生长方式定义,网络的每个节点的连接数与此节点产生新连接的概率成增函数关系;按分布定义网络中有一定数量的连接的节点数与此连接数量成减函数。
节点连接数的zipf分布,符合zipf分布的无标度网络,A.-L.BarabasiandR.Albert,Science,286,509(1999).,1999,Barabasi和Albert:
BA无标度网络P(k)k幂律分布(一般是负指数),网络称之为无尺度网络,是相对于有尺度网络来讲的;,随机网络中每个节点有的连接数符合正态分布(左图)因为有大多数节点的连接数居中,于是我们可以称这个中值为这个网络的尺度;无尺度网络的分布符合幂律分布(右图)大多数人只有很少的连接,而有少数人有很多的连接,这个网络没有一个尺度来衡量网络中节点的距离,于是称之为无尺度网络。
无尺度网络的意义,新用户建立连接时候的有优先情节,它更倾向于与活跃用户建立连接;拥有有大量连接的活跃用户,随着网络规模的增加,连接会越来越多,也就是富者愈富;对于社交网站:
建立一个完全草根化的SNS(社交网站)是不现实的,因为人们需要活跃用户,活跃用户对SNS的拉动不容忽视;SNS中20%的人产生了80%的连接,这些人是整个网络的核心,关注这部分人的行为、喜好、特点,设计有针对性的产品会产生更好的效果;另外80%的人在网络中处于失势的地位,虽然他们有出声的权利,但是他们的声音很难成为主流。
Internet就是无尺度网络;分析Internet的度分布,Internet连接有两种:
入连接和出连接;如果我的网页有一个连接指向你的网页,而你却没有指向我,则我有一个出连接而你则有一个入连接;将网页的入连接数量称为网页的入度。
有几个研究团队都发现网页入度分布可以用非常简单的规则来描述:
入度为k的网页数量正比于1/(k2.3)。
入度1000-10000,频率0-0.000001,入度100000-1000000频率0-1*10(-10),为了解释为何Internet是”无尺度“,用三种不同的尺度画出遵循上面的规则的入度分布;x轴为入度,y轴为频率。
入度10000-100000频率0-0.00000001无尺度就是“在不同尺度下具有不变性”,对无标度网络的理解,在做实验之前,很多人都认为:
连接数k应当服从泊松分布或正态分布,即每个网站的被访问量差异不会太大,就像人类身高差异不会太大那样;Barabasi等人设计了一种软件,可以从一个节点跳到另一节点,收集并记录网上的所有连接。
在对几十万个节点进行统计后发现:
在绝大多数网站的连接数很少的情况下,却有极少数网站拥有高于普通网站百倍、千倍甚至万倍的连接数;,就像在茫茫人海中突然发现若干身高数百尺的巨人那样,令人意外。
巨人的身高之大,已不能用普通人高度的尺度来度量,于是想出了“无尺度”的一词,反映少数节点连接数超乎异常的事实。
实验结果用数学语言表达为:
出现连接数为k的概率p(k),反比于k的n次方;其中,n称为幂数,它是很接近于2的一个常数;也就是说,WWW巳成为无尺度网络(scalefreenetwork)。
无尺度现象的成因,Barabasi等人认为优先连接性和网络的成长性是两个起因成长性是指网民网页急剧增加,优先连接性是指新网民总是优先选择前人经常访问的网站;随着时间的演进,某些热门的网站愈加热门,不知名的网站愈加冷门。
信息社会同时兼有“大世界”与“小世界”两种属性网民、网页、带宽随时间快速成长,使互联网巳成为全球范围内的巨大网络;互联网是为一个个人提供服务的,每个人一天之内所能接受的信息,受到生理带宽与生理精力的限制,又是一个不随时间增长的有限世界;大世界与小世界之间,技术世界与人文世界之间存在明显的差异与矛盾。
无尺度现象的成因,信息学家认为无尺度现象反映了信息共享和物质共享存在本质差异信息共享的本质:
信源母体不限数量(scalefree)的复制(copy);物质共享的本质:
只是资源母体有限量的瓜分(share)。
随机网络与无尺度网络的抗毁性:
随机网络如果有大量结点发生故障,可能导致系统分散成多个孤岛;无尺度网络承受随机故障后的抗毁性较强,但是对于协同式攻击则更加脆弱。
复杂网络研究的简史列表,不同领域的复杂网络,社会网:
演员合作网、友谊网、姻亲关系网、科研合作网、Email网生物网:
食物链网、神经网、新陈代谢网、蛋白质网、基因网络信息网络:
WWW、专利使用、论文引用、信息共享技术网络:
电力网、Internet、电话线路网交通运输网:
航线网、铁路网、公路网、自然河流网,复杂网络研究内容,1)复杂网络模型典型的复杂网络:
随机网、小世界网、无标度网等;实际网络及其分类。
2)网络的统计量及与网络结构的相关性度分布的定义和意义,聚集性、连通性的统计量及其实际意义等。
3)复杂网络性质与结构的关系同步性、鲁棒性和稳定性与网络结构的关系。
4)复杂网络的动力学信息传播动力学、网络演化动力学、网络混沌动力学。
5)复杂网络的复杂结构社团结构、层次结构、节点分类结构等。
6)网络控制关键节点控制、主参数控制和控制的稳定性和有效性。
7)复杂网络建模机理建模、数据建模和实际系统的复杂网络正向与逆向建模。
8)复杂逻辑网络逻辑与高阶逻辑定义、分类、判定算法,高阶逻辑的实际意义等等。
复杂网络研究,突破性进展的主要原因越来越强大的计算设备和迅猛发展的Internet,使得人们开始能够收集和处理规模巨大且种类不同的实际网络数据;学科之间的相互交叉使得研究人员可以广泛比较各种不同类型的网络数据,从而揭示复杂网络的共性;以还原理论和整体论相结合为重要特色的复杂性科学的兴起,也促使人们开始从整体上研究网络的结构与性能之间的关系。
主要研究目标发现:
揭示刻画网络系统结构的统计性质,以及度量这些性质的合适方法;建模:
建立合适的网络模型以及理解网络的统计性质的意义与产生机理;分析:
基于单个节点的特性和整个网络的结构性质分析与预测网络的行为;控制:
提出改善已有网络性能和设计新的网络的有效方法,特别是稳定性、同步和数据流通等方面。
复杂网络中的基本概念,度(degree):
节点i的度ki定义为与该节点连接的其他节点的数目;直观上看,一个节点的度越大就意味着这个节点在某种意义上越“重要”(“能力大”);网络的平均度:
网络中所有节点的度和的平均值;度分布函数p(k):
随机选定节点的度为k的概率;,复杂网络中的基本概念,节点的聚类系数(簇系数):
简单图中,设节点v的邻集为N(v),|N(v)|=ki,则节点v的聚类系数定义为这ki个节点之间存在边数Ei与总的可能边数ki(ki-1)/2之比,即:
Ci=2Ei/ki(ki-1)节点v的邻点间关系的密切程度。
在随机网络中,当P较小时(P0.01),最短路径平均长度急剧下降,而聚类系数几乎没有变化。
这些网络具有较短的特征路径长度和较大的聚类系数,称其为“小世界网络”。
网络的聚类系数C:
所有节点i的聚类系数Ci的平均值,(0C1),网络中所有节点都是孤立点网络中任意节点间都有边相连,C=0C=1说明,网络节点间联系的密切程度,体现网络的凝聚力;许多大规模的实际网络都具有明显的聚类效应。
事实上,在很多类型的网络(如社会关系网络)中,你的朋友同时也是朋友的概率会随着网络规模的增加而趋向于某个非零常数,即当N时,C=O
(1);这意味着这些实际的复杂网络并不是完全随机的,而是在某种程度上具有类似于社会关系网络中“物以类聚,人以群分”的特性。
最短路径(Shortestpath):
两个节点之间边数最少的路径,最短路径的长度称为两点间的距离,用dij表示。
平均路径长度(特征路径长度)L:
所有节点对之间的距离的平均值。
d(a,b)=1;d(a,d)=1;d(a,b)=1;d(b,c)=2;d(b,d)=1;d(c,d)=2L=8*2/4*3=16/12=1.33研究发现:
尽管许多实际复杂网络的节点数巨大,网络的平均路径长度却小的惊人。
(小世界效应),介数(Betweenness),点介数:
网络中通过该节点的最短路径的条数;如果一对节点间共有B条不同的最短路径,其中有b条经过节点i,那么节点i对这对节点的介数的贡献为b/B;把节点i对所有节点对的贡献累加起来再除以节点对总数,就可得到节点i的介数。
边介数:
网络中通过该边的最短路径的条数;所有节点对的最短路径中经过该边的数量比例。
介数(Betweenness),说明:
介数反映了节点或边的作用和影响力;介数越大,说明经过该节点(边)的最短路径的数目越多;在信息传播过程中,通过该节点(边)的信息量就越大,于是就越容易发生拥塞;研究表明:
节点介数与度之间有很强的相关性,不同
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 复杂网络 PPT课件 复杂 网络 PPT 课件