复杂网络理论研究综述①

安沈昊,于荣欢

(航天工程大学 复杂电子系统仿真实验室,北京 101400)

复杂网络理论研究最早可追溯到18世纪由数学家欧拉提出的“七桥问题”,将陆地抽象为点,将连接陆地的桥梁抽象为边,点与连接点的边就组成了网络.随着复杂系统的快速发展,复杂网络的分析方法被广泛应用于社会、经济、军事等领域,如在线社交网络、国际贸易、现代化信息作战系统等.

目前,复杂网络各分支方向的研究已引起广泛关注,国内多名学者先后对复杂网络的相关理论、研究和应用方向进行系统的整理和总结[1-6].朱涵等最早介绍了复杂网络理论[7],何宇等从部件、权重、机制、动态变化及侧重条件5 个方面整理其演化模型并分类[8],周涛等详述大数据时代下复杂网络亟需解决的十大问题[9].随着复杂网络理论研究的发展,有必要继续对其理论进行归纳和整理,以推动进一步研究.

1 复杂网络基本概念

关于什么是复杂网络,目前还没有一个统一的定义.钱学森先生认为具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络可称为复杂网络.在研究网络时,人们往往只关注节点之间是否存在连边,忽视节点位置、边的性质等因素.复杂网络就可看作复杂系统的高度抽象,将网络中的节点抽象为复杂系统中的个体,网络中的边抽象为复杂系统中个体之间的关系,这样由大量的节点及节点间相互连接的边所构成的网络就可称为复杂网络.

1.1 度分布

节点的度定义为与该节点相连的边的个数,反映该节点在网络中的重要程度.网络中所有节点的度的平均值是该网络的平均度.网络中节点的度分布表示为分布函数P(k),代表该节点的度等于k的概率,也可代表网络中度为k的节点数在总节点数中所占的比例.

1.2 平均路径长度

连接两个节点的最短路径所用边的个数为两节点之间的距离,网络中所有节点对之间距离的平均值为网络的平均路径长度.平均路径长度反映了节点之间联系的紧密程度和网络的大小.

1.3 集聚系数

节点的集聚系数表示为邻居节点之间实际存在的边数与最大可能边数之比,反映一个节点的相邻节点之间相互连接的情况.网络的集聚系数表示为所有节点集聚系数的平均值,反映了网络的社团结构特性.

1.4 介数

介数分为点介数和边介数.点介数表示为经过该节点的最短路径数目占所有最短路径数目的比例,边介数表示为所有经过该边的最短路径数目占所有最短路径数目的比例.介数反映了相应节点或边在整个网络中的作用和地位.

2 典型复杂网络模型

网络的结构与功能联系紧密,拓扑结构决定功能,功能影响拓扑结构演化.为研究复杂网络拓扑结构特性,Erdos 与Renyi 最早根据随机图理论构建了随机网络模型(ER 模型)[10],但ER 模型的连接规则与节点分布的随机性使其不适合研究真实复杂网络.因此,基于已有网络模型的缺陷与真实网络研究的需求,学者们提出了大量不同的复杂网络模型.

2.1 小世界网络模型

通常认为如果网络的平均路径长度L与节点数N的对数成正比,则称该网络具有小世界效应.绝大部分真实复杂网络都具有小世界效应,即具有较小的平均路径长度和较大的集聚系数.

基于此,Watts 和Strogatz 提出了小世界网络模型(WS 模型)[11].在一个包含N个节点的环状规则网络中,以顺时针方向访问每个节点并选取与当前节点连接的边,以概率p对每条边进行删除和重连,将边的另一端随机连接到其他节点上,在这个过程中可能会出现长程边从而减小网络的平均路径长度,以概率1-p保留原有边,整个过程中不允许出现重复连接和自环.可以改变p值来调节网络的随机性,并保持网络中边数的平衡,p=0 时对应规则网络,p=1 时对应随机网络.通过这种方法构造出来的小世界网络具有较小的平均路径长度和较大的集聚系数.

考虑到WS 模型的构造方法可能会破坏网络的连通性,Newman 和Watts 对其进行了改进,提出了NW模型[12].NW 模型的改进之处在于用随机化加边取代了随机化重连,即以概率p在随机选取的节点对之间添加连接边,不改动原有连接边,且不允许出现重复连接和自环.当网络规模N足够大而p足够小时,WS 模型与NW 模型在本质上是一样的.

2.2 无标度网络模型

在随机网络和小世界网络中,节点的度分布近似为泊松分布.但研究者发现大多数真实复杂网络的度分布服从幂律分布,即随着节点度k增大,分布函数P(k)衰减速度变小.

针对这种情况,Barabas 和Albert 提出了无标度网络模型(BA 模型)[13]从两方面来描述其产生机制,即网络增长和优先连接.网络增长意味着网络中不断有新节点加入并连接到已存在的节点上,初始网络包含m0个节点和m1条边,每个时间步增加一个新节点和m(m≤m0)条边,连接到m个已有的节点上;优先连接意味着新增加的节点会优先连接度值较大的节点,将节点i的度ki和所有节点度的总和k的比值作为新增加的节点连接到节点i的概率,新增加的节点根据此概率选择所要连接的m个节点.经过t个时间步后初始网络就会演化成具有m0+t个节点和m1+mt条边的网络,其中大多数节点度值较小,少数节点度值很大.结果显示,BA 网络不仅兼具小世界效应和较大的集群系数,其度分布也满足幂律分布.

2.3 局域世界网络模型

BA 模型中的优先连接机制存在于全局网络,然而Li 等通过对真实复杂网络的研究,发现优先连接机制仅存在于局部网络,因此在BA 模型的基础上提出一种简单局域世界网络模型(LC 模型)[14].该模型首先随机选取m个节点作为新增节点的局域世界,新增节点会优先连接所对应的局域世界中度值较大的节点,而不是选择全局网络中度值较大的节点进行连接.

在BA 模型中,新增节点拥有全局信息;在LC 模型中,新增节点仅拥有局部信息.在真实复杂网络中,总是存在少数节点拥有全局信息,大部分节点仅拥有局部信息.基于此,Qin 等对LC 模型进行了改进,建立了一种新的局域世界网络模型[15].该模型引入了全局节点数与总结点数的比值作为新增节点属于全局节点的概率p.当p=0 时,该模型对应于LC 模型;当p=1时,对应于BA 模型.

2.4 权重网络模型

上述网络模型均将网络视为无权网络,忽略了节点之间的相互作用程度或节点和边的物理量等信息.而真实网络往往为节点或边具有权重的有权网络,相比于无权网络,有权网络更能反映真实情况.

Yook 提出了一种基于BA 模型的简单加权网络模型[16],通过赋予边权重来描述节点之间的相互作用强度与连接边之间的异质性.

Barrat 等提出了具有较强代表性的BBV 模型[17].该模型综合考虑了拓扑结构和权重在网络动态演化过程中的影响,随着网络规模的增大,其度分布、边权分布和节点权分布都具有无标度特性.

周健等把局域世界特征引入到BBV 模型中,提出了一种基于局域世界演化的BBV 模型[18].该模型的构建考虑了局域世界内新节点和新连接的产生、局域世界内旧连接的消亡、局域世界外新连接的产生、权值优先连接这4 个方面.

周鹏尧等在BBV 模型的基础上,提出一种广义的加权网络演化(FBBV)模型[19].该模型与BBV 模型的不同之处在于,当网络中加入新节点时,网络中所有边权都会发生变化,变化程度取决于各边所处的实际位置.

3 复杂网络研究现状

3.1 社团结构研究

在现实生活中人们可能因各种因素处于不同的团体中,成员之间联系频繁,而团体之间仅偶尔有往来.在复杂网络中同样有着类似的社团现象,社团结构是复杂网络的一个重要特征.

关于社团结构的定义,根据连接密度可理解为社团是对网络内节点的分组,组内节点之间联系紧密,组间节点联系稀疏;根据连通性可将社团看作一个派系,即由两个以上的节点组成的全连通子图,其中任意两个节点之间都存在连接边.

复杂网络中的社团根据不同的标准可分为不同的类型.根据社团内部节点联系的紧密程度,可分为强社团和弱社团;根据社团之间是否有重叠节点,可分为重叠社团与非重叠社团.

如何对隐藏在复杂网络中的社团结构进行检测与划分,是复杂网络研究中的一个重要内容.关于社团结构的检测算法,汪小帆等首先介绍了计算机科学中的谱平分法和Kernighan-Lin 算法、社会学中具有代表性的分裂算法和凝聚算法[20].

复杂网络中多数节点的“多属性”特征使重叠社团的检测算法具有更高的实用性.为准确检测出权重网络中的重叠社团,贾郑磊等提出了一种基于Jaccard系数的BGLL 模块密度优化算法,相比于传统BGLL算法,该算法能充分利用局部、全局信息,将有权节点与社团相似度相结合,具有更高准确率[21].李欢等从不同角度将重叠社团检测算法分为基于派系过滤的算法、基于局部拓展的算法、基于边划分的算法、基于动力学的算法和基于模糊检测的算法[22].

针对无权无向网络中非重叠社团的检测,张鹏改进了密度峰值聚类算法,通过自定义加权集合密度算法寻找聚类中心,然后计算节点之间的相似性,最终完成社团划分[23].

3.2 抗毁性研究

网络的抗毁性可理解为当网络受到攻击或出现故障时所表现出的恢复性或适应性,或在部分节点或边失效的情况下仍能继续提供服务的能力.如果一个网络在受到攻击而被移除少量节点后,剩余节点之间仍然是连通的,那么该网络对这种攻击具有较强抗毁性.

Albert 等最早开始研究复杂网络在节点失效情况下的抗毁性[24].他们用随机攻击与选择性攻击两种不同策略分别对随机网络和无标度网络进行攻击.随机攻击指的是随机移除网络中的节点,选择性攻击即按照节点度从大到小的顺序移除节点.结果表明:无标度网络在随机攻击下表现出较强的抗毁性,在选择性攻击下却非常脆弱,若移除有大量连接的关键节点,网络将立刻崩溃.

与最初基于图论的研究方法不同,目前复杂网络抗毁性的研究方法已发展为基于统计物理的方法,其方向包括抗毁性指标测度和抗毁性策略优化.

在抗毁性指标测度方面,孙成雨等对二进制粒子群算法的概率映射函数和位置更新式进行改进,并结合适应度函数求解算法,设计出点韧性度算法,该算法能够快速获取网络点韧性度以衡量其抗毁性性能,还可用于求解边韧性度[25].

有关研究显示,根据网络实际情况选择合适的、包含多种信息的抗毁性指标,对抗毁性策略的优化有重要的意义[26,27].此外,张煜等从拓扑结构、网络容量和路由策略等3 个方面介绍了抗毁性优化策略的研究进展[28],并指出除了拓扑结构,网络的防御与故障修复策略都将成为重要研究方向.

3.3 节点影响力研究

小世界效应与无标度特性使得复杂网络中的节点分布呈现不均匀的现象,少数节点具有大量连接,处于重要地位,例如在国际贸易中对整个贸易体系有重要影响的一些国家,相比于大多数普通节点,这些少数节点对于整体网络有着更大的影响.因此准确识别复杂网络中的重要节点,对于优化复杂网络的结构与功能具有重要意义.

节点影响力研究包括节点重要性排序和影响力最大化,李梦甜对二者进行了深入研究,提出了一种中心性方法对节点传播力进行评估与排序,该方法将本节点聚类系数与相邻节点度值结合,具有良好的分辨率与排序准确性,运用该方法找出的节点集合能够影响更多的节点[29].

考虑到节点影响力指标受节点属性、网络结构等因素影响,张应青等将节点影响力测度方法分为基于节点多属性的多指标测度方法、基于节点局部信息和基于网络全局信息的单属性指标测度,并介绍了贪心算法、启发式算法和渗流方法3 种寻找影响力节点集合的方法[30].

上述重要节点的识别方法仅局限于寻找在静态网络中具有深刻拓扑特征的节点,而真实复杂网络的规模与结构时刻都在变化.基于此,任卓明讨论了节点影响力算法在增长网络、实时动态网络与结构突变或微扰的动态网络中遇到的问题,对于动态网络的节点影响力研究有重要的意义[31].

3.4 信息传播研究

如今网络已成为信息的主要传播渠道,这使得人们的社交网络从线下接触式拓展至线上非接触式.对信息在社交网络上传播的动力学机理进行研究,是有效实施风险管控的基础.建立合适的信息传播模型能准确反映网络个体之间信息传播情况随时间产生的变化.

典型的信息传播模型主要参照流行病传播模型,包括SI 模型、SIS 模型、SIR 模型、SEIR 模型、SIRS模型等.李丹丹等从经典谣言传播模型到社会网络上的谣言传播模型、从微观机制和宏观机制,分别评述了谣言传播模型的发展历程[32].钱亚飞分析了元胞自动机模型、多数决定模型、Ising 模型、有界信任模型、Sznajd 模型这5 种舆情演化模型,将其分为离散与连续两类观点模型,指出网络舆情研究应当注重真实数据集的获取与多学科的有机结合[33].

谣言在实际社交网络中的传播率是非一致性的,每个用户对谣言的抵抗力不同,用户之间的亲密程度也会影响谣言的传播.翟倩倩等建立了一种S2IR 网络谣言传播模型,该模型充分考虑谣言传播的差异性与谣言免疫策略,更加符合实际网络中的谣言传播,不足之处是未能进一步对谣言未知节点进行细分[34].

3.5 同步控制研究

无论是在日常生活中还是在专业领域内,同步都是一种常见的现象,例如鱼群中每条鱼的同时摆动、超导体中电子的一致前进等.由于同步既会产生有益结果也会产生有害结果,因此有必要对复杂网络中的同步进行控制.复杂网络中的同步控制就是指通过对网络施加外力对其进行控制,使内部多个节点动力系统达到相同状态并保持稳定.如何实现复杂网络的同步控制,从而维持有益同步规避有害同步,已成为当前研究的热点问题.

信息在网络中的传播速度会受到各种因素的影响与限制,这就导致在控制器接受与发送节点状态信息的过程中出现滞后现象[35].针对复杂动态网络节点本身可能存在的滞后现象,王亚楠分别从马尔可夫切换转移率部分已知和完全已知两种情况出发研究复杂动态网络系统的同步控制问题[36].

由于网络中节点数量众多,对所有节点进行控制显然是不切实际的,因此牵制控制策略的研究受到广泛关注,即仅对一部分节点进行控制进而使全局网络保持同步.王瑞峰等引入事件激发函数实现牵制节点集的实时更新,依据合适的节点集选取规则,有效提高了同步效率与资源使用率[37].曹进德等从控制条件、节点选取策略、影响因素、算法、应用等方面概述了复杂网络牵制同步的研究进展[38],在目前大多数牵制控制策略依赖全局信息的背景下,如何利用局部信息实现分布式的牵制控制值得深入研究.

3.6 随机行走研究

随机行走是复杂网络领域研究的诸多动力学行为之一,并且与信息传播、同步等其它动力学行为存在紧密联系.复杂网络上的随机行走是指随机行走粒子以复杂网络结构为载体,从初始节点出发,在每个时间步以一定概率选择当前节点的邻居节点进行传输最终到达目的节点的过程.

景兴利等运用图谱理论,给出一般网络上随机行走平均到达时间的精确解,对加权网络的平均首到达时间和平均陷阱时间进行分析,发现二者与网络规模、陷阱点度值、权重系数、平均度有密切关系[39].

4 结论与展望

本文从复杂网络的基本概念、网络模型、研究现状3 个层面简要介绍了近几年复杂网络领域的研究成果和进展.从中可以看到:大多数复杂网络模型是在BA 模型的基础上,通过新的机制演化而来,BA 模型将继续为复杂网络模型研究提供重要的参考价值;当前复杂网络的研究更侧重于结构特性和网络动力学两个领域,并且两个领域间的研究相互影响,如何描述并分析网络结构特性与动力学行为之间的关系,将是众多学者面临的难题.

随着科技发展与众多复杂巨系统的出现,复杂网络的结构和动力学行为趋向复杂化.人们仅依靠数字、表格等传统形式已无法有效对复杂网络进行全局性的规划与管理,需要运用可视化技术全面、直观、清晰、实时地描述复杂网络拓扑结构与动力学行为,以便对其进行分析、管理与评估.对复杂网络进行可视化处理,既可以帮助人们从视觉层面上理解复杂网络的结构,也便于学者研究复杂网络拓扑结构变化对其动力学行为的影响.因此,复杂网络可视化将是未来复杂网络研究的热点之一,具体有以下几个方向:

(1)可视化算法

可视化算法按照适用规模,可分为布点算法和可视化压缩算法[40];按照布局方式,可分为基于节点-链接的可视化方法、基于邻接矩阵的可视化方法和基于图嵌入的可视化方法[41].随着大数据的兴起与节点关系的复杂化,可视化算法在性能与可观性等方面遇到了巨大的挑战.对此,一是可以对现有算法进行改进,提高计算效率,以减少计算资源的占用;二是可以引入“可视化分层”的概念,将运算压力与可视化结果随着用户的交互操作分配到不同的层面上.

(2)网络拓扑可视化

网络拓扑可视化是一种将点和线构成图形、图像来对网络中的拓扑信息进行描述与分析的技术[42].在大数据处理与云计算等技术的推动下,能够合理运用有限资源,高效地管理大量关系复杂的节点,并简洁、直观地展示其运行状态等信息,具有重要的意义.因此,如何实现拓扑特性、布局算法和可视化方式三者的结合,是当前面临的难点.

(3)动态网络可视化

复杂网络所具有“无标度”特性使其处在一个数据不断更新的状态,且新数据会对原始可视化效果带来不可控、不可估计的影响,为其可视化带来了巨大的挑战[43].目前的可视化算法与工具大多用于静态网络的可视化,无法准确描述持续演变的真实动态网络,怎样有效实现动态网络可视化也是一个值得关注的问题.

时至今日,复杂网络的应用已远远超出物理学和数学的范畴,其分析与应用也为诸多学科提出了新的具有挑战性的难题.把复杂网络理论与实际问题联系起来,增强其实用性,进而应用到实际复杂系统中,将是复杂网络理论研究未来的发展趋势.