付凯1,2,夏靖波3,赵小欢4
(1.空军工程大学 信息与导航学院,西安710077; 2. 95246部队,南宁530003; 3.厦门大学 嘉庚学院, 福建 漳州363105; 4. 95340部队,广西 百色 533616)
摘要:
为挖掘复杂网络中的关键节点及提高网络鲁棒性,针对有/无线多网融合的层级网络,提出了动态融合复杂网络模型及其节点重要度评估方法.结合动态融合复杂网络的特点,定义了边连通概率、路径连通概率、网络连通概率、融合节点比例、融合节点分布和融合路径比例等与网络动态性和融合性相关的参数.在单层复杂网络节点重要度评估指标的基础上,设计了融合网络节点度中心性、节点介数中心性和节点融合中心性指标.其中,融合节点的节点融合中心性表示融合节点对网络融合的贡献程度,非融合节点的节点融合中心性表示非融合节点对网络融合的辅助作用程度,主要体现在作为融合节点之间的中继节点.最后,综合考虑网络拓扑结构、动态融合特性等因素进行节点重要度评估.以改进的动态交织风筝网络为例进行仿真分析,结果表明该方法能够比较全面地刻画节点在动态融合复杂网络中的重要性.利用NS2搭建由光通信网和卫星通信网融合构成的仿真实验网络,进一步验证了在仿真网络环境中本方法的有效性.
关键词: 复杂网络 动态融合 节点重要度 度中心性 介数中心性 融合中心性
DOI:10.11918/j.issn.0367-6234.201607012
分类号:TP393
文献标识码:A
基金项目:航空科学基金(20141996018);陕西省自然科学基础研究计划项目(2012JZ8005)
Node importance evaluation in dynamic convergence complex networks
FU Kai1,2,XIA Jingbo3,ZHAO Xiaohuan4
(1.Information and Navigation College, Air Force Engineering University, Xi’an 710077, China; 2.Unit 95246, Nanning 530003, China; 3.Tan Kah Kee College, Xiamen University, Zhangzhou 363105, Fujian, China; 4.Unit 95340, Baise 533616, Guangxi, China)
Abstract:
To seek key nodes and improve network robustness, the dynamic convergence complex network model and its node importance evaluation method are proposed for wired and wireless integrating layered networks. Considering characteristic of dynamic convergence complex networks, parameters including edge connection probability, path connection probability, network connection probability, convergence node proportion, convergence node distribution and convergence path proportion are designed. Based on node importance evaluation indexes in single-layer complex networks, the node degree centrality, node betweenness centrality and node convergence centrality in dynamic convergence complex networks are presented. Node convergence centrality of convergence nodes indicates their contribution to network convergence, and that of non-convergence nodes indicates their auxiliary effect to network convergence, especially they are used as relay nodes among convergence nodes. At last, node importance evaluation is implemented considering network topology structure and its dynamic convergence characteristic. Typical example results of improved dynamic convergence kite networks show that the proposed method can comprehensively depict the node importance in dynamic convergence complex networks. Simulation network composed of fiber communication network and satellite communication network is designed by NS2, further indicating the effectiveness of the proposed method.
Key words: complex networks dynamic convergence node importance degree centrality betweenness centrality convergence centrality
付凯, 夏靖波, 赵小欢. 动态融合复杂网络节点重要度评估方法[J]. 哈尔滨工业大学学报, 2017, 49(10): 112-119. DOI: 10.11918/j.issn.0367-6234.201607012.
![复制到剪切板](http://hit.alljournals.cn/html/hitxb_cn/2017/10/images/copy.gif)
FU Kai, XIA Jingbo, ZHAO Xiaohuan. Node importance evaluation in dynamic convergence complex networks[J]. Journal of Harbin Institute of Technology, 2017, 49(10): 112-119. DOI: 10.11918/j.issn.0367-6234.201607012.
![复制到剪切板](http://hit.alljournals.cn/html/hitxb_cn/2017/10/images/copy.gif)
基金项目 航空科学基金(20141996018);陕西省自然科学基础研究计划项目(2012JZ8005) 作者简介 付凯(1987—),男,博士研究生;
夏靖波(1963—),男,教授,博士生导师 通信作者 付凯,fukaia3@163.com 文章历史 收稿日期: 2016-07-05
Contents -->Abstract Full text Figures/Tables PDF
动态融合复杂网络节点重要度评估方法
付凯1,2
![通讯作者](http://hit.alljournals.cn/html/hitxb_cn/2017/10/images/REcor.gif)
![fukaia3@163.com](http://hit.alljournals.cn/html/hitxb_cn/2017/10/images/REemail.gif)
1. 空军工程大学 信息与导航学院,西安 710077;
2. 95246部队,南宁 530003;
3. 厦门大学 嘉庚学院,福建 漳州 363105;
4. 95340部队,广西 百色 533616
收稿日期: 2016-07-05
基金项目: 航空科学基金(20141996018);陕西省自然科学基础研究计划项目(2012JZ8005)
作者简介: 付凯(1987—),男,博士研究生;
夏靖波(1963—),男,教授,博士生导师
通信作者: 付凯,fukaia3@163.com
摘要: 为挖掘复杂网络中的关键节点及提高网络鲁棒性,针对有/无线多网融合的层级网络,提出了动态融合复杂网络模型及其节点重要度评估方法.结合动态融合复杂网络的特点,定义了边连通概率、路径连通概率、网络连通概率、融合节点比例、融合节点分布和融合路径比例等与网络动态性和融合性相关的参数.在单层复杂网络节点重要度评估指标的基础上,设计了融合网络节点度中心性、节点介数中心性和节点融合中心性指标.其中,融合节点的节点融合中心性表示融合节点对网络融合的贡献程度,非融合节点的节点融合中心性表示非融合节点对网络融合的辅助作用程度,主要体现在作为融合节点之间的中继节点.最后,综合考虑网络拓扑结构、动态融合特性等因素进行节点重要度评估.以改进的动态交织风筝网络为例进行仿真分析,结果表明该方法能够比较全面地刻画节点在动态融合复杂网络中的重要性.利用NS2搭建由光通信网和卫星通信网融合构成的仿真实验网络,进一步验证了在仿真网络环境中本方法的有效性.
关键词: 复杂网络 动态融合 节点重要度 度中心性 介数中心性 融合中心性
Node importance evaluation in dynamic convergence complex networks
FU Kai1,2
![Corresponding author](http://hit.alljournals.cn/html/hitxb_cn/2017/10/images/REcor.gif)
![fukaia3@163.com](http://hit.alljournals.cn/html/hitxb_cn/2017/10/images/REemail.gif)
1. Information and Navigation College, Air Force Engineering University, Xi'an 710077, China;
2. Unit 95246, Nanning 530003, China;
3. Tan Kah Kee College, Xiamen University, Zhangzhou 363105, Fujian, China;
4. Unit 95340, Baise 533616, Guangxi, China
Abstract: To seek key nodes and improve network robustness, the dynamic convergence complex network model and its node importance evaluation method are proposed for wired and wireless integrating layered networks. Considering characteristic of dynamic convergence complex networks, parameters including edge connection probability, path connection probability, network connection probability, convergence node proportion, convergence node distribution and convergence path proportion are designed. Based on node importance evaluation indexes in single-layer complex networks, the node degree centrality, node betweenness centrality and node convergence centrality in dynamic convergence complex networks are presented. Node convergence centrality of convergence nodes indicates their contribution to network convergence, and that of non-convergence nodes indicates their auxiliary effect to network convergence, especially they are used as relay nodes among convergence nodes. At last, node importance evaluation is implemented considering network topology structure and its dynamic convergence characteristic. Typical example results of improved dynamic convergence kite networks show that the proposed method can comprehensively depict the node importance in dynamic convergence complex networks. Simulation network composed of fiber communication network and satellite communication network is designed by NS2, further indicating the effectiveness of the proposed method.
Key words: complex networks dynamic convergence node importance degree centrality betweenness centrality convergence centrality
复杂网络小世界效应[1]和无标度特性[2]的发现,掀起了国内外研究复杂网络的热潮.随着网络科学[3-4]的蓬勃发展,节点重要度评估进一步受到研究人员的关注,寻找复杂网络中的关键节点成为网络科学的重要研究内容.目前,节点重要度评估方法主要包括基于网络结构的方法和基于传播动力学的方法[5].度中心性、介数中心性[6]、特征向量中心性[7]等是典型的基于网络结构的评估指标,其依据是网络局部或全局属性信息.基于传播动力学的方法通过计算网络中节点的影响范围来衡量其重要度,如社会网络中关键节点的挖掘[8-9].
上述评估指标主要针对单层复杂网络,随着研究的深入和应用的拓展,多种层级复杂网络模型[10]被相继提出.相互依存网络[11]描述了具有相互影响和依赖关系的网络模型,对于预防和控制复杂系统中的相继故障具有重要意义,如电力-计算机网等.陈宏斌等[12]提出了二元随机网的概念,它是一种特殊的二元网,不考虑同类节点之间的相互作用,如图书借阅网络等.邵峰晶等[13]提出多子网复合网络模型,通过网络加载和拆分等网络运算进行网络的复合与分解,实现复杂网络中同一子网元素间、不同子网元素间以及不同子网之间的相互关系等形式描述.超网络[14]是一种“高于而又超于现存网络”的网络,用以描述规模巨大、连接复杂、具有嵌套网络的大型复杂网络,如供应链网络等.以上层级复杂网络侧重不同子网之间的相互关系,而对于网络模型中的节点重要性未做深入研究.沈迪等[15]提出一种交织型层级复杂网,描述由两个具有部分相同节点、连接边属性近似的子网构成的层级复杂网络,并且定义了相关测度用于衡量子网之间的密切程度及节点中心性,但只适用于静态网络.而节点重要度评估问题已逐渐向动态变化的时变网络延伸,在拓扑结构变化的网络中发现关键节点更具有挑战性[16]. Basaras等[17]在介数和K-SHELL基础上提出了动态复杂网络中的关键节点发现算法,基于局部信息从而降低计算开销,更加适合动态网络中应用. Masaki[18]以动态变化的社会网络为背景,提出了加权动态复杂网络中的节点重要度评估方法.
随着对网络应用的需求不断增强,多网系融合、有/无线并用成为未来网络的发展趋势.例如,手机、平板电脑等移动网络终端通过无线路由器实现对互联网的接入,就构成了有线的宽带互联网与无线的手机通信网之间的融合互联,而且网络带宽、信号强度等使得有线和无线信道的通信质量存在差异.为了在这种融合网络中发现关键节点、优化网络结构等,需要构建新的网络模型研究节点重要度评估问题.本文在文献[15]的基础上提出动态融合复杂网络(dynamic convergence complex networks,DCCN)模型,定义了与动态性和融合性相关的网络参数,结合网络动态融合特性改进了节点度中心性和介数中心性指标,并提出了节点融合中心性以反映各类节点对促进网络融合的贡献程度,在此基础上进行动态融合复杂网络节点重要度评估,最后通过仿真分析验证了方法的有效性.与现有模型相比,本文模型结合当前有/无线网络融合发展的需求,在融合网络的基础上又考虑了网络动态特性,并结合网络动态融合特性设计或改进节点中心性指标,能够比较全面地刻画节点在动态融合复杂网络中的重要性.
1 动态融合复杂网络模型 1.1 理论基础设图Ga= (Va, Ea)是一个无环无向无权的单层复杂网络,Va={v1, v2, …, vn}表示网络a的节点集合,节点数量为|Va| =n,Ea={e1, e2, …, em}=Va×Va为网络a的边集合,边的数量为|Ea| =m. A = (Aij)n×n为网络a的邻接矩阵,取值为0或1,表示节点之间是否存在连接边.在图Ga中任意两个节点之间最长的路径称为图Ga的直径,记为Dnd.
在单层复杂网络中,节点vi的度中心性定义为
${d_i} = \frac{{{g_i}}}{{n-1}}.$
式中:gi为节点vi的度,n为网络的节点数.
节点vi的介数中心性定义为
$ {b_i} = \frac{{\sum\limits_{s = 1}^n {\sum\limits_{t = 1}^n {\frac{{{N_{sp}}\left( {s, i, t} \right)}}{{{N_{sp}}\left( {s, t} \right)}}} } }}{{n\left( {n-1} \right)/2}}. $
式中:Nsp(s, t)为节点vs和vt之间的最短路径数量,Nsp(s, i, t)为节点vs和vt之间经过节点vi的最短路径数量.
1.2 模型概述定义1?动态融合复杂网络.由两种以上单层复杂网络融合而成,且其中至少有一种为动态网络的层级网络称为动态融合复杂网络.动态融合复杂网络中的“动态”是指网络中的边以一定概率进行连通(主要指无线传输手段等间歇连接),而节点数量保持不变.网络动态性对介数等与路径相关的参数影响较大,而对度等基于网络局部属性的参数影响较小.动态融合复杂网络中的“融合”是指多个网络之间存在部分节点复用,节点之间可能存在两种以上属性的边.为方便研究,本文仅考虑由两种单层复杂网络组成的动态融合复杂网络,且其中一种为动态网络.
动态融合复杂网络c(以下简称“融合网络”)由单层复杂网络a和b融合构成,Vc={v1, v2, …, vN}=Va∪Vb为融合网络的节点集,节点数量为|Vc|=N,Vc*={v1, v2, …, vM}=Va∩Vb表示融合网络的融合节点集,融合节点数量为|Vc*| =M.Ec=Ea∪Eb为融合网络的边集,边的数量为|Ec|,由于边不存在复用,所以融合网络的边集即为各单层复杂网络的边集之和. C = A ∪ B =(Cij)N×N为网络c的邻接矩阵,取值为0或1,表示融合网络的节点之间是否存在连接边,规定节点之间无连接边时取值为0,节点之间有1条或2条边时取值均为1.
1.3 参数定义动态融合复杂网络最重要的特性是动态和融合,因此本文主要从动态和融合两方面设计网络参数.其中,网络连通参数主要包括边连通概率、路径连通概率和网络连通概率,用以描述网络的连通状况;网络融合参数主要包括融合节点比例、融合节点分布和融合路径比例,用以描述网络的融合程度.
1.3.1 边连通概率在动态网络中,如果节点vi和vj之间存在连接边,则Pij表示该边的连通概率,并假定非动态网络中边的连通概率为1.令P =(Pij)N×N为融合网络c的连通性矩阵,规定节点之间无连接边时取值为0,节点之间有1条边时为该边的连通概率,节点之间有2条边时取2条边的连通概率的最大值.
1.3.2 路径连通概率设路径vi-vm-vn-…-vz-vj,则Qij(k)= Pim× Pmn×…× Pzj表示该路径的连通概率,为该路径上所有边的连通概率之积.值得注意的是,Qij(k)= Pim× Pmn×…× Pzj表示特定的一条路径(vi-vm-vn-…-vz-vj,其路径编号为k)的连通概率,而不是指节点vi和vj之间的路径连通概率,因为节点vi和vj可能存在多条路径(路径编号k取不同的值),而每一条路径都对应一个路径连通概率.
1.3.3 网络连通概率网络连通概率定义为
${R_{ncp}} = (\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^N {{\mathit{\boldsymbol{P}}_{ij}}/2} } )/(\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^N {{\mathit{\boldsymbol{C}}_{ij}}/2} } ), $
反映整个网络的平均连通状况.
1.3.4 融合节点比例融合节点比例定义为
${R_{cnp}} = M/N, $
表示网络节点集中融合节点所占的比例,从融合节点数量的角度反映网络融合程度,融合节点越多则越能促进网络的融合.
1.3.5 融合节点分布融合节点比例在一定程度上反映了网络的融合程度,但还存在片面性.如果融合节点比较密集地分布在局部区域,那么与融合节点分散分布的情形相比,其对促进整个网络融合的作用会减弱.因此,定义融合节点分布为
${R_{cnd}} = {D_{{\rm{avg}}}}/{D_{nd}}, $
表示网络中融合节点的紧密程度,从融合节点位置的角度反映网络融合程度,融合节点在网络中的位置越分散则越能促进网络的融合.其中,Davg为融合节点之间的平均距离,Dnd为融合网络的直径.
1.3.6 融合路径比例融合路径比例定义为
${R_{cpp}} = {N_{cp}}/{N_{sp}}, $
表示最短路径中融合路径所占的比例,从消息传播的角度反映网络融合程度,融合路径越多则越能促进网络的融合.其中,Nsp为网络中所有节点对之间的最短路径的数量,Ncp为这些最短路径中融合路径的数量.融合路径是指包含两种边的路径,仅包含融合节点但只有一种边的路径不是融合路径.如图 1所示,对于路径1-2-3-4,图 1(a)、(b)为融合路径,而图 1(c)不是融合路径.
Figure 1
![点击查看原图](http://hit.alljournals.cn/html/hitxb_cn/2017/10/PIC/hebgydxxb-49-10-112-1.jpg)
2 节点重要度评估方法动态融合复杂网络的节点重要度评估主要是在网络拓扑结构的基础上,考虑动态及融合特性的影响.度中心性和介数中心性是节点重要度评估中最常用的指标,分别基于网络局部属性和全局属性反映单层复杂网络中节点的重要性.但对于动态融合复杂网络,其拓扑结构由于网络融合而具有新的变化,因此本文结合其特性进行重新定义.此外,提出节点融合中心性指标,从节点促进网络融合的角度反映其重要性.
定义2?融合网络节点度中心性.
融合网络中节点vi的度中心性定义为
${D_i} = \frac{{{g_i}}}{{n-1}}(2-\frac{{\left| {{N_a}-{N_b}} \right|}}{{\max \{ {N_a}, {N_b}\} }}).$ (2)
式中,Na为节点vi的邻居节点中属于单层复杂网络a的节点数量,Nb同理.从理论分析的角度,对于非融合节点,有Na=0或Nb=0,因此Di=di,即非融合节点的度中心性与经典度中心性的计算结果相同;对于融合节点,有Na≠0且Nb≠0,则
定义3?融合网络节点介数中心性.
融合网络中节点vi的介数中心性定义为
${B_i} = \frac{1}{{n\left( {n-1} \right)/2}}\sum\limits_{s = 1}^n {\sum\limits_{t = 1}^n {\frac{{\sum\limits_{k = 1}^j {{Q_{st}}\left( k \right)} }}{{{N_{sp}}\left( {s, t} \right)}}} } .$ (3)
式中,j=Ncsp(s, i, t)为节点vs和vt之间经过节点vi的融合最短路径数量,即经过节点vi的最短路径中融合路径的数量.其中,Ncsp(s, i, t)的值越大,则对跨网信息传播越重要;Qst(k)为对应编号k的融合最短路径的连通概率(当j=0时,Qst(k)=0),反映融合最短路径的可靠性,这对于动态融合复杂网络中介数的计算是比较重要的.对比式(3)和式(1),由于0≤Qst(k)≤1,则
定义4?融合网络节点融合中心性.
融合网络中节点vi的融合中心性定义为
${C_i} = \left\{ \begin{array}{l}\frac{1}{{(1 + {R_{cnp}})(1 + {R_{cnd}})(1 + {R_{cpp}} \times {R_{ncp}}), }}{v_i} \in V_{_c}^{^*};\\\frac{{{N_{acn}}}}{{{g_i}}}(1 + {c_i}), {v_i} \in {V_c}-V_{_c}^{^*}.\end{array} \right.$
对于融合节点,其融合中心性表示融合节点对网络融合的贡献程度.一旦网络拓扑参数确定,所有融合节点的融合中心性是一个与其位置特性无关的固定值,从宏观上反映网络中所有融合节点对网络融合的贡献程度.融合节点比例越低,融合路径比例越低,融合节点分布越密集,则网络的融合程度越低.而在网络融合程度低的情形下,融合节点发挥的作用就越大,从而融合节点对网络融合的贡献程度就越高.另外,加入参数Rncp考虑网络动态性对融合路径的影响,使指标的计算更加客观.
对于非融合节点,其融合中心性表示非融合节点对网络融合的辅助作用程度,主要体现在作为融合节点之间的中继节点.其中,Nacn为节点vi的邻居融合节点数量,ci为节点vi的融合聚类系数,反映其邻居融合节点之间的连通程度,定义为
${c_i} = \frac{{2{f_i}}}{{{N_{acn}}({N_{acn}}-1)}}.$
式中,fi为节点vi与其任意两个邻居融合节点之间所形成的三角形的个数.若gi=1或Nacn=0,则令ci=+∞.
由于非融合节点的融合中心性主要体现在连通那些原本相互之间连通程度较弱的融合节点上,因此节点vi的邻居融合节点的比例越高,且它们之间的连通程度越弱,则非融合节点对网络融合的辅助作用程度越高.如图 2所示,图 2(a)、(b)、(c)中节点1的融合中心性分别为0.40、0.60、0.36.图 2(b)比图 2(a)的值高是因为融合节点比例增加,图 2(c)比图 2(b)的值低是因为融合聚类系数提高,节点1在连通融合节点3、4、5的作用上减弱了,其融合中心性也要降低.
Figure 2
![点击查看原图](http://hit.alljournals.cn/html/hitxb_cn/2017/10/PIC/hebgydxxb-49-10-112-2.jpg)
定义5?融合网络节点重要度.
根据定义2~定义4,综合考虑局部位置信息、全局位置信息、网络融合特性3个方面,定义融合网络的节点重要度为
${I_i} = \alpha \times {D_i} + \beta \times {B_i} + \gamma \times {C_i}.$
式中,α、β、γ∈(0, 1),且α+β+γ=1,通过3个参数的设置可以调节各中心性在最终节点重要度评估中的权重.一般来说,网络拓扑结构对节点重要度的影响是主要的,因此参数α和β应设置较大一些.融合中心性是在动态融合网络模型中对节点重要度评估的一个改进和补充,因此参数γ应设置小一些.
3 实验分析 3.1 典型算例为验证本文节点重要度评估方法的有效性,以文献[15]中的交织风筝网络为基础网络,并加入连边的动态特性以构成动态融合复杂网络(如图 3所示).其中,单层网络a包含10个节点、18条边;单层网络b为动态网络,包含8个节点、13条边,边上的数值代表边的连通概率;融合网络c为网络a和b融合构成的网络,包含13个节点、31条边,其中5个融合节点分别由网络a和b中具有相同编号的节点融合形成.
Figure 3
![点击查看原图](http://hit.alljournals.cn/html/hitxb_cn/2017/10/PIC/hebgydxxb-49-10-112-3.jpg)
实验中设置参数α=0.4,β=0.4,γ=0.2,通过MATLAB 2010a进行仿真实验,分别计算单层网络a和b中各节点的度中心性和介数中心性,以及网络融合后各节点在融合网络中的中心性指标,仿真结果见表 1~3.
表 1
![点击查看表格内容](http://hit.alljournals.cn/html/hitxb_cn/2017/10/images/table-icon.gif)
网络a 0.111 0.222 0.333 0.556 0.556 0.333 0.667 0.333 0.444 0.444 — — —
网络b 0.428 — 0.714 — — 0.571 0.286 0.571 — — 0.429 0.429 0.286
网络c(文献[15]) 0.674 0.167 1.586 0.416 0.416 1.445 1.349 1.445 0.333 0.333 0.231 0.231 0.167
网络c(本文) 0.444 0.167 1.067 0.416 0.416 0.875 0.667 0.875 0.333 0.333 0.250 0.250 0.167
表 1 度中心性 Table 1 Degree centrality
表 2
![点击查看表格内容](http://hit.alljournals.cn/html/hitxb_cn/2017/10/images/table-icon.gif)
网络a 0 0.222 0.389 0.231 0.231 0 0.102 0 0.023 0.023 — — —
网络b 0 — 0.432 — — 0.211 0.135 0.211 — — 0.254 0.254 0
网络c(文献[15]) 0.092 0.184 0.856 0.396 0.396 0.586 0.602 0.586 0.126 0.126 0.503 0.503 0
网络c(本文) 0.044 0 0.374 0.020 0.023 0.157 0.021 0.175 0.010 0.011 0.009 0.011 0
表 2 介数中心性 Table 2 Betweenness centrality
表 3
![点击查看表格内容](http://hit.alljournals.cn/html/hitxb_cn/2017/10/images/table-icon.gif)
融合中心性 0.429 0.500 0.429 0.375 0.375 0.429 0.429 0.429 0.300 0.300 0.600 0.600 1.000
节点重要度 0.281 0.167 0.662 0.250 0.252 0.499 0.361 0.506 0.197 0.198 0.223 0.224 0.267
重要度排序 5 13 1 8 7 3 4 2 12 11 10 9 6
表 3 融合中心性和节点重要度 Table 3 Convergence centrality and node importance
由表 1可以看出,融合节点1、3、6、7、8的度中心性较高,一是网络融合后这些节点的度有所增加,二是式(2)使融合节点的度中心性得到加强,而非融合节点由于融合网络节点总数的增加而使其度中心性降低,说明本文计算节点度中心性考虑了网络融合的影响,这与文献[15]是类似的.节点3在融合网络中具有最高的度值并且得到加强,因而其度中心性排名最高.
由表 2可以看出,本文计算的所有节点的介数中心性都不高,虽然网络融合产生了更多的节点对和最短路径,但式(3)考虑融合路径和网络动态性后使计算结果较小.与文献[15]相比,虽然本文计算节点介数中心性的条件比较严格,但能够在动态融合的网络环境下真实反映信息传播对介数的贡献.节点3在各单层网络中就具有最高的介数中心性,网络融合后仍是许多融合最短路径所经过的节点,因此其介数中心性排名最高.节点6和8在单层网络中的介数中心性排名比较低,但网络融合后在融合最短路径上的贡献度较大,因此介数中心性排名比较靠前.同时,节点8比节点6的值稍高,是因为网络b左半部分的边连通概率比右半部分的高,这点在其他对称的节点对(如节点4、5、9和10、11和12)之间也有所体现,从而说明本文的指标能够反映网络连通性的影响.节点1的介数中心性不再是单层网络中的0,主要是网络融合后该节点在融合最短路径上有所贡献.节点2的介数中心性由网络a中的0.222变为0,是由于节点1和3之间的连边使节点2的两条邻边成为了冗余路径.
如表 3所示,融合中心性方面,融合节点的值为0.429,是融合节点比例、融合路径比例和融合节点分布等3个网络融合参数共同决定的,反映了融合节点对网络融合的贡献程度.非融合节点2、11、12、13的融合中心性较高,说明它们在辅助网络融合方面起到了较大作用,从网络拓扑中也可以看出它们都是连接融合节点的枢纽,在融合程度不高的网络中它们的重要性更是不能忽视.节点重要度方面,本文综合考虑网络拓扑结构和动态融合特性等因素,对节点重要度的评估是一个综合评价指标.5个融合节点的重要度位居前列,这也与指标设计的基本思想是一致的.对称节点对的重要度差异主要来自介数中心性的计算,最终反映了网络动态性对节点重要度的影响.非融合节点13的排名紧跟融合节点之后,主要在于其融合中心性的作用,体现了对非融合节点重要度的加强,使节点重要度评估更加全面、客观.
在节点重要度评估中,节点度中心性和融合中心性主要考虑网络融合性的影响,节点介数中心性主要考虑网络动态性的影响,并通过α、β、γ这3个参数的设置进行调节.由于节点度中心性和介数中心性是以网络拓扑结构为基础,而网络拓扑结构是节点重要度的主要影响因素,因此本文给参数γ一个较小的固定值,并考察参数α和β的不同变化对节点重要度的影响,仿真结果如图 4所示.可以看出,随着α的增大,网络融合性的影响增强,融合节点的重要度有显著的提高.随着β的增大,网络动态性的影响增强,各节点的重要度均有所降低,尤其对节点9~12等介数中心性较小的节点影响较大,β=0.2时其重要度均排在节点13之前,而β=0.8时均排在节点13之后.
Figure 4
![点击查看原图](http://hit.alljournals.cn/html/hitxb_cn/2017/10/PIC/hebgydxxb-49-10-112-4.jpg)
3.2 仿真网络为进一步验证本文方法的适用性,利用NS2搭建仿真网络,仿真场景及其对应的网络拓扑如图 5、6所示.该仿真网络由光通信网和卫星通信网融合构成,是典型的有线与无线混合组网的情景.网络中共有15个节点,其中有线节点7个(W1~W7),无线节点5个(M1~M4,B1),融合节点3个(B2~B4).网络中共18条链路,其中有线链路11条,无线链路7条.另外,仿真网络中仅反映无线节点之间的连通关系(即两个无线节点之间是否存在无线链路),而不考虑其运动情况.
Figure 5
![点击查看原图](http://hit.alljournals.cn/html/hitxb_cn/2017/10/PIC/hebgydxxb-49-10-112-5.jpg)
Figure 6
![点击查看原图](http://hit.alljournals.cn/html/hitxb_cn/2017/10/PIC/hebgydxxb-49-10-112-6.jpg)
链路连通率反映了链路两端点之间成功发送或接收数据的情况,因此本文采用链路连通率计算无线链路的边连通概率.设置背景流量模拟网络中的数据传输情况,通过流量发生器的源/目的节点设置使数据流覆盖所有链路.仿真时间共100 s,以1 s为时间间隔测量无线链路的连通率,并取仿真时间内测量所得的链路连通率的平均值作为该无线链路的边连通概率,计算结果见表 4.设置参数α=0.4,β=0.4,γ=0.2,计算节点的度中心性、介数中心性、融合中心性和节点重要度,见表 5.
表 4
![点击查看表格内容](http://hit.alljournals.cn/html/hitxb_cn/2017/10/images/table-icon.gif)
边连通概率 0.445 0.543 0.135 0.043 0.302 0.502 0.422
表 4 边连通概率 Table 4 Edge connection probability
表 5
![点击查看表格内容](http://hit.alljournals.cn/html/hitxb_cn/2017/10/images/table-icon.gif)
度中心性 0.071 0.286 0.286 0.286 0.214 0.071 0.071 0.286 0.321 0.571 0.321 0.214 0.143 0.143 0.071
介数中心性 0 0.022 0.024 0.047 0.034 0 0 0.020 0.044 0.053 0.074 0.002 0.010 0 0
融合中心性 0 0.428 0.375 0.428 0 0 0 0.492 0.491 0.491 0.491 0.667 0.500 1.000 0
节点重要度 0.028 0.209 0.199 0.219 0.099 0.028 0.028 0.221 0.244 0.348 0.256 0.220 0.161 0.257 0.028
表 5 中心性指标及节点重要度 Table 5 Centrality indexes and node importance
由表 5可以看出,B2~B4等3个融合节点的度中心性和介数中心性相对其他非融合节点较高,反映了在动态融合网络环境中融合节点在拓扑结构上的重要性,而对于W1、W6、W7、M4等处于网络边缘的节点,其度中心性和介数中心性均较低.3个融合节点的融合中心性为0.491,而M1~M3等3个非融合节点的融合中心性较高,反映出它们对网络融合的辅助作用程度较大.综合3个中心性指标计算得出,3个融合节点的重要度较高,M3节点由于其融合中心性高而使其重要度也较高,W1、W6、W7、M4等节点由于各中心性指标均较低而使其重要度较低,其他节点的重要度处于中间的位置.通过上述分析,利用本文方法基本能够合理地反映不同节点在动态融合网络中的重要程度,进一步验证了在仿真网络环境中本文方法的有效性.
4 结论1) 针对有/无线多网融合的层级网络,本文综合考虑网络拓扑结构、动态融合特性等因素,提出了动态融合复杂网络模型及其节点重要度评估方法.以改进的动态交织风筝网络和NS2搭建的仿真实验网络为例进行仿真分析,结果表明,该方法能够比较全面地反映动态融合复杂网络中节点的重要度.
2) 本文定义的动态网络仅限于边的连通性变化,未考虑节点数量的增减[19],下一步可采用大规模有/无线融合通信网等真实网络进行验证.
3) 文中节点重要度的计算采用各中心性指标线性加权得出,参数设置比较简单,未来可考虑采用多属性决策[20]等方法作进一步研究.
参考文献
[1]WATTS D J, STROGATZ S H. Collective dynamics of small-world networks[J].Nature, 1998, 393(6684): 440-442.DOI: 10.1038/30918
[2]BARABASI A L, ALBERT R. Emergence of scaling in random networks[J].Science, 1999, 286(5439): 509-512.DOI: 10.1126/science.286.5439.509
[3]纽曼. 网络科学引论[M]. 郭世泽, 陈哲, 译. 北京: 电子工业出版社, 2014: 106.
NEWMAN M E J. Networks: an introduction[M]. Guo S Z, Chen Z. Beijing: Publishng House of Electronics Industry, 2014: 106.
[4]周涛, 张子柯, 陈关荣, 等. 复杂网络研究的机遇与挑战[J].电子科技大学学报, 2014, 43(1): 1-5.
ZHOU Tao, ZHANG Zike, CHEN Guanrong, et al. The opportunities and challenges of complex networks research[J].Journal of University of Electronic Science and Technology of China, 2014, 43(1): 1-5.DOI: 10.3969/j.issn.1001-0548.2014.01.001
[5]刘建国, 任卓明, 郭强, 等. 复杂网络中节点重要性排序的研究进展[J].物理学报, 2013, 62(17): 178901.
LIU Jianguo, REN Zhuoming, GUO Qiang, et al. Node importance ranking of complex networks[J].Acta Physica Sinica, 2013, 62(17): 178901.DOI: 10.7498/aps.62.178901
[6]KOURTELLIS N, ALAHAKOON T, SIMHA R, et al. Identifying high betweenness centrality nodes in large social networks[J].Social Network Analysis and Mining, 2013, 3(4): 899-914.DOI: 10.1007/s13278-012-0076-6
[7]SOLá L, ROMANCE M, CRIADO R, et al. Eigenvector centrality of nodes in multiplex networks[J].Chaos, 2013, 23(3): 033131.DOI: 10.1063/1.4818544
[8]SAITO K, KIMURA M, OHARA K, et al. Efficient discovery of influential nodes for SIS models in social networks[J].Knowledge and Information Systems, 2012, 30(3): 613-635.DOI: 10.1007/s10115-011-0396-2
[9]ZHOU Jingyu, ZHANG Yunlong, CHENG Jia. Preference-based mining of top-K influential nodes in social network[J].Future Generation Computer Systems, 2014, 31: 40-47.DOI: 10.1016/j.future.2012.06.011
[10]张欣. 多层复杂网络理论研究进展:概念、理论和数据[J].复杂系统与复杂性科学, 2015, 12(2): 103-107.
ZHANG Xin. Multilayer networks science: concepts, theories and data[J].Complex Systems and Complexity Science, 2015, 12(2): 103-107.DOI: 10.13306/j.1672-3813.2015.02.016
[11]BULDYREV S V, PARSHANI R, PAUL G, et al. Catastrophic cascade of failures in interdependent networks[J].Nature, 2010(464): 1025-1028.DOI: 10.1038/nature08932
[12]陈宏斌, 樊瑛, 方锦清, 等. 二元随机网[J].物理学报, 2009, 58(3): 1383-1390.
CHEN Hongbin, FAN Ying, FANG Jinqing, et al. Bielemental random networks[J].Acta Physica Sinica, 2009, 58(3): 1383-1390.DOI: 10.7498/aps.58.1383
[13]邵峰晶, 孙仁诚, 李淑静, 等. 多子网复合复杂网络及其运算研究[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.
[14]郭进利, 祝昕昀. 超网络中标度律的涌现[J].物理学报, 2014, 63(9): 090207.
GUO Jinli, ZHU Xinyun. Emergence of scaling in hypernetworks[J].Acta Physica Sinica, 2014, 63(9): 090207.DOI: 10.7498/aps.63.090207
[15]沈迪, 李建华, 张强, 等. 交织型层级复杂网[J].物理学报, 2014, 63(19): 190201.
SHEN Di, LI Jianhua, ZHANG Qiang, et al. Interlacing layered complex networks[J].Acta Physica Sinica, 2014, 63(19): 190201.DOI: 10.7498/aps.63.190201
[16]HOLME P, SARAMAKI J. Temporal networks[J].Physics Reports, 2012, 519(3): 97-125.DOI: 10.1016/j.physrep.2012.03.001
[17]BASARAS P, KATSAROS D, TASSIULAS L. Detecting influential spreaders in complex, dynamic networks[J].Computer, 2013, 46(4): 24-29.DOI: 10.1109/MC.2013.75
[18] MASAKI O. A method for extracting influential nodes while considering the development of social networks[C]// Proceedings of the 2012 Second International Conference on Cloud and Green Computing. Xiangtan, China: IEEE, 2012: 456-459. DOI: 10.1109/CGC.2012.77.
[19] ZHOU Jian, PAN Jiaxin, ZHOU Yanran. Node importance evaluation based on network heterogeneity[C]// Proceedings of the 2010 International Conference on Communications and Mobile Computing. Shenzhen, China: IEEE, 2010:188-194. DOI: 10.1109/CMC.2010.112.
[20]于会, 刘尊, 李勇军. 基于多属性决策的复杂网络节点重要性综合评价方法[J].物理学报, 2013, 62(2): 020204.
YU Hui, LIU Zun, LI Yongjun. Key nodes in complex networks identified by multi-attribute decision-making method[J].Acta Physica Sinica, 2013, 62(2): 020204.DOI: 10.7498/aps.62.020204