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

简介 复杂网络理论及其应用 王继民2006年5月21日 outline 小世界实验六度分离 Erdos数 bacon数等一些实际的复杂网络系统Web 科学家合作网络 经济网络 交通网络 疾病传播等复杂网络的静态几何量度分布 聚类系数 平均路径长度等网络拓扑的基本模型及其性质随机网络 SmallWorld网络 ScaleFree网络等近几年的研究态势发展历程 会议 论文 软件 实证等 小世界实验 六度分离 我们或许有过这样的经历 偶尔碰到一个陌生人 同他聊了一会后发现你认识的某个人居然他也认识 然后一起发出 这个世界真小 的感叹 那么对于世界上任意两个人来说 借助第三者 第四者这样的间接关系来建立起他们两人的联系平均来说最少要通过多少人呢 美国社会心理学家斯坦利 米尔格伦 StanleyMilgram 在1967年通过一些实验后得出结论 中间的联系人平均只需要5个 他把这个结论称为 六度分离 sixdegreesofseparation 六度分离 平均只要通过5个人 你就能与世界任何一个角落的任何一个人发生联系 这个结论定量地说明了我们世界的 大小 或者说人与人关系的紧密程度 30多年来 六度分离理论一直被作为社会心理学的经典范例之一 尽管如此 实际上这个理论并没有得到严格的证实 美国心理学教授朱迪斯 克兰菲尔德 JudithKleinfeld 对米尔格伦最初的实验提出不同意见 因为她发现实验的完成率极低 小世界实验 六度分离 米尔格伦的实验过程是 他计划通过人传人的送信方式来统计人与人之间的联系 首先把信交给志愿者A 告诉他信最终要送给收信人S 如果他不认识S 那么就送信到某个他认识的人B手里 理由是A认为在他的交集圈里B是最可能认识S的 但是如果B也不认识S 那么B同样把信送到他的一个朋友C手中 就这样一步步最后信终于到达S哪里 这样就从A到B到C到 最后到S连成了一个链 斯坦利 米尔格伦就是通过对这个链做了统计后做出了六度分离的结论 然而在这个实验中 实际上只有三分之一的信送到了收信人哪里 因此实验的完成率很低 小世界实验 Erdos数 PaulErdos 1913 1996 出生于匈牙利的犹太籍数学家 被公认为本世纪最伟大的天才之一 Erdos毕生发表的论文超过1500篇 在数学史上仅次于欧拉 Euler 1707 1783 超长的合作者名单 合作者超过450位 但若加上别人所做但曾获他关键性的提示之论文 则他的论文应有数万篇 他的研究领域主要是数论和组合数学 但他的论文中涵盖的学科有逼近论 初等几何 集合论 概率论 数理逻辑 格与序代数结构 线性代数 群论 拓扑群 多项式 测度论 单复变函数 差分方程与函数方程 数列 Fourier分析 泛函分析 一般拓扑和代数拓扑 统计 数值分析 计算机科学 信息论等等 MathematicalReviews 曾把数学划分为大约六十个分支 Erdos的论文涉及到了其中的40 小世界实验 Erdos数 Erdos从来没有一固定的职位 从来不定居在一个地方 也没有结婚 带著一半空的手提箱 穿梭于学术研讨会 浪迹天涯 颇富传奇色彩 有人称他为流浪学者 wanderingscholar 他效忠的是科学的皇后 而非一特定的地方 各地都有热心的数学家提供他舒适的食宿 安排他的一切 他则对招待他的主人 给出一些挑战性的数学难题 或给予研究上的指导做为回馈 他可以和许多不同领域的数学家合作 数学家常将本身长久解决不了的问题和他讨论 于是很快地一篇论文便诞生了 小世界实验 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 在具有有限Erdos数的人名单中往往还能发现一些其他领域的专家 如 比尔盖兹 BillGates 他的Erdos数是4 通过如下途径实现 Erdos PavolHell XiaoTieDeng ChristosH Papadimitriou WilliamH Bill Gates 爱因斯坦是2 小世界实验 Bacon数 截止到几天前 世界电影史上共产生了大约23万部电影 78多万名电影演员 参见互联网电影库 KavinBacon在许多部电影中饰演小角色 几年前 Virginia大学的计算机专家BrettTjaden设计了一个游戏 他声称电影演员KevinBacon是电影界的中心 在游戏里定义了一个所谓的Bacon数 随便想一个演员 如果他 她 和KavinBacon一起演过电影 那么他 她 的Bacon数就为1 如果他 她 没有和Bacon演过电影 但是和Bacon数为1的演员一起演过电影 那么他的Bacon数就为2 以此类推 发现 在曾经参演的美国电影演员中 没有一个人的Bacon数超过4 小世界实验 Bacon数 小世界实验 Bacon数 在网上有一个网页http www cs virginia edu oracle 网站的数据库里总共存有有783940个世界各地的演员的信息以及231 088部电影信息 通过简单地输入演员名字就可以知道这个演员的bacon数 目前比如输入StephenChow 周星驰 就可以得到这样的结果 周星驰在1991年的 豪门夜宴 Haomenyeyan 中与洪金宝 SammoHungKam Bo 合作 而洪金宝又在李小龙的最后一部电影 即1978年的 死亡的游戏 GameofDeath 中与ColleenCamp合作 ColleenCamp在去年的电影 Trapped 中与KevinBacon合作 这样周星驰的培根数为3 是对所有这将近78万个演员所做的统计 结果如下页所示 左边是Bacon数 右边是拥有这个Bacon数的演员个数 可以看到最大的培根数仅仅为8 平均培根数仅为2 948 小世界实验 Bacon数 小世界实验 Bacon数 KavinBacon图有明确的定义 顶点和边 数据库中90 的演员被归入到一个单独的连通分支最高的有限Bacon数为8平均Bacon数为2 9注 少数演员承担了将多数演员联系在一起的工作 小世界实验 用E mial传递 检验六度分离的假说 D watts2001年开始 18名目标对象 166个国家共6万多志愿者 平均转发5 7次 outline 小世界实验六度分离 Erdos数 bacon数等一些实际的复杂网络系统Web 科学家合作网络 经济网络 交通网络 疾病传播等复杂网络的静态几何量度分布 聚类系数 平均路径长度等网络拓扑的基本模型及其性质随机网络 SmallWorld网络 ScaleFree网络等近几年的研究态势发展历程 会议 论文 软件 实证等 网络的拓扑性质 网络是一个包含了大量个体及个体之间相互作用的系统 任何一个网络可以抽象为一个图 最早可追溯到Euler对Konogsberg七桥问题的研究 网络的拓扑性质 网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质 图的分类 无向图 有向图 加权图 混合图简单图是指 无向 无权 无重边 无自环的图 目前关于简单网络的研究结果较多 一些实际的复杂网络系统 WebInternet网络 电影演员合作网络 科学家合作网络 论文引用网络电话呼叫网络语言学网络 电力网络经济网络 交通网络疾病传播神经网络人类性关系网络 蛋白质互作用网络 蛋白质折叠关系网络 ComplexNetworkExample WWW K C Claffy 有向网络 结点 web页面 边 超链 ComplexNetworkExample Internet WilliamR Cheswick 无向网络 结点 路由器和计算机 边 通讯设备 如电缆等 ComplexNetworkExample TelecommNetworks StephenG Eick ComplexNetworkExample RoutesofAirlines ComplexNetworkExample Usenet NaveenJamal ComplexNetworkExample VLSICircuits CNN ComplexNetworkExample BiologicalNetworks ComplexNetworkExample Arts 一些实际的复杂网络系统 Web有向网络 结点 web页面 边 超链Internet网络无向网络 结点 路由器和计算机 边 通讯设备 如电缆等 电影演员合作网络无向网络 结点 电影演员 边 两个电影演员一起演过电影科学家合作网络无向网络 结点 科学家 边 两个科学家一起发表过一篇论文论文引用网络有向网络 结点 论文 有向边 论文引用电话呼叫网络有向网络 结点 电话号码 有向边 电话呼叫语言学网络无向网络 结点 单词 边 两个词相邻 或出现在同一个句子中 或相同语义 电力网络无向网络 结点 发电厂 电站 接转站 边 高压线经济网络 交通网络疾病传播神经网络人类性关系网络 蛋白质互作用网络 蛋白质折叠关系网络 outline 小世界实验六度分离 Erdos数 bacon数等一些实际的复杂网络系统Web 科学家合作网络 经济网络 交通网络 疾病传播等复杂网络的静态几何量度分布 聚类系数 平均路径长度等网络拓扑的基本模型及其性质随机网络 SmallWorld网络 ScaleFree网络等近几年的研究态势发展历程 会议 论文 软件 实证等 复杂网络的静态几何量 度分布 degreedistribution 聚类系数 clusteringcoefficient 平均路径长度 averagepathlength 无向网络的基本几何量有 度及其分布特征 度的相关性 集聚程度及其分布特征 最短距离及其分布特征 介数 Betweenness 及其分布特征 连通集团的规模分布有向网络的特殊静态几何量包括 In度和Out度的分布特征 基于顶点的In Out度关联性 基于边的 In Out In In Out In Out Out 度关联性 双向比 In集团和Out集团的集聚程度 加权网络的静态几何量包括 度及其分布特征 权及其分布特征 权的相关性 权与度的相关性 最短距离及其分布特征 介数及其分布特征与隧道现象 与相应无权网络的对比 距离关系与类聚分析 以及在加权网络上集聚程度的定义及其统计性质 平均路径长度 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上 现在常称为 WSmodel SmallWorld模型 方法 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取某一范围内的随机数时 指数也不变 现在常称为 BAModel ScaleFree网络 等级网络 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个 链接关系图 教育网数据 input 50个 入度大小 按网络影响因子核心站点 教育网数据 output 34个 按出度大小 情报学报 Papers ComplexNetworks SCIpapersEIpapers Papers Small WorldNetworks SCIpapersEIpapers Papers Scale FreeNetworks SCIpapersEIpapers 面临的挑战性课题 20世纪美国最有影响的五十人物之一E O Wilson指出 今天最大的挑战性 不仅是细胞生物学和生态学 而是科学的所有方面 特别是如何精确地和完全地描述复杂系统 科学家已经认识了许多类型的复杂系统 他们认为已经知道系统中大多数元素和受力况 下一步的任务就是怎么综合起来 至少在数学模型方面必须抓住整个系综的关键性质 如下为中国原子能科学研究院方锦清列举 挑战性问题之一 从理论上急待深入探索复杂动态网络的数学物理模型 建立精确的理论框架 例如 统一混合择优理论 六度分离理论 无标度特性 多标度特性和超家族特性 以及量子信息网络等 这是网络发展面临的一大课题 挑战性问题之二 探索从随机方法 确定性方法 到多种混合方法 以及不同网络特性的互相转变关系 从而构造符合实际要求和工程应用的复杂网络 挑战性问题之三 复杂网络是否存在普遍动力学性质 是否存在更多的统计分布规律和非统计规律 大规模复杂网络是否存在富标度特性 它们之间有什么内在联系挑战性问题之四 研究非线性动态复杂网络中动力学过程的时空复杂性及其主要表现形式 包括 相同和不同的结点动力学下 分叉 混沌 阵发混沌等及其各种广义同步 同步的产生机制分析 控制和同步问题 面临的挑战性课题 挑战性问题之五 探索不同类型网络的非线性演化和时空斑图的涌现产生的挑战性问题之六 如何描述复杂物理机制 为什么社会网络与技术网络和生物网络的拓扑特性差异很大挑战性问题之七 动态网络基本性质的特征量如何发展定量与定性分析方法 不仅需要几何描述 而且需要物理和信息等更多的描述 以便有效地刻画复杂动态网络的主要特性 挑战性问题之八 进一步研究和发展广义随机与确定论相结合理论 交叉理论方法 非平衡统计理论方法 相变理论方法 玻色 爱因斯坦凝聚理论方法 等等 推进整体复杂动态网络研究的深入 挑战性问题之九 复杂动态网络的应用研究 如何把复杂网络的研究成果尽快地实应用于我国实际工程 国防领域 例如无线特设通信网络等 中去 这正是该领域深入研究的迫切要求和进一步发展的推动力所在 挑战性问题之十 生物复杂网络的研究 software Software Software pajek 处理近千万个顶点 复杂寓于简单 在不同领域许多系统都呈自相似结构 即局部与总体相似 例如国家 河流 行星系等都是这样 分形 是研究自相似结构的 分形的构成常遵循一种法则 复杂的分形外形是由简单的规则重复迭代生成的 以Koch曲线为例 将一直线三等分 中间的1 3用一等边三角形取代 直线变为4段等长折线 每段直线再按此规则变化 一直重复下去 即生成Koch曲线 outline 小世界实验六度分离 Erdos数 bacon数等一些实际的复杂网络系统Web 科学家合作网络 经济网络 交通网络 疾病传播等复杂网络的静态几何量度分布 聚类系数 平均路径长度等网络拓扑的基本模型及其性质随机网络 SmallWorld网络 ScaleFree网络等近几年的研究态势发展历程 会议 论文 软件 实证等 Thankyou 911