第5卷第4期 复杂系统与复杂性科学 Vol 5 No 4 008年12月 COMPLEX SYSTEMS AND COMPLEXITY SCIENCE Dec.2008 文章编号:1672-3813(2008)04-0001-20 网络科学的理论模型及其应用课题研究的若干进展 方锦清',汪小帆2,郑志刚 (1.中国原子能科学研究院,北京102413;2.上海交通大学自动化系,上海200240;3.北京师范大学物理系,北京100875) 摘要:概述了“一院两校”网络科学联合项目组在复杂网络的理论模型及相关应用 课题近年来的若干研究进展。首先,基于国际上三大经典的复杂网络模型(ER随 机图,小世界模型和无标度模型),结合统一混合理论框架里3个模型(和谐统一 的混合择优模型 混合网络模型和统一混合变速增加长模型),提出构建 描述和评论了网络科学模型金字塔;其次,把宏观网络推进到微观网络模型(量子 信息网络与纳米相干网络);然后概述了規则网络的非局域连接模型及其相关的 社区网络、属性连接的网络模型;含权科学家合作网络模型和提高网络冋步能力的模型等。相关应 用课题的进展包括:小世界和无标度拓扑下束流输运网络中柬晕一混沌同步与控制、复杂混沌网络 的多目标分区同步的控制及同步能力、多智能体网络系统、网络上的交通拥塞与路由问題、网络上 的病毒传播问题、网络上的博弈问题,以及高科技企业网络等。这些进展反映和揭示了当前国内外 网络科学同步发展的趋势和面临的挑战。 关键词:网络科学;理论楼型:网络金字塔;小世界效应;无标度特性;动力学复杂性;应用相关课题 中图分类号:0231.3;N93 文献标识码:A Several Advances in Theoretical Modeling and related Application Subjects for Network Science FANG Jin-qing, WANG Xiao-fan, ZHENG Zhi-gang (1. China Institute of Atomic Energy, Beijing 102413, China; 2. Department of Automation, Shanghai Jiaotong University Shanghai 200240, China; 3. Physics Department, Beijing Normal University, Beijing 100875, China) Abstract This review puts emphasis on a description of main progresses in theoretical modeling and as- sociated with application subjects of network science supported by the key program of National Nature Sci ence Foundation of China for our united network research group of"One Institute and Two Universities China Institute of Atomic Energy, Shanghai Jiaotong University and Beijing Normal University ) First ly, based on deep analysis of three milestones of network science work theoretical frame with three models( Harmonious unifying hybrid preferential network model, Large unified hybrid network model and unified hybrid network model with variable speed growing ) complex network model pyramid is suggested, described and summarized briefly. Secondly, theoretical model of the macro-network is impelled toward micro-network, the quantum information network model and the 收稿日期:2008-08-28 基金项目:国家自然基金重点资助项目(70431002) 作者简介:方锦清(1939-),男,福建莆田人,研究员,博导,主要研究方向为网络科学与非线性-复杂性科学
第 5卷第 4期 2008年 12月 复 杂 系 统 与 复 杂 性 科 学 C0MPLEX SYSTEMSAND C0MPLEXITY SCm NCE Vol_5 Dec． NO．4 2008 文 章 编 号 ：1672—3813(2008)04—0001—20 网络科学的理论模 型及其应用课题研究的若干进展 方锦清 ，汪小帆 ，郑志刚 (1．中 国原 子 能科 学 研 究 院 ，北 京 102413；2．上 海 交 通 大 学 自动化 系 ，上 海 200240；3．北 京 师范 大 学 物 理 系 ，北 京 100875) 摘要 ：概 述 了“一 院两校” 网络科 学联合 项 目组在 复杂 网络的理论模 型及相 关应 用 课 题近年 来的若 干研 究进展 。首 先 ，基 于 国际上 三 大经典 的 复杂 网络模 型 (ER随 机 图，小世界模 型和无标 度模 型 )，结合 统 一混 合 理论 框 架 里 3个模 型 (和谐 统 一 的混合择 优模型 、大统 一 混合 网络模 型 和统 一 混合 变速增 加 长模 型 )，提 出构建 、 描述和 评论 了网络科 学模 型金 字塔 ；其 次 ，把 宏观 网络推 进 到微 观 网络模 型 (量子 信 息网络与纳 米相干 网络 )；然后 概述 了规 则 网络 的非 局域 连接 模 型 及其 相 关的 社 区网络 、属性 连接 的网络模型 ；含权科 学 家合作 网络模 型和提 高 网络 同步能力 的模 型等 。相关应 用课题 的进展 包括 ：小世界 和无标 度拓扑 下束流 输运 网络 中束 晕 一混沌 同步与控 制、复杂 混沌 网络 的多 目标分 区同步的控 制及 同步 能力 、多智能体 网络 系统 、网络 上 的 交通拥 塞与路 由 问题 、网络 上 的病毒传播 问题 、网络 上的博 弈问题 ，以及 高科技 企业 网络等 。这些进展 反映和揭 示 了3"-前 国内外 网络科学 同步发展 的趋 势和 面临的挑战 。 关键 词 ：网络科 学 ；理论 模型 ；网络金 字塔 ；小世界 效应 ；无标度特 性 ；动 力学复杂性 ；应 用相 关课 题 中图分 类号 ：0231．3：N93 文 献标识码 ：A SeveralAdvancesin TheoreticalM odeling and Related ApplicationSubjectsforNetworkScience FANG Jin—qing ，W ANG Xiao．fan ，ZHENG Zhi—gang (1．ChinaInstituteofAtomicEnergy，Beijing102413，China；2．DepartmentofAutomation，ShanghaiJiaotongUniversity， Shanghai200240，China；3．PhysicsDepartment，BeijingNormalUniversity，Beijing100875，China) Abstract：Thisreview putsemphasison adescription ofmain progressesin theoreticalmodelingandas— sociatedwithapplicationsubjectsofnetworksciencesupportedbythekeyprogramofNationalNatureSci— enceFoundationofChinaforourunited network research groupof“OneInstitute and TwoUniversities” (ChinaInstituteofAtomicEnergy，ShanghaiJiaotongUniversityandBeijingNormalUniversity)．First— ly，basedondeepanalysisofthreemilestonesofnetwork sciencedevelopmentand theunifiedhybridnetworktheoreticalflamewiththreemodels(Harmoniousunifyinghybridpreferentialnetworkmodel，Large unifiedhybridnetworkmodelandunifiedhybridnetworkmodelwithvariablespeedgrowing)，complex network modelpyramid issuggested，described and summarized briefly． Secondly，theoreticalmodelof themacro．network is impelled toward micro—network，the quantum information network modeland the 收 藕 日期 ：2008—08—28 基金项 目：国家 自然基金重点资助项 目(70431002) 作者简介 ：方锦清(1939一)，男，福建莆田人 ，研究员 ，博导 ，主要研究方向为网络科学 与非线性 一复杂性科学
2 复杂系统与复杂性科学 008年12月 hexagonal nanowire coherent network are proposed and investigated Thirdly, a regular network model with only a few nonlocal couplings is proposed, partial synchronization is numerically and theoretically discussed and applied to discussions of synchronizations between sparsely coupled communities. Then the scientist cooperation evolution model and some models/methods of improved network synchronizability are briefly introduced. Associated with application subjects of network include synchronization and control of halo-chaos in transport network with small-world or scale-free topology, multi-goal control in different b-networks connected by chaotic dynamics, multiple intelligent agent system, traffic and routing prob- lem on the internet, spreading problem and gaming on the networks, high-tech networks and so on These topic advances basically reflect and reveal development trend of network science research and face severe challenges at home and abroad Key words: network science; theoretical modeling; network pyramid; small-world effect; scale-free dy- ociated subject with application of complex network 1引言 自然界和人类社会中网络无处不在,五彩缤纷,触手可及,应用广泛。自从1998年 Watts与 Stroma 1999年 Barabasi与 Albert3*分别发现了小世界(SW)网络和无标度(SF)网络以来,国内外复杂网 络取得了突飞猛进的进展,网络科学及其应用研究已经成为当前国内外的一个前沿热点课题,具有巨 大的应用前景。在国内外推动和国家自然科学基金的支持下,中国原子能科学研究院(CIAE),上海交通大 学(SJTU)和北京师范大学(BNU)共同组成网络科学联合研究组,简称“一院两校”,近年来开展了非线性复 杂网络的动力学复杂性硏究,该项目涉及物理科学、计算机与信息科学、应用数学、社会经济科学等众多广泛 交叉的科学。为了探索和科学理解复杂网络的定性特征与定量规律,我们以非线性动态复杂网络系统作为 主要研究对象,结合物理系统、互联网、科学家合作网、高科技网络及相关社会网络等若干典型的复杂网络 提出和建立合理的网络理论框架,探索复杂网络的复杂性与普适性,研究复杂网络的动力学同步与控制方 法,包括完全同步和广义(部分)同步、同步化能力、物理机制及其转变规律,探索网络拓扑结构与网络动力 学之间的关系,研究与复杂网络应用相关的课题,包括复杂网络上的拥塞与路由问题、拥塞与博弈问题、病毒 传播等 小世界效应和无标度特性两项开创性的理论工作为复杂网络理论研究奠定了基础,由此诞生了一门广 泛交叉的科学——网络科学·,标志着复杂网络研究进入了网络科学的新时代。美国20世纪50名有影响 的科学家之一的E.0.Wlon指出:“今天最大的挑战性,不仅是细胞生物学和生态学,而是科学的所有方 面,特别是如何精确地和完全地描述复杂系统。……下一步的任务就是怎么综合起来,至少在数学模型方面 必须抓住整个系综的关键性质。”国内外发屐表明:网络科学的理论模型及其应用的探索是最具挑战性课 题。为此,我们联合组已经探索了若干有意义的网络理论模型和相关应用课题。根据目前初步统计,迄今整 个项目组已经发表了100多篇论文,分别发表在 Phys Rev E(物理评论E), Phys Lett A(物理快报A),Eun phys Lett(欧洲物理快报), Phys A,(物理A), Advance in Complex Systems(复杂系统进展), Int J Moder Phys B(国际现代物理B), Chin Sci g(中国科学G), Chin Phys Lett(中国物理快报), Commn Theor Phys(理论物 理通讯), Chin Phys(中国物理), IEEE Transactions on Systems(IEEE电路与系统汇刊),中国科学、物理学进 展、物理学报、自然科学进展、复杂系统与复杂性科学、科技导报、计算机工程与应用、系统工程学报、通信学 报等20多种国内外刊物上,这些成果反映了本项目取得的有意义的进展,本文只是简介和评述近年的主要 进展概况。 2探索网络模型金字塔及其奥妙 网络科学的发展迄今经历了3个里程碑-212-13,每个里程碑无一不是从理论模型首先取得突破的
· 2· 复 杂 系 统 与 复 杂 性 科 学 2008年 l2月 hexagonalnanowirecoherentnetwork are proposed and investigated． Thirdly，a regularnetwork model with only a few nonlocalcouplingsisproposed，partialsynchronization isnumerically and theoretically discussed andappliedtodiscussionsofsynchronizationsbetweensparselycoupledco,mmunities．Thenthe scientistcooperation evolution modeland somemodels／methodsofimprovednetwork synchronizabiltyare brieflyintroduced．Associatedwithapplicationsubjectsofnetworkinclude：synchronizationandcontrolof halo—chaosin transportnetwork with small-world orscale—free topology， multi—goalcontrolin diferent sub·networksconnected bychaoticdynamics，multipleintelligentagentsystem，trafficand routing prob— lem on the internet， spreading problem and gaining on the networks，high—tech networks and SO on． Thesetopicadvancesbasically reflectandrevealdevelopmenttrendofnetwork scienceresearchandface severechallengesathomeand abroad． Key words： network science；theoreticalmodeling；network pyramid；small—world effect；scale—free；dy— namicalcomplexityanduniversality；associatedsubjectwithapplicationofcomplexnetwork 1 引言 自然界 和人类社 会 中 网 络 无 处 不 在 ，五 彩 缤 纷 ，触 手 可 及 ，应 用 广 泛 。 自从 1998年 Watts与 Stroga． tz 。 、 1999年 Barabasi与 Albert 分别发现 了小世 界 (SW )网络 和无 标 度 (SF)网络 以来 ，国 内外 复 杂 网 络取 得 了突 飞猛进 的进展 ，网络科 学及 其 应用研 究 已经 成 为 当前 国内外 的一 个前 沿热 点 课题 ，具 有 巨 大的应用前景 。在 国内外推动 和 国家 自然科学 基金 的支 持下 ，中国原 子能 科学 研究 院 (CIAE)，上 海交 通 大 学 (SJTU)和北 京师范大 学 (BNU)共 同组 成 网络 科学联 合研 究组 ，简称 “一 院两校 ”，近年 来开 展 了非线 性 复 杂网络 的动 力学复 杂性 研究 ，该 项 目涉 及物理 科学 、计算 机 与信息科学 、应用数学 、社会经 济科学等 众多广泛 交 叉的科学 。为 了探 索和科学理 解 复杂网络 的定性特 征与 定量规 律 ，我们 以非线 性 动态 复杂 网络 系统 作 为 主要研究对 象 ，结 合物理 系统 、互联 网 、科 学 家合作 网 、高科技 网络 及相 关社 会 网络 等若 干典 型 的复杂 网络 ， 提 出和建立 合理 的网络理论 框架 ，探索 复 杂 网络 的复 杂性 与普 适 性 ，研究 复 杂 网络 的动 力学 同步 与控 制方 法 ，包括 完全 同步 和广义 (部分 )同步 、同步化 能力 、物 理机 制及其 转变 规律 ，探索 网络 拓扑结 构 与 网络 动 力 学之间 的关 系 ，研 究与复杂 网络应用 相关 的课 题 ，包括 复杂 网络上 的拥 塞与路 由问题 、拥 塞与博弈 问题 、病 毒 传播等 。 小世 界效应 和无标度特性 两项 开创性 的理论工作 为复 杂 网络理论 研究 奠 定 了基础 ，由此 诞 生 了一 门广 泛交叉 的科学—— 网络科学 ，标 志着 复杂 网络 研究进 入 了网络科 学 的新 时代 。美 国 20世 纪 50名有 影 响 的科学家 之一的 E．O．Wilson指 出… ：“今天最 大的挑 战性 ，不仅是 细胞生 物学 和生 态学 ，而是科学 的所 有方 面 ，特别 是如何精 确地和完 全地 描述 复杂 系统 。 ……下一步 的任务就是 怎么综 合起来 ，至少在数学 模型方 面 必须抓住 整个系综 的关键性 质 。”国 内外 发 展表 明 ：网络 科 学 的理 论模 型及 其应 用 的探 索 是 最 具挑 战性 课 题。为此 ，我们联合 组 已经探 索 了若 干有意 义的 网络 理论模 型和相关应 用 课题 。根据 目前 初步统 计 ，迄今 整 个项 目组 已经发表 了 100多篇论 文 ，分 别发表在 PhysRevE(物理评论 E)，PhysLettA (物理快 报 A)，Eur physLett(欧洲物 理快报 )，PhysA，(物 理 A)，AdvanceinComplexSystems(复杂 系统 进展 )，IntJModerPhys B(国际现代物理 B)，ChinSciG(中国科学 G)，ChinPhysLett(中国物理快报 )，CommnTheorPhys(理论 物 理通讯 )，ChinPhys(中国物理 )，IEEETransactionsonSystems(IEEE电路 与系统汇刊 )，中 国科学 、物理学 进 展 、物理学 报 、自然科学进 展 、复杂 系统 与 复杂性科学 、科技 导报 、计 算机工 程与应用 、系统 工程 学报 、通 信 学 报等 2O多种 国内外 刊物上 ，这些 成果反 映 了本项 目取 得的 有意 义的进 展 ，本 文 只是 简介 和评 述 近年 的主要 进 展概况 2 探索网络模 型金字塔及其奥妙 网络科学 的发展迄今 经历 了 3个 里程 碑 ’ ，每个 里 程碑 无一 不 是 从理 论 模 型首 先 取得 突 破 的
第5卷第4期 方锦清,等:网络科学的理论模型及其应用课题研究的若干进展 因此,为了深入探索和全面了解复杂网络特性,我们首先深入分析了网络科学模型从无权网络到有权网络的 发展历程3-,提出了混合网络理论框架M-,从而提出、构建和描述了多层次的网络理论模型金字塔,如 图1所示,它总结了迄今网络模型研究的主要进展,揭示了网络金字塔的复杂性-简单性和多样性一普适 性,以及它们之间相互转变的错综复杂关系。 网络模型金字塔的最顶部(第5 层)是三大著名模型: Euler图论、ER 随机图、WS小世界网络和BA无标度 网络,它们标志着网络科学发展史上 的3个里程碑。第4层次是从无权网 络发展到有权演化网络模型 (WENM);第3层次是和谐统一混合 择优网络模型( HUHPM);第2层次是 大统一混合网络模型( LUHNM);第1 层次是统一混合变速增长网络(UH- NM-VSG);最底层是现实世界的许多 实际网络,这是金字塔的奠基层。以 下各节简述金字塔的不同层次,重点 是描述我们提出的第1层次至第3层 左边箭头从上到下表明复杂性与多样性增加了 次 右边箭头从下向上指明简单性与普适性增强了 2.1金字塔的最顶层(第5层):3个 图1复杂网络金字塔示意图 网络发展里程碑 网络科学发展的3个里程碑位居 复杂网络模型金字塔的最顶层:第1个里程碑标志欧拉( Euler)规则图论的诞生,归功于图论之父欧拉的开 创性贡献,他最早在1736年的论著中首先解决了著名的柯尼斯堡七桥问题和多面体的欧拉定理2,从此开 创了图论这门新的数学分支。第2个里程碑是两位著名的匈牙利数学家Erds(爱多士)和 Renyi,他们在 20世纪50年代末和60年代建立了著名的随机图理论3,用相对简单的随机图来描述网络,简称ER随机图 理论,他们成功地揭示了随机网络的许多重要性质都是随着网络规模的增大突然涌现的,他们创立的ER随 机图理论为图类的阈函数和巨大分支涌现的相变等提供了研究网络的一种重要的数学理论,爱多士被誉为 20世纪的欧拉,并于1984年获得数学界的最高奖——一沃尔夫奖。用图论的语言和符号精确简洁地加以描 述各种网络,为数学家和物理学家等提供了描述网络的共同语言和研究平台,至今仍然是网络科学研究的有 力方法之一。网络科学发展的第3个里程碑,首先是美国Was和 Stromal冲破了ER理论框框,提出了小世 界(SW)网络模型,揭示了复杂网络的小世界特性:较短的平均路径长度和较大的群聚系数。接着,1999年 美国 Barabasi与 Albert提出了一个无标度(SF)网络模型"-1,发现了复杂网络的度分布具有幂函数形式 即无标度性质。小世界网络和无标度网络的发现,在国际上产生了广泛而深刻的影响,不仅具有重大的先锋 意义,而且极富创新性和启迪作用,证明大多数真实网络既不是规则网络,也不是随机网络,而是混合网络 兼具小世界和无标度特性,具有与规则网络和随机图皆不同的统计特性152-3),这些特性在现实世界网 络中具有普遍意义,由此开辟了网络科学的新时代,普遍受到了空前的关注和广泛的重视,研究遍及自然科 学、社会科学、技术科学、工程技术等众多科学领域,近10年来网络科学取得了突飞猛进的发展。可见网络 科学3个里程碑当之无愧屹立在网络金字塔的最顶层(第5层),像一盏灯塔照耀着网络科学的发展历程。 2.2金字塔的第4层:WENM 不难发现:网络金字塔的最高层三大模型都是无权网络,它确实石破天惊,反映了现实世界网络主要的 基本特性,并深刻地揭示了无标度特性产生的两个主要机制:网络增长和随机择优(偏好)连接。然而,随着
第 5卷第 4期 方锦清 ，等 ：网络科学的理论模 型及其应用课题研究的若干进 展 因此 ，为 了深入探索 和全 面了解复 杂网络特性 ，我们 首先深 入分析 了网络科学模 型从 无权 网络 到有权 网络 的 发展历程 ，提 出 了混合 网络理论 框架 …。 ，从 而提出 、构 建和描 述 了多层 次 的网络 理论模 型金字塔 ，如 图 1所示 ，它总结 了迄今 网络模型研 究 的主要 进展 ，揭 示 了 网络 金字 塔 的复 杂性 一简 单性 和 多样 性 一普 适 性 ，以及 它们 之 间相 互转 变的错综 复杂关 系。 网络模 型 金 字 塔 的最 顶 部 (第 5 层 )是 三 大著 名 模 型 ：Euler图论 、ER 随机 图 、WS小世 界 网络 和 BA无标 度 网络 ，它们 标 志 着 网络 科学 发展 史 上 的 3个里程 碑 。第 4层次是从 无权 网 络 发 展 到 有 权 演 化 网 络 模 型 (WENM)；第 3层 次是 和谐统 一混 合 择优 网络模 型 (HUHPM)；第 2层次 是 大统一混 合 网络模 型 (LUHNM)；第 1 层次是 统 一混 合 变 速 增 长 网络 (UH— NM—VSG)；最底层 是 现实 世 界 的许 多 实际 网络 ，这是 金 字 塔 的奠 基 层 。以 下各节简 述金 字 塔 的 不 同层 次 ，重点 是 描述我们 提 出的第 l层次 至第 3层 次 。 2．1 金字塔 的最顶层 (第 5层 )：3个 网络发展 里程碑 左 边 箭头 从 上 到 下表 明 复 杂性 与 多 样性 增 加 了 ； 右 边 箭 头从 下 向 上 指 明简 单 性 与普 适 性 增 强 了 。 图 1 复 杂 网 络金 字 塔 示 意 图 网络科 学发展 的 3个里程 碑位居 复杂 网络模型金 字塔的最顶 层 ：第 1个里程碑 标 志欧拉 (Euler)规 则 图论 的诞生 ，归 功 于 图论 之 父欧 拉 的开 创性贡献 ，他最早 在 l736年 的论 著 中首先解决 了著名 的柯尼 斯 堡七桥 问题 和多 面体 的 欧拉 定理 ，从此 开 创 了图论 这 门新 的数学分 支 。第 2个里 程碑是 两位著 名的匈牙 利数学 家 Erdtis(爱 多士 )和 Renyi，他 们在 20世 纪 50年代末 和 60年代建立 了著名 的随机 图理论 ，用相对简 单的随 机图来描 述 网络 ，简称 ER随 机图 理论 ，他们成功地 揭示 了随机网络 的许 多重要 性质都是 随着 网络规模 的增大 突然 涌现 的 ，他 们创立 的 ER随 机 图理论 为图类 的阈函数 和巨大分 支涌现 的相 变等提 供 了研究 网络 的一 种重 要 的数学 理论 ，爱 多士 被誉 为 20世 纪的欧拉 ，并 于 l984年 获得数 学界 的最 高 奖—— 沃尔夫 奖 。用 图论 的语 言 和符 号精 确 简洁 地加 以描 述各种 网络 ，为数学 家和物理 学家等提 供 了描 述 网络 的共 同语 言和研究 平 台，至 今仍然 是网络科 学研究 的有 力方法之一 。 网络科 学发 展的第 3个 里程碑 ，首 先是美 国 Watts和 Strogatz冲破 了 ER理论 框框 ，提 出了小世 界 (SW)网络模 型 ，揭示 了复杂 网络 的小 世 界特性 ：较 短 的平 均路 径长 度 和较 大 的群 聚系 数 。接 着 ，1999年 美 国 Barabasi与 Albert提 出 了一个 无标度 (SF)网络模 型 … ，发现 了复 杂 网络 的 度分 布具 有幂 函数 形式 ， 即无标度性 质 。小世 界 网络 和无标度 网络 的发 现 ，在 国际上产 生 了广泛 而深刻 的影响 ，不仅具有 重大的先锋 意义 ，而且极 富创新性 和启迪 作用 ，证 明大多数 真实 网络既 不是 规则 网络 ，也不 是随 机 网络 ，而是 混合 网络 ， 兼具小世 界和无标度 特性 ，具 有与规 则 网络 和 随机 图 皆不 同的统 计特 性 ，这些 特 性 在现 实世 界 网 络中具有普遍 意 义 ，由此开辟 了 网络科 学 的新 时代 ，普 遍受 到 了空前 的关 注和广 泛 的重 视 ，研 究遍 及 自然科 学 、社 会科学 、技术科 学 、T程 技术等众 多科学 领域 ，近 10年来 网络科学 取 得 了突 飞猛进 的发展 。可 见 网络 科学 3个里程 碑 当之 无愧屹立 在网络 金字塔 的最顶层 (第 5层 )，像 一盏灯塔 照耀着 网络科学 的发展 历程。 2．2 金字塔 的第 4层 ：WENM 不 难发现 ：网络金字塔 的最高层 三大模 型都是无权 网络 ，它确 实石 破天 惊 ，反映 了现 实世 界 网络 主要 的 基本特性 ，并深刻地 揭示 了无 标度特性 产生 的两个主要 机制 ：网络增长 和随 机择 优 (偏 好 )连接 。然 而 ，随着
复杂系统与复杂性科学 2008年12月 网络增长模型研究的深入,许多研究进一步揭示和完善了产生小世界和无标度特性的物理机制的多样性,例 如,复制、最近邻连接、点强驱动、边权驱动、适应度等多种混合驱动机制式。研究越来越多地发现:现实世界 中实际网络节点之间相互作用的重要性程度和影响作用并非相同,具有复杂性和多样性,因此,必须在无权 网络研究的基础上,进一步研究加权演化网络,以便更深入捕捉和揭示真实网络上动力学特征与拓扑结构之 间的联系,以及权重变化对网络演化特性或系统功能所产生的重要影响。于是,在三大基本模型基础上,科 学家不断开拓创新,2000年开始陆续提出了许多有意义的有权网络模型。例如,BBV权重演化模型2提 出点强度驱动和边权逐渐加强的双驱动机制,同时得到点度、点权和边权的3种幂律分布,且依赖于权重参 数δ和训。但是该模型还无法反映真实网络中群聚系数较大和异配相称性系数问题。中国科大小组提出 交通流驱动有权网络(TDE)模型,除了获得点度、点权和边权的3个幂律分布外,还给出高群聚性和异配相 称性特征,克服BBV模型的不足。 纵观文献可见,当前有权网络模型主要是广义随机网络模型,归纳起来,根据网络节点之间连边概率p 不同,迄今有如下有权网络的主要生成方式和基本特点:1)点强驱动机制;2)边权驱动机制;3)点强与边权 混合择优驱动机制,或点强或边权的耦合排序择优;4)权重和适应度联合驱动机制;5)拓扑生长和强度耦合 同步联合驱动机制;6)“近水楼台先得月”机制,即地理位置最(次)邻近优先连接;7)利用邻近局域信息;8) 权重驱动与局域世界规则联合驱动机制;9)拓扑结构与动力学(或网络功能)演化相互影响机制,等等。总 之,在这些驱动机制下,几乎现有的有权演化网络模型的度分布、点强分布和边权分布都服从幂律分布,只是 幂指数不同而已,这就是金字塔第4层次的规律和特色所在,它揭示了多个幂律分布规律及其形成的物理机 制的多样性和复杂性。因此,在最高层次的无权网络的基础上,自然推进到WENM,作为网络金字塔的次高 层次。 23金字塔的第3层次: HUHPM-1 可以看到:第4层次所有有权网络模型几乎都属于广义随机网络模型,都忽视了确定性驱动机制,没有 反映现实世界中自然和谐统一的随机性与确定性两种混合连接的可能方式。究其最主要原因是两种混合情 形从理论上很难求得解析解,目前还缺乏有力工具和好方法。因此,进一步完善和发展网络的混合理论模型 是网络模型研究的最重要方向之一。大量研究发现:许多实际网络兼有小世界特性和无标度性质,但是又不 尽如此,而是存在错综复杂的不同特性之间的转变。为了揭示实际网络的完全特性,更好反映随机性与确定 性连接混合生长的真实网络特性,我们提出了 HUHPM构成网络金字塔的第3层次,其特点是,为了克服无 权BA网络模型和许多有权网络模型缺乏确定性择优的不足,考虑确定性择优思想,模型只引人一个总混合 比dr d总确定性择优时间步数(DA) r-总随机性择优时间步数(RA) (1) 这里,d为总确定性连接时数(DA);r为总随机性连接时数(RA);d、r∈[0,+∞),由此确定一个总混合比。 HUHPM表现出具有不同特点的3种典型的混合情形:1)如果dr<1/1,则属于随机性连接占主导情形;2)如 果如=l/1,则属于随机性与确定性两种连接相同(平分秋色,或势均力敌)情形;3)如果d≯1/1,则属于确 定性连接占主导情形。1)和2)两种都是不对称混合连接。在 HUHPM中,网络性质和生长所需的规模大小 都完全取决于一个总混合比dr。该层次 HUHPM模型能够较好地描述从规则(确定性)和随机网络之间的 转变特性。在网络生长演化过程中总混合比d大小是唯一的调控参数,实施随机性择优与确定性择优相 结合,双择优思想与方法适用于任何现有的典型模型,如无权BA模型、有权BBV模型和TDE模型,分别称 为 HUHPM-BA网络, HUHPM-BBⅤ网络和 HUHPM-TDE网络,以此类推。第3层次研究发现:除了得到原来 模型的主要结果外,新发现了混合网络的一些普适规律。首先,无权和有权 HUHPM网络(如 HUHPM-BA、 HUHPM-BBⅤ与 HUHPM-TDE)中的节点度,点强和边权3种分布都服从幂律分布,并且所有幂指数y都对 总混合比山r的变化具有敏感性,随着log(dr)的增加而增加。理论导出了幂指数γ与混合比d及权重参数 之间存在的复杂解析关系,不论是无权网络,还是有权网络,它们的幂律指数y与混合比dr以及与权重参
复 杂 系 统 与 复 杂 性 科 学 2008年 l2月 网络 增长模 型研究 的深 入 ，许 多研 究进 一步揭示 和完善 了产生 小世界 和无标度特 性的物理 机制 的多样性 ，例 如 ，复制 、最 近邻 连接 、点强驱动 、边权驱 动 、适应 度等 多种混合 驱动机制式 。研究 越来越 多地发现 ：现实世界 中实 际 网络 节点之间相 互作用 的重要性 程度 和影 响作 用并 非相 同 ，具 有复 杂性 和 多样性 ，因 此 ，必 须在 无权 网络 研究 的基 础上 ，进 一步研究 加权演 化网络 ，以便更 深入捕 捉和揭示 真实 网络上 动力学 特征与拓 扑结构之 间的联系 ，以及权重 变化对 网络 演化特性 或 系统 功能 所产 生 的重要 影响 。于是 ，在 三大基 本 模型 基础 上 ，科 学 家不断开 拓创新 ，2000年 开始陆续提 出 了许 多有意 义的有权 网络模 型” 。例如 ，BBV权 重演化模 型 提 出点强度驱 动和边权 逐渐加强 的双驱 动机制 ，同时得 到点度 、点 权和边 权 的 3种 幂 律分 布 ，且 依赖 于权 重参 数 6和 W 。但 是该模 型还无法 反映真 实 网络 中群 聚 系数 较大 和异 配相 称性 系数 问题 。中 国科 大 小组 提 出 交通 流驱动 有权 网络 (TDE)模 型 ，除 了获得点 度 、点权 和边权 的 3个幂 律分 布外 ，还 给 出高群 聚性 和 异配相 称性 特征 ，克 服 BBV模 型的不 足。 纵观文 献可见 ，当前有权 网络模 型主要 是 广义 随机 网 络模 型 ，归 纳起 来 ，根据 网络 节点 之 间连边 概 率 P 不同 ，迄今有 如下有 权 网络 的主要生 成方式 和基本 特点 ：1)点强 驱 动机 制 ；2)边 权驱 动机 制 ；3)点强 与边权 混合择优驱 动机制 ，或点强或 边权 的耦 合排序 择优 ；4)权重和适 应度联 合 驱动机 制 ；5)拓 扑生 长和强 度耦 合 同步联合驱 动机制 ；6)“近水楼 台先得月 ”机制 ，即地理位 置最 (次 )邻 近优 先连 接 ；7)利用 邻近 局域信 息 ；8) 权 重驱动 与局域世界 规则联 合驱动机 制 ；9)拓 扑结 构 与动 力学 (或 网络功 能 )演化 相互 影 响机制 ，等 等 。总 之 ，在这些 驱动机 制下 ，几乎 现有 的有 权演化 网络模 型的度分 布 、点强 分布和边 权分布 都服从幂 律分布 ，只是 幂指数不 同而 已 ，这 就是金字 塔第 4层 次的规 律和特 色所在 ，它揭示 了多个幂 律分布规 律及其形成 的物理 机 制的多样性 和复杂性 。因此 ，在最高 层次 的无 权 网络 的基础 上 ，自然 推进 到 WENM，作 为网络 金字塔 的次 高 层次 。 2．3 金 字塔的第 3层次 ：HUHPM ll 可以看到 ：第 4层次所有 有权 网络模型几 乎都属 于广 义随 机 网络 模 型 ，都 忽视 了确 定性 驱 动机制 ，没有 反映 现实世界 中 自然和谐统 一的随机 性与确 定性两种 混合连 接 的可能方式 。究其最 主要原 因是 两种混合情 形从 理论上很 难求得解 析解 ，目前还 缺乏有力 工具 和好方法 。 因此 ，进 一步完 善 和发展 网络 的混合理论模 型 是 网络模型研 究的最重要 方 向之一 。大量研 究发 现 ：许多 实际 网络兼 有小世 界特性 和无标度性 质 ，但是 又不 尽 如此 ，而是存 在错综 复杂的不 同特 性之 间的转变 。为 了揭 示实 际网络 的完全特性 ，更好反 映随机性与 确定 性连 接混合生 长的真 实网络特 性 ，我们 提 出了 HUHPM，构 成 网络金 字塔 的第 3层次 ，其特点 是 ，为了克服 无 权 BA网络模型 和许 多有权 网络模 型缺乏确定 性择优 的不 足 ，考虑确 定性择优 思想 ，模 型只引 入一个 总混 合 比 ： 一 ， d 总确 定性择 优时间步 数 (DA) ，，、 r 总 随机性择 优时 间步数 (础 ) 这里 ，d为总确定性 连接时数 (DA)；r为 总随机性 连接时数 (RA)；d、r∈[0，+∞)，由此 确定 一个 总混合 比。 HUHPM表现 出具有不 同特点 的 3种典 型的混合情 形 ：1)如果 dr<<l／1，则属 于随机性连 接 占主导情 形 ；2)如 果 dr=l／1，则属 于随机性 与确 定性两 种连接相 同(平 分秋 色 ，或势 均力 敌 )情形 ；3)如果 》 1／1，则 属 于确 定性连 接 占主 导情形 。1)和 2)两种都是 不对称 混合连 接。在 HUHPM 中 ，网络性质 和生 长所 需 的规 模 大小 都完 全取决于 一个总混合 比 dr。该 层 次 HUHPM模 型 能够 较好 地 描述 从规 则 (确定性 )和 随机 网络 之 间的 转变 特性 。在 网络生长 演化过程 中总混 合 比 dr大 小是 唯 一 的调控 参数 ，实施 随机 性择 优 与确定 性 择优 相 结合 ，双择优思 想与方法适 用于任何 现有 的典型模 型 ，如 无权 BA模 型 、有权 BBV 模型 和 TDE模 型 ，分别 称 为 HUHPM—BA网络 ，HUHPM．BBV网络和 HUHPM—TDE网络 ，以此类推 。第 3层次研 究发现 ：除 了得到 原来 模型 的主要结果外 ，新发 现 了混合 网络 的一 些普 适规 律 。首先 ，无权 和有 权 HUHPM 网络 (如 HUHPM—BA 、 HUHPM-BBV与 HUHPM—TDE)中 的节点度 ，点 强 和边权 3种 分布 都服从 幂 律分 布 ，并且 所 有幂指 数 '，都 对 总混合 比 的变化 具有敏感性 ，随着 log(dr)的增 加而增加 。理论 导 出了幂 指数 与混 合 比 dr及 权重 参数 之间存在 的复杂解析关 系 ，不论是 无权 网络 ，还 是有权 网络 ，它 们 的幂律指 数 与混合 比 dr以及 与权重 参
第5卷第4期 方锦清,等:网络科学的理论模型及其应用课题研究的若干进展 5 数(8,切)和连接边数m之间都存在复杂的指数及参数成反比的复合关系,并非原来模型中简单的指数关 系,所有公式都与混合比和权重参数(d/r,δ,)之间相互关联,说明这种错综复杂的拓扑关系与产生的网 络混合方式、结构、模型类型(参数)等紧密相关,这样第3层次揭示了两种混合择优网络既保持了和谐混合 共存,又能体现它们之间的相互作用与竞争的状况。其理论结果与数值模拟结果相一致。同时 HUHPM网 络具有更突出的小世界特性(最短平均路径距离L和最大的平均群聚系数C),更符合许多实际网络的拓扑 特性27281。此外,当满足网络同步第一判据(类型I)时该层次增强了网络同步能力;网络的熵随着d增加 而减少,可增强网络系统的自组织的有序度13)。总之,第3层次 HUHPM模型,在采取双择优后,通过调 控一个总混合比达到和谐统一,同时产生了无标度特性和小世界效应,并出现了网络新特点 2.4金字塔的第2层次: LUHNM1-21 第3层次 HUHPM模型不足是:它仅仅考虑两大类的择优连接方式,还不能完全地反映实际世界网络形 成中存在连接方式的多样性和复杂性。因为不论随机性连接,还是确定性连接,只考虑一种择优方式,而不 考虑其他的可能连接方式,并不完全符合实际情形。在现实世界网络中,随机性和确定性两大类连接都存在 多种混合方式,比如,既可择优,又能扶贫,还有折中、平衡、特殊等其他多种混合连接方式。因此,我们把 HUHPM推广到 LUHNM,其特点是在总混合比dr下,又分别引人了2个混合比:一是随机混合比gr定义为 般随机连接的时步数(GRA) 总随机性连接的时步数(RA) (2) 是确定性混合比fd定义为 =确定性扶贫连接的时步数(mP4) (3) 它们之间的关系为:DA=HPA+DPA,RA=GRA+RPA或DA=f+d,RA=g+r。根据实际需要,该模型还可 灵活增加混合比个数。因此,第2层次模型形成了具有多个混合比的大统一混合网络模型。该模型包括了 不对称连接比。第2层次与第3层次类似,存在3种不同的典型混合情形。第2层次模型与第3层次模型 不同的是考虑了3个混合比(dr,gr,fd)。研究显示了结构及特性的多样性和复杂性,把目前文献上绝大多 数网络模型类型基本都统一起来,作为特例包括在该理论框架内。第2层次 LUHNM网络通过3个混合比 灵活控制网络生长,能够更细致揭示复杂网络的特性。第2层次不仅囊括了前面各层次模型的主要结果,又 发现了新特性和新现象。值得关注的是度-度关联系数r(或相称性系数)通过调控3个混合比(dr,gr,f )参数,使r在(-1,1)大范围的正负值之间实现转变,并出现了多极值现象。在不同gr和d情形下发现 的与3个混合比(dr,gr,fd)之间关系错综复杂,既有线性关系,也有非线性关系,取决于3个混合比的不同 匹配、工作模式和大小。利用这个层次的理论结果,可以解释为什么社会网络和技术及生物网络之间的r出 现的差异。其次发现:累计度分布随着3种混合比的变化可在幂律函数分布和指数分布之间进行转变,一些 奥秘和规律隐藏在混合比的巧妙组合之中。因此,第2层次 LUHNM更具灵活性,无论无权和有权网络都能 通过调控3个混合比发现网络的新特点和新现象,且完全依赖于3个混合比的组合和变化。 25金字塔的第1层次:UHNMⅤSG1 进一步不难发现,即使在理论模型第2层次模型里,仍然还有考虑不周之处,即没有全面反映网络实际 增长情形,而网络演化变化必然影响网络特性。因为许多实际网络不论是节点的增减和边的增长速度都是 不同的,而且同时随时间和空间而变化。如中国四川汶川抗震救灾网、高技术网络、因特网、人类社会关系 网、通讯网等等,通常它们是随时间空间快速变化的。因此,我们又进一步构造了第1层次模型:UHNM VSG3,其特点是,在总混合比d及第2层次混合比基础上,又引进了一个变速增长混合比eg: DVG RVG 这里,DVG为确定性变速增长时步数;RVG为随机性变速增长时步数。 实际复杂网络存在多种变速增长方式,其中典型的变速方式之 m (t)=p(N(t)) (5)
第 5卷第 4期 方锦清，等 ：网络科学 的理论模型及其应用课题研究的若干进展 ·5· 数 (6，W)和连接边 数 m 之间都 存 在复 杂 的指 数 及参 数 成反 比的 复合关 系 ，并非 原 来模 型 中 简单 的指 数关 系 ，所有公式 都与混合 比和权 重参数 (d／r，6，W)之 间相 互关 联 ，说 明这 种错 综 复杂 的拓 扑关 系 与产生 的网 络混合 方式 、结 构 、模 型类型 (参 数 )等 紧密相关 ，这样 第 3层次 揭示 了两种混合 择优 网络既保持 了和谐混合 共存 ，又能体 现它们之 间 的相互 作用 与竞争 的状况 。其 理论结 果与 数值 模拟 结果 相一 致 。同时 HUHPM 网 络具有 更突 出的小世 界特性 (最 短平均路 径距 离 和最 大 的平 均群 聚系数 c)，更 符合 许多实 际 网络 的拓扑 特性 。此外 ，当满足 网络 同步第-N 据 (类 型 I)时该 层次 增强 了 网络 同步能力 ；网络的熵 随着 dr增加 而减少 ，可增强 网络系统 的 自组 织的有 序 度 。总之 ，第 3层 次 HUHPM 模 型 ，在 采取 双择 优后 ，通 过调 控一个 总混合 比达到 和谐 统一 ，同时产 生 了无标 度特性 和小世 界效应 ，并 出现 了网络新特 点。 2．4 金 字塔 的第 2层次 ：LUHNM I2 第 3层次 HUHPM模 型不足是 ：它仅 仅考虑两 大类 的择 优连接方 式 ，还 不能完全 地反映 实 际世界 网络形 成 中存 在连接方 式的 多样性和 复杂性 。因为不论 随机性 连接 ，还 是确定 性 连接 ，只考 虑一 种 择优 方式 ，而不 考虑其 他的可 能连接方 式 ，并不 完全符 合实际情 形 。在 现实世界 网络 中 ，随机性 和确定性 两大类连 接都存在 多种混 合方 式 ，比如 ，既可 择 优 ，又能 扶 贫 ，还有 折 中 、平 衡 、特 殊 等其 他 多种 混 合连 接方 式 。 因此 ，我 们把 HUHPM推广 到 LUHNM，其特点 是在 总混 合 比 下 ，又分别 引入 了 2个 混合 比 ：一是 随机混合 比 gr定 义为 一 g 一 般随机 连接 的时步数 (GRA) ， r 一 总随机性 连接 的时步数 (肼 ) 二是确 定性混 合 比 定义 为 ， ， 确定 性扶 贫连接 的时步数 (例 ) ，¨ jtt一 总确定性 连接 的时步数 ( ) 它们之 间的关 系为 ：DA= +DPA，t54=GRA+兄PA或 DA=，+d，RA=g+r。根 据 实际需 要 ，该 模 型还可 灵活增 加混合 比个数 。因此 ，第 2层 次模 型形成 了具有 多个混 合 比的 大统一 混合 网络模 型 。该 模 型包 括 了 不对称 连接 比。第 2层次 与第 3层 次类似 ，存在 3种 不 同的典 型混 合情 形 。第 2层 次模 型与 第 3层次 模 型 不 同的是考虑 了 3个混合 比( ，gr，．厂d)。研究显 示 了结 构及特性 的多样 性和 复杂性 ，把 目前 文献 上绝 大多 数 网络 模型类 型基本都统 一起来 ，作 为特 例包 括在 该理 论 框架 内。第 2层次 LUHNM 网络 通 过 3个 混 合 比 灵活控 制网络生 长 ，能够更 细致揭示 复杂 网络 的特性 。第 2层次不仅 囊括 了前 面各层 次模 型的主要结 果 ，又 发现 了新特性 和新现象 。值得关 注的是度 一度关 联系数 rr(或相 称性系 数 )通过 调控 3个 混 合 比(d，，gr， )参数 ，使 r在 (一1，1)大 范围的正 负值之 间实现转 变 ，并 出现 了多极 值现 象 。在不 同 g，和 ，d情形 下发 现 的与 3个 混合 比(dr，gr，fd)之 间关系错综 复杂 ，既有线性 关系 ，也 有非线性 关系 ，取决 于 3个 混合 比的不 同 匹配 、工作模式 和大小 。利用这个层 次 的理 论结果 ，可 以解 释为什 么社会 网络和技术 及生物 网络之 间的 r出 现的差异 。其次 发现 ：累计度 分布 随着 3种混 合 比的变化可在 幂律 函数分布 和指数分 布之 间进 行转变 ，一些 奥秘 和规律隐藏在 混合 比的巧妙组 合之 中。因此 ，第 2层次 LUHNM更具灵 活性 ，无 论 无权 和有权 网络 都能 通过调控 3个混合 比发现 网络 的新特 点 和新 现象 ，且 完全依 赖于 3个 混合 比的组合 和变化 。 2．5 金字塔 的第 1层次 ：UHNM．VSG¨ 进一 步不难发 现 ，即使 在理论模 型第 2层 次模 型里 ，仍 然还 有考 虑不 周之 处 ，即没 有全 面反 映 网络 实际 增 长情形 ，而 网络演 化变化必 然影 响网络特性 。因为许 多实际 网络 不论 是节点 的增 减 和边 的增 长速 度都 是 不同 的 ，而且 同时随时间 和空间而变 化 。如 中 国 四川汶 川I抗 震 救灾 网 、高 技术 网络 、因特 网 、人类 社 会关 系 网 、通讯 网等等 ，通 常 它们 是 随 时 间 空 问快 速 变 化 的。因 此 ，我 们 又进 一 步 构造 了第 1层 次 模 型 ：UHNM． VSG ，其特点 是 ，在 总混合 比 及 第 2层 次混合 比基础上 ，又引进 了一个变 速增长混 合 比 g： vg- (4) 这里 ，DVG为确定性 变速增长 时步数 ；RVG为随机性变 速增长 时步数 。 实际复杂 网络存在 多种 变速增长 方式 ，其 中典 型的变速方 式之一 ： m(t)=P(N(t)) (5)