复杂网络理论及其应用课件

简介:复杂网络理论及其应用2006年5月21日outline小世界实验

六度分离、Erdos数、bacon数等一些实际的复杂网络系统

Web、科学家合作网络、经济网络、交通网络、疾病传播等复杂网络的静态几何量

度分布、聚类系数、平均路径长度等网络拓扑的基本模型及其性质

随机网络、SmallWorld网络、ScaleFree网络等近几年的研究态势

发展历程、会议、论文、软件、实证等小世界实验---六度分离我们或许有过这样的经历：偶尔碰到一个陌生人，同他聊了一会后发现你认识的某个人居然他也认识，然后一起发出”这个世界真小”的感叹。那么对于世界上任意两个人来说，借助第三者、第四者这样的间接关系来建立起他们两人的联系平均来说最少要通过多少人呢？美国社会心理学家斯坦利•米尔格伦(StanleyMilgram)在1967年通过一些实验后得出结论：中间的联系人平均只需要5个。他把这个结论称为”六度分离”(sixdegreesofseparation)。六度分离:平均只要通过5个人，你就能与世界任何一个角落的任何一个人发生联系。这个结论定量地说明了我们世界的”大小”，或者说人与人关系的紧密程度。30多年来，六度分离理论一直被作为社会心理学的经典范例之一。尽管如此，实际上这个理论并没有得到严格的证实。美国心理学教授朱迪斯•克兰菲尔德(JudithKleinfeld)对米尔格伦最初的实验提出不同意见，因为她发现实验的完成率极低。小世界实验---Erdos数

PaulErdos((1913-1996)，出生于匈牙利的犹太籍数学家，被公认为本世纪最伟大的天才之一。Erdos毕生发表的论文超过1500篇（在数学史上仅次于欧拉(Euler

，1707-1783))，超长的合作者名单,合作者超过450位。但若加上别人所做但曾获他关键性的提示之论文，则他的论文应有数万篇。他的研究领域主要是数论和组合数学，但他的论文中涵盖的学科有逼近论、初等几何、集合论、概率论、数理逻辑、格与序代数结构、线性代数、群论、拓扑群、多项式、测度论、单复变函数、差分方程与函数方程、数列、Fourier分析、泛函分析、一般拓扑和代数拓扑、统计、数值分析、计算机科学、信息论等等。"MathematicalReviews"曾把数学划分为大约六十个分支，Erdos的论文涉及到了其中的40%.

小世界实验---Erdos数Erdos从来没有一固定的职位，从来不定居在一个地方，也没有结婚，带著一半空的手提箱，穿梭于学术研讨会，浪迹天涯，颇富传奇色彩。有人称他为流浪学者(wandering

scholar)。他效忠的是科学的皇后，

而非一特定的地方。各地都有热心的数学家提供他舒适的食宿，安排他的一切，他则对招待他的主人，给出一些挑战性的数学难题，或给予研究上的指导做为回馈。他可以和许多不同领域的数学家合作。数学家常将本身长久解决不了的问题和他讨论，于是很快地一篇论文便诞生了。

小世界实验---Erdos数数学家以下述方式来定义Erdos数(Erdos

number)

:

Erdos本人之Erdos数为0，任何人若曾与Erdos合写过论文，则其Erdos数为1。任何人若曾与一位Erdos数为l(且不曾与有更少的Erdos数)

的人合写过论文，

则他的Erdos数为2…几乎每一个当代数学家都有一个有限的Erdos数，而且这个数往往非常小，小得出乎本人的预料。比如说证明Fermat大定理的AndrewWiles，他的研究方向与Erdos相去甚远，但他的Erdos数只有3，是通过这个途径实现的：Erdos--AndrewOdlyzko--ChrisM.Skinner--AndrewWiles.

小世界实验---Bacon数截止到几天前，世界电影史上共产生了大约23万部电影，78多万名电影演员（参见互联网电影库）.KavinBacon在许多部电影中饰演小角色。几年前,Virginia大学的计算机专家BrettTjaden设计了一个游戏，他声称电影演员KevinBacon是电影界的中心。在游戏里定义了一个所谓的Bacon数：随便想一个演员，如果他（她）和KavinBacon一起演过电影，那么他（她）的Bacon数就为1；如果他（她）没有和Bacon演过电影，但是和Bacon数为1的演员一起演过电影，那么他的Bacon数就为2；以此类推。发现:在曾经参演的美国电影演员中，没有一个人的Bacon数超过4。小世界实验---Bacon数小世界实验---Bacon数在网上有一个网页。网站的数据库里总共存有有783940个世界各地的演员的信息以及231,088部电影信息。通过简单地输入演员名字就可以知道这个演员的bacon数。目前比如输入StephenChow（周星驰）就可以得到这样的结果：周星驰在1991年的《豪门夜宴(Haomenyeyan)》中与洪金宝(SammoHungKam-Bo)合作；而洪金宝又在李小龙的最后一部电影，即1978年的《死亡的游戏（GameofDeath）》中与ColleenCamp合作；ColleenCamp在去年的电影《Trapped》中与KevinBacon合作。这样周星驰的培根数为3。是对所有这将近78万个演员所做的统计。结果如下页所示:左边是Bacon数，右边是拥有这个Bacon数的演员个数。可以看到最大的培根数仅仅为8。平均培根数仅为2.948。小世界实验---Bacon数KavinBacon图有明确的定义（顶点和边）数据库中90%的演员被归入到一个单独的连通分支最高的有限Bacon数为8平均Bacon数为2.9注：少数演员承担了将多数演员联系在一起的工作。小世界实验---用E-mial传递,检验六度分离的假说D.watts2001年开始,18名目标对象,166个国家共6万多志愿者,平均转发5—7次outline小世界实验

六度分离、Erdos数、bacon数等一些实际的复杂网络系统

Web、科学家合作网络、经济网络、交通网络、疾病传播等复杂网络的静态几何量

度分布、聚类系数、平均路径长度等网络拓扑的基本模型及其性质

随机网络、SmallWorld网络、ScaleFree网络等近几年的研究态势

发展历程、会议、论文、软件、实证等一些实际的复杂网络系统WebInternet网络,电影演员合作网络,科学家合作网络,论文引用网络电话呼叫网络语言学网络,电力网络经济网络,交通网络疾病传播神经网络人类性关系网络,蛋白质互作用网络,蛋白质折叠关系网络……..ComplexNetworkExample:WWW-----(K.C.Claffy)

有向网络，结点：web页面，边：超链ComplexNetworkExample:

Internet

(WilliamR.Cheswick)

无向网络，结点：路由器和计算机，边：通讯设备（如电缆等）

ComplexNetworkExample:RoutesofAirlines

ComplexNetworkExample:Usenet

(NaveenJamal)ComplexNetworkExample:VLSICircuits,CNNComplexNetworkExample:Arts

一些实际的复杂网络系统Web有向网络，结点：web页面，边：超链Internet网络无向网络，结点：路由器和计算机，边：通讯设备（如电缆等）电影演员合作网络无向网络，结点：电影演员，边：两个电影演员一起演过电影科学家合作网络无向网络，结点：科学家，边：两个科学家一起发表过一篇论文论文引用网络有向网络，结点：论文，有向边：论文引用电话呼叫网络有向网络，结点：电话号码，有向边：电话呼叫语言学网络无向网络，结点：单词，边：两个词相邻，（或出现在同一个句子中，或相同语义）电力网络无向网络，结点：发电厂，电站，接转站。边：高压线经济网络,交通网络疾病传播神经网络人类性关系网络,蛋白质互作用网络,蛋白质折叠关系网络……..平均路径长度(averagepathlength)网络中两个顶点i，j之间的最短路径定义为所有连通(i,j)的通路中,所经过的其他顶点最少的一条或几条路径。两个顶点i，j之间的距离dij定义为i，j之间最短路径上的边数。网络的直径(diameter),定义为网络中任意两个顶点之间距离的最大值。网络的平均路径长度(averagepathlength),定义为网络中任意两个顶点之间距离的平均值。即：聚类系数(clusteringcoefficient)

在朋友关系网中，你的两个朋友很可能彼此也是朋友。这种属性称为网络的聚类特性。用数学化的语言来说，对于某个节点i，它的聚类系数Ci被定义为它所有相邻节点之间连的数目占可能的最大连边数目的比例。整个网络的聚类系数C则是所有节点聚类系数的平均值。在随机网络中，C=p,（由于边的分布是随机的）度分布（degreedistribution）一个顶点的度是指与此顶点连接的边的数量。在有向网络中，分为：出度，入度研究包括：度及其分布特征，度的相关性。度值的分布特征是网络的重要几何性质。规则网络各顶点度值相同，因而符合delta分布随机网络符合泊松分布大量实际网络存在幂律(power-law)形式的度分布，即无标度网络（ScaleFreeNetworks）。无标度网络包括Internet网络，电影与电视剧演员合作网络，科学家合作网络，人类性关系网络，蛋白质互作用网络，语言学网络等，同时还存在高斯型，如蛋白质折叠网络和指数衰减型的概率分布。度的相关性：Newman把它称为“匹配模式”，意思是考察度值大的点倾向于和度值大的点连接，还是倾向于和度值小的点连接。实际网络的分析表明，不同的网络存在不同的匹配模式，有正相关也有负相关。（有向网络中）基于顶点的In-Out度关联性。outline小世界实验

六度分离、Erdos数、bacon数等一些实际的复杂网络系统

Web、科学家合作网络、经济网络、交通网络、疾病传播等复杂网络的静态几何量

度分布、聚类系数、平均路径长度等网络拓扑的基本模型及其性质

随机网络、SmallWorld网络、ScaleFree网络等近几年的研究态势

发展历程、会议、论文、软件、实证等网络拓扑的基本模型及其性质

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

是否存在一个同时具有高的集聚程度,小的最短路径网络呢?对于传染病模型,平均集聚程度对应于传播的广度,平均最短距离代表的是传播的深度。因此,如果实际网络同时存在宽的广度和大的深度的话,在这样的网络上的传染病传播显然将大大高于规则网络与随机网络。1998年Watts和Strogatz为我们找到了这样的网络模型—SmallWorld网络（发表在Nature上）.现在常称为：WSmodelSmallWorld模型方法：Watts和Strogatz发现,只需要在规则网络上稍作随机改动就可以同时具备以上两个性质。改动的方法是,对于规则网络的每一个顶点的所有边,以概率p断开一个端点,并重新连接,连接的新的端点从网络中的其他顶点里随机选择,如果所选的顶点已经与此顶点相连,则再随机选择别的顶点来重连。当p=0时就是规则网络,p=1则为随机网络,对于0<p<1的情况,存在一个很大的p的区域,同时拥有较大的集聚程度和较小的最小距离。形成机制：规则网络，以概率p断开一个端点，随机连接）NW模型WSmodel的构造过程有可能破坏网络的连通性1999年NewmanandWatts提出了NW模型：用“随机化加边”替代“随机化重连”还有许多改进的模型：加点，加边，去点，去边，以及不同形式的交叉，产生多种形式的小世界模型实际的SmallWorld网络ScaleFree网络节点度服从幂律分布，就是说具有某个特定度的节点数目与这个特定的度之间的关系可以用一个幂函数近似地表示。幂函数曲线是一条下降相对缓慢的曲线，这使得度很大的节点可以在网络中存在。对于随机网络和规则网络，度分布区间非常狭窄，几乎找不到偏离节点度均值较大的点，故其平均度可以被看作其节点度的一个特征标度。在这个意义上，我们把节点度服从幂律分布的网络叫做无标度网络（scale-freenetworks），并称这种节点度的幂律分布为网络的无标度特性。ScaleFree网络1999年，Barabási和Albert给出了构造无标度网络的演化模型。形成机制：生长和择优连接取初始m0个顶点任意连接或完全连接。每一步在原网络G(t-1)的基础上加上一个新的顶点,同时加上从此顶点出发的m条边,形成新的网络G(t)。其中新加边的另一个端点按照正比于顶点度数的分布。随机选取。重复以上新加点的过程足够多步所形成的网络的各顶点的度满足幂律分布p(k)~

k^(-γ)。而且,指数γ=3与模型的参数m0,m无关。进一步的数值模拟表明,当m取某一范围内的随机数时,指数也不变。现在常称为：BAModelScaleFree网络等级网络(Hierarchicalnetwork)以模块生成等级网络实例具有:scale-free特征outline小世界实验

六度分离、Erdos数、bacon数等一些实际的复杂网络系统

Web、科学家合作网络、经济网络、交通网络、疾病传播等复杂网络的静态几何量

度分布、聚类系数、平均路径长度等网络拓扑的基本模型及其性质

随机网络、SmallWorld网络、ScaleFree网络等近几年的研究态势

发展历程、会议、论文、软件、实证等复杂网络研究简史过去讲究较小规模的网络国内外的研究情况从2002年起，国内不同学科的研究人员和青年学者对复杂网络研究的兴趣越来越浓，至今国内已召开过多次以复杂网络为主题的学术会议和论坛2004年4月在无锡组织了有40余人参加的首届全国复杂动态网络学术论坛。武汉大学在国内率先成立了校级复杂网络研究中心并于2005年春季组织了全国复杂网络学术会议2005年10月在北京召开的由中国高等学术研究中心组织的第二届全国复杂网络学术论坛一些国际著名大学（如MIT，哥伦比亚大学和密歇根大学等）已相继开设了有关复杂网络的课程，汪小帆教授也在上海交通大学为研究生开设了复杂网络课程。2006年10月武汉会议2006全国复杂网络学术会议复杂网络中理论及其应用--book复杂网络中理论及其应用--book复杂网络的主要研究内容实证研究结合应用的研究简单的如：LibraryAndInformationScienceAbstracts(LISA)图书馆与信息科学文摘库中1996年－2005年所有的英文论文数据，共109249条教育网数据教育网数据:对xzm搜集的edu数据网页数量〉1000，有376个，链接关系图教育网数据--input50个（入度大小.按网络影响因子核心站点？）教育网数据-output34个（按出度大小）情报学报Papers:ComplexNetworks

SCIpapersEIpapersPapers:Small-WorldNetworks

SCIpapersEIpapersPapers:Scale-FreeNetworks

SCIpapersEIpapers面临的挑战性课题20世纪美国最有影响的五十人物之一E.O.Wilson指出:"今天最大的挑战性,不仅是细胞生物学和生态学,而是科学的所有方面,特别是如何精确地和完全地描述复杂系统.科学家已经认识了许多类型的复杂系统.他们认为已经知道系统中大多数元素和受力况.下一步的任务就是怎么综合起来,至少在数学模型方面必须抓住整个系综的关键性质."如下为中国原子能科学研究院方锦清列举:

挑战性问题之一,从理论上急待深入探索复杂动态网络的数学物理模型,建立精确的理论框架,例如,统一混合择优理论,六度分离理论,无标度特性,多标度特性和超家族特性,以及量子信息网络等,这是网络发展面临的一大课题.挑战性问题之二,探索从随机方法,确定性方法,到多种混合方法,以及不同网络特性的互相转变关系,从而构造符合实际要求和工程应用的复杂网络.挑战性问题之三,复杂网络是否存在普遍动力学性质,是否存在更多的统计分布规律和非统计规律,大规模复杂网络是否存在富标度特性,它们之间有什么内在联系挑战性问题之四,研究非线性动态复杂网络中动力学过程的时空复杂性及其主要表现形式,