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. 边权幂