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