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