复杂网络理论及其应用上课讲义.ppt

复杂网络理论及其应用信息管理系信息管理系outlineoutlineoo小世界实验小世界实验小世界实验小世界实验 六度分离、六度分离、ErdosErdos数、数、baconbacon数等数等oo一些实际的复杂网络系统一些实际的复杂网络系统一些实际的复杂网络系统一些实际的复杂网络系统 WebWeb、科学家合作网络、经济网络、交通网络、疾病传播、科学家合作网络、经济网络、交通网络、疾病传播等等oo复杂网络的静态几何量复杂网络的静态几何量复杂网络的静态几何量复杂网络的静态几何量 度分布、聚类系数、平均路径长度等度分布、聚类系数、平均路径长度等oo网络拓扑的基本模型及其性质网络拓扑的基本模型及其性质网络拓扑的基本模型及其性质网络拓扑的基本模型及其性质 随机网络、随机网络、Small WorldSmall World网络、网络、Scale FreeScale Free网络等网络等oo近几年的研究态势近几年的研究态势近几年的研究态势近几年的研究态势 发展历程、会议、论文、软件、实证等发展历程、会议、论文、软件、实证等信息管理系信息管理系信息管理系信息管理系信息管理系信息管理系信息管理系信息管理系小世界实验小世界实验-ErdosErdos数数ooErdosErdos从来没有一固定的职位，从来不定居在一个从来没有一固定的职位，从来不定居在一个从来没有一固定的职位，从来不定居在一个从来没有一固定的职位，从来不定居在一个地方，也没有结婚，带著一半空的手提箱，穿梭于地方，也没有结婚，带著一半空的手提箱，穿梭于地方，也没有结婚，带著一半空的手提箱，穿梭于地方，也没有结婚，带著一半空的手提箱，穿梭于学术研讨会，浪迹天涯，颇富传奇色彩。有人称他学术研讨会，浪迹天涯，颇富传奇色彩。有人称他学术研讨会，浪迹天涯，颇富传奇色彩。有人称他学术研讨会，浪迹天涯，颇富传奇色彩。有人称他为流浪学者为流浪学者为流浪学者为流浪学者(wande ringscholar)(wande ringscholar)。oo他效忠的是科学的皇后，他效忠的是科学的皇后，他效忠的是科学的皇后，他效忠的是科学的皇后，而非一特定的地方。各地而非一特定的地方。各地而非一特定的地方。各地而非一特定的地方。各地都有热心的数学家提供他舒适的食宿，安排他的一都有热心的数学家提供他舒适的食宿，安排他的一都有热心的数学家提供他舒适的食宿，安排他的一都有热心的数学家提供他舒适的食宿，安排他的一切，他则对招待他的主人，给出一些挑战性的数学切，他则对招待他的主人，给出一些挑战性的数学切，他则对招待他的主人，给出一些挑战性的数学切，他则对招待他的主人，给出一些挑战性的数学难题，或给予研究上的指导做为回馈。难题，或给予研究上的指导做为回馈。难题，或给予研究上的指导做为回馈。难题，或给予研究上的指导做为回馈。oo他可以和许多不同领域的数学家合作。数学家常将他可以和许多不同领域的数学家合作。数学家常将他可以和许多不同领域的数学家合作。数学家常将他可以和许多不同领域的数学家合作。数学家常将本身长久解决不了的问题和他讨论，于是很快地一本身长久解决不了的问题和他讨论，于是很快地一本身长久解决不了的问题和他讨论，于是很快地一本身长久解决不了的问题和他讨论，于是很快地一篇论文便诞生了。篇论文便诞生了。篇论文便诞生了。篇论文便诞生了。信息管理系信息管理系小世界实验小世界实验-ErdosErdos数数oo数学家以下述方式来定义数学家以下述方式来定义数学家以下述方式来定义数学家以下述方式来定义ErdosErdos数数数数(Erdosnumber):Erdos(Erdosnumber):Erdos本人之本人之本人之本人之ErdosErdos数为数为数为数为0 0，任何人，任何人，任何人，任何人若曾与若曾与若曾与若曾与ErdosErdos合写过论文，则其合写过论文，则其合写过论文，则其合写过论文，则其ErdosErdos数为数为数为数为1 1。任何人若。任何人若。任何人若。任何人若曾与一位曾与一位曾与一位曾与一位ErdosErdos数为数为数为数为l(l(且不曾与有更少的且不曾与有更少的且不曾与有更少的且不曾与有更少的ErdosErdos数数数数)的人的人的人的人合写过论文，合写过论文，合写过论文，合写过论文，则他的则他的则他的则他的ErdosErdos数为数为数为数为22oo几乎每一个当代数学家都有一个有限的几乎每一个当代数学家都有一个有限的几乎每一个当代数学家都有一个有限的几乎每一个当代数学家都有一个有限的ErdosErdos数，而且这数，而且这数，而且这数，而且这个数往往非常小，小得出乎本人的预料。比如说证明个数往往非常小，小得出乎本人的预料。比如说证明个数往往非常小，小得出乎本人的预料。比如说证明个数往往非常小，小得出乎本人的预料。比如说证明FermatFermat大定理的大定理的大定理的大定理的Andrew WilesAndrew Wiles，他的研究方向与，他的研究方向与，他的研究方向与，他的研究方向与ErdosErdos相去甚远，但他的相去甚远，但他的相去甚远，但他的相去甚远，但他的ErdosErdos数只有数只有数只有数只有3 3，是通过这个途，是通过这个途，是通过这个途，是通过这个途径实现的：径实现的：径实现的：径实现的：Erdos-Andrew Odlyzko-Chris Erdos-Andrew Odlyzko-Chris M.Skinner-Andrew Wiles.M.Skinner-Andrew Wiles.信息管理系信息管理系小世界实验小世界实验-ErdosErdos数数oo FieldsFields奖奖奖奖得主的得主的得主的得主的ErdosErdos数都不超过数都不超过数都不超过数都不超过5 5，（只有，（只有，（只有，（只有CohenCohen和和和和GrothendieckGrothendieck的的的的ErdosErdos数是数是数是数是5 5，），），），）oo Nevanlinna Nevanlinna奖得主的奖得主的奖得主的奖得主的ErdosErdos数不超过数不超过数不超过数不超过3 3，（只有，（只有，（只有，（只有ValiantValiant的的的的ErdosErdos数是数是数是数是3 3）ooWolfWolf数学奖数学奖数学奖数学奖得主的得主的得主的得主的ErdosErdos数不超过数不超过数不超过数不超过6 6，（只有，（只有，（只有，（只有V.I.ArnoldV.I.Arnold是是是是6 6，且只有，且只有，且只有，且只有KolmogorovKolmogorov是是是是5 5，），），），）ooSteeleSteele奖的终身成就奖得主的奖的终身成就奖得主的奖的终身成就奖得主的奖的终身成就奖得主的ErdosErdos数不超过数不超过数不超过数不超过4.4.oo在具有有限在具有有限在具有有限在具有有限ErdosErdos数的人名单中往往还能发现一些其他领域数的人名单中往往还能发现一些其他领域数的人名单中往往还能发现一些其他领域数的人名单中往往还能发现一些其他领域的专家，如的专家，如的专家，如的专家，如:比尔盖兹比尔盖兹比尔盖兹比尔盖兹(Bill Gates)(Bill Gates)，他的他的他的他的ErdosErdos数是数是数是数是4 4，通过如下途径实现：通过如下途径实现：通过如下途径实现：通过如下途径实现：Erdos-Pavol Hell-Xiao Tie Erdos-Pavol Hell-Xiao Tie Deng-Christos H.Papadimitriou-William H.(Bill)Deng-Christos H.Papadimitriou-William H.(Bill)Gates.Gates.oo爱因斯坦是爱因斯坦是爱因斯坦是爱因斯坦是2.2.信息管理系信息管理系小世界实验小世界实验-Bacon-Bacon数数 oo截止到几天前，世界电影史上共产生了大约截止到几天前，世界电影史上共产生了大约2323万部电影，万部电影，7878多万名电影演员（参见互联网电多万名电影演员（参见互联网电影库影库 ）.ooKavin BaconKavin Bacon在许多部电影中饰演小角色。在许多部电影中饰演小角色。oo几年前几年前,Virginia,Virginia 大学的计算机专家大学的计算机专家Brett Brett TjadenTjaden设计了一个游戏，他声称电影演员设计了一个游戏，他声称电影演员Kevin Kevin BaconBacon是电影界的中心。是电影界的中心。oo在游戏里定义了一个所谓的在游戏里定义了一个所谓的BaconBacon数：随便想一数：随便想一个演员，如果他（她）和个演员，如果他（她）和Kavin BaconKavin Bacon一起演过一起演过电影，那么他（她）的电影，那么他（她）的BaconBacon数就为数就为1 1；如果他；如果他（她）没有和（她）没有和BaconBacon演过电影，但是和演过电影，但是和BaconBacon数数为为1 1的演员一起演过电影，那么他的的演员一起演过电影，那么他的BaconBacon数就数就为为2 2；以此类推。；以此类推。oo发现发现:在曾经参演的在曾经参演的美国电影演员美国电影演员中，没有一个中，没有一个人的人的BaconBacon数超过数超过4 4。信息管理系信息管理系小世界实验小世界实验-Bacon-Bacon数数信息管理系信息管理系小世界实验小世界实验-Bacon-Bacon数数oo在网上有一个网页在网上有一个网页http:/www.cs.virginia.edu/oracle/http:/www.cs.virginia.edu/oracle/。网站。网站的数据库里总共存有有的数据库里总共存有有783940783940个世界各地的演员的信息以及个世界各地的演员的信息以及231,088231,088部电影信息。部电影信息。oo通过简单地输入演员名字就可以知道这个演员的通过简单地输入演员名字就可以知道这个演员的baconbacon数。目数。目前比如输入前比如输入Stephen ChowStephen Chow（周星驰）就可以得到这样的结果：（周星驰）就可以得到这样的结果：周星驰在周星驰在19911991年的豪门夜宴年的豪门夜宴(Haomen yeyan)(Haomen yeyan)中与洪金宝中与洪金宝(Sammo Hung Kam-Bo)(Sammo Hung Kam-Bo)合作；而洪金宝又在李小龙的最后一合作；而洪金宝又在李小龙的最后一部电影，即部电影，即19781978年的死亡的游戏年的死亡的游戏 （Game of DeathGame of Death）中中与与 Colleen Camp Colleen Camp 合作；合作；Colleen Camp Colleen Camp 在去年的电影在去年的电影TrappedTrapped 中与中与Kevin Bacon Kevin Bacon 合作。这样周星驰的培根数为合作。这样周星驰的培根数为3 3。oo是对所有这将近是对所有这将近7878万个演员所做的统计。结果如下页所示万个演员所做的统计。结果如下页所示:左左边是边是BaconBacon数，右边是拥有这个数，右边是拥有这个BaconBacon数的演员个数。可以看数的演员个数。可以看到最大的培根数仅仅为到最大的培根数仅仅为8 8。平均培根数仅为。平均培根数仅为2.9482.948。信息管理系信息管理系小世界实验小世界实验-Bacon-Bacon数数信息管理系信息管理系小世界实验小世界实验-Bacon-Bacon数数oo Kavin Bacon Kavin Bacon图图 有明确的定义（顶点和边）有明确的定义（顶点和边）数据库中数据库中90%90%的演员被归入到一个单独的连通分支的演员被归入到一个单独的连通分支 最高的有限最高的有限BaconBacon数为数为8 8 平均平均BaconBacon数为数为2.92.9oo注：少数演员承担了将多数演员联系在一起的注：少数演员承担了将多数演员联系在一起的工作。工作。信息管理系信息管理系小世界实验小世界实验-用用用用E-mialE-mialE-mialE-mial传递传递传递传递,检验六度分离的假说检验六度分离的假说检验六度分离的假说检验六度分离的假说D.wattsD.watts20012001年开始年开始,1818名目标对象名目标对象,166166个国家共个国家共6 6万多志愿者万多志愿者,平均转发平均转发5757次次信息管理系信息管理系outlineoutlineoo小世界实验小世界实验小世界实验小世界实验 六度分离、六度分离、ErdosErdos数、数、baconbacon数等数等oo一些实际的复杂网络系统一些实际的复杂网络系统一些实际的复杂网络系统一些实际的复杂网络系统 WebWeb、科学家合作网络、经济网络、交通网络、疾病传播、科学家合作网络、经济网络、交通网络、疾病传播等等oo复杂网络的静态几何量复杂网络的静态几何量复杂网络的静态几何量复杂网络的静态几何量 度分布、聚类系数、平均路径长度等度分布、聚类系数、平均路径长度等oo网络拓扑的基本模型及其性质网络拓扑的基本模型及其性质网络拓扑的基本模型及其性质网络拓扑的基本模型及其性质 随机网络、随机网络、Small WorldSmall World网络、网络、Scale FreeScale Free网络等网络等oo近几年的研究态势近几年的研究态势近几年的研究态势近几年的研究态势 发展历程、会议、论文、软件、实证等发展历程、会议、论文、软件、实证等信息管理系信息管理系网络的拓扑性质网络的拓扑性质oo网络网络是一个包含了大量个体及个体之间相互作用的系统是一个包含了大量个体及个体之间相互作用的系统.oo任何一个网络可以抽象为一个图任何一个网络可以抽象为一个图.（最早可追溯到（最早可追溯到EulerEuler对对KonogsbergKonogsberg七七桥问题的研究）桥问题的研究）oo网络的拓扑性质：网络的拓扑性质：网络不依赖于节点的具体位置和边的具体形态就能表网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质。现出来的性质。oo图的分类图的分类:无向图无向图,有向图有向图,加权图加权图,混合图混合图oo简单图是指简单图是指:无向无向,无权无权,无重边无重边,无自环的图无自环的图.目前关于简单网络的研究结目前关于简单网络的研究结果较多果较多信息管理系信息管理系一些实际的复杂网络系统一些实际的复杂网络系统ooWebWebooInternet Internet 网络网络,oo电影演员合作网络电影演员合作网络,oo科学家合作网络科学家合作网络,oo论文引用网络论文引用网络oo电话呼叫网络电话呼叫网络oo语言学网络语言学网络,oo电力网络电力网络oo经济网络经济网络,oo交通网络交通网络oo疾病传播疾病传播oo神经网络神经网络oo人类性关系网络人类性关系网络,oo蛋白质互作用网络蛋白质互作用网络,oo蛋白质折叠关系网络蛋白质折叠关系网络oo.信息管理系信息管理系Complex Network Complex Network ExampleExample:WWW -WWW -(K.C.Claffy)(K.C.Claffy)(K.C.Claffy)(K.C.Claffy)有向网络，有向网络，有向网络，有向网络，结点：结点：结点：结点：webwebwebweb页面，边：超链页面，边：超链页面，边：超链页面，边：超链信息管理系信息管理系Complex Network Complex Network ExampleExample:Internet Internet (William R.Cheswick)(William R.Cheswick)(William R.Cheswick)(William R.Cheswick)无向网络，无向网络，无向网络，无向网络，结点：路由器和计算机，结点：路由器和计算机，结点：路由器和计算机，结点：路由器和计算机，边：通讯设备（如电缆等）边：通讯设备（如电缆等）边：通讯设备（如电缆等）边：通讯设备（如电缆等）信息管理系信息管理系Complex Network Complex Network ExampleExample:Telecomm NetworksTelecomm Networks (Stephen G.Eick)(Stephen G.Eick)(Stephen G.Eick)(Stephen G.Eick)信息管理系信息管理系 Complex Network Complex Network ExampleExample:Routes of AirlinesRoutes of Airlines信息管理系信息管理系Complex Network Complex Network ExampleExample:UsenetUsenet (Naveen Jamal)(Naveen Jamal)(Naveen Jamal)(Naveen Jamal)信息管理系信息管理系Complex Network Complex Network ExampleExample:VLSI Circuits,CNNVLSI Circuits,CNN信息管理系信息管理系Complex Network Complex Network ExampleExample:Biological NetworksBiological Networks信息管理系信息管理系Complex Network Complex Network ExampleExample:ArtsArts 信息管理系信息管理系一些实际的复杂网络系统一些实际的复杂网络系统ooWebWeb 有向网络，有向网络，结点：结点：webweb页面，边：超链页面，边：超链ooInternet Internet 网络网络 无向网络，无向网络，结点：路由器和计算机，结点：路由器和计算机，边：通讯设备（如电缆等）边：通讯设备（如电缆等）oo电影演员合作网络电影演员合作网络 无向网络，无向网络，结点：电影演员，结点：电影演员，边：两个电影演员一起演过电影边：两个电影演员一起演过电影oo科学家合作网络科学家合作网络 无向网络，无向网络，结点：科学家，结点：科学家，边：两个科学家一起发表过一篇论文边：两个科学家一起发表过一篇论文 oo论文引用网络论文引用网络 有向网络，有向网络，结点：论文，有向边：论文引用结点：论文，有向边：论文引用oo电话呼叫网络电话呼叫网络 有向网络，有向网络，结点：电话号码，有向边：电话呼叫结点：电话号码，有向边：电话呼叫oo语言学网络语言学网络 无向网络，无向网络，结点：单词，结点：单词，边：两个词相邻，（或出现在同一个句子中，或相同语义）边：两个词相邻，（或出现在同一个句子中，或相同语义）oo电力网络电力网络 无向网络，无向网络，结点：结点：发电厂，电站，接转站。发电厂，电站，接转站。边：高压线边：高压线oo经济网络经济网络,oo交通网络交通网络oo疾病传播疾病传播oo神经网络神经网络oo人类性关系网络人类性关系网络,oo蛋白质互作用网络蛋白质互作用网络,oo蛋白质折叠关系网络蛋白质折叠关系网络oo.信息管理系信息管理系outlineoutlineoo小世界实验小世界实验小世界实验小世界实验 六度分离、六度分离、ErdosErdos数、数、baconbacon数等数等oo一些实际的复杂网络系统一些实际的复杂网络系统一些实际的复杂网络系统一些实际的复杂网络系统 WebWeb、科学家合作网络、经济网络、交通网络、疾病传播、科学家合作网络、经济网络、交通网络、疾病传播等等oo复杂网络的静态几何量复杂网络的静态几何量复杂网络的静态几何量复杂网络的静态几何量 度分布、聚类系数、平均路径长度等度分布、聚类系数、平均路径长度等oo网络拓扑的基本模型及其性质网络拓扑的基本模型及其性质网络拓扑的基本模型及其性质网络拓扑的基本模型及其性质 随机网络、随机网络、Small WorldSmall World网络、网络、Scale FreeScale Free网络等网络等oo近几年的研究态势近几年的研究态势近几年的研究态势近几年的研究态势 发展历程、会议、论文、软件、实证等发展历程、会议、论文、软件、实证等信息管理系信息管理系复杂网络的静态几何量复杂网络的静态几何量oo度分布（度分布（degree distributiondegree distribution）oo聚类系数聚类系数(clustering coefficient)(clustering coefficient)oo平均路径长度平均路径长度(average path length)(average path length)n n无向网络无向网络的基本几何量有的基本几何量有:度及其分布特征度及其分布特征,度的相关性度的相关性,集聚程度及其分集聚程度及其分布特征布特征,最短距离及其分布特征最短距离及其分布特征,介数介数(Betweenness)(Betweenness)及其分布特征及其分布特征,连通连通集团的规模分布集团的规模分布n n有向网络有向网络的特殊静态几何量包括的特殊静态几何量包括:In:In 度和度和Out Out 度的分布特征度的分布特征,基于顶点的基于顶点的In-Out In-Out 度关联性度关联性,基于边的基于边的(In-Out,In-In,Out-In,Out-Out)(In-Out,In-In,Out-In,Out-Out)度关联性度关联性,双双向比向比,In,In 集团和集团和Out Out 集团的集聚程度。集团的集聚程度。n n加权网络加权网络的静态几何量包括的静态几何量包括:度及其分布特征度及其分布特征,权及其分布特征权及其分布特征,权的相权的相关性关性,权与度的相关性权与度的相关性,最短距离及其分布特征最短距离及其分布特征,介数及其分布特征与隧道介数及其分布特征与隧道现象现象,与相应无权网络的对比与相应无权网络的对比,距离关系与类聚分析距离关系与类聚分析,以及在加权网络上集以及在加权网络上集聚程度的定义及其统计性质。聚程度的定义及其统计性质。信息管理系信息管理系平均路径长度平均路径长度(average path length)(average path length)oo网络中两个顶点网络中两个顶点i i，j j之间的之间的最短路径最短路径定义为所有连通定义为所有连通(i,j)(i,j)的通路中的通路中,所经过的其他顶点最少的一条或几条路径。所经过的其他顶点最少的一条或几条路径。oo两个顶点两个顶点i i，j j之间的之间的距离距离dijdij定义为定义为i i，j j之间最短路径上的之间最短路径上的边数。边数。oo网络的直径网络的直径(diameter),(diameter),定义为网络中任意两个顶点之间定义为网络中任意两个顶点之间距离的最大值。距离的最大值。oo网络的网络的平均路径长度平均路径长度(average path length),(average path length),定义为网络定义为网络中任意两个顶点之间距离的平均值。即：中任意两个顶点之间距离的平均值。即：信息管理系信息管理系聚类系数聚类系数聚类系数聚类系数(clustering coefficient)(clustering coefficient)(clustering coefficient)(clustering coefficient)oo在朋友关系网中，你的两个朋友很可能彼此也是朋友。这在朋友关系网中，你的两个朋友很可能彼此也是朋友。这种属性称为种属性称为网络的聚类特性网络的聚类特性。oo用数学化的语言来说，对于某个用数学化的语言来说，对于某个节点节点i i，它的聚类系数，它的聚类系数CiCi被被定义为它所有相邻节点之间连的数目占可能的最大连边数定义为它所有相邻节点之间连的数目占可能的最大连边数目的比例。目的比例。oo整个网络的聚类系数整个网络的聚类系数C C则是所有节点聚类系数的平均值。则是所有节点聚类系数的平均值。oo在随机网络中，在随机网络中，C=p,C=p,（由于边的分布是随机的）（由于边的分布是随机的）信息管理系信息管理系度分布（度分布（degree distributiondegree distribution）oo一个一个顶点的度顶点的度是指与此顶点连接的边的数量。是指与此顶点连接的边的数量。oo在有向网络中，分为：出度，入度在有向网络中，分为：出度，入度oo研究包括：研究包括：度及其分布特征，度的相关性度及其分布特征，度的相关性。oo度值的分布特征是网络的重要几何性质。度值的分布特征是网络的重要几何性质。oo规则网络各顶点度值相同，因而符合规则网络各顶点度值相同，因而符合deltadelta分布分布oo随机网络符合泊松分布随机网络符合泊松分布oo大量实际网络存在幂律大量实际网络存在幂律(power-law)(power-law)形式的度分布，即无标度网络（形式的度分布，即无标度网络（Scale Scale Free NetworksFree Networks）。）。oo无标度网络包括无标度网络包括InternetInternet网络，电影与电视剧演员合作网络，科学家合作网络，电影与电视剧演员合作网络，科学家合作网络，人类性关系网络，蛋白质互作用网络，语言学网络等，同时还存在网络，人类性关系网络，蛋白质互作用网络，语言学网络等，同时还存在高斯型，如蛋白质折叠网络和指数衰减型的概率分布。高斯型，如蛋白质折叠网络和指数衰减型的概率分布。oo度的相关性度的相关性：NewmanNewman把它称为把它称为“匹配模式匹配模式”，意思是考察度值大的点倾向于，意思是考察度值大的点倾向于和度值大的点连接，还是倾向于和度值小的点连接。实际网络的分析表明，和度值大的点连接，还是倾向于和度值小的点连接。实际网络的分析表明，不同的网络存在不同的匹配模式，有正相关也有负相关。（有向网络中）不同的网络存在不同的匹配模式，有正相关也有负相关。（有向网络中）基于顶点的基于顶点的In-Out In-Out 度关联性。度关联性。信息管理系信息管理系outlineoutlineoo小世界实验小世界实验小世界实验小世界实验 六度分离、六度分离、ErdosErdos数、数、baconbacon数等数等oo一些实际的复杂网络系统一些实际的复杂网络系统一些实际的复杂网络系统一些实际的复杂网络系统 WebWeb、科学家合作网络、经济网络、交通网络、疾病传播、科学家合作网络、经济网络、交通网络、疾病传播等等oo复杂网络的静态几何量复杂网络的静态几何量复杂网络的静态几何量复杂网络的静态几何量 度分布、聚类系数、平均路径长度等度分布、聚类系数、平均路径长度等oo网络拓扑的基本模型及其性质网络拓扑的基本模型及其性质网络拓扑的基本模型及其性质网络拓扑的基本模型及其性质 随机网络、随机网络、Small WorldSmall World网络、网络、Scale FreeScale Free网络等网络等oo近几年的研究态势近几年的研究态势近几年的研究态势近几年的研究态势 发展历程、会议、论文、软件、实证等发展历程、会议、论文、软件、实证等信息管理系信息管理系网络拓扑的基本模型及其性质网络拓扑的基本模型及其性质网络拓扑的基本模型及其性质网络拓扑的基本模型及其性质oo规则网络规则网络oo随机网络随机网络ooSmall WorldSmall World网络网络ooScale FreeScale Free网络网络oo等级网络等级网络信息管理系信息管理系规则网络规则网络oo规则网络是指平移对称性晶格规则网络是指平移对称性晶格,任何一个格点的近邻数目都相同。任何一个格点的近邻数目都相同。oo各个节点的具有相同的度值各个节点的具有相同的度值oo如图为最近邻耦合网络：每个节点都与它左右的如图为最近邻耦合网络：每个节点都与它左右的K/2K/2个节点相连。个节点相连。oo对大的对大的N,K,N,K,有：聚类系数有：聚类系数C3/4,C3/4,平均路径长度平均路径长度LL无穷大无穷大oo一般地，规则网络具有大的簇系数和大的平均距离一般地，规则网络具有大的簇系数和大的平均距离信息管理系信息管理系随机网络随机网络 ooERER随机图模型：顶点的度值服从随机图模型：顶点的度值服从 Poisson distributionPoisson distribution，也称，也称，也称，也称PoissonPoisson随机图随机图oo如：如：pajekpajek的生成的生成 oo平均度：平均度：kp*Nkp*Noo平均路径长度平均路径长度Lln(N)/ln(k)Lln(N)/ln(k)oo聚类系数聚类系数:C=p 1 (:C=p 1 (由于极度稀疏由于极度稀疏)oo一般地，随机网络具有小的簇系数和小的平均距离。一般地，随机网络具有小的簇系数和小的平均距离。信息管理系信息管理系 Small World Small World模型模型 oo是否存在一个同时具有高的集聚程度是否存在一个同时具有高的集聚程度,小的最短路径网络呢小的最短路径网络呢?oo对于传染病模型对于传染病模型,平均集聚程度对应于传播的广度平均集聚程度对应于传播的广度,平均最短平均最短距离代表的是传播的深度。距离代表的是传播的深度。oo因此因此,如果实际网络同时存在宽的广度和大的深度的话如果实际网络同时存在宽的广度和大的深度的话,在这在这样的网络上的传染病传播显然将大大高于规则网络与随机样的网络上的传染病传播显然将大大高于规则网络与随机网络。网络。oo19981998年年WattsWatts和和Strogatz Strogatz 为我们找到了这样的网络模型为我们找到了这样的网络模型Small World Small World 网络（发表在网络（发表在NatureNature上）上）.oo现在常称为：现在常称为：WS modelWS model信息管理系信息管理系Small WorldSmall World模型模型oo方法：方法：WattsWatts和和Strogatz Strogatz 发现发现,只需要在规则网络上稍作随机改动就可只需要在规则网络上稍作随机改动就可以同时具备以上两个性质。以同时具备以上两个性质。oo改动的改动的方法方法是是,对于规则网络的每一个顶点的所有边对于规则网络的每一个顶点的所有边,以概率以概率p p 断开一个断开一个端点端点,并重新连接并重新连接,连接的新的端点从网络中的其他顶点里随机选择连接的新的端点从网络中的其他顶点里随机选择,如如果所选的顶点已经与此顶点相连果所选的顶点已经与此顶点相连,则再随机选择别的顶点来重连。则再随机选择别的顶点来重连。oo当当p=0 p=0 时就是规则网络时就是规则网络,p=1,p=1 则为随机网络则为随机网络,对于对于0 p 1 0 p 1 的情况的情况,存存在一个很大的在一个很大的p p 的区域的区域,同时拥有较大的集聚程度和较小的最小距离。同时拥有较大的集聚程度和较小的最小距离。oo形成机制形成机制：规则网络，以概率：规则网络，以概率p p 断开一个端点，随机连接）断开一个端点，随机连接）信息管理系信息管理系NWNW模型模型ooWS modelWS model的构造过程有可能破坏网络的连通性的构造过程有可能破坏网络的连通性oo19991999年年Newman and WattsNewman and Watts提出了提出了NWNW模型：用模型：用“随机化加边随机化加边”替代替代“随机化重连随机化重连”oo还有许多改进的模型：加点，加边，去点，去边，还有许多改进的模型：加点，加边，去点，去边，以及不同形式的交叉，产生多种形式的小世界模型以及不同形式的交叉，产生多种形式的小世界模型信息管理系信息管理系实际的实际的Small WorldSmall World网络网络信息管理系信息管理系Scale FreeScale Free网络网络 oo节点度服从幂律分布，节点度服从幂律分布，就是说具有某个特定度就是说具有某个特定度的节点数目与这个特定的度之间的关系可以用的节点数目与这个特定的度之间的关系可以用一个幂函数近似地表示。一个幂函数近似地表示。oo幂函数曲线是一条下降相对缓慢的曲线，这使幂函数曲线是一条下降相对缓慢的曲线，这使得度很大的节点可以在网络中存在。得度很大的节点可以在网络中存在。oo对于随机网络和规则网络，度分布区间非常狭对于随机网络和规则网络，度分布区间非常狭窄，几乎找不到偏离节点度均值较大的点，故窄，几乎找不到偏离节点度均值较大的点，故其平均度可以被看作其节点度的一个特征标度。其平均度可以被看作其节点度的一个特征标度。在这个意义上，我们在这个意义上，我们把节点度服从幂律分布的把节点度服从幂律分布的网络叫做无标度网络（网络叫做无标度网络（scale-free scale-free networksnetworks），并称这种节点度的幂律分布为网），并称这种节点度的幂律分布为网络的无标度特性。络的无标度特性。信息管理系信息管理系Scale FreeScale Free网络网络oo19991999年，年，Barabsi Barabsi 和和AlbertAlbert给出了构造无标度网络的演化模型。给出了构造无标度网络的演化模型。oo形成机制：形成机制：生长和择优连接生长和择优连接oo取初始取初始m0m0个顶点任意连接或完全连接。每一步在原网络个顶点任意连接或完全连接。每一步在原网络G(t-1)G(t-1)的的基础上加上一个新的顶点基础上加上一个新的顶点,同时加上从此顶点出发的同时加上从此顶点出发的m m 条边条边,形成新形成新的网络的网络G(t)G(t)。其中新加边的另一个端点按照正比于顶点度数的分。其中新加边的另一个端点按照正比于顶点度数的分布。布。oo随机选取。重复以上新加点的过程足够多步所形成的网络的各顶点随机选取。重复以上新加点的过程足够多步所形成的网络的各顶点的度满足幂律分布的度满足幂律分布p(k)p(k)k(k(-)。而且。而且,指数指数=3=3 与模型的参数与模型的参数mm0 0,m,m 无关。无关。oo进一步的数值模拟表明进一步的数值模拟表明,当当m m 取某一范围内的随机数时取某一范围内的随机数时,指数也不变。指数也不变。oo现在常称为：现在常称为：BA ModelBA Model信息管理系信息管理系Scale FreeScale Free网络网络信息管理系信息管理系等级网络等级网络(Hierarchical network)(Hierarchical network)oo以模块生成等以模块生成等级网络实例级网络实例oo具有具有:scale-freescale-free特征特征信息管理系信息管理系outlineoutlineoo小世界实验小世界实验小世界实验小世界实验 六度分离、六度分离、ErdosErdos数、数、baconbacon数等数等oo一些实际的复杂网络系统一些实际的复杂网络系统一些实际的复杂网络系统一些实际的复杂网络系统 WebWeb、科学家合作网络、经济网络、交通网络、疾病传播、科学家合作网络、经济网络、交通网络、疾病传播等等oo复杂网络的静态几何量复杂网络的静态几何量复杂网络的静态几何量复杂网络的静态几何量 度分布、聚类系数、平均路径长度等度分布、聚类系数、平均路径长度等oo网络拓扑的基本模型及其性质网络拓扑的基本模型及其性质网络拓扑的基本模型及其性质网络拓扑的基本模型及其性质 随机网络、随机网络、Small WorldSmall World网络、网络、Scale FreeScale Free网络等网络等oo近几年的研究态势近几年的研究态势近几年的研究态势近几年的研究态势 发展历程、会议、论文、软件、实证等发展历程、会议、论文、软件、实证等信息管理系信息管理系复杂网络研究简史复杂网络研究简史过去讲究较小规模的网络信息管理系信息管理系国内外的研究