第38卷第6期 力学进展 Vol 38 No 6 008年11月25日 ADVANCES IN MECHANICS Nov.25.2008 网络科学中统一混合理论模型的若干研究进展 方锦清↑李永 中国原子能科学研究院,北京102413 摘要复杂网络的理论模型研究一直是网络科学的最重要课题之一.首先概述网络科学理论发展史上的3 个里程碑以及有权演化网络的发展概况。为了全面反映确定性与随机性混合的真实世界的统一性、多样性和 复杂性,使网络理论模型更加接近实际网络的全面特性,着重评述近年来发展的统一混合网络理论模型的3部 曲:和谐混合择优模型、统一混合网络模型和统一混合变速増长网络模型,总结和评述了混合理论模型3部曲 的不同特点和相互联系,揭示了统一混合网络的复杂性与普适性及其错综复杂的转变关系.最后指出,该理论 在多层次高科技网络等实际网络中的应用前景 关键词网络科学,统一混合网络理论模型3部曲,复杂性,普适性,小世界,无标度 1引言 们成功地揭示了随机网络的许多重要性质都是随 着网络规模的增大突然涌现的,ER理论对于网络 正如美国最有影响的科学家之一E.O.Wi-科学理论的影响长达40年之久爱多士被誉为20 som指出:“今天最大的挑战性,不仅是细胞生物世纪的欧拉,并于1984年获得沃尔夫奖.确实,用 学和生态学,而是科学的所有方面,特别是如何精图论的语言和符号精确简洁地描述各种网络,为 确地和完全地描述复杂系统.至少在数学模数学家和物理学家等提供了描述网络的共同语言 型方面必须抓住整个系统的关键性质.”因此,复和研究平台,至今仍然是网络科学研究的有力方 杂网络中理论模型的研究成为最富挑战性的问题法之 之一.网络科学中理论模型的研究一直是最重要 直到20世纪末科学家迎来了网络科学又 的课题之一,它的发展历史至今经历了3个里程 次突破性进展,1998年首先冲破了ER理论的 碑,当中每个无一不是从理论模型取得突破的第是美国康奈尔(Come)学Watt和 Strogatz,他 1个里程碑当属图论的诞生,归功于图论之父欧拉们提出了小世界( small world,sw)网络模型及其 的开创性贡献,“图论”最早出现在欧拉1736年的随后的改进小世界模型-10.接着,199年美国 论著中,他首先解决了著名的柯尼斯堡七桥问题圣母( Notre dame)大学 barabasi与 Albert提出 和多面体的欧拉定理,从此开创了图论”这门了一个无标度( (scale-free,SF)网络模型11,发 新的数学分支叫,这就是第1代科学家树起网络现了复杂网络的无标度性质,200年 Barabasi与 科学的第1个里程碑,也是拓扑学的“先声因 Newmann及Wats共同主编了《网络的结构与动 此,关于哥尼斯堡七桥问题、多面体的欧拉定理、力学》专著,在国际上产生了广泛的影响,对网 四色问题等成为拓扑学发展史上的著名问题 络科学作出了杰出的贡献,因此, Barabasi于2006 第2个里程碑是两位匈牙利著名的数学家年获得了美国 von neumann(冯·纽曼)计算金奖. Edos(爱多士)和 Renyi,他们在20世纪50年代末上述小世界效应和无标度特性等发现标志着网络 和60年代建立了著名的随机图理论例,用相对简科学发展的第3个里程碑,表明网络无处不在,并 单的随机图来描述网络,简称ER随机图理论,他具有普遍的规律,由此诞生了一门广泛交叉的新 收稿日期:2008-06-30,修回日期:2008-07-10 国家自然科学基金重点基金(70431002),面上基金(0874087)和理论物理专项基金(10647001)资助项目 E-mail: fjq9601
第 38 卷 第 6 期 力 学 进 展 Vol. 38 No. 6 2008 年 11 月 25 日 ADVANCES IN MECHANICS Nov. 25, 2008 网络科学中统一混合理论模型的若干研究进展* 方锦清 † 李 永 中国原子能科学研究院, 北京 102413 摘 要 复杂网络的理论模型研究一直是网络科学的最重要课题之一. 首先概述网络科学理论发展史上的 3 个里程碑以及有权演化网络的发展概况. 为了全面反映确定性与随机性混合的真实世界的统一性、多样性和 复杂性, 使网络理论模型更加接近实际网络的全面特性, 着重评述近年来发展的统一混合网络理论模型的 3 部 曲: 和谐混合择优模型、统一混合网络模型和统一混合变速增长网络模型, 总结和评述了混合理论模型 3 部曲 的不同特点和相互联系, 揭示了统一混合网络的复杂性与普适性及其错综复杂的转变关系. 最后指出, 该理论 在多层次高科技网络等实际网络中的应用前景. 关键词 网络科学, 统一混合网络理论模型 3 部曲, 复杂性, 普适性, 小世界, 无标度 1 引 言 正如美国最有影响的科学家之一 E. O. Wilson 指出 [1]: “今天最大的挑战性, 不仅是细胞生物 学和生态学, 而是科学的所有方面, 特别是如何精 确地和完全地描述复杂系统. . . . . . .至少在数学模 型方面必须抓住整个系统的关键性质. ” 因此, 复 杂网络中理论模型的研究成为最富挑战性的问题 之一. 网络科学中理论模型的研究一直是最重要 的课题之一, 它的发展历史至今经历了 3 个里程 碑, 当中每个无一不是从理论模型取得突破的. 第 1 个里程碑当属图论的诞生, 归功于图论之父欧拉 的开创性贡献, “图论” 最早出现在欧拉 1736 年的 论著中, 他首先解决了著名的柯尼斯堡七桥问题 和多面体的欧拉定理 [2] , 从此开创了 “图论” 这门 新的数学分支 [1] , 这就是第 1 代科学家树起网络 科学的第 1 个里程碑, 也是拓扑学的 “先声”. 因 此, 关于哥尼斯堡七桥问题、多面体的欧拉定理、 四色问题等成为拓扑学发展史上的著名问题. 第 2 个里程碑是两位匈牙利著名的数学家 Edos(爱多士) 和 Renyi, 他们在 20 世纪 50 年代末 和 60 年代建立了著名的随机图理论 [3] , 用相对简 单的随机图来描述网络, 简称 ER 随机图理论, 他 们成功地揭示了随机网络的许多重要性质都是随 着网络规模的增大突然涌现的, ER 理论对于网络 科学理论的影响长达 40 年之久. 爱多士被誉为 20 世纪的欧拉, 并于 1984 年获得沃尔夫奖. 确实, 用 图论的语言和符号精确简洁地描述各种网络, 为 数学家和物理学家等提供了描述网络的共同语言 和研究平台, 至今仍然是网络科学研究的有力方 法之一. 一直到 20 世纪末科学家迎来了网络科学又 一次突破性进展, 1998 年首先冲破了 ER 理论的 是美国康奈尔 (Cornell) 大学 Watts 和 Strogatz, 他 们提出了小世界 (small world, SW) 网络模型及其 随后的改进小世界模型 [4∼10] . 接着, 1999 年美国 圣母 (Notre Dame) 大学 Barab´asi 与 Albert 提出 了一个无标度 (scale-free, SF) 网络模型 [11∼14] , 发 现了复杂网络的无标度性质, 2006 年 Barab´asi 与 Newmann 及 Watts 共同主编了《网络的结构与动 力学》专著 [15] , 在国际上产生了广泛的影响, 对网 络科学作出了杰出的贡献, 因此, Barab´asi 于 2006 年获得了美国 von Neumann(冯 · 纽曼) 计算金奖. 上述小世界效应和无标度特性等发现标志着网络 科学发展的第 3 个里程碑, 表明网络无处不在, 并 具有普遍的规律, 由此诞生了一门广泛交叉的新 收稿日期 : 2008-06-30, 修回日期 : 2008-07-10 ∗ 国家自然科学基金重点基金 (70431002), 面上基金 (60874087) 和理论物理专项基金 (10647001) 资助项目 † E-mail: fjq96@126.com
664 力 展 2008年第38卷 兴科学:网络科学63.1.从自然界到人类社会,述了若干加权网络理论模型的主要特点 从物理科学到生命科学,从自然科学到社会科学 从表1可见:当前有权网络模型主要是广义 以至技术科学、工程技术等众多领域,网络科学普随机网络模型,归纳起来,根据网络节点之间连边 遍受到了空前的关注和广泛重视,具有广泛的应概率p不同,有权网络有如下的主要生成方式和 用和发展前景.关于网络科学发展的3个里程碑基本特点6~2.36~39 中3个基本网络模型请读者参看本专集陈关荣先 (1)度和点强驱动机制.边连接按度择优的连 生的评述,本文不再赘述.第2节简要评论有权演接概率为 化网络模型的研究概况,第3节开始将着重评述 Ⅱ-;=k/∑ 近年来发展的网络科学中的统一混合网络理论模 型的3部曲:和谐混合择优模型、统一混合网络当m条边连接完后,给节点j的每条边赋予权 模型和统一混合变速增长网络模型,总结统一混重(m=a)n=k/∑k和点强度为 合网络模型3部曲的理论框架及其特点和有关规3=∑0=1.式中|表示新节点j所连接 律,及其相互转变的错综复杂关系最后简要总结的点的集合还可以采用不同的边权赋值方式 全文的中心思想和理论应用 (2)度和适应度联合驱动机制在BA模型基 础上,提出把节点度和适应度相结合,每个新节点 2有权演化网络模型的研究概况 以m条边连接到已存在网络中的节点i上,连接 到节点j上的概率与i的度和适应度( fitness)两 小世界网络模型是确定性圆周连接与长程随者成正比 机连接的一种典型混合网络模型,无标度网络 I;= niki (BA)模型及其许多改进的模型,以及许多真实 网络的实证研究都表明:真实世界网络既不是规 (3)权重和适应度联合驱动机制.与(2)类似 则网络,也不是随机网络,而是一大类确定性与与度择优改为与权重联合 随机性混合的网络,兼具小世界和无标度两种特 (4)点强择优和边权随动态重新分配.考虑 性,具有与规则网络和随机图完全不同的统计特了:()增长性.新节点将连接m个已有节点,节 点i被选择的概率为In swe-dni/Re 性9~15 式 Balb和 Albert通过追踪万维网的动态演中R是特征距离,an是节点n和间的欧氏距 化过程,发现了许多复杂网络具有大规模的高度离.(i)动态边权每条新边(n,)被赋予固定权重 自组织特性,形成无标度特性的主要机制是网络0(取0=1),新增边将导致改变已有边的权重: 增长和随机择优连接两条规则,而且随机择优(偏 好)是产生无标度特性的最重要的机制.然而,随 (5)点强度驱动和边权逐渐加强机制(BBV模 着网络研究的深入,考察现实世界的许多网络发型).可以模拟实际网络系统中相互作用强度的变 现:现实世界中实际网络节点之间相互作用并非化.其演化算法是:首先,网络增长时,新节点n与 相同,重要性和影响程度各异,实际网络几乎都老节点i的连接概率与点强择优概率为 是有权网络,因此,不仅需要研究无权网络,而 且必须研究加权网络,才能更好地捕捉和揭示真 Imn=i-55,.,s5 实网络上动力学特征与拓扑结构之间的联系,以这里s2s表示相应节点(的强度.在每时步, 及权重变化在网络时空动力学特性演化(或对系带有m条边的新节点;加入到网络中,其中每条 统功能)的重要意义和作用许多研究丰富了能边的权重为n,每条边根据点强度驱动的方式选 够产生无标度特性和小世界效应的物理机制的多择老节点i与之相连新边h的加入会导致节点 样性,如:复制、最近邻连接、点强和边权驱动 与其邻居之间的边权重新分配如下 权重和适应度联合驱动以及多种混合驱动等方 式口7~24,有权网络模型成为网络科学的一个非常 uit→tit+△ua,Ⅶ∈△a,△it=bui/s 重要的课题和方向,国内外已经提出了许多有意 研究表明:拓扑特性同时兼有度、点权和边权 义的加权网络模型口~24.我们在表1简介和评3种幂律分布,且依赖于权重参数6和v0.边权幂
664 力 学 进 展 2008 年 第 38 卷 兴科学: 网络科学 [6,13,16] . 从自然界到人类社会, 从物理科学到生命科学, 从自然科学到社会科学, 以至技术科学、工程技术等众多领域, 网络科学普 遍受到了空前的关注和广泛重视, 具有广泛的应 用和发展前景. 关于网络科学发展的 3 个里程碑 中 3 个基本网络模型请读者参看本专集陈关荣先 生的评述, 本文不再赘述. 第 2 节简要评论有权演 化网络模型的研究概况, 第 3 节开始将着重评述 近年来发展的网络科学中的统一混合网络理论模 型的 3 部曲: 和谐混合择优模型、统一混合网络 模型和统一混合变速增长网络模型, 总结统一混 合网络模型 3 部曲的理论框架及其特点和有关规 律, 及其相互转变的错综复杂关系. 最后简要总结 全文的中心思想和理论应用. 2 有权演化网络模型的研究概况 小世界网络模型是确定性圆周连接与长程随 机连接的一种典型混合网络模型, 无标度网络 (BA) 模型及其许多改进的模型, 以及许多真实 网络的实证研究都表明: 真实世界网络既不是规 则网络, 也不是随机网络, 而是一大类确定性与 随机性混合的网络, 兼具小世界和无标度两种特 性, 具有与规则网络和随机图完全不同的统计特 性 [9∼15] . Barab´asi 和 Albert 通过追踪万维网的动态演 化过程, 发现了许多复杂网络具有大规模的高度 自组织特性, 形成无标度特性的主要机制是网络 增长和随机择优连接两条规则, 而且随机择优 (偏 好) 是产生无标度特性的最重要的机制. 然而, 随 着网络研究的深入, 考察现实世界的许多网络发 现: 现实世界中实际网络节点之间相互作用并非 相同, 重要性和影响程度各异, 实际网络几乎都 是有权网络, 因此, 不仅需要研究无权网络, 而 且必须研究加权网络, 才能更好地捕捉和揭示真 实网络上动力学特征与拓扑结构之间的联系, 以 及权重变化在网络时空动力学特性演化 (或对系 统功能) 的重要意义和作用. 许多研究丰富了能 够产生无标度特性和小世界效应的物理机制的多 样性, 如: 复制、最近邻连接、点强和边权驱动、 权重和适应度联合驱动以及多种混合驱动等方 式 [17∼24] , 有权网络模型成为网络科学的一个非常 重要的课题和方向, 国内外已经提出了许多有意 义的加权网络模型 [17∼24] . 我们在表 1 简介和评 述了若干加权网络理论模型的主要特点. 从表 1 可见: 当前有权网络模型主要是广义 随机网络模型, 归纳起来, 根据网络节点之间连边 概率 p 不同, 有权网络有如下的主要生成方式和 基本特点 [16∼24,36∼39]: (1) 度和点强驱动机制. 边连接按度择优的连 接概率为 Π j→i = ki .X j kj 当 m 条边连接完后, 给节点 j 的每条边赋予权 重 (wij = wji): wji = ki/ P |i 0 | ki 0 和点强度为 sj = P i wij = 1. 式中 |i 0 | 表示新节点 j 所连接 的点的集合. 还可以采用不同的边权赋值方式. (2) 度和适应度联合驱动机制. 在 BA 模型基 础上, 提出把节点度和适应度相结合, 每个新节点 以 m 条边连接到已存在网络中的节点 i 上, 连接 到节点 j 上的概率与 i 的度和适应度 (fitness) 两 者成正比 Πi = ηiki .X j ηjkj (3) 权重和适应度联合驱动机制. 与 (2) 类似, 与度择优改为与权重联合. (4) 点强择优和边权随动态重新分配. 考虑 了: (i) 增长性. 新节点将连接 m 个已有节点, 节 点 i 被选择的概率为 Πn→i = s w i e −dni/Rc P j s w j e−dnj /Rc , 式 中 Rc 是特征距离, dni 是节点 n 和 i 间的欧氏距 离. (ii) 动态边权. 每条新边 (n, i) 被赋予固定权重 w0 (取 w0 = 1), 新增边将导致改变已有边的权重: wij → wij + δwij/sw i . (5) 点强度驱动和边权逐渐加强机制 (BBV 模 型). 可以模拟实际网络系统中相互作用强度的变 化. 其演化算法是: 首先, 网络增长时, 新节点 n 与 老节点 i 的连接概率与点强择优概率为 Π BBV n→i = P si j sj = P snsi j snsj 这里 si , sj 表示相应节点 (i,j) 的强度. 在每时步, 带有 m 条边的新节点 j 加入到网络中, 其中每条 边的权重为 w0, 每条边根据点强度驱动的方式选 择老节点 i 与之相连. 新边 lji 的加入会导致节点 i 与其邻居 l 之间的边权重新分配如下 wil → wil + ∆wil, ∀l ∈ ∆wil, ∆wil = δwil/si 研究表明: 拓扑特性同时兼有度、点权和边权 3 种幂律分布, 且依赖于权重参数 δ 和 w0. 边权幂
第6期 方锦清等:网络科学中统一混合理论模型的若干研究进展 律指数 2+1/6:当6很大时,仍为无标度网(k)≈Ak,A≠u),B=1,y=1s=(46+3)/ 络,当δ→∞时, 点强与度之间关系为(26+1) 表1若干加权网络理论模型研究概况一览表 模型特点与网络形成机制 模型主要结果 简评 文献 DM模型:(1)任给一组节点和边,从 边权分布、度分布和 得到3个幂律 条权重为1的边开始,每时步根据与权 点强分布都服从幂律 分布.但是无 重成正比的概率先选择一条边,使该边 分布,其幂指数分别 法反映真实网 的权重增加一个小量6;(2)一对新节点 为~m=2+2/6和 络中具有群聚 连接到该边的两个端点上,新边的权重 =s=2+1/(6+1) 系数C和关联 设为1.模型主要依赖于权重高的边 系数rc问题. YJBT模型,每时步新节点j加入网络 度分布和强度分布都 两个幂律分 [18 新节点具有m≤mo(初始节点数)条边 为幂律函数,度幂律布.仍存在上 这些边按度择优规则连接到老节点后 y=3.点强幂律7 述问题 给节点j的每条边赋予边权和点强.可 依赖于m,两幂指数 以采用不同的赋权值方式 不同 BBPⅤ模型,在BA模型基础上,提出 度分布为不同幂律 累积度幂律分 把节点度和适应度相结合,每个新节点 数的加权之和,存在 布与度对数有 以m条边连接到已存在网络中的节点 对数的幂律分布,并 关.存在问题 上,连接到节点j上的概率与i的度和 与适应度分布的选择 同上 适应度( fitness)两者成正比 有关 属于YJBT推广模型.新的连接赋权既 强度分布为幂律函 给出点强幂律 受到以随机连接概率p的驱动,又要按 数,幂律~s依赖于p 分布的表达 节点的适应度以1-p的概率赋权连接 随p增加而减小,p= 式.存在问题 当p=1时为YJBT模型;当p=0时,边 时权重分布由适应度 同上 权的赋值完全由节点的适应度决定 决定 AK模型,点强驱动增长模型.考虑了 点强分布为有幂律尾 点强驱动适合 边权对网络结构演化的影响.新节点 的稳定分布,而与边 于一些实际网 选择一个老节点i连接概率正比于节点权分布无关.当平均 络.存在问题 的强度,关注节点强度对连接的驱动作 度从1趋向+∞时 同上 用,即点强度越大的点被连接到的概率 其扩展模型的点强为 幂指数从3趋于2 BB模型,考虑了点权优先连接机制和 分析了国际航空加权 适于实现世界 边权的动态重新分配新增边改变已有 网的统计性质.点强 中交通加权 边的权重:m→ny+bmi/s 分布和边权分布都是 网.存在问题 幂律分布 同上 BBⅤ模型,它基于BB模型,提出点强 拓扑特性同时兼有点 具有代表性加 度驱动和边权逐渐加强机制,模拟实际 度、点权和边权的3 权无标度网 网络系统中强度的变化新加入边导致 种幂律分布,且依赖 节点i与其邻居l之间的边权重新分配 于权重参数6和to 3A模型 模型允许在老节点之间连边,已有的沿 着连边的交通流也将随着网络的生长 而不断更新 TDE模型.引进两种机制:相互影响的 度分布、边权分布、点 所得网络特性 [24 拓扑生长和强度耦合同步,保持拓扑生 强度分布均为幂律分 比较接近实 长规则,强度大的节点优先连接.增加 布,并且群聚系数C际但v>1 老节点之间的连边,含权择优服从强度 随ω的增大而增大 不大符合实 耦合动力学更新机制边权总增量取平和度度关联具有异 均权值.带有m条边的新节点n按BBV 配相称性 规则与老节点随机连接
第 6 期 方锦清等 : 网络科学中统一混合理论模型的若干研究进展 665 律指数 γw = 2 + 1/δ; 当 δ 很大时, 仍为无标度网 络, 当 δ → ∞ 时, γ = 2. 点强与度之间关系为 s(k) ≈ Akβ , A 6= hwi, β = 1, γ = γs = (4δ + 3)/ (2δ + 1). 表 1 若干加权网络理论模型研究概况一览表 模型特点与网络形成机制 模型主要结果 简 评 文 献 DM 模型: (1) 任给一组节点和边, 从一 条权重为 1 的边开始, 每时步根据与权 重成正比的概率先选择一条边, 使该边 的权重增加一个小量 δ; (2) 一对新节点 连接到该边的两个端点上, 新边的权重 设为 1. 模型主要依赖于权重高的边. 边权分布、度分布和 点强分布都服从幂律 分布, 其幂指数分别 为 γw = 2 + 2/δ 和 γ = γs ＝ 2+1/(δ+1) 得到 3 个幂律 分布. 但是无 法反映真实网 络中具有群聚 系数 C 和关联 系数 rc 问题. [17] YJBT 模型, 每时步新节点 j 加入网络, 新节点具有 m≤m0(初始节点数) 条边, 这些边按度择优规则连接到老节点后, 给节点 j 的每条边赋予边权和点强. 可 以采用不同的赋权值方式. 度分布和强度分布都 为幂律函数, 度幂律 γ = 3. 点强幂律 γs 依赖于 m, 两幂指数 不同. 两 个 幂 律 分 布. 仍存在上 述问题. [18] BBPV 模型, 在 BA 模型基础上, 提出 把节点度和适应度相结合, 每个新节点 以 m 条边连接到已存在网络中的节点 i 上, 连接到节点 j 上的概率与 i 的度和 适应度 (fitness) 两者成正比. 度分布为不同幂律函 数的加权之和, 存在 对数的幂律分布, 并 与适应度分布的选择 有关. 累积度幂律分 布与度对数有 关. 存在问题 同上. [19] 属于 YJBT 推广模型. 新的连接赋权既 受到以随机连接概率 p 的驱动, 又要按 节点的适应度以 1 − p 的概率赋权连接. 当 p=1 时为 YJBT 模型; 当 p=0 时, 边 权的赋值完全由节点的适应度决定. 强 度 分 布 为 幂 律 函 数, 幂律 γs 依赖于 p, 随 p 增加而减小, p=0 时权重分布由适应度 决定. 给出点强幂律 分 布 的 表 达 式. 存在问题 同上. [20] AK 模型, 点强驱动增长模型. 考虑了 边权对网络结构演化的影响. 新节点 j 选择一个老节点 i 连接概率正比于节点 的强度, 关注节点强度对连接的驱动作 用, 即点强度越大的点被连接到的概率 越高. 点强分布为有幂律尾 的稳定分布, 而与边 权分布无关. 当平均 度从 1 趋向 +∞ 时, 其扩展模型的点强为 幂指数从 3 趋于 2. 点强驱动适合 于一些实际网 络. 存在问题 同上. [21] BB 模型, 考虑了点权优先连接机制和 边权的动态重新分配. 新增边改变已有 边的权重: wij → wij + δwij/sw i . 分析了国际航空加权 网的统计性质. 点强 分布和边权分布都是 幂律分布. 适于实现世界 中 交 通 加 权 网. 存在问题 同上. [22] BBV 模型, 它基于 BB 模型, 提出点强 度驱动和边权逐渐加强机制, 模拟实际 网络系统中强度的变化. 新加入边导致 节点 i 与其邻居 l 之间的边权重新分配. 模型允许在老节点之间连边, 已有的沿 着连边的交通流也将随着网络的生长 而不断更新. 拓扑特性同时兼有点 度、点权和边权的 3 种幂律分布, 且依赖 于权重参数 δ 和 w0. 具有代表性加 权 无 标 度 网 络. 当 δ = 0 即 BA 模型. [23] TDE 模型. 引进两种机制: 相互影响的 拓扑生长和强度耦合同步, 保持拓扑生 长规则, 强度大的节点优先连接. 增加 老节点之间的连边, 含权择优服从强度 耦合动力学更新机制. 边权总增量取平 均权值. 带有 m 条边的新节点 n 按 BBV 规则与老节点随机连接. 度分布、边权分布、点 强度分布均为幂律分 布, 并且群聚系数 C 随 ω 的增大而增大, 和度 - 度关联具有异 配相称性. 所得网络特性 比 较 接 近 实 际. 但 w > 1 不 大 符 合 实 际. [24]
666 力 展 2008年第38卷 (6)相互影响的拓扑生长和强度耦合同步机杂网络的混合理论模型3部曲的主要框架及其 制(TDE模型)24.引进两种机制:保持拓扑生长进展 规则,按照点强择优连接;增加了老节点之间的连 边,含权择优服从强度耦合动力学更新机制 3统一混合网络模型理论的3部曲 cy→{y+1,以概率 Sis ;,以概率1 自然界和人类社会生活在一个既可确定又有 a1;群聚系数C随ω的增大而增大 及多种混合方式.另一种典型表现在由混沌方程 (⑦)地理位置最(次)邻近择优机制,可谓“近为节点组成的复杂动态网络,随着网络演化,网 水楼台先得月”.类似地,还可以利用局域信息 络系统随时空发生分岔、阵发和混沌等斑图现象, (8)权重驱动与局域世界规则联合驱动机制.就是复杂网络上再次体现出确定性与随机性、有 (9)拓扑结构与动力学(或网络功能)演化相序与无序、简单与复杂的一种典型的和谐统一形 互影响机制 式.不论是物理网络、还是生物网络和技术网络 总之,在这些驱动机制下,几乎现有的有权演概不例外,只不过确定性和随机性两者的混合程 化网络模型的度分布、点强分布和边权分布都服度和采取方式依具体对象不同而己,它们总是自 从幂律分布,只是它们的幂函数形式和幂指数不然地和谐地共存在自组织复杂网络系统之中.因 同而已.显然,有权演化网络的研究揭示了形成多此,多种混合和择优方式在自然界和人类社会中 个幂律分布的物理机制及其多样性和复杂性.把具有普遍性和广泛性,这是理论研究的实际基础 无权网络推进了一步,更接近实际网络特性 和真实背景,完全符合自然的、社会的、物理的、 必须指出:除了个别模型外,上述所有有权模技术的以及生命的实际网络情况.许多研究已经 型几乎都属于广义随机网络模型.显然,这些有权发现许多实际网络兼有小世界特性和无标度性质 网络模型存在的最主要的一个共同问题是:它们即它们的拓扑特性不仅具有小的最短平均路径长 都只考虑随机性驱动机制,而且都忽视了确定性度( average path length,APL),而且具有大的平均 驱动(包括不同确定性择优连接等)机制,也就是群聚系数( Average clustering coefficient,ACC)那 它们都缺乏实际世界中自然存在的两种混合连接么,为什么许多广义随机网络的理论模型仍然还 的可能方式.追究其最主要原因可能与这些理论不足以同时揭示或完全具备实际网络的完全特性 模型能否求其解析解有密切的关系,只考虑随机呢?wats和 Strogatz提出的小世界模型是在网 性连接无疑方便于理论推导工作,可以比较容易络大小固定的规则圆周上,只通过对少数节点进 地求到理论表达式,而两种混合情形非常难求得行随机的“远程连接”,就可导致从规则到随机之 解析解.因此上述这些模型虽然也可以部分反映间的转变特性.于是,人们又要问:如果网络是 实际有权网络的主要特性,但是仍然很不全面,就动态增长演化的情形,那么生长网络的连接方式 是因为这些模型从根本上与自然界和人类社会中从随机到规则或从规则到随机相互转变时,将使 普遍存在的随机性和确定性两者是和谐统一的真演化网络的拓扑特性和动力学行为发生什么样转 世界并不符合所致 变?换句话说,若采用随机性与确定性连接混合 为了刻画具有随机性和确定性两者混合的生长和多种混合方式时,这样的网络模型是否能 真实网络的复杂性与多样性,进一步改进和完够得到更符合实际网络的特性?如此又会揭示和 善有关网络理论模型,深入开展混合网络理论模出现什么新的特点和规律?为了寻求这个问题的 型的研究是很有必要的.本文下面重点评述复答案和相应的解决方法与途径,为了描述确定性
666 力 学 进 展 2008 年 第 38 卷 (6) 相互影响的拓扑生长和强度耦合同步机 制 (TDE 模型) [24] . 引进两种机制: 保持拓扑生长 规则, 按照点强择优连接; 增加了老节点之间的连 边, 含权择优服从强度耦合动力学更新机制 wij → ( wij + 1,以概率wpij , wij ,以概率1 − wpij , wpij = P sisj a 1; 群聚系数 C 随 ω 的增大而增大. (7) 地理位置最 (次) 邻近择优机制, 可谓 “近 水楼台先得月”. 类似地, 还可以利用局域信息. (8) 权重驱动与局域世界规则联合驱动机制. (9) 拓扑结构与动力学 (或网络功能) 演化相 互影响机制. 总之, 在这些驱动机制下, 几乎现有的有权演 化网络模型的度分布、点强分布和边权分布都服 从幂律分布, 只是它们的幂函数形式和幂指数不 同而已. 显然, 有权演化网络的研究揭示了形成多 个幂律分布的物理机制及其多样性和复杂性. 把 无权网络推进了一步, 更接近实际网络特性. 必须指出: 除了个别模型外, 上述所有有权模 型几乎都属于广义随机网络模型. 显然, 这些有权 网络模型存在的最主要的一个共同问题是: 它们 都只考虑随机性驱动机制, 而且都忽视了确定性 驱动 (包括不同确定性择优连接等) 机制, 也就是 它们都缺乏实际世界中自然存在的两种混合连接 的可能方式. 追究其最主要原因可能与这些理论 模型能否求其解析解有密切的关系, 只考虑随机 性连接无疑方便于理论推导工作, 可以比较容易 地求到理论表达式, 而两种混合情形非常难求得 解析解. 因此上述这些模型虽然也可以部分反映 实际有权网络的主要特性, 但是仍然很不全面, 就 是因为这些模型从根本上与自然界和人类社会中 普遍存在的随机性和确定性两者是和谐统一的真 实世界并不符合所致. 为了刻画具有随机性和确定性两者混合的 真实网络的复杂性与多样性, 进一步改进和完 善有关网络理论模型, 深入开展混合网络理论模 型的研究是很有必要的. 本文下面重点评述复 杂网络的混合理论模型 3 部曲的主要框架及其 进展. 3 统一混合网络模型理论的 3 部曲 自然界和人类社会生活在一个既可确定又有 随机概率的世界里, 这就是随机性与确定性的统 一和谐的世界. 基于这个最基本事实确认: 进一 步完善和发展网络的混合理论模型是网络模型研 究的最重要方向之一. 随机性与确定性的共存现 象普遍存在, 比比皆是, 例如, 每年全国高考招生 网、公务员考试网和社会就业 (人才招聘) 网, 等 等, 都包含随机性和确定性两种混合择优过程, 以 及多种混合方式. 另一种典型表现在由混沌方程 为节点组成的复杂动态网络, 随着网络演化, 网 络系统随时空发生分岔、阵发和混沌等斑图现象, 就是复杂网络上再次体现出确定性与随机性、有 序与无序、简单与复杂的一种典型的和谐统一形 式. 不论是物理网络、还是生物网络和技术网络, 概不例外, 只不过确定性和随机性两者的混合程 度和采取方式依具体对象不同而已, 它们总是自 然地和谐地共存在自组织复杂网络系统之中. 因 此, 多种混合和择优方式在自然界和人类社会中 具有普遍性和广泛性, 这是理论研究的实际基础 和真实背景, 完全符合自然的、社会的、物理的、 技术的以及生命的实际网络情况. 许多研究已经 发现许多实际网络兼有小世界特性和无标度性质, 即它们的拓扑特性不仅具有小的最短平均路径长 度 (average path length, APL), 而且具有大的平均 群聚系数 (Average clustering coefficient, ACC). 那 么, 为什么许多广义随机网络的理论模型仍然还 不足以同时揭示或完全具备实际网络的完全特性 呢？Watts 和 Strogatz 提出的小世界模型是在网 络大小固定的规则圆周上, 只通过对少数节点进 行随机的 “远程连接”, 就可导致从规则到随机之 间的转变特性. 于是, 人们又要问: 如果网络是 动态增长演化的情形, 那么生长网络的连接方式 从随机到规则或从规则到随机相互转变时, 将使 演化网络的拓扑特性和动力学行为发生什么样转 变？换句话说, 若采用随机性与确定性连接混合 生长和多种混合方式时, 这样的网络模型是否能 够得到更符合实际网络的特性？如此又会揭示和 出现什么新的特点和规律？为了寻求这个问题的 答案和相应的解决方法与途径, 为了描述确定性
第6期 方锦清等:网络科学中统一混合理论模型的若干研究进展 与随机性的和谐统一的世界以及增长过程的复杂环为和谐统一的混合择优模型( harmonious unify 性和多样性,已经提出和发展了统一的混合网络 ing hy brid preferential model, HUHPM);中间环是大 模型,形成网络理论模型的3部曲,如图1所示,统一混合网络模型( large unifying hybrid network 数值模拟和理论分析揭示了统一混合网络演化模 model,LUHN;最外环是大统一混合变速增长 型随多个混合比变化的若干普适特性,包括同时模型( large unifying hybrid variable growing model 兼备小世界效应和无标度特性及其他新特点和新 LUHVGM或 unifying hy brid network model variable 现象,并已经应用于一些现有的无权的和有权的 speed growth, UHNMVSG).在整个理论体系里引进 复杂网络演化模型,确实可以达到更接近于实际了4个混合比,构成统一混合网络模型的3部曲 网络的特性.图1给出统一混合网络理论模型其主要思想、理论框架和结果分别在以下各节概 的3部曲的基本思想和理论框架的示意图,最内述和评论 HUHPM→ LUHNM→ LUHVGN 确定性变速「大 (LUHVGI 长模型□随机性变速 3 RVG 大统一混合模型( LUHNM) 第2曲 和谐统一混合择优模型( HUHPM) 曲 dr= DPA/RPA 确定性连接(DA 随机性连接(RA) 方式 HPAI(DPA) (RPA) (GRA)(OL) DA=HPA+DPA, /d= HPA/DA, RA- RPA+GRA, gr=GRA/RA 图1统一混合网络理论模型的3部曲示意图.最内环(第1曲)为 HUHPM;中间环(第2曲)是 LUHNM;最外环 (第3曲)是 LUHVGM,其中DPA:确定性择优时间步数;RPA:随机性择优时间步数;GRA:为一般随机连 接的时步数;HPA:为确定性扶贫连接的时步数;RA:为总随机性连接的时步数;DA:为总确定性连接的时 步数 31第1部曲:和谐统一的混合择优模型B25~32 dom attachment,RA),d与r范围都为∈0,+∞],由 图1中最内环示出 HUHPM,该模型主要是为此确定一个总混合比. HUHPM表现出具有不同特 了克服无权BA网络模型叫和表1中许多有权点的3种典型的混合工作模式:(1)如果d>1/1, 网络模型只有“随机性择优”的不足,中国原子能则属于确定性连接占主导情形;(i)如果d=1/1, 科学研究院网络科学小组(CIAE)在这类网络模则属于随机性与确定性两种连接相同(平分秋色 型中提出引入“确定性择优”思想,在复杂网络生或势均力敌)情形;(i)如果d∝1/,则属于随机 长中采用两种混合择优连接,以改进和完善这一性连接占主导情形;()和(i)两种都是不对称混 大类的无权和有权网络,为此, HUHPM作为混合合连接.在这个混合模型第1曲 HUHPM中,网络 网络理论模型的第一曲,其最大特点是只定义一性质和生长所需的规模大小都完全取决于一个总 个总混合比dr 混合比dr.HUHM模型能够较好地描述了规则 d DA 要云()(确定性)和随机网络之间的转变特性它原则上适 用于任何类型的无权及有权复杂网络模型,例如 这里d为总确定性连接的时步数( determinatin at-已应用于典型的无权BA( Barabasi-albert)模型、 tachment,DA);r为总随机性连接的时步数(ran有权BBv( barrat-barthelemy- vespignanI)模型和有
第 6 期 方锦清等 : 网络科学中统一混合理论模型的若干研究进展 667 与随机性的和谐统一的世界以及增长过程的复杂 性和多样性, 已经提出和发展了统一的混合网络 模型, 形成网络理论模型的 3 部曲, 如图 1 所示, 数值模拟和理论分析揭示了统一混合网络演化模 型随多个混合比变化的若干普适特性, 包括同时 兼备小世界效应和无标度特性及其他新特点和新 现象, 并已经应用于一些现有的无权的和有权的 复杂网络演化模型, 确实可以达到更接近于实际 网络的特性. 图 1 给出统一混合网络理论模型 的 3 部曲的基本思想和理论框架的示意图, 最内 环为和谐统一的混合择优模型 (harmonious unifying hybrid preferential model, HUHPM); 中间环是大 统一混合网络模型 (large unifying hybrid network model, LUHNM); 最外环是大统一混合变速增长 模型 (large unifying hybrid variable growing model, LUHVGM 或 unifying hybrid network model variable speed growth, UHNMVSG). 在整个理论体系里引进 了 4 个混合比, 构成统一混合网络模型的 3 部曲, 其主要思想、理论框架和结果分别在以下各节概 述和评论. 图 1 统一混合网络理论模型的 3 部曲示意图. 最内环 (第 1 曲) 为 HUHPM; 中间环 (第 2 曲) 是 LUHNM; 最外环 (第 3 曲) 是 LUHVGM, 其中 DP A: 确定性择优时间步数; RP A: 随机性择优时间步数; GRA: 为一般随机连 接的时步数; HP A: 为确定性扶贫连接的时步数; RA: 为总随机性连接的时步数; DA: 为总确定性连接的时 步数. 3.1 第 1 部曲: 和谐统一的混合择优模型 [25∼32] 图 1 中最内环示出 HUHPM, 该模型主要是为 了克服无权 BA 网络模型 [11] 和表１中许多有权 网络模型只有 “随机性择优” 的不足, 中国原子能 科学研究院网络科学小组 (CIAE) 在这类网络模 型中提出引入 “确定性择优” 思想, 在复杂网络生 长中采用两种混合择优连接, 以改进和完善这一 大类的无权和有权网络, 为此, HUHPM 作为混合 网络理论模型的第一曲, 其最大特点是只定义一 个总混合比 dr dr = d r = DA RA (1) 这里 d 为总确定性连接的时步数 (determinatic attachment, DA); r 为总随机性连接的时步数 (random attachment, RA), d 与 r 范围都为 ∈ [0, +∞], 由 此确定一个总混合比. HUHPM 表现出具有不同特 点的 3 种典型的混合工作模式: (i) 如果 dr À 1/1, 则属于确定性连接占主导情形; (ii) 如果 dr = 1/1, 则属于随机性与确定性两种连接相同 (平分秋色, 或势均力敌) 情形; (iii) 如果 dr ¿ 1/1, 则属于随机 性连接占主导情形; (i) 和 (iii) 两种都是不对称混 合连接. 在这个混合模型第 1 曲 HUHPM 中, 网络 性质和生长所需的规模大小都完全取决于一个总 混合比 dr. HUHPM 模型能够较好地描述了规则 (确定性) 和随机网络之间的转变特性, 它原则上适 用于任何类型的无权及有权复杂网络模型, 例如 已应用于典型的无权 BA(Barab´asi-albert) 模型、 有权 BBV(barrat-barth´elemy-vespignani) 模型和有
668 力学 展 2008年第38卷 权 TDE(traffic-driven evolution)模型(参看表1),γ与混合比dr及权重参数存在复杂的关系,对于 分别称它们为 HUHPM-BA网络, HUHPM-BBV网 HUHPM-BA和 HUHPM-BBV分别为26~28 络和 HUHPM-TDE网络 在网络生长演化的过程中总混合比d大小 UHPM 1 是唯一的参数,实施随机性择优与确定性连接相 结合,而两者连接的优先次序是完全灵活的,两者和 混合交替生长达到所需的比较大网络规模(长时 间连接)的最终结果不受影响 HUHPM实行混合M= 生长网络的主要机制和原则如下 1)增长方式:对任何无权和有权网络模型, 46+41/exp +A4/(26+1) 先依它们原来模型的各自生长规则进行生长即可 (2)新连接方式:根据所研究的总混合比dr,同样得到 HUHPM-TDE网络的?与混合比d及 混合连接的次序先后可以灵活,从统计意义上说,的复杂关系26~23.上述理论结果与数值模拟结果 最终并不影响统计结果.()对于确定性择优方式:比较一致.从上可见:不论是无权 HUHPM-BA网 在每次连接后,整个网络按照节点度从大到小进络,还是有权 HUHPM-BBV网络(包括 HUHPM 行排序:k1>k>…>km>…>kn,然后对mTDE等网络),它们的幂率指数y与混合比d以 个度最大的节点优先连接.(i)对于随机性择优方及与权重参数(6,m)和连接边数m之间都存在复 式:由现有的网络模型中择优规则而定.这样,可杂的指数及参数成反比的复合关系,并非原来模 以把 HUHPM的思想与方法应用于任何典型模型,型中简单的指数关系,所有公式都与混合比和原 如:无权BA模型、有权BBⅤ模型和TDE模型,来模型的权重参数(d/r,6,w,x)之间相互关联, 分别称为 HUHPM-BA网络, HUHPM-BBV网络和说明这种错综复杂的拓扑关系与产生的网络混合 HUHPM-TDE网络,比原来模型的关键不同点是:方式、结构、模型类型(参数)等紧密相关,揭示了 不仅仅有随机择优方式,而且有确定性择优方式,两种混合择优方式既保持了和谐混合共存,又体 即必须是实行两种混合择优连接,交替进行,直到现它们之间的相互作用与竞争的状况.由于混合 生成所需要的网络规模为止.研究表明:不同领域连接情形下精确求解在理论上难度很大,还需要 的任何已有的复杂网络模型都可在 HUHPM的框进一步探讨 架下进行重新硏究,既能够保持原来模型的特点 (2) HUHPM网络的小世界特性与其他模型 和规律,而且还赋予模型新的特性,使得原有的模比较,具有最短平均路径距离L和最大的平均群 型更加符合和谐统一的真实世界.由于 HUHPM聚系数C,这就更加符合许多实际网络的拓扑特 模型基本抓住真实世界两大类择优连接的混合特性2728.由于平均群聚系数C随d增加而增加 点,所以除了得到与原来模型的主要结果外,还发混合择优模型具有很高群聚系数,3种典型模型的 现了混合网络的一些普适规律 群聚系数随混合比的变化趋势基本一致,增加混 第1曲 HUHPM的主要结果概述如下 合比有利于网络局部集团化 (1) HUHPM的无权和有权网络(如 HUHPM (3)混合择优产生的拓扑结构变化对网络系 BA、 HUHPM-BBV与 HUHPM-TDE)中的节点度,统的动力学特性有明显的影响.当满足网络同 点强和边权3种分布都服从幂律分布,发现所有步第一判据(类型I)时 HUHPM网络动力学同步 幂指数γ都对总混合比d的变化具有很强的敏能力增强了,而满足网络同步第二判据(类型I 感性,且随log(dr)的增加而增加,dr=1/1是一时 HUHPM的网络动力学同步能力减小了.另外 个阈值,它是拓扑特性的一个转变点(相变点).在 HUHPM网络的一致性收敛速度随dr增加而增 d≤1/1时,7≤3,这符合随机择优占主导的所有加,而减少了网络到达一致性的最大容忍延迟时 广义随机模型情形;对于>1/1情形,在BA模间.这些结果有助于理解和设计实际需要的网络 型和BBV模型中,尽管δ不同,γ按照log(dx)迅以达到所需的动力学特性 速上升;对于 HUHPM-TDE模型,考虑v<1情形 4) HUHPM网络中的熵随着dr增加而减少, 是比较符合实际,γ是随log(dr)迅速增加.幂指数说明提高总混合比可以增强网络系统的自组织的
668 力 学 进 展 2008 年 第 38 卷 权 TDE(traffic-driven evolution) 模型 (参看表１), 分别称它们为 HUHPM-BA 网络, HUHPM-BBV 网 络和 HUHPM-TDE 网络. 在网络生长演化的过程中总混合比 dr 大小 是唯一的参数, 实施随机性择优与确定性连接相 结合, 而两者连接的优先次序是完全灵活的, 两者 混合交替生长达到所需的比较大网络规模 (长时 间连接) 的最终结果不受影响. HUHPM 实行混合 生长网络的主要机制和原则如下: (1) 增长方式: 对任何无权和有权网络模型, 先依它们原来模型的各自生长规则进行生长即可. (2) 新连接方式: 根据所研究的总混合比 dr, 混合连接的次序先后可以灵活, 从统计意义上说, 最终并不影响统计结果. (i) 对于确定性择优方式: 在每次连接后, 整个网络按照节点度从大到小进 行排序: k1 > k2 > · · · > km > · · · > kn, 然后对 m 个度最大的节点优先连接. (ii) 对于随机性择优方 式: 由现有的网络模型中择优规则而定. 这样, 可 以把 HUHPM 的思想与方法应用于任何典型模型, 如: 无权 BA 模型、有权 BBV 模型和 TDE 模型, 分别称为 HUHPM-BA 网络, HUHPM-BBV 网络和 HUHPM-TDE 网络, 比原来模型的关键不同点是: 不仅仅有随机择优方式, 而且有确定性择优方式, 即必须是实行两种混合择优连接, 交替进行, 直到 生成所需要的网络规模为止. 研究表明: 不同领域 的任何已有的复杂网络模型都可在 HUHPM 的框 架下进行重新研究, 既能够保持原来模型的特点 和规律, 而且还赋予模型新的特性, 使得原有的模 型更加符合和谐统一的真实世界. 由于 HUHPM 模型基本抓住真实世界两大类择优连接的混合特 点, 所以除了得到与原来模型的主要结果外, 还发 现了混合网络的一些普适规律. 第 1 曲 HUHPM 的主要结果概述如下: (1) HUHPM 的无权和有权网络 (如 HUHPMBA 、HUHPM-BBV 与 HUHPM-TDE) 中的节点度, 点强和边权 3 种分布都服从幂律分布, 发现所有 幂指数 γ 都对总混合比 dr 的变化具有很强的敏 感性, 且随 log(dr) 的增加而增加, dr = 1/1 是一 个阈值, 它是拓扑特性的一个转变点 (相变点). 在 dr ≤ 1/1 时, γ ≤ 3, 这符合随机择优占主导的所有 广义随机模型情形; 对于 dr > 1/1 情形, 在 BA 模 型和 BBV 模型中, 尽管 δ 不同, γ 按照 log(dr) 迅 速上升; 对于 HUHPM-TDE 模型, 考虑 w < 1 情形 是比较符合实际, γ 是随 log(dr) 迅速增加. 幂指数 γ 与混合比 dr 及权重参数存在复杂的关系, 对于 HUHPM-BA 和 HUHPM-BBV 分别为 [26∼28] γ HUHPM BA = 1 β + 1 = A1 , exp "µ dr A2 ¶A3 # + A4 (2) 和 γ HUHPM BA = Ã 4δ + A1 , exp "µ dr A2 ¶A3 # + A4 !,(2δ + 1) (3) 同样得到 HUHPM-TDE 网络的 γ 与混合比 dr 及 w 的复杂关系 [26∼28] . 上述理论结果与数值模拟结果 比较一致. 从上可见: 不论是无权 HUHPM-BA 网 络, 还是有权 HUHPM-BBV 网络 (包括 HUHPMTDE 等网络), 它们的幂率指数 γ 与混合比 dr 以 及与权重参数 (δ,w) 和连接边数 m 之间都存在复 杂的指数及参数成反比的复合关系, 并非原来模 型中简单的指数关系, 所有公式都与混合比和原 来模型的权重参数 (d/r, δ, w, χ) 之间相互关联, 说明这种错综复杂的拓扑关系与产生的网络混合 方式、结构、模型类型 (参数) 等紧密相关, 揭示了 两种混合择优方式既保持了和谐混合共存, 又体 现它们之间的相互作用与竞争的状况. 由于混合 连接情形下精确求解在理论上难度很大, 还需要 进一步探讨. (2) HUHPM 网络的小世界特性与其他模型 比较, 具有最短平均路径距离 L 和最大的平均群 聚系数 C, 这就更加符合许多实际网络的拓扑特 性 [27,28] . 由于平均群聚系数 C 随 dr 增加而增加, 混合择优模型具有很高群聚系数, 3 种典型模型的 群聚系数随混合比的变化趋势基本一致, 增加混 合比有利于网络局部集团化. (3) 混合择优产生的拓扑结构变化对网络系 统的动力学特性有明显的影响 [29] . 当满足网络同 步第一判据 (类型 I) 时 HUHPM 网络动力学同步 能力增强了, 而满足网络同步第二判据 (类型 II) 时 HUHPM 的网络动力学同步能力减小了. 另外 HUHPM 网络的一致性收敛速度随 dr 增加而增 加, 而减少了网络到达一致性的最大容忍延迟时 间. 这些结果有助于理解和设计实际需要的网络, 以达到所需的动力学特性. (4) HUHPM 网络中的熵随着 dr 增加而减少, 说明提高总混合比可以增强网络系统的自组织的
第6期 方锦清等:网络科学中统一混合理论模型的若干研究进展 有序度8.32 fd≠1/1和gr≠1/1任一情形出现,该模型实际上 由此可见,第1曲 HUHPM模型同时进行随包括了不对称连接.第2曲中与第1曲类似,存 机性择优与确定性择优后,初步理论分析结果与在3种不同的典型混合情形,对于随机性连接:(i) 数值模拟结果相一致,通过调控总混合比可以达如果gr>1/1,则属于随机性连接中一般随机(等 到和谐统一,从物理机制上揭示了适当的随机性概率)连接占主导地位;(i)如果gr=1/1,则属 与确定性混合择优能够同时产生无标度特性和小 般随机连接与随机性择优连接两者平分秋色 世界效应上述发现具有应用潜力,主要有以下3情形;(i)如果gr≤1/1,则属于随机性择优连接 方面的应用前景.(1)由于度分布、点强分布和边占主导地位;这里()和(i)两种是随机性择优连 权分布幂律指数γ对总混合比dr的变化具有敏接中不对称混合连接.同样,对于确定性连接:(i) 感性,这一特性与混沌轨道对初始条件的敏感性如果fd》1/1,则属于确定性连接中扶贫(度大 相类似,因此只要巧妙设计就有可能被应用作为的节点与度小的节点)连接占主导地位;(i)如果 种新的加密通信原理和手段,应用于密码学和fd=1/1,则属于确定性连接中扶贫与择优连接两 保密通信领域.(2)由于最短平均路径距离小,而者平分秋色情形;(ⅲ)如果fd≤1/1,则属于确定 群聚系数高,并且随混合比d大小而改变,这样性连接中确定性择优连接占主导情形;显然,()和 人们就可以根据实际需要和要求来设计和调控网(i)两种情形是确定性连接情形下不对称混合连 络结构,以满足实现工程技术上所需要的不同特接.因此,第2部曲的网络所有特性取决于3个混 殊的用途.(3)上述发现有助于理解生命系统、人合比(dr,gr,fd)及其各种组合形式,如此形成的复 类社会和自然界中发生的某些网络特性 杂网络将产生丰富的多样性和复杂性 3.2第2部曲:大统一混合网络模型③3~4o 第2部曲模型的基本算法与第1部曲模型类 应该注意到第1曲 HUHPM模型的精确理似所不同的是考虑了3个混合比(ar,g,fd).当 论分析极具挑战性,模型还需要进一步完善,最主在网络中选择节点与新增节点连接时,假定被选 要一个不足之处是:它仅仅考虑两大类的择优连择的节点1与新节点连接的概率为k,即首先 接方式,还不能完全地反映实际世界网络形成中按照所需的总混合比d确定节点i是随机性连 存在连接方式的多样性和复杂性因为不论随机接还是确定性连接如果是随机性连接方式,就以 性连接,还是确定性连接,只考虑一种“择优”方9的比率按照BA模型的既定生长方式增长网络 式,而不考虑其他的可能连接方式,这与实际情形 以(1-gr)的比率按照ER连接规则增长网络;如 不完全符合.现实世界网络中,随机性和确定性两果是确定性连接方式,按照度分布从大到小进行 大类连接都存在多种混合方式,比如,既可“择优”,排序,以fd的比率按照最大度择优增长网络,以 又能“扶贫",还搞折中”或求“平衡”、特殊”照(1-fd)的比率按照最小度选择增长网络,总的连 顾等其他多种混合连接方式.因此,自然地可把接概率为 HUHPM推广到 LUHNM133(图1中间一环所 Iki 1-gr)ki+gr 示),其特点是:在总混合比d下分别引入了第2 d+rEil(1-gr)k;+grl 层次的二个混合比:一是随机混合比gr定义为 (1-fd +fd 9 GRA RA (4)其中表示取整运算 通过实施把随机性连接与确定性连接相结合 二是确定性混合比fd定义为 的形式,在经过t个时间间隔后,便形成一个有 HPA (5)N=mo+t个节点,mt条边的网络.为了示范 已经利用式(1)、(4)和(5)3种混合比和式(6)进 这样,它们存在的关系为:DA=HPA+DPA;行了研究,结果确实显示了结构及特性的多样性 RA=GRA+RPA,或DA=f+d,RA=g+r.和复杂性,它可把目前文献上大多数网络模型类 事实上,依此类推,根据实际需要,随时可灵活增型统一在内,例如其中至少有8种特殊情形被关 加混合比个数.因此,第2曲模型形成了具有多注:(1)fd=0/1和gr=0/1:退化为和谐统一的混合 个混合比的大统一混合网络模型.只要dr≠1/1,择优模型( HUHPM;(i)fd=0/1,gr不限制:确定
第 6 期 方锦清等 : 网络科学中统一混合理论模型的若干研究进展 669 有序度 [31,32] . 由此可见, 第 1 曲 HUHPM 模型同时进行随 机性择优与确定性择优后, 初步理论分析结果与 数值模拟结果相一致, 通过调控总混合比可以达 到和谐统一, 从物理机制上揭示了适当的随机性 与确定性混合择优能够同时产生无标度特性和小 世界效应. 上述发现具有应用潜力, 主要有以下 3 方面的应用前景. (1) 由于度分布、点强分布和边 权分布幂律指数 γ 对总混合比 dr 的变化具有敏 感性, 这一特性与混沌轨道对初始条件的敏感性 相类似, 因此只要巧妙设计就有可能被应用作为 一种新的加密通信原理和手段, 应用于密码学和 保密通信领域. (2) 由于最短平均路径距离小, 而 群聚系数高, 并且随混合比 dr 大小而改变, 这样 人们就可以根据实际需要和要求来设计和调控网 络结构, 以满足实现工程技术上所需要的不同特 殊的用途. (3) 上述发现有助于理解生命系统、人 类社会和自然界中发生的某些网络特性. 3.2 第 2 部曲: 大统一混合网络模型 [33∼40] 应该注意到: 第 1 曲 HUHPM 模型的精确理 论分析极具挑战性, 模型还需要进一步完善, 最主 要一个不足之处是: 它仅仅考虑两大类的择优连 接方式, 还不能完全地反映实际世界网络形成中 存在连接方式的多样性和复杂性. 因为不论随机 性连接, 还是确定性连接, 只考虑一种 “择优” 方 式, 而不考虑其他的可能连接方式, 这与实际情形 不完全符合．现实世界网络中, 随机性和确定性两 大类连接都存在多种混合方式, 比如, 既可 “择优”, 又能 “扶贫”, 还搞 “折中” 或求 “平衡”、“特殊” 照 顾等其他多种混合连接方式. 因此, 自然地可把 HUHPM 推广到 LUHNM[33∼36](图 1 中间一环所 示), 其特点是: 在总混合比 dr 下分别引入了第 2 层次的二个混合比: 一是随机混合比 gr 定义为 gr = g r = GRA RA (4) 二是确定性混合比 f d 定义为 f d = HP A DA (5) 这样, 它们存在的关系为: DA = HP A + DP A; RA = GRA + RP A, 或 DA = f + d, RA = g + r. 事实上, 依此类推, 根据实际需要, 随时可灵活增 加混合比个数. 因此, 第 2 曲模型形成了具有多 个混合比的大统一混合网络模型. 只要 dr6=1/1, f d6=1/1 和 gr6=1/1 任一情形出现, 该模型实际上 包括了不对称连接. 第 2 曲中与第 1 曲类似, 存 在 3 种不同的典型混合情形, 对于随机性连接: (i) 如果 gr À 1/1, 则属于随机性连接中一般随机 (等 概率) 连接占主导地位; (ii) 如果 gr = 1/1, 则属 于一般随机连接与随机性择优连接两者平分秋色 情形; (iii) 如果 gr ¿ 1/1, 则属于随机性择优连接 占主导地位; 这里 (i) 和 (iii) 两种是随机性择优连 接中不对称混合连接. 同样, 对于确定性连接: (i) 如果 f d À 1/1, 则属于确定性连接中扶贫 (度大 的节点与度小的节点) 连接占主导地位; (ii) 如果 f d = 1/1, 则属于确定性连接中扶贫与择优连接两 者平分秋色情形; (iii) 如果 f d ¿ 1/1, 则属于确定 性连接中确定性择优连接占主导情形; 显然, (i) 和 (iii) 两种情形是确定性连接情形下不对称混合连 接. 因此, 第 2 部曲的网络所有特性取决于 3 个混 合比 (dr, gr, f d) 及其各种组合形式, 如此形成的复 杂网络将产生丰富的多样性和复杂性. 第 2 部曲模型的基本算法与第 1 部曲模型类 似, 所不同的是考虑了 3 个混合比 (dr, gr, f d). 当 在网络中选择节点与新增节点连接时, 假定被选 择的节点 i 与新节点连接的概率为 Π ki , 即首先 按照所需的总混合比 dr 确定节点 i 是随机性连 接还是确定性连接, 如果是随机性连接方式, 就以 gr 的比率按照 BA 模型的既定生长方式增长网络, 以 (1 − gr) 的比率按照 ER 连接规则增长网络; 如 果是确定性连接方式, 按照度分布从大到小进行 排序, 以 f d 的比率按照最大度择优增长网络, 以 (1 − f d) 的比率按照最小度选择增长网络, 总的连 接概率为 Π ki = r d + r (1 − gr)ki + gr Σj [(1 − gr)kj + gr] + d d + r · (1 − f d) hh ki kmax ii + f dhhkmin ki ii¸ (6) 其中 [[·]] 表示取整运算. 通过实施把随机性连接与确定性连接相结合 的形式, 在经过 t 个时间间隔后, 便形成一个有 N = m0 + t 个节点, mt 条边的网络. 为了示范, 已经利用式 (1)、(4) 和 (5) 3 种混合比和式 (6) 进 行了研究, 结果确实显示了结构及特性的多样性 和复杂性, 它可把目前文献上大多数网络模型类 型统一在内, 例如其中至少有 8 种特殊情形被关 注: (i)f d=0/1 和 gr=0/1: 退化为和谐统一的混合 择优模型 (HUHPM); (ii) f d=0/1, gr 不限制: 确定
力学 展 2008年第38卷 性连接为完全确定性择优连接( determinastic pref-的三维关系图(a)以及在不同gr下,re随着总混合 erential attachment,DPA),而随机连接方式可以有比对数log(dr)的变化曲线(b)(c)1,其中fd=1/1 不同的匹配情形.(i)fd=1/1,gr不限制:确定属于完全扶贫情形.从图2看到:随着总混合比dr 性连接为完全确定性扶贫连接( helping preferen-变化r变化出现了新特点:多极值现象 tial attachment,HPA);而随机连接方式可以有不BA模型的r对应图2中dr=0/1且gr=0/1 同的匹配情形.(iv)gr=1/1,fd不限制:完全一对应的值;ER模型中的r。对应图2中dr=0/1且 般随机连接( general random attachment,GRA),确g=1/1对应的值; HUHPM模型中的相称性系 定性连接方式可有不同的匹配情形.(v)gr=0/1:数变化为图2中gr=0/0的情形. Newman曾提出 完全随机择优连接( randomness preferential attach- ER模型中re应该为零24,而 Callaway通过引入 ment,RPA,确定性连接方式可以有不同的匹配情种随机增长模型(m=1)和静态ER随机图进行 形.(vi)fd=00和gr=0/1:退化为BA,BBV和了比较,发现该模型有正的度的相关性,r最 TDE模型等;(ⅶi)fd=0/0和gr=1/0:退化为ER大值约为0.35;在 LUHNM模型中,数值模拟显示 随机图模型(vi)fd≠0和gr=0/0:退化为完全增长的ER模型r最大值约为0.2,同样表明具有 确定性模型.因此, LUHNM网络的主要理论框架正的度的相关性.对于不同的dr,随着随机性选 中至少有3个混合比可以灵活控制整个网络生长,择方式gr的变化,re值变化不是很大在多种不 当然,只要实际研究需要,该模型还可以引进其他同gr和f情形,rε的变化图错综复杂,既有线性 混和比. LUHNN网络可以更细致揭示复杂网络的关系也有非线性关系,具体取决于3个混合比的 特性,除了包括第1部曲模型的有关结果外,还发组合和大小.表2给出一些网络模型中re的变化 现了新特性和新现象,其中度-度关联系数(或相范围341-61.目前有关相称性方面的研究大多 称性系数)re( assortative coefficient),与dr的关系数集中在实际网络计算re、建立或改进现有有关 值得关注.图2示出度-度关联系数r与(dr,m)模型方面,通过调控模型参数,可以单独得到相称 0.8 0.2 0. 051 0.1●◆ b)fd=0.99/1 (c)fd=1/1 图2(a)r与(dr,m)的三维关系;(b)(c)在不同gr下,度-度关联系数随着总混合比对数og(dr) 的变化4.固定fd=1/1(属于完全扶贫),m=3,N=1000
670 力 学 进 展 2008 年 第 38 卷 性连接为完全确定性择优连接 (determinastic preferential attachment, DPA), 而随机连接方式可以有 不同的匹配情形. (iii) f d = 1/1, gr 不限制: 确定 性连接为完全确定性扶贫连接 (helping preferential attachment, HPA); 而随机连接方式可以有不 同的匹配情形. (iv) gr = 1/1, f d 不限制: 完全一 般随机连接 (general random attachment, GRA), 确 定性连接方式可有不同的匹配情形. (v) gr=0/1: 完全随机择优连接 (randomness preferential attachment, RPA), 确定性连接方式可以有不同的匹配情 形. (vi) f d=0/0 和 gr = 0/1: 退化为 BA, BBV 和 TDE 模型等; (vii) f d =0/0 和 gr = 1/0: 退化为 ER 随机图模型. (viii) f d 6=0 和 gr = 0/0: 退化为完全 确定性模型. 因此, LUHNM 网络的主要理论框架 中至少有 3 个混合比可以灵活控制整个网络生长, 当然, 只要实际研究需要, 该模型还可以引进其他 混和比. LUHNM 网络可以更细致揭示复杂网络的 特性, 除了包括第 1 部曲模型的有关结果外, 还发 现了新特性和新现象, 其中度 - 度关联系数 (或相 称性系数) rc (assortative coefficient), 与 dr 的关系 值得关注. 图 2 示出度 - 度关联系数 rc 与 (dr, m) 的三维关系图 (a) 以及在不同 gr 下, rc 随着总混合 比对数 log(dr) 的变化曲线 (b)(c)[41] , 其中 f d = 1/1 属于完全扶贫情形. 从图 2 看到: 随着总混合比 dr 变化 rc 变化出现了新特点: 多极值现象. BA 模型的 rc 对应图 2 中 dr=0/1 且 gr=0/1 对应的值; ER 模型中的 rc 对应图 2 中 dr=0/1 且 gr = 1/1 对应的值; HUHPM 模型中的相称性系 数变化为图 2 中 gr=0/0 的情形．Newman 曾提出 ER 模型中 rc 应该为零 [42] , 而 Callaway 通过引入 一种随机增长模型 (m=1) 和静态 ER 随机图进行 了比较, 发现该模型有正的度的相关性 [35] , rc 最 大值约为 0.35; 在 LUHNM 模型中, 数值模拟显示 增长的 ER 模型 rc 最大值约为 0.2, 同样表明具有 正的度的相关性．对于不同的 dr, 随着随机性选 择方式 gr 的变化, rc 值变化不是很大. 在多种不 同 gr 和 f d 情形, rc 的变化图错综复杂, 既有线性 关系也有非线性关系, 具体取决于 3 个混合比的 组合和大小. 表 2 给出一些网络模型中 rc 的变化 范围 [35,41∼51] . 目前有关相称性方面的研究大多 数集中在实际网络计算 rc、建立或改进现有有关 模型方面, 通过调控模型参数, 可以单独得到相称 图 2 (a) rc 与 (dr, m) 的三维关系; (b) (c) 在不同 gr 下, 度 - 度关联系数随着总混合比对数 log(dr) 的变化 [41] . 固定 f d = 1/1(属于完全扶贫), m = 3, N = 1 000
第6期 方锦清等:网络科学中统一混合理论模型的若干研究进展 网络或异称网络,但是相称性系数rc也只能在(0,相称和异称网络之间变化,得到的re可以在正负 1)或(-1,0)之间变化;而第2部曲模型通过调控定小范围之间转变,但是我们模型B337r。变化 3个混合比参数,可使r在大范围的正负值之间的范围最广,从而网络结构也更为丰富多样,更适 实现转变.另外,也有模型1通过可调的参数在用于实际网络 表2各种网络模型中r的变化范围 化范围网络模型或模型控制参数 (-1,1) 统一混合模型( LUHNM),由3个混合比控制 -1,0或[0.1 种算法1),有一个控制参数 BA模型、随机ER模型 0.0.5) Callaway提出的一种模型,有一个控制参数 异配 自相似无尺度网络 4444 同配 地震网络 交通流驱动模型,有一个控制参数 社会模型 (-0.6,0.4) 相互吸引模型,两个控制参数 (-0.21,0.41) 22个公共运输系统,观察到随着规模N的递增, 出现异配到同配的转变,转变点约在N=500 Penna位串模型,N ularxiv org科学家合作网 )指模型的具体构造方法,主要思想为“节点更倾向于选择和该节点的度相似的节点进行连接” 在理论模型第2部曲 LUHNM中还发现:累积只要fd≥0.99/1(这个条件比较无权情形更高了), 度分布随着3种混合比的变化可在幂律函数分布不管gr是什么数值,都存在相称性系数的极值现 和指数分布之间进行转变,不仅适合于无权网络,象.特别是,在相称性系数re,fd和gr之间存在非 而且适合于有权混合网络,许多奥秘和变化规律线性关系,随d的增加使相称性系数r。非线性地 隐藏在混合比的巧妙组合之中.图3和图4示出,从负值转变到正值;相反地,在gr=1/1或0.8/1占 有权 LUHNM-BBV网络中相称性系数re与dr、gr主导时,相称性系数re随dr的增加非线性地从正 或fd的三维关系,其中fd和gr为固定混合比,权向负的减少,并且在dr≥1/1(确定性为主)时相称 重参数6=3.从图3可见:在 LUHNM-BBV网络中性系数re与gr的非线性变化更大当dr≤1/10(随 冋样出现相称性系数r。与无权网络类似的多个波机性为主)时,相称性系数r变小,gr越大,r。变 峰现象,而且曲线关系更为复杂.在d>1/1情形,化越小 fd=0.6=3 fd=0.9,6=3 fd=1,6=3 0.5 010-5 图3对于固定fd下有权 LUHNM- BBV网络中re与(dr,gr)的关系
第 6 期 方锦清等 : 网络科学中统一混合理论模型的若干研究进展 671 网络或异称网络, 但是相称性系数 rc 也只能在 (0, 1) 或 (−1, 0) 之间变化; 而第 2 部曲模型通过调控 3 个混合比参数, 可使 rc 在大范围的正负值之间 实现转变．另外, 也有模型 [41] 通过可调的参数在 相称和异称网络之间变化, 得到的 rc 可以在正负 一定小范围之间转变, 但是我们模型 [33∼37]rc 变化 的范围最广, 从而网络结构也更为丰富多样, 更适 用于实际网络． 表 2 各种网络模型中 rc 的变化范围 rc 的变化范围 网络模型或模型控制参数 文献 (−1, 1) 统一混合模型 (LUHNM), 由 3 个混合比控制 [35] [−1, 0]或 [0, 1] 一种算法 1) , 有一个控制参数 [41] 0 BA 模型、随机 ER 模型 [42] [0, 0.5) Callaway 提出的一种模型, 有一个控制参数 [43] 异配 自相似无尺度网络 [44] 同配 地震网络 [45] (−1, 0] 交通流驱动模型, 有一个控制参数 [46] 同配 社会模型 [47] (−0.6, 0.4) 相互吸引模型, 两个控制参数 [48] (−0.21, 0.41) 22 个公共运输系统, 观察到随着规模 N 的递增, [49] 出现异配到同配的转变, 转变点约在 N=500 0.495 2 Penna 位串模型, N = 500 [50] 同配 cul.arxiv.org 科学家合作网 [51] 1) 指模型的具体构造方法, 主要思想为 “节点更倾向于选择和该节点的度相似的节点进行连接” 在理论模型第 2 部曲 LUHNM 中还发现: 累积 度分布随着 3 种混合比的变化可在幂律函数分布 和指数分布之间进行转变, 不仅适合于无权网络, 而且适合于有权混合网络, 许多奥秘和变化规律 隐藏在混合比的巧妙组合之中. 图 3 和图 4 示出, 有权 LUHNM-BBV 网络中相称性系数 rc 与 dr、gr 或 f d 的三维关系, 其中 f d 和 gr 为固定混合比, 权 重参数 δ=3. 从图 3 可见: 在 LUHNM-BBV 网络中 同样出现相称性系数 rc 与无权网络类似的多个波 峰现象, 而且曲线关系更为复杂. 在 dr > 1/1 情形, 只要 f d≥ 0.99/1 (这个条件比较无权情形更高了), 不管 gr 是什么数值, 都存在相称性系数的极值现 象. 特别是, 在相称性系数 rc, fd 和 gr 之间存在非 线性关系, 随 dr 的增加使相称性系数 rc 非线性地 从负值转变到正值; 相反地, 在 gr =1/1 或 0.8/1 占 主导时, 相称性系数 rc 随 dr 的增加非线性地从正 向负的减少, 并且在 dr≥1/1(确定性为主) 时相称 性系数 rc 与 gr 的非线性变化更大. 当 dr≤ 1/10(随 机性为主) 时, 相称性系数 rc 变小, gr 越大 , rc 变 化越小. 图 3 对于固定 f d 下有权 LUHNM- BBV 网络中 rc 与 (dr, gr) 的关系
672 力学 展 2008年第38卷 024 0.3 0.1 0.4 00.20.40.60.81 (a)dr=1/99 (c)dr=19/1 图4有权网络在3种典型d下相称性系数r与fd及gr的复杂关系 总之,第2部曲确实把目前大多数网络模型整个国家采取技术扶贫政策,让东部地区的“高端 和主要连接方式大范围地统一在一起,因为三混技术”全力支持西部的“低端技术”,这种技术扩 合比(dr,gr,fd)可根据实际网络需求而确定混合散就可改变西部的技术落后状态,这样组成的技 比大小的匹配,所以它比第1部曲具有更强的适应术网络也会出现正的相称性系数.因此,正负的相 性、灵活性和应用性.3种混合比组合必然产生丰称性系数转变不论在什么类型网络里都可能发生 富多彩的网络拓扑特性、动力学行为和系统功能这种转变特性密切依赖于3个混合比的适当匹配 之间错综复杂的关系,无论无权和有权网络都能和大小,可以根据需要拓广和增加新的混合比,以 通过调控3个混合比揭示复杂混合网络的新特点满足实际应用 和新现象,度-度关联系数(或相称性系数)c能够33第3部曲:统一的变速增长混合模型 在(-1,1)之间的大范围内变化,而且出现多峰现 再进一步,继续深入分析和比较实际网络,发 象,说明网络之间的关联在3个混合比相空间中现在理论模型第二部曲里,仍然还有没有全面反 有波峰和波谷起伏变化,网络的不同区域关联性映网络实际增长过程的曲折变化情形,因为许多 不同,具有不均匀性利用这个理论结果,可以解实际网络,不论是节点增减和边的发展(增长)速 度都是不一样的,而且同时随时间和空间变化,如 异由于人类社会普遍具有“扶贫济困”和“助人中国四川汶川抗震救灾网每时每刻不断变化,而 为乐”的社会美德和社会责任感最突出的典型实高技术网络、因特网、人类社会关系网、通讯网等 例是,2008年5月12日发生在我国四川汶川抗震等通常也是随时间空间变化的B25.因此,在混 中全人类的这种高尚品德,“一人有难,八方支援” 合网络理论模型的第2部曲的基础上,又发展了 和“众志成城,抗震救灾”,不仅在全中国,而且在第3部曲: LUHVSGI56n,示于图1中最外一环 全世界淋漓尽致地突现出来,全球迅速形成了抗其最大特点是,在总混合比如及第2层次的两 震救灾网.应用 LUHNM模型可知,在抗震救灾网个混合比(fdgr)基础上,又引进了变速增长混合 中当确定性连接是完全扶贫连接,或扶贫连按占比g 绝对优势(fd≥90%以上)时,正是在这种确定性 DVG 与随机性混合情况下,网络必然出现了正的re,而 且相称性系数出现多峰(极值)现象.这表明:抗震 实际复杂网络存在多种变速增长方式,其中 救灾网中如汶川、北川、都江堰、唐家山等几个重典型的变速方式之一为25 灾区形成人们最为关注和全力支援的中心,因此 m()=p((t) 出现多峰现象就不足为奇了.第2部曲模型揭示 了在 LUHNM-BBV网络中出现了类似的结果至这里m(t)为t时刻被增加的节点连接边数,N(t) 于技术网络,大多数采用强-强联合,所以这样的为t时刻网络的节点数目,p是一个概率常数, 技术网络自然出现负的相称性系数.另外,只要p(t)为常数时属于确定性增长,当为随机概率0<
672 力 学 进 展 2008 年 第 38 卷 图 4 有权网络在 3 种典型 dr 下相称性系数 rc 与 f d 及 gr 的复杂关系 总之, 第 2 部曲确实把目前大多数网络模型 和主要连接方式大范围地统一在一起, 因为三混 合比 (dr, gr, f d) 可根据实际网络需求而确定混合 比大小的匹配, 所以它比第 1 部曲具有更强的适应 性、灵活性和应用性. 3 种混合比组合必然产生丰 富多彩的网络拓扑特性、动力学行为和系统功能 之间错综复杂的关系, 无论无权和有权网络都能 通过调控 3 个混合比揭示复杂混合网络的新特点 和新现象, 度 - 度关联系数 (或相称性系数)rc 能够 在 (−1, 1) 之间的大范围内变化, 而且出现多峰现 象, 说明网络之间的关联在 3 个混合比相空间中 有波峰和波谷起伏变化, 网络的不同区域关联性 不同, 具有不均匀性. 利用这个理论结果, 可以解 释社会网络和技术及生物网络之间的 rc 出现的差 异. 由于人类社会普遍具有 “扶贫济困” 和 “助人 为乐” 的社会美德和社会责任感, 最突出的典型实 例是, 2008 年 5 月 12 日发生在我国四川汶川抗震 中全人类的这种高尚品德, “一人有难, 八方支援” 和 “众志成城, 抗震救灾”, 不仅在全中国, 而且在 全世界淋漓尽致地突现出来, 全球迅速形成了抗 震救灾网. 应用 LUHNM 模型可知, 在抗震救灾网 中当确定性连接是完全扶贫连接, 或扶贫连接占 绝对优势 (f d≥90% 以上) 时, 正是在这种确定性 与随机性混合情况下, 网络必然出现了正的 rc, 而 且相称性系数出现多峰 (极值) 现象. 这表明: 抗震 救灾网中如汶川、北川、都江堰、唐家山等几个重 灾区形成人们最为关注和全力支援的中心, 因此 出现多峰现象就不足为奇了. 第 2 部曲模型揭示 了在 LUHNM-BBV 网络中出现了类似的结果. 至 于技术网络, 大多数采用强 - 强联合, 所以这样的 技术网络自然出现负的相称性系数. 另外, 只要 整个国家采取技术扶贫政策, 让东部地区的 “高端 技术” 全力支持西部的 “低端技术”, 这种技术扩 散就可改变西部的技术落后状态, 这样组成的技 术网络也会出现正的相称性系数. 因此, 正负的相 称性系数转变不论在什么类型网络里都可能发生, 这种转变特性密切依赖于 3 个混合比的适当匹配 和大小, 可以根据需要拓广和增加新的混合比, 以 满足实际应用. 3.3 第 3 部曲: 统一的变速增长混合模型 再进一步, 继续深入分析和比较实际网络, 发 现在理论模型第二部曲里, 仍然还有没有全面反 映网络实际增长过程的曲折变化情形, 因为许多 实际网络, 不论是节点增减和边的发展 (增长) 速 度都是不一样的, 而且同时随时间和空间变化, 如 中国四川汶川抗震救灾网每时每刻不断变化, 而 高技术网络、因特网、人类社会关系网、通讯网等 等通常也是随时间空间变化的 [32∼54] . 因此, 在混 合网络理论模型的第 2 部曲的基础上, 又发展了 第 3 部曲: LUHVSG[55∼57] , 示于图 1 中最外一环, 其最大特点是, 在总混合比 dr 及第 2 层次的两 个混合比 (f d, gr) 基础上, 又引进了变速增长混合 比 vg vg = DV G RV G (7) 实际复杂网络存在多种变速增长方式, 其中 典型的变速方式之一为 [52∼57] m(t) = p(N(t))α (8) 这里 m(t) 为 t 时刻被增加的节点连接边数, N(t) 为 t 时刻网络的节点数目, p 是一个概率常数, p(t) 为常数时属于确定性增长, 当为随机概率 0 <
