复杂网络研究——现状与前瞻

复杂网络研究 现状与前瞻 狄增如北京师范大学管理学院系统科学系北京师范大学复杂性研究中心北京大学 2007 11 关于复杂性 关于复杂性 我们所关心的问题 大量个体 更典型的是具有适应性的主体 所组成的复杂系统 在没有中心控制 非完全信息 仅仅存在局域相互作用的条件下 通过个体之间的非线性相互作用 可以在宏观层次上涌现出一定的结构和功能 Internet 全局相互作用 晶格 相互作用与复杂性 扩散 平均场 复杂系统不能够用分析的方法去研究 必须考虑个体之间的关联和作用 理解复杂系统的行为应该从理解系统相互作用网络的拓扑结构开始 网络拓扑结构的信息是构建系统模型 研究系统性质和功能的基础 为什么研究复杂网络 复杂网络是构成复杂系统的基本框架 backbone 每一个复杂系统都可以看作是单元或个体之间的相互作用网络 复杂网络在刻画复杂性方面的重要性是由于结构和功能之间是相互影响的 复杂网络是研究复杂系统的一种角度和方法 它关注系统中个体相互关联的作用的拓扑结构 是理解复杂系统性质和功能的基础 为什么研究复杂网络 技术网络 WWW 电力网 因特网 社会网络 朋友关系网 性关系网 科学引文网 演员网 科学家合著网 交通运输网络 航空网 道路交通网 城市公共交通网 生物网络 神经网络 基因网络 蛋白质相互作用网络 生态网络 新陈代谢网络 生命金字塔 不同领域的复杂网络 社会网 演员合作网 友谊网 姻亲关系网 科研合作网 Email网生物网 食物链网 神经网 新陈代谢网 蛋白质网 基因网络信息网络 WWW 专利使用 论文引用 计算机共享技术网络 电力网 Internet 电话线路网 交通运输网 航线网 铁路网 公路网 自然河流网 Afoodweb AUnifiedApproachtowardstheConnectionTopologyofvariousComplexSystems 复杂网络 网络研究的历史 1736 欧拉 哥尼斯堡七桥1950 Erdos Renyi 随机图论1998 Strogatz Barabasi 小世界和无标度网络 为什么现在才开始研究复杂网络 计算机技术的发展 使我们拥有各种网络的数据库 并有可能对大规模的网络进行实证研究普适性的发现 许多实际网络具有相同的定性性质且已有的理论不能描述和解释理论研究的发展小世界网络 SmallWorldNetwork 无标度网络 Scale freeNetwork 统计物理学的研究手段 复杂网络研究所关心的问题 如何定量刻画复杂网络 网络结构的描述及其性质网络是如何发展成现在这种结构的 网络演化模型网络特定结构的后果是什么 网络结构的鲁棒性网络上的动力学行为和过程 复杂网络的结构 四种结构模型 规则网络随机网络小世界网络无标度网络 对网络结构的描述 几何量及其分布度 Degree 朋友的个数集聚系数 群系数 Clusteringcoefficient 朋友的朋友还是不是朋友的情况最短路径 Shortestpath 两个顶点之间边数最少的路径介数 Betweenness 经过我的最短路径的条数 一个简单的例子 K 5C 0 K 5C 1 规则网络 一般情况下 聚集系数较大 平均最短路径较长 ER随机网络 当p不太小时 聚集系数较小 平均最短路径较短 随机网络的平均最短路径及其与实证数据的比较 随机网络的平均聚集系数及其与实证数据的比较 SmallWorldNetwork C p 平均聚集系数L p 平均最短路径 度分布 分布函数f k 网络中度值为k的顶点占总点数的比例随机网络的度分布 Poisson分布 10000个顶点p 0 0015 度分布 幂律分布 PowerLaw g 3 WorldWideWeb 800milliondocuments S Lawrence 1999 Nodes WWWdocumentsLinks URLlinks NWWW 109 N k 500 103 P k 500 10 6 INTERNETBACKBONE Faloutsos FaloutsosandFaloutsos 1999 Nodes computers routersLinks physicallines Nodes actorsLinks castjointly N 212 250actors k 28 78 P k k 2 3 ACTORCONNECTIVITIES SCIENCECITATIONINDEX Nodes papersLinks citations 1736PRLpapers 1988 Nodes scientist authors Links writepapertogether Newman 2000 H Jeongetal2001 SCIENCECOAUTHORSHIP Sex web Nodes people Females Males Links sexualrelationships Liljerosetal Nature2001 4781Swedes 18 74 59 responserate Metabolicnetwork Organismsfromallthreedomainsoflifearescale freenetworks H Jeong B Tombor R Albert Z N Oltvai andA L Barabasi Nature 407651 2000 Archaea Bacteria Eukaryotes ScaleFree网络的基本特征 PowerLawDegreeDistribution 幂律度分布 1 自相似结构 2 两极分化 高度弥散 复杂网络中顶点度的匹配关系AssortativeMixingbyDegree 如果网络中度值高的顶点倾向于与其他高度值的顶点相互连接 则称网络具有同向匹配性质 例如 社会网络如果网络中度值高的顶点倾向于与度值低的顶点相互连接 则称网络具有反向匹配性质 例如 大部分生物 技术网络 同向匹配无标度网络 反向匹配无标度网络 Physicscollaborationnetwork Pallaetal Nature435 9 2005 复杂网络中的社团结构CommunityStructures 社团内部连接紧密 社团之间连接相对稀疏 SantaFe研究所的科学家合作网 Rhesus猴子网 经济物理学科学家合作网 网络模体 NetworkMotifs 模体 在网络中密度明显较高的子图 基本结构单元 复杂网络演化模型 BA模型网络增长 偏好连接基于蛋白质相互作用的演化模型复制 分化 变异优化演化模型 其形成机制是什么 结构与功能 Mostrealworldnetworkshavethesameinternalstructure Scale freenetworks BA偏好连接模型 PREFERENTIALATTACHMENT 1 Thenumberofnodes N isNOTfixed Networkscontinuouslyexpandbytheadditionofnewnodes 2 TheattachmentisNOTuniform Anodeislinkedwithhigherprobabilitytoanodethatalreadyhasalargenumberoflinks Examples WWW newdocumentslinktowellknownsites CNN YAHOO NewYorkTimes etc Citation wellcitedpapersaremorelikelytobecitedagain Examples WWW additionofnewdocumentsCitation publicationofnewpapers Scale freemodel 1 GROWTH Ateverytimestepweaddanewnodewithmedges connectedtothenodesalreadypresentinthesystem 2 PREFERENTIALATTACHMENT Theprobability thatanewnodewillbeconnectedtonodeidependsontheconnectivitykiofthatnode A L Barab si R Albert Science286 509 1999 P k k 3 网络的结构与功能 网络上的动力学行为和过程动力系统 自旋 振子或混沌的同步 可激发系统传播过程 信息传播与拥堵 网络搜寻 运输过程 疾病传播 谣言的传播 舆论形成博弈与其他社会行为 囚徒困境 少数者博弈其他过程 电力网的级联失效等 复杂网络上的渗流和网络鲁棒性 给定度分布P k 的复杂网络上的点缺陷 顶点以概率q被随机的占据 工作状态良好 或以概率1 q被空置 被破坏 然后考察系统存在无限大连通集团的临界概率qc 对无标度网络当 3 临界概率qc是0或负值 无标度网络对于顶点的随机移除非常稳健 PercolationandNetworkResilience Callywayetal 占据某个顶点的概率可以是该顶点度值k的任意函数 qk 取qk k kmax Heavisidestepfunction只需移除掉很少比例的顶点就可以完全摧毁网络中的最大连通集团 无标度网络对有目的的最大度攻击非常脆弱 ErrorandAttackTolerance 网络上的动力系统 网络同步 全局耦合下萤火虫的同步 小世界网络上混沌映象的同步 SW 随着短边重连概率的增加 同步得到加强 影响同步的结构因素 平均最短距离 度分布最大度值 最大点介数值 可激发系统 复杂网络上的疾病传播 网络上的动力学 疾病传播 EpidemicDynamicsinComplexNetworks ReachabilityinColoradoSprings Sexualcontactonly High riskactorsover4years695peoplerepresentedLongestpathis17stepsAveragedistanceisabout5stepsAveragepersoniswithin3stepsof75otherpeople137peopleconnectedthrough2independentpaths coreof30peopleconnectedthrough4independentpaths Nodesize logofdegree Drugsharingnetwork 传染病动力学 SI模型 接触数目 I S 固定人口总数的疾病传播模型 I t 易受感染者人数 总人数 传染者人数 传染比例 t EpidemicDynamics SIModel 传染病动力学 SIS模型 有效扩散速率 传染病动力学 SIR模型 疾病扩散条件 OR 网络上的疾病传播 完全混合 网络拓扑结构的影响规则网格 复杂网络 SISmodelonNetworks 网络上的疾病传播 小世界网上的SIS模型 利用平均场理论计算被感染顶点密度随时间的变化 稳态解 传播阈值 有效扩散速率 AndLetg 1 小世界网上的SIS模型 计算机数值模拟N 103 N 3 106 6 10个不同的网络 100个不同的初始分布 BA无标度网络上的SIS模型 利用平均场理论计算被感染顶点密度随时间的变化 SW BA 稳态解 BA无标度网度分布 Evolution BA无标度网络上的SIS模型 SIRModelonComplexNetworks Diseasespreading Percolation 复杂网络上的SIR模型 Diseasespreading Percolation 无标度网络上的SIR模型 复杂网络上的疾病传播 网络结构上的少数者博弈模型 少数者博弈 网络结构的影响 数值模拟结果 关于复杂网络研究现状 复杂网络研究是否已经形成并仍处于热潮之中 在复杂网络研究中有什么应该注意的问题 我们还应该继续做些什么 复杂网络研究的综述与著作 S H Strogatz Nature 410 2001 268R Albert A L Barabasi Rev Mod Phys 51 2002 1079M E J Newman SIAMRev 45 2003 167S N Dorogovtesev J Mendes EvolvingofNetworks OxfordUn Press 2003E Ben Naim etal ComplexNetworks Springer 2004S Boccaletti etal ComplexNetworks Structureanddynamics Phys Rep 424 2006 175 308Newman Barabasi Watts TheStructureandDynamicsofNetworks PrincetonUniversityPress 2006 部分由物理学推动的科研热潮 混沌和分形ChaosandFractals自旋玻璃SpinGlasses自组织临界性Self organizedcriticality统计物理学在生物进化中的应用经济物理学Econophysics复杂网络Complexnetworks 例如PerBak s关于自组织临界性的著作冠名为 HowNatureWorks中译本 大自然是如何工作的 毫无疑问 这些工作对科学的发展做出了贡献 但有些研究的意义被夸大了 波及面也各有不同 尽管自组织临界性被认为有广泛的应用价值 但研究工作事实上仅仅局限在物理学领域中 对于经济物理学 我们很少能够在经济学杂志上见到相关工作 经济物