多重边融合复杂网络动态演化模型

杨迎辉,李建华,沈迪,南明莉,2,崔琼

(1.空军工程大学信息与导航学院,710077,西安;2.中国人民解放军95881部队,100095,北京)



多重边融合复杂网络动态演化模型

杨迎辉1,李建华1,沈迪1,南明莉1,2,崔琼1

(1.空军工程大学信息与导航学院,710077,西安;2.中国人民解放军95881部队,100095,北京)

针对多个性质不同、相互融合的复杂网络演化过程时变非均衡,网络结构层级交织,特点规律难以测度的问题,提出了一个多重边融合复杂网络动态演化模型。首先,定义多重边融合复杂网络的相关概念,分析融合关系与层级关系的转化过程,按照节点、边性质的差异,拆分融合节点和重合边,将多重边融合复杂网络转化成交织型层级复杂网络;其次,定义节点的度值饱和度和吸引因子,提出交织型层级复杂网络的演化算法和局域世界演化模型,讨论了4种典型的节点演化情形,运用平均场方法分析了模型演化的度分布规律;最后进行了数值仿真分析,结果表明,演化过程结束后,未达到饱和状态的节点度值服从指数分布且误差不超过6%,已达到饱和状态的节点度值服从其连接容量的分布规律且误差不超过3%,网络交织系数与最高的新增节点概率、初始边数呈正相关性。研究结果验证了模型的可行性和有效性,为探索多重边融合复杂网络演化过程与规律提供了新的思路和方法,在交通网、通信网、社交网等结构与动力学研究方面具有良好的应用前景。

多重边融合复杂网络;交织型层级复杂网络;动态演化;饱和度;吸引因子

随着现代社会网络化程度的不断加剧,复杂网络已经在政治、经济、军事等众多领域广泛应用[1-2]。现实生活中包含大量的由多种性质子网络构成的多重边融合复杂网络(MLUCN),例如交通网、通信网、社交网等,存在着1个节点具有多种性质、2个节点之间有多条边连接的情况。相较单一性质、单边的复杂网络,MLUCN中边与边之间的性质存在较大差异,节点之间的可达路径数量更多,网络的演化过程及规律也更加复杂。

当前,关于网络演化问题的研究主要集中在模型构建、算法设计、特性分析等方面。文献[3]引入时滞对网络进行拆分,建立多重边复杂网络动力学模型,并基于Lyapunov理论研究网络的稳定性;文献[4]针对SF和ER网络,研究了随机攻击条件下层级网络间的依存关系和依存强度对系统的作用效果;文献[5]定义了网络节点度值饱和度,基于二分网络建立了一种类局域世界演化模型,并分析了演化统计特性;文献[6]定义了吸引因子概念,提出了一种吸引因子存在的无尺度网络演化模型,仿真对比了同等网络规模下,吸引因子模型与BA模型的度分布情况。

已有成果主要是针对单边、单一性质的网络,对具有多重边和融合节点的复杂网络研究较少,未能有效区分节点和边的多种性质差异进行演化建模。因此,本文首先根据性质差异,拆分融合节点和重合边,将MLUCN转化成交织型层级复杂网络(ILCN)进行研究;其次,定义节点的度值饱和度和吸引因子,建立ILCN局域世界动态演化模型,并对度分布规律进行理论推算。最后,通过数值仿真验证了模型的可行性与有效性。

1 MLUCN模型转化

1.1 相关概念

定义4 交织型层级复杂网络是由部分节点相连,边性质近似的多个子网组成的具有层级结构、彼此交织的复合网络[8],记为CC(VC,EC,TC,φC)。其中VC为节点集合,EC为边集合,TC=(tij)NC×NC为邻接矩阵,NC=|VC|,φC为网络交织系数,用于描述子网间交织关系的密切程度[9]。

1.2 融合关系与层级关系转化

融合关系与层级关系都是对网络结构进行直观描述[9],融合关系主要关注网络的全局属性,用于分析融合网络的节点(边)综合属性、可达路径以及关联关系,支撑节点等级设置、信息路由规划等工作。层级关系可较好描述不同子网独立的拓扑结构,用于分析网络的分层属性,支撑子网的任务分配、功能划分、分层管理等工作[10]。伴随子网融合程度的改变,融合关系与层级关系可相互转化。

时的融合关系时的融合关系

时的层级关系时的层级关系图1 融合关系与层级关系演化示意图

1.3 拆分运算

在MLUCN中,融合节点的多种性质为其演化中的性质归属带来不便,使新节点在优选时不能准确区分节点性质。重合边的存在造成多条性质不同的边在外在形式上统一表现为一条总的边,使统计已有节点的度值变得较为困难和不准确。在ILCN中各个节点、边相对独立,不存在融合、重合的情况,有利于准确探索不同性质子网的演化规律[11]。本文通过拆分运算将MLUCN转化为ILCN进行研究,根据对象的不同,拆分运算分为融合节点拆分、重合边拆分和网络整体拆分。

(1)

(a)MLUCN (b)ILCN图2 MLUCN与ILCN转化过程示意图

(2)

1.3.3 网络整体拆分 在融合节点、重合边拆分基础上,网络整体可被拆分为多个单一性质的子网,且部分子网可能不为连通网络。对于CM,网络整体拆分运算为

(3)

2 ILCN动态演化模型

与BA无标度网络不同,由于受管理体制、成本、体积等影响,多数现实网络节点往往具有差异化的连接增长能力,都具有一定的连接容量(连接数量上限),所能连接的节点数是有限的,网络边不会无限制增长。为保证网络具有良好的均衡性和较强的抗毁性[1],新增节点会从饱和度较低的节点集合中择优连接。同时,网络中已有节点都具有各自的吸引因子,也会影响新增节点的择优过程及结果。本文以饱和度作为已有节点成为候选节点的判定准则,以吸引因子作为新增节点优先连接的主要依据,探索构建ILCN动态演化模型。

2.1 节点饱和度与吸引因子

定义5 节点饱和度是节点连接容量与度值之间的分段函数。通过饱和度的限制,可降低网络演化中节点度值的差异性,使生成的边相对均匀分布,促进网络整体的均衡性。在演化时刻t,节点Vi的饱和度函数可表示为

(4)

式中:Ωi为节点Vi的连接容量;ki(t)为节点Vi的度值;k*为节点的度值阈值;Ω*为饱和度的相对稳态值;Θ(Ωi,ki(t))为节点饱和度函数,通常与Ωi的变化趋势成正比,与ki(t)的变化趋势成反比。若Ωi相对固定,初始时Bi(t)随ki(t)的增大而减小,当ki(t)达到阈值k*后,虽然后续仍会不断增大,但Bi(t)基本不再变化,稳定在Ω*。

选择节点饱和度作为网络已有节点是否需要增加边的衡量标准,并以此被动生成新增节点的动态局域世界[5]。不同类别节点集合中新加入的节点,只能在对应类别、未饱和的节点集中择优选择。为便于表述,文中设定节点饱和度函数为Bi(t)=Ωi-ki(t),其中ki(t)∈[0,Ωi]。若Bi(t)=0,即ki(t)=Ωi,表明节点达到了度饱和状态,不会成为新增节点的候选连接对象。若Bi(t)>0,即ki(t)<Ωi,表明节点会成为局域世界的候选连接对象。

定义6 节点吸引因子是指单位时间内节点获得的新增边数量,表示网络中已存在节点对新增节点的复合吸引变量。对节点Vi,吸引因子可表示为

(5)

式中:Δt为时间间隔;ΔE为节点获得的新增边数。

吸引因子的存在对新增节点择优选择概率具有较大影响,一个仅有很少连接但具有很高吸引因子的节点,虽然进入网络的时间不久,也能具有很高的连接速率,并在短时间内获得大量连接,快速达到度饱和状态[7]。

2.2 演化模型构造算法

设初始时刻节点连接容量矩阵为Ω=[Ωi]m0×1,其中m0为节点数量。不同性质节点具有各自新增概率,优先与同类节点相连接,只有当同类未饱和节点数量小于新增节点初始连接数时,新增节点才会从其他类别未饱和的节点中根据节点度值和吸引因子进行选择。当新增节点与被选中节点类型确定后,边的类型随之确定。因此,演化过程中不考虑边的类型及概率,构造算法如下。

(1)开始于较少的节点数m0和连接数e0,每个演化步长内新增1个单一性质节点,性质为S的节点新增概率为pS(0≤pS≤1),并连接到m(m≤m0)个已存在的同类节点上[12]。

(2)根据演化时刻t的网络中同类节点度值,计算每个同类节点的饱和度,被动生成新增节点的同类型局域世界。

(6)

(7)

经过t个演化步长,该算法可产生一个拥有t+m0个节点和mt+e0条边的网络。

2.3 节点演化不同情形的讨论

受节点饱和度及吸引因子的影响,ILCN演化中节点会分为4种不同的情形,如图3所示。其中,节点中白色圆孔的数量代表节点固有的连接容量。

图3 ILCN演化过程示意图

当Bi小、Υi大时,此类节点一般会快速与新增节点相连,但受制于饱和容量,当节点度值达到相对饱和的状态后便保持不变,成为比较稳定的节点,与进入网络时间的长短无关。

当Bi、Υi小时,此类节点优先连接概率最小,边的增加十分缓慢,一般都会逐渐演变成为边缘节点。

2.4 节点度分布分析

受节点连接容量的限制,节点的度分布分为2种极端的情况。

(1)节点连接容量Ωi较大,演化结束后各节点度值均未达到饱和状态,可用平均场方法分析节点度分布规律。ILCN演化中仅存在优先连接,分析中假设

(8)

(9)

经历演化时间t后,平均度数为

(10)

(11)

将式(11)代入式(7),可得

(12)

(13)

(14)

新增节点在相同时间间隔内加入网络,则时间t服从均匀分布,即

(15)

由此可得

(16)

kS(t)的概率密度为

(17)

当t→∞时,节点的度分布为

(18)

ILCN模型的节点度分布服从指数分布规律,通过调节参数m、pS,可使指数在-4～0之间变化。

(2)节点连接容量Ωi较小,演化结束后各节点度值全部达到饱和状态。节点度值等于连接容量,节点的度分布规律与连接容量的分布规律相一致,可能服从固定分布,也可能是随机分布。实际中,每个节点的连接容量都是在综合考虑成本、效益、需求及外在环境等因素的基础上确定的。

通常,ILCN模型演化介于上述2种极端情况之间,节点的度分布表现为混合分布形式,未达到饱和状态的节点度分布服从指数分布规律,而已达到饱和状态的节点度分布服从连接容量的分布规律。

3 仿真实验分析

图4 初始MLUCN模型及转化后的ILCN模型

3.1 MLUCN模型转化

3.2 m固定,pa、pb、pc变化时的节点度分布

当m=1,pa、pb、pc取不同概率组合时,各类节点的度分布如图5所示。由图5可知,对任意一条分布曲线,随着节点度值k的增加,概率值总体在减小,当k达到一定数值后,概率值便保持相对平稳,呈现典型的指数分布特点。这是因为m较小,新增节点加入网络后,对已有节点度值的影响较慢,演化结束后,网络中多数节点仍处于未饱和状态,仅少数连接容量较小或吸引因子较大的节点达到度饱和状态。以m=1、pa=0.2、pb=0.3、pc=0.5时节点为例,24个节点中仅3个节点达到度饱和状态,占总数的12.5%,通过仿真拟合方法确定节点度值服从指数分布,且指数λ=2.773。将参数pb、m代入式(18)中,得到理论计算的指数值为2.6,仿真拟合结果与理论计算值基本一致,仅存在约6%的误差,验证了模型中度分布理论推算的正确性。

由图5可知:当pa=0.2、pb=0.3、pc=0.5时,仿真拟合得到λ=2.773;当pa=0.3、pb=0.4、pc=0.3时,仿真拟合得到λ=2.876,2个概率组合的指数λ结果基本一致,误差仅为3.6%。由此可得,当m相同时,尽管pa、pb、pc发生了变化,但各类性质节点的度分布曲线变化不大,仅个别度值的概率产生起伏,总体仍服从指数分布,表明在本文模型中新增节点的概率不是影响节点度分布的关键因素。

图5 m=1,pa、pb、pc逐渐改变时节点的度分布

3.3 pa、pb、pc固定,m变化时的节点度分布

当pa=0.2、pb=0.3、pc=0.5,m由1变化至3时,节点度分布如图6所示。由图6可知,m=1时3类节点度分布曲线基本服从指数分布,但随着m增加,初段度值(1～3)的概率大幅下降,中段度值(4～7)的概率明显提升,末段度值(8～10)的概率基本保持不变,曲线中仅部分区间呈指数分布。这是因为m≥2时新增节点进入网络的初始边数在2以上,在随后的多次演化中节点度值快速增加使低度值节点不断减少,m越大,低度值衰减越快、出现概率越小。由于演化总步长显著大于各节点的连接容量,演化结束后大部分节点度值都稳定在连接容量附近,达到度饱和状态[13]。对已饱和节点的度分布进行拟合,与仿真设置的理论结果基本一致,数学期望误差约为2%,方差误差约为3%。当m=2时,对未达到饱和状态的节点度分布进行仿真拟合,得出指数λ=1.37。将参数pb、m代入式(18)中,得到理论计算的指数值为1.3。由此可知,仿真拟合结果与理论计算值基本一致,仅存在约5%的误差。

图6 pa=0.2、pb=0.3、pc=0.5,m逐渐增大时 节点的度分布

3.4 pa、pb、pc及m变化时φc的变化趋势

图7 pa、pb、pc及m变化时φc的变化趋势

当pa、pb、pc及m分别取2组值时,ILCN的网络交织系数φc随演化步长的变化趋势如图7所示。由图7可知,任意2层网络的交织系数总体上随演化的推进而呈现阶梯式起伏振荡,最终趋于相对稳定。当pa、pb、pc固定时,m取值越大,φc也相应较大。这是因为较大的m要求新增节点与较多节点建立连接,当同类未饱和节点数量小于m时,新增节点会选择与其他类别的未饱和节点(属于其他子网)相连接,增加了网络之间的交织节点数量,促进了网络的节点交织程度[14]。

当m固定时,包含新增概率较高类别节点的φc较大。这是因为c类节点的概率值最高,节点新增数量最多,优先连接机理会使LC中节点的度值普遍较大且增速较快,甚至有部分节点提前达到度饱和状态。为满足连接数量要求,新增节点会从其他类别的未饱和节点中择优建立连接,从而增加了不同类别节点之间的交织边数量,使网络间的边交织关系更加密集、更加复杂。

4 结 论

本文针对多个性质不同、相互融合的复杂网络演化问题,探索建立了一种基于节点饱和度和吸引因子的动态演化模型,并仿真分析了节点度分布及网络交织系数的变化情况,有以下主要结论。

(1)在节点度值饱和度和吸引因子的共同作用下,网络全部节点的度值服从混合分布规律,即未达到饱和状态的节点度值服从指数分布,已达到饱和状态的节点度值服从其连接容量的分布规律;混合分布的参数取值与m密切相关,但与新增节点的类型概率相关性不强。

(2)网络交织系数与最高的新增节点概率、m呈正相关性,随着演化步长的逐步推进,发生阶梯式起伏振荡,并最终趋于相对稳定。

[1] CASTET J F, SALEH J H. Interdependent multi-layer networks: modeling and survivability analysis with applications to space-based networks [J]. PLOS ONE, 2013, 8(4): e60402.

[2] WANG Zhen, SZOLNOKI A, PERC M. Self-organization towards optimally interdependent networks by means of coevolution [J]. New Journal of Physics, 2014, 16: 033041.

[3] 高洋, 李丽香, 彭海朋, 等. 多重边复杂网络系统的稳定性分析 [J]. 物理学报, 2008, 57(3): 1444-1451. GAO Yang, LI Lixiang, PENG Haipeng, et al. Stability analysis of complex networks with multi-links [J]. Acta Phys Sin, 2008, 57(3): 1444-1451.

[4] JIANG J, LI W, CAI X. The effect of interdependence on the percolation of interdependent networks [J]. Physica: A Statistical Mechanics and Its Applications, 2014, 410: 573-581.

[5] 田立新, 贺莹环, 黄益. 一种新型二分网络类局域世界演化模型 [J]. 物理学报, 2012, 61(22): 228903. TIAN Lixin, HE Yinghuan, HUANG Yi. A novel local-world-like evolving bipartite network model [J]. Acta Physica Sinica, 2012, 61(22): 228903.

[6] 陶少华, 赵会洋, 平源, 等. 基于吸引因子的无尺度网络演化模型研究 [J]. 复杂系统与复杂性科学, 2008, 5(2): 88-92. TAO Shaohua, ZHAO Huiyang, PING Yuan, et al. Attractive factors based scale-free networks evolving model [J]. Complex Systems and Complexity Science, 2008, 5(2): 88-92.

[7] AOKI T, YAWATA K, AOYAGI T. Self-organization of complex networks as a dynamical system [J]. Physical Review: E, 2015, 91(1): 012908.

[8] STIPPINGER M. Enhancing resilience of interdependent networks by healing [J]. Physica: A Statistical Mechanics and Its Applications, 2014, 416: 481-487.

[9] 沈迪, 李建华, 张强, 等. 交织型层级复杂网 [J]. 物理学报, 2014, 63(19): 190201. SHEN Di, LI Jianhua, ZHANG Qiang, et al. Interlacing layered complex networks [J]. Acta Physica Sinica, 2014, 63(19): 190-201.

[10]SANTOS M D, DOROGOVTSEV S N, MENDES J F. Biased imitation in coupled evolutionary games in interdependent networks[R/OL]. [2015-12-26]. http: ∥www.nature.com/articles/srep04436?message -global=remove&WT.ec_id=SREP-639-20140325.

[11]邵峰晶, 孙仁诚, 李淑静, 等. 多子网复合复杂网络及其运算研究 [J]. 复杂系统与复杂性科学, 2012, 9(4): 20-25. SHAO Fengjing, SUN Rencheng, LI Shujing, et al. Research of multi-subnet composited complex network and its operation [J]. Complex Systems and Complexity Science, 2012, 9(4): 20-25.

[12]孙钦东, 孙亚红, 管晓宏, 等. 动态短信通信复杂网络演化模型研究 [J]. 西安交通大学学报, 2009, 43(6): 5-9. SUN Qindong, SUN Yahong, GUAN Xiaohong, et al. A dynamic evolution model of short message complex network [J]. Journal of Xi’an Jiao Tong University, 2009, 43(6): 5-9.

[13]WANG Baokui, PEI Zhenhua, WANG Long. Evolutionary dynamics of cooperation on interdependent networks with the Prisoner’s Dilemma and snowdrift game [J]. EPL, 2014, 107(5): 58006.

[14]向海涛, 梁世东. 双复杂网络间的演化博弈 [J]. 物理学报, 2015, 64(1): 018902. XIANG Haitao, LIANG Shidong. Evolutionary gambling dynamic for two growing complex networks [J].

Acta Physica Sinica, 2015, 64(1): 018902.

[本刊相关文献链接]

戴启华,刘勤让,沈剑良,等.采用集簇方法的片上网络动态映射算法.2016,50(8):52-58.[doi:10.7652/xjtuxb201608 009]

孙泽宇,伍卫国,曹仰杰,等.无线传感器网络中能量均衡参数可控覆盖算法.2016,50(8):77-83.[doi:10.7652/xjtuxb 201608013]

赵皓,高智勇,高建民,等.一种采用相空间重构的多源数据融合方法.2016,50(8):84-89.[doi:10.7652/xjtuxb201608 014]

徐张宝,马大为,姚建勇,等.采用干扰估计的液压系统自适应鲁棒控制.2016,50(8):123-129.[doi:10.7652/xjtuxb2016 08020]

魏倩,蔡远利.一种基于神经网络的中制导改进算法.2016,50(7):125-130.[doi:10.7652/xjtuxb201607019]

张小栋,郭晋,李睿,等.表情驱动下脑电信号的建模仿真及分类识别.2016,50(6):1-8.[doi:10.7652/xjtuxb201606001]

姜涛,黄伟,王安麟.多路阀阀芯节流槽拓扑结构组合的神经网络模型.2016,50(6):36-41.[doi:10.7652/xjtuxb201606 006]

刘兆丽,秦涛,管晓宏,等.采用用户名相似度传播模型的线上用户身份属性关联方法.2016,50(4):1-6.[doi:10.7652/xjtuxb201604001]

陈斌,胡平舸,屈丹.子空间域相关特征变换与融合的语音识别方法.2016,50(4):60-67.[doi:10.7652/xjtuxb201604010]

王富平,水鹏朗.采用多尺度方向微分比率的角点检测算法.2016,50(4):68-75.[doi:10.7652/xjtuxb201604011]

贺王鹏,訾艳阳,陈彬强.冲击特征受控极小化通用稀疏表示及其在机械故障诊断中的应用.2016,50(4):94-99.[doi:10.7652/xjtuxb201604015]

丁建坤,韩德强,杨艺.最短特征线段多分类器系统设计.2015,49(9):77-83.[doi:10.7652/xjtuxb201509014]

周远,周玉生,刘权,等.一种适用于图像拼接的DSIFT算法研究.2015,49(9):84-90.[doi:10.7652/xjtuxb201509015]

孙忱,奚宏生,高荣.邻域线性最小二乘拟合的推荐支持度模型.2015,49(6):77-83.[doi:10.7652/xjtuxb201506013]

朱爱斌,胡浩强,何大勇,等.采用频域融合方法的砂轮刀具磨损三维重构技术.2015,49(5):82-86.[doi:10.7652/xjtuxb201505013]

谢文军,付晓,于振华,等.信息物理融合系统中恶意软件传播动力学研究.2015,49(4):78-83.[doi:10.7652/xjtuxb 201504013]

徐田华,杨连报,胡红利,等.高速铁路信号系统异构数据融合和智能维护决策.2015,49(1):72-78.[doi:10.7652/xjtuxb201501012]

(编辑 赵炜)

Dynamic Evolution Model of United Complex Networks with Multi-Links

YANG Yinghui1,LI Jianhua1,SHEN Di1,NAN Mingli1,2,CUI Qiong1

(1. Information and Navigation Institute, Air Force Engineering University, Xi’an 710077, China; 2. The Unit 95881 of PLA, Beijing 100095, China)

Aiming at the problem that during the evolution process of interconnected complex networks, there exist nonuniform time-varying property and layered interlaced network structure, leading to the difficulty in measuring their characteristics and rules, a dynamic evolution model of united complex network with multi-links (MLUCN) is proposed. Firstly, we define some related concepts of MLUCN, analyze the conversion process of fusion and hierarchy relationship, and split fusion nodes and overlapped edges according to the property difference between nodes and edges, then the MLUCN is transformed to interlaced layered complex networks (ILCN). Secondly, the node degree saturation and attraction factor are defined. The evolution algorithm and local-world evolution model for ILCN are put forward, and four situations of node evolution are discussed. The mean field method is used to analyze the degree distribution rule during evolution. Finally, numerical simulation is performed. The results show that the node degree not reaching saturation obeys the exponential distribution with an error no more than 6%; the node degree reaching saturation obeys their connection capacities’ distribution with an error no more than 3%; the network weaving coefficients have a positive correlation with the highest probability of new node and the initial number of connected edges. The results verified the feasibility and effectiveness of the proposed model. This model provides a new idea and method for exploring MLUCN evolution process and rule, and also has good application prospects in the structure and dynamics researches of transportation network, communication network and social network, etc.

united complex network with multi-links; interlaced layered complex network; dynamic evolution; saturation; attraction factor

2016-01-18。 作者简介:杨迎辉(1988—),男,博士生;李建华(通信作者),男,教授。 基金项目:国家自然科学基金资助项目(61573017,61401499,61174162)。

10.7652/xjtuxb201609021

N94

A

0253-987X(2016)09-0132-08