第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 自然界和人类社会生活在一个既可确定又有 a<b 随机概率的世界里,这就是随机性与确定性的统 由此确定权重;的增量.若节点i与节点j不相和谐的世界.基于这个最基本事实确认:进 连,ω;=0.边杈总增量取平均权值.带有m条步完善和发展网络的混合理论模型是网络模型研 边的新节点n按BBⅤ规则与老节点随机连接.每究的最重要方向之一.随机性与确定性的共存现 条新边权重值为.于是得到边权分布、度分布象普遍存在,比比皆是,例如,每年全国高考招生 和点强度分布均为幂律分布,其中点强幂指数为网、公务员考试网和社会就业(人才招聘)网,等 7s=2+m/(m+2u);点强与度之关系为s(k)≈k,等,都包含随机性和确定性两种混合择优过程,以 并且β>1;群聚系数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<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 部曲的主要框架及其 进展. 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) 模型和有