力 展 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 不限制: 确定性