第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<b sasb . 由此确定权重 wij 的增量. 若节点 i 与节点 j 不相 连, wij ＝ 0. 边权总增量取平均权值. 带有 m 条 边的新节点 n 按 BBV 规则与老节点随机连接. 每 条新边权重值为 w0. 于是得到边权分布、度分布 和点强度分布均为幂律分布, 其中点强幂指数为 γs = 2 +m/(m+ 2ω); 点强与度之关系为 s(k) ≈ k β , 并且 β > 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) 模型和有