一种定量评估复杂网络节点重要度的算法

浅议几种复杂网络节点重要度分析的中心性方法作者：张廷萍来源：《价值工程》2016年第14期摘要：网络节点重要度分析是研究和分析复杂网络的一种非常重要的方法。

识别有影响力的节点比较常用的是利用中心性方法解决这个问题。

本文介绍了几种常见的进行网络节点重要度分析的中心性方法，并通过实例对几种中心性方法进行了分析比较。

Abstract： To study and analyze complex networks， identifying influential nodes is a very important methodology. Many centrality measures have been proposed to address this issue. In this paper， centrality measures to identify influential nodes in complex networks are described. Numerical examples show the analysis and comparison of several methods to identify influential nodes.关键词：复杂网络；重要节点；中心性方法Key words： complex networks；identify influential nodes；centrality measures中图分类号：TN711 文献标识码：A 文章编号：1006-4311（2016）14-0209-020 引言当前，从疾病传播网络到全球医疗诊断网络，从电力网到交通网络，从交际网络到社会关系网络，复杂网络已经渗透到人类社会生活，给我们带来了极大的便利，但是，同时也产生了诸如交通瘫痪、谣言快速传播等不容忽视的负面冲击。

因此，对复杂网络进行深入的研究和分析以方便对其负面影响进行预测、避免和控制是刻不容缓的。

复杂网络中的节点中心性度量与分析在复杂网络中，节点的中心性度量和分析是一项关键任务，它可以帮助我们理解网络的结构、功能和影响力分布。

中心性度量通常用来衡量节点在网络中的重要性和影响力，以及它们在信息传播、交流和决策中的作用。

一种常用的中心性度量是度中心性，它是指节点与其他节点之间的连接数量。

在无向网络中，节点的度中心性仅仅是连接到该节点的边的数量。

而在有向网络中，节点的度中心性包括连接到该节点和从该节点出发的边的数量。

具有高度中心性的节点通常是网络中连接较多的节点，因此它们在信息流动和传播中扮演重要角色。

另一种中心性度量是接近中心性。

接近中心性衡量了节点与其他节点之间的距离，即节点到其他节点的平均最短路径长度。

节点的接近中心性越高，表示它在网络中更容易跟其他节点保持紧密联系。

接近中心性常被用于测量节点在信息传递和扩散中的速度和效率，以及节点在网络中的凝聚性。

具有高接近中心性的节点通常是在信息传播中起关键作用的中转站。

介数中心性是另一种常见的中心性度量。

它衡量了网络中节点在所有最短路径中出现的频率。

节点的介数中心性越高，说明它在网络中扮演着重要的桥梁或者关键节点的角色。

具有高介数中心性的节点在信息传递和交流中具有重要作用，它们有助于信息在网络中的快速传播。

除了以上几种常用的中心性度量，还有一些其他衡量节点重要性和影响力的指标，例如特征向量中心性、总度中心性和PageRank等。

特征向量中心性基于节点的连接和连接的重要程度，它可以衡量节点的影响力。

总度中心性将节点的度中心性与节点的邻居的中心性加权求和，可以更全面地衡量节点的重要性。

PageRank是一种基于随机游走理论的中心性度量，它通过考虑节点之间的连接结构和连接强度来评估节点的影响力。

中心性分析对于理解复杂网络的结构和功能至关重要。

它可以揭示出网络中的关键节点和影响力分布，有助于我们预测和模拟网络的行为和性质。

通过对节点中心性的测量和分析，我们可以识别出网络中最重要的节点，从而优化网络设计、提高信息传播的效率以及更好地管理和控制网络。

复杂网络中关键节点的识别方法研究引言：随着互联网的快速发展，复杂网络已成为重要的研究领域。

在复杂网络中，节点的重要性不同，有些节点对网络的稳定性和功能起着至关重要的作用，我们称这些节点为关键节点。

识别并理解复杂网络中的关键节点对于网络管理、灾难应对和信息传输优化等方面具有重要意义。

本文将研究复杂网络中关键节点的识别方法，包括基于网络拓扑性质、结构层次和动态演化的方法。

一、基于网络拓扑性质的关键节点识别方法1.1 度中心性度中心性是一种常用的关键节点识别方法，它基于节点的度来衡量节点在网络中的重要性。

具有较高度的节点往往是关键节点，因为它们在网络中具有更多的联系和控制能力。

然而，度中心性只考虑了节点的连接数，忽略了节点的位置和影响力，因此准确性受到一定限制。

1.2 中介中心性中介中心性是另一种依据节点在网络中作为中间人的作用来衡量节点的重要性的方法。

在复杂网络中，拥有较高中介中心性的节点往往在信息传递和通信方面起着至关重要的作用。

通过计算节点在最短路径中的出现次数，可以识别中介节点，进而找到关键节点。

然而，该方法也存在计算复杂度较高的问题，并且无法准确衡量节点的重要性。

1.3 特征向量中心性特征向量中心性是一种综合考虑节点的邻居节点的信息来计算节点重要性的方法。

它利用矩阵运算的方法，将节点的邻居节点与其本身权衡结合起来，计算节点的特征向量，从中可以得到节点的重要性指标。

特征向量中心性在识别复杂网络中的关键节点方面具有较高的准确性和鲁棒性。

二、基于结构层次的关键节点识别方法2.1 社区结构复杂网络中常常存在分布式的社区结构，即节点之间存在着紧密的连接，而社区之间的连接较少。

识别复杂网络中的关键节点可以通过分析社区的结构。

具有较高连接度的节点常常位于社区之间，因此可以被认为是关键节点。

通过社区的划分和节点的连接度等指标，可以准确识别关键节点。

2.2 共享益中心性共享益中心性是一种新近提出的方法，通过考虑节点在网络上所连接的路线各自的贡献来表示节点的重要性。

复杂网络中节点关键性分析与检测方法研究随着互联网的发展和人们对网络的依赖程度的提高，研究复杂网络的拓扑结构和节点关键性变得越来越重要。

在复杂网络中，节点的关键性反映了其对网络整体结构和功能的重要性。

因此，针对节点关键性的分析与检测方法成为了复杂网络研究的一个热门方向。

节点关键性是指网络中的某个节点对网络功能的影响程度。

在复杂网络中，节点的关键性可以从多个角度进行分析和检测。

以下将从几个常用的方法进行介绍。

1. 度中心性（Degree Centrality）度中心性是最简单直观的节点关键性度量方法之一。

它通过计算节点的度数（即与其相连的边的数量）来评估其在网络中的重要程度。

度中心性认为度数越高的节点越重要，因为具有更多连接的节点在信息传播和网络传输中起到关键的作用。

2. 特征向量中心性（Eigenvector Centrality）特征向量中心性是基于矩阵代数的节点关键性度量方法。

它不仅考虑到节点自身的度数，还考虑到与其相连节点的关键性。

具有更多来自关键节点的连接的节点会具有更高的特征向量中心性。

通过特征向量中心性，我们可以找到在网络中具有较高的影响力的节点。

3. 紧密中心性（Closeness Centrality）紧密中心性是通过计算节点到其他节点的平均最短路径长度来评估节点的关键性。

具有较低平均最短路径长度的节点在信息传播和资源传输中具有更高的效率。

紧密中心性认为节点与其他节点之间距离更短的节点更重要。

4. 介数中心性（Betweenness Centrality）介数中心性是一种基于节点在网络中充当“中介者”的概念的节点关键性度量方法。

它通过计算节点在网络最短路径中的出现次数来评估节点的关键性。

具有较高介数中心性的节点在信息传播、资源传输和网络通信中起到关键作用。

介数中心性可用于识别那些具有重要连接性的节点。

除了上述常用的节点关键性分析方法外，还有许多其他度量方法可以用于检测复杂网络中的节点关键性。

复杂网络聚类系数复杂网络聚类系数是一个衡量复杂网络结构的重要指标。

它是网络聚类理论中一种重要的度量方式，可以被用来衡量网络节点间的内部结构特性，从而了解网络节点之间的关联程度。

一、什么是复杂网络聚类系数复杂网络聚类系数是指在复杂网络中，两个节点之间的比较参数，衡量隔离节点和其它节点的聚类水平，计算机科学家认为这是衡量复杂网络的重要指标。

它揭示了复杂网络的拓扑结构，用来发现网络的局部结构，分析链路性质，以及研究网络内部结构以便做决策。

二、复杂网络聚类系数的计算复杂网络聚类系数通过比较该节点的邻居节点与其它节点的联系，来计算出来。

它能反映出该节点的社交圈子中的紧密度，即节点的局部聚类系统的紧密度。

计算公式如下：C_i=\frac{2e_i}{k_i\left (k_i-1 \right )}其中，C_i 是该节点的聚类系数，e_i 表示该节点的邻居节点所嵌入的边数，k_i表示该节点的度数。

三、复杂网络聚类系数的价值复杂网络聚类系数是非常重要的，能够衡量复杂网络中节点间联系紧密程度的重要指标，可以用于解决社交凝聚、识别社区结构等问题。

它也可以用于分析网络的稳定性，这样研究者可以更了解网络中节点间的关系和节点之间的影响。

同时，复杂网络聚类系数还可以用于节点识别，即研究具有聚类特性的节点，以及它们与网络结构的关系。

四、复杂网络聚类系数的研究聚类系数是一个度量方式，在复杂网络研究中一直是很重要的。

通过与其他网络指标相结合，有助于了解网络中发生的事件，从而推断信息传播的速度和发展趋势。

在实践中，复杂网络聚类系数也可以帮助分析未知网络的社会层级结构以及节点之间分布的关系。

此外，复杂网络聚类系数还可以帮助研究人员识别和预测网络中重要节点的功能特性，构建网络社会结构模型，以及研究复杂网络的自同步特性等。

基于熵的节点重要度评估方法作者：潘想想姚红光来源：《计算机时代》2023年第12期摘要：针对网络中关键节点识别问题，提出一种基于熵的有向加权网络节点重要度评估方法，即EnRank算法。

通过定义有向加权网络中各个节点吸引率AR和传输率TR，运用熵法对节点的度、吸引率和传输率进行综合运算，从而得出有关于节点重要性综合评价指标。

该算法既考虑了节点本身的重要性，也考虑了相邻节点对其相对重要性。

经过对ARPA网络及社交网络连锁故障仿真实验，验证了该方法的可靠性。

关键词：节点重要性；熵法；有向加权网络； EnRank算法中图分类号：O157.5 文献标识码：A 文章编号：1006-8228（2023）12-01-04Entropy based node importance evaluation methodPan Xiangxiang， Yao Hongguang（School of Air Transport， Shanghai University of Engineering Science， Shanghai 201600，China）Abstract： Aiming at the problem of identifying key nodes in a network， an entropy based network node importance evaluation method， namely EnRank algorithm， is proposed. By defining the attraction rate AR and the transmission rate TR of each node in the directed weighted network，the degree， attraction rate and transmission rate of the node are comprehensively calculated by entropy method， and the comprehensive evaluation index of node importance is obtained. The algorithm considers both the importance of nodes themselves and the relative importance of neighboring nodes. The reliability of the method is verified by simulation experiments on ARPA network and social network.Key words： node importance; entropy method; directed weighted network; EnRank algorithm0 引言近年來，复杂网络的理论研究吸引了来自复杂性科学、信息科学、经济学、社会学、生物信息学等相关领域的大量研究者。

复杂网络中的节点与边的重要性评估研究随着社交网络、交通网络、信息网络等复杂网络的快速发展，人们对于网络中节点和边的重要性评估的研究变得越来越重要。

在复杂网络中，信息传播、疾病传播、网络崩溃等现象的发生和传播往往与节点和边的属性息息相关。

因此，准确评估节点和边的重要性对于网络科学和实际应用具有重要意义。

在复杂网络中，节点的重要性评估一般通过度中心性（degree centrality）来衡量。

度中心性反映了节点在网络中的连接程度，即节点与其他节点之间的连边数量。

度中心性高的节点往往具有更多的连接，因此在信息传播和网络崩溃中所起的作用更为重要。

而边的重要性评估则可以通过介数中心性（betweenness centrality）来衡量。

介数中心性反映了边在网络中作为信息传播的桥梁的重要程度。

具有高介数中心性的边在信息传播和疾病传播中扮演着关键角色，而如果这些边被移除，网络的连通性往往会显著降低。

除了度中心性和介数中心性之外，还有其他方法可以评估节点和边的重要性。

例如，特征向量中心性（eigenvector centrality）可以通过考虑节点与其邻居节点之间的关系来评估节点的重要性。

如果某个节点与其他重要节点有较强的连接，那么它的特征向量中心性将更高。

此外，在网络中还存在一些其他的中心性指标，如接近中心性（closeness centrality）、网络影响力（network influence）等，用于评估节点和边的重要性。

然而，复杂网络中的节点和边的重要性评估也存在一些挑战和问题。

首先，对于大规模网络来说，计算所有节点和边的中心性指标是非常耗时的。

针对这个问题，研究者们提出了一些基于采样的方法，通过计算子图的中心性指标来近似整个网络的评估结果。

其次，在某些网络中，节点和边的重要性可能受到其他因素的影响。

例如，在社交网络中，影响力和重要性经常是相互关联的，一个有影响力的用户不一定是网络中最重要的节点。

复杂网络上节点重要度的确定方法张斌武;邹森;王勤【期刊名称】《兰州理工大学学报》【年(卷),期】2013(39)3【摘要】Node importance in complex networks was evaluated by taking comprehensively the local and global property of nodes into consideration.Two algorithms were given to determine the node importance:one was based on neighborhood and the other was based on key field.The former algorithm could be used to decrease the computational complexity efficiently and the latter efficiently characterize the node importance and suit to weighted graph.Finally,the validity of these two algorithms was verified by giving an example.%采用综合考虑节点的局部特性和全局特性的方法来评价复杂网络的节点重要度,给出基于邻域的节点重要度算法及基于关键域的节点重要度算法.前一种算法有效地降低了计算的复杂度；后一种算法能更有效地刻画节点的重要度且适用于加权图.然后通过实例验证两种算法的有效性.【总页数】3页(P85-87)【作者】张斌武;邹森;王勤【作者单位】河海大学常州校区数理部,江苏常州213022;河海大学常州校区物联网学院,江苏常州213022;中国计量学院理学院,浙江杭州310018【正文语种】中文【中图分类】TP301【相关文献】1.节点重要度贡献的复杂网络节点重要度评估方法 [J], 张喜平;李永树;刘刚;王蕾2.基于介度熵的复杂网络节点重要度识别方法 [J], 卢鹏丽; 郭旭东; 董璊; 曹乐3.基于冗余度的复杂网络抗毁性及节点重要度评估模型 [J], 王梓行;姜大立;漆磊;陈星;赵禹博4.基于复杂网络的城市群铁路网络节点重要度研究 [J], 王晋;王伯礼5.基于VIKOR模型的复杂网络节点重要度评估 [J], 尹梦梦;王磊;姚昌华;武欣嵘因版权原因，仅展示原文概要，查看原文内容请购买。

基于m阶邻居节点的复杂网络关键节点评估王锋;许梁煌;郑玉芳【摘要】基于无向无权复杂网络理论,提出一种基于m阶邻居节点重要度贡献的节点重要度评估方法.在综合考虑了节点自身的属性,节点在网络中的位置以及m阶邻居节点的度重要度贡献和介数重要度贡献后,提出m阶邻居节点重要度贡献系数矩阵概念,建立评估模型.通过实验并和其他算法结果进行对比分析,表明所提出的评估方法具有可行性和更高的精确性.当m的取值接近网络的平均路径长度时,节点的重要度评估趋于稳定,可有效提高评估效率.【期刊名称】《福州大学学报（自然科学版）》【年(卷),期】2019(047)002【总页数】7页(P237-243)【关键词】复杂网络;关键节点;m阶邻居矩阵;贡献矩阵;评估效率【作者】王锋;许梁煌;郑玉芳【作者单位】福州大学土木工程学院,福建福州 350108;福州大学土木工程学院,福建福州 350108;福州大学土木工程学院,福建福州 350108【正文语种】中文【中图分类】U4910 引言随着复杂网络小世界效应[1]及无标度性[2]的发现，复杂网络研究已成为各个学科的研究热点，复杂网络的鲁棒性研究[3-6]是复杂网络研究的一个重要分支. 研究表明：不同拓扑结构的网络在承受不同的打击方式时表现出不同的鲁棒性，无标度网络能够很好地抵抗随机攻击，但在蓄意攻击下却迅速崩溃，少数关键节点一旦被攻击，网络便迅速瘫痪[7]. 蓄意攻击本质上是优先攻击网络中的“关键节点”，因此如何确定网络中的关键节点意义重大. 通过节点重要度评估找出网络中重要的“关键节点”，一方面可重点保护这些“核心节点”来提高整个网络的可靠性，另一方面可攻击这些“薄弱环节”达到摧毁整个网络的目的.目前复杂网络中的关键节点的评估方法主要分为两类：① 节点重要性等于破坏性，该方法通过比较在删除该节点后对网络的破坏程度来定义节点的重要性. 文献[8-9]基于源点到汇点最短路径来评价节点重要度，最重要的节点定义为删除该节点使源点到汇点最短路径距离的增加最大；文献[10]提出一种基于生成树数目的节点删除法，定义最重要的节点为去掉该节点使得生成树数目最小，而该方法存在片面性，如处于网络末梢的一个节点在删除后造成该网络不连通，依据这种方法该节点就会被评估为较为重要，这显然与实际情况不符. ② 节点重要性等价于显著性，从网络中寻找可以凸显节点的属性来“放大”，用单一指标定义节点的重要性. 常见的属性有度、介数、凝聚度等，文献[11]将凝聚度定义为网络平均距离与节点数乘积的倒数，采用节点收缩前后网络凝聚度的变化来定义节点的重要度，一般认为节点越重要，收缩后网络的凝聚度越大；文献[12]在此基础上进行改进，引入节点连边重要度的概念，将节点重要度定义为节点重要度和节点连边重要度的加权和.上述网络研究只考虑了节点自身的属性，并没有考虑与节点相邻的节点和连边的影响，也忽略了节点在网络中的位置对重要度的影响，而实际上节点的重要度和邻居节点有必然的联系，单纯地从节点的某一属性考虑，而不考虑相邻节点的影响，显得不够全面，从而影响评估的精度. 为弥补删除法和节点收缩法的不足，文献[13-14]引入重要度评价矩阵的概念，综合考虑节点的度值，节点在网络中信息传输的作用以及邻居节点对目标节点的重要度贡献. 但这里所考虑的邻居节点也仅仅是与目标节点直接相连的节点. 而现实存在的复杂网络中，节点的重要度不仅与其直接相连的邻居节点有关，非直接相连的节点也对目标节点的重要度有较大的影响. 本文引入m阶邻居节点的概念，考虑目标节点的m阶邻居节点对其重要度的贡献值，以便使评估结果更具有可信度.1 理论基础1.1 基本概念图1 复杂网络示意图Fig.1 Complex network diagram设图G(V, E)是一个无自环的无向网络，其中V ={v1, v2, v3, …, vn}是网络中所有节点的集合； E={E1, E2， E3，…， En}是网络节点间边的集合，如图1所示. 定义1 点的度是指节点i所拥有的边的数量[15]，是刻画和衡量网络中节点特性最重要的指标. 一个节点的度越大说明该节点在网络中与其它节点的连接更加紧密. 其公式为：(1)式中： K表示节点的度值； n为网络中的节点数； e为节点i和j之间所连接的边数.定义2 节点介数是指整个复杂网络中经过该节点最短路径的数量比例，是网络中节点和边在整个网络中的作用和影响力的体现，是复杂网络的另一个重要指标. 其计算公式为：(2)式中： dinj为节点i和节点j之间的最短路径中经过节点n的数量； dij表示节点i和节点j之间的最短路径.定义3 节点效率值的大小反映节点到网络中其他节点的难易程度，体现节点对网络信息传输所做的贡献. 节点的效率值越大，在网络信息传输过程中所处的位置越重要. 节点i的网络效率值Ei为：(3)式中： n为网络中节点的数量； dki为节点k到节点i之间的距离.1.2 m阶邻居节点的定义图2 节点1各邻居节点示意图Fig.2 Neighbor nodes diagram belong to node 1对于复杂网络G={V， E}中任意节点i(i∈V)，其一阶邻居节点为与节点i的最短距离为一步的节点，该类节点构成的集合称作节点i的一阶邻居节点集，记为&(1)(i)；同理，其二阶邻居节点为与节点i的最短距离为两步的节点，该类节点构成的集合称作节点i的二阶邻居节点集，记为&(2)(i)；如此类推，则与节点i 之间的最短距离为m的节点称为m阶邻居节点，其构成的集合称作节点i的m 阶邻居节点，记为&(m)(i). 节点1的一阶至三阶邻居节点如图2所示，其中节点2、 3、 6、 10为一阶邻居节点； 4、 5、 7、 8、 11为二阶邻居节点； 9为三阶邻居节点.1.3 构建m阶节点重要度评价矩阵在构建m阶节点重要度评价矩阵时，综合考虑邻居节点的重要度贡献以及节点在网络中的位置. 假设节点重要度评估过程中邻居节点的重要度贡献随距离的增加呈指数衰减趋势[16]，首先构建m阶邻居矩阵的重要度贡献系数矩阵. 网络的邻接矩阵反映了节点之间相邻的情况，存在一定的映射关系并方便实现计算机编程计算，若网络中有n个节点，则构成n×n的邻接矩阵，其具体的映射关系为:(4)对该映射关系做如下调整:(5)式(5)构成一个n×n的矩阵，其中γ为可调参数，且定义0<γ<1，用于调整1到m阶邻居节点的依赖程度，该映射关系综合考虑节点自身及1到m阶邻居节点的重要度贡献. 为便于理解，可以将评估的m阶邻居节点称作节点重要度评估深度，且其值应满足0≤m≤D， D值为网络的最大直径，最后得到的矩阵如下式.(6)式(6)为n×n阶方阵，矩阵中的所有元素均为1与γ的指数幂构成，0≤x≤D，该矩阵根据m值大小而变化，当x=m时，矩阵中x>m的位置均以0代替，即得到m阶邻居矩阵重要度贡献系数矩阵Am.为全面考虑其他阶数的邻居节点的重要度贡献，基于文献[1]做以下改进： 1)节点vi为所有m阶邻居节点贡献ki/K2的重要度； 2)该重要度的贡献值根据不同的邻居阶数乘以相同的系数. 所有节点对其m阶邻居的度重要度贡献值用矩阵的形式表现出来，如下式.(7)式(7)中的对角线表示节点对自身的重要度贡献值为1，其与邻接矩阵的映射关系规则如下式.(8)该映射规则反映了网络重要度贡献关系的拓扑，并充分利用邻接矩阵的信息.为反映节点在网络中的位置重要性，采用网络效率来衡量节点在网络中的位置关系. 对上述度重要度贡献比例矩阵(7)进行改进，将矩阵中所有对角线的元素用相对应的节点效率值进行替换，得到改进后的重要度贡献矩阵，如下式.(9)类似地构建m阶邻居节点的介数重要度贡献矩阵如下式.(10)其中Ji表示节点i的介数值，其映射关系为:δij=Ji (i=j); δij=Jj (i≠j)(11)考虑节点m阶邻居矩阵的度以及介数重要度贡献矩阵，节点的最终重要度矩阵Cn×n定义如下：(12)式中：Cn×n表示n个节点构成的的重要度矩阵； A为重要度系数贡献矩阵；和T2为两个重要度贡献矩阵；ω1和ω2为比例系数，用于调整度以及介数所占的比例；Cn×n为n阶方阵，其中节点i的重要度为方阵中的对角线元素，即Ii=Cii (i∈[1， n])(13)2 节点重要度的确定算法综合考虑节点自身的属性、节点在网络中的位置、 m阶邻居节点度重要度贡献和介数重要度贡献后建立评价模型，其算法如下.1) 根据网络中各个节点的邻接关系，由本文提出的映射规则确定整个网络m阶邻居矩阵重要度贡献系数矩阵；2) 确定网络的重要度贡献比例矩阵T1；3) 确定网络的度重要度贡献矩阵4) 确定网络的介数重要度贡献矩阵T2；5) 根据重要度定义公式计算各个节点的重要度.根据本文所提出的模型方法，可看出整个重要度确定的关键在于m阶邻居矩阵中m的取值，若取值太小，评估过程将依赖于节点自身的特性，从而忽略网络中某些节点对目标节点的重要度贡献，即忽略节点在网络中的位置信息，评估结果将近似于传统连接度和连接介数方法；反之，若m取值太大，一方面增大了算法的复杂性，另一方面m值的不断增大对评估是否有影响及影响程度，将是实验讨论的重点.3 实验分析3.1 本文与其它算法的评价结果对比图3 实验分析复杂网络示意图Fig.3 Experimental analysis of complex network schematicsARPA拓扑网络是目前研究复杂网络普遍使用的拓扑干线网络，其网络的平均度值为2～3之间，其中大部分节点的度值为2，如图3所示. 本文研究时所选的分析网络与ARPA拓扑网络基本相似. 该图存在24个节点， 28条边，网络的平均度为2.42，平均路径长度为4.75，直径为9. 如果单纯采用度值对其进行分析，显然不尽合理，网络中存在15个节点的度值为2，但是这15个节点的重要度显然并非全部相同，如节点6和节点16.文献[1]提出考虑节点的介数法来对节点重要度进行评估，但无法细分介数值相同的节点；如果采用节点删除法对网络进行分析，由于网络拓扑结构的特殊性，节点1、 13、 14、 16、 17、 18在删除之后对网络重要性影响都是相同的，因此无法区分其重要度；文献[11]采用节点收缩法对网络进行分析，考虑的是收缩前后网络凝聚度的变化情况，网络凝聚度又与网络的节点完全相同，因此也无法区分其重要度. 综上分析，上述算法均存在其缺陷，无法对某些网络的节点重要度进行精确区分，并且对一些特殊节点也发挥不了作用. 现应用本文所提出的算法对该网络进行分析并与其它算法进行对比，其分析结果如表1所示(取ω1，ω2，γ=0.5).表1 节点重要度评估结果Tab.1 Node importance evaluation result节点本文算法m=0m=1m=2m=3m=4m=5度值法介数法文献[11]文献[13]v10.25490.41310.50280.55740.57380.587920.2120.18580.1500v20.2005 0.42400.56620.62420.64820.656520.0810.16750.2396v30.30840.53170.605 70.63680.65620.667830.2710.23020.2555v40.26760.44000.52720.54680.56 010.569830.2120.22850.2069v50.19440.39430.45700.50300.52650.538520. 0840.17160.2136v60.19440.38510.49840.53140.55480.566920.0840.17160. 1959v70.28420.40860.52180.57360.58760.599430.2300.22850.2466v80.242 50.24880.57860.62620.64770.652630.1390.21470.3035v90.17540.33610.44 250.47450.48430.489120.0400.15430.2059v100.19500.40730.51140.53940. 55120.562020.0730.16580.2353v110.28140.45330.57800.62160.62360.6265 40.1940.25240.3459v120.24630.50630.63930.66460.67460.686330.1520.21 470.2983v130.26160.44090.48040.51740.54530.479820.2160.19040.1789v1 40.29340.40550.52620.56770.59650.602820.2670.19040.2151v150.27480.3 6880.44300.47630.48600.496830.2130.22850.2449v160.25600.35040.43660 .48080.48080.495220.2110.19040.1708v170.25350.41030.45750.50620.533 80.543120.2110.19040.1717v180.29650.39050.47380.53260.55110.564920.2670.21500.1989v190.21040.36600.44020.27700.51090.522820.1100.13710 .1844v200.21120.26520.36310.42370.44950.463420.1120.16740.1837v210.2 8630.48870.56670.28040.58840.593230.2280.23020.2513v220.20640.36200 .43720.49800.52160.533520.1020.13710.1844v230.21120.37550.47340.299 20.53620.550120.1120.16740.1837v240.30790.51150.61160.66490.68290.6 95730.2740.24030.2274由表1可知，本文算法与其他算法相比，存在以下两点不同： 1) 由于考虑了邻居节点之间的相互影响，使得节点之间的重要度在可以区分的前提趋于接近，相对于其他算法，评估结果更为精细. 2) 用本文算法进行节点重要度识别时， m的阶数取接近于网络的平均直径时(本文网络的平均直径为4.75，因此m取5)，评价结果会趋向稳定.不同的算法所得结论存在较为明显的差异, 如度值法认为重要度靠前的节点是{11，3， 12， 7， 8}；介数法的评估结果则是{24， 3， 14， 18， 7}；本文算法随着m取值的不同，结果略有变动，但重要度排序在前的几个节点主要为{12，24， 3， 8， 7}，这与文献[11]、文献[13]、度值法以及介数法的结果基本符合，即本文算法与其他算法对于较为重要的节点集均为{11， 3， 21， 24， 8}. 度值法的不足在于无法细分度值相同节点的重要度，如节点{11， 17， 10， 14， 18}等，这些节点在网络中的作用和位置不尽相同，但度值法无法对其做更加精确的判别；仅仅根据介数指标得出的结果认为v14的重要度排在第3， v11排在第11，这显然不尽合理， v11处于网络连接的关键通路，起到“桥梁”的作用，其重要性应大于v14.综上，本文算法可以对前述的节点集进行精度更高的细分且能够解决单一评估指标带来的片面性, 说明本算法的可行性. 本文所提出的方法综合考虑了节点在网络中的全局重要性及局部重要性，较好地顾及了节点自身及1到m阶邻居节点对该节点的重要度贡献. 运用本文方法对节点重要度进行评估，可以显著地区分节点之间的重要度差异，具有较高的评估精度. 随着邻居节点阶数m值的增加，从重要度的排序看其结果逐步趋向稳定，为进一步分析m的取值对于评估结果的影响，针对上述例子，构建小世界网络随机进行分析.3.2 m取值对实验结果的影响图4 小世界随机网络示意图Fig.4 Small world random network diagramm∈[0， D]，针对上文的实验分析构造小世界网络，分析节点重要度随m取值的变化情况. 所构造出的小世界随机网络如图4所示，网络参数分别为：节点数为20，邻居节点概率为2，重连概率取0.5，平均路径长度为2.63，平均度值为4，网络的直径为4，平均介数值0.064 6.运用本文所提出的算法在邻居节点阶数m取值不同的情况下对小世界随机网络和上文实验分析所采用的网络节点的重要度进行评估，结果汇总如图5所示.图5 关键节点重要度随m变化图Fig.5 The key node importance changeswith m从实验分析可知，随着邻居阶数m的增加，节点的重要度值呈现先增加后稳定的趋势，即节点的重要度从“不稳定的状态”向“稳定的状态”转化，而阈值为网络的平均路径长度m0. 当m∈{0， m0]时，节点的重要度处于“不稳定状态”；当m∈[m0， D]时，节点的重要度处于稳定状态，即重要度随着m的增加几乎不再增加. 由此得出结论：运用本文算法进行节点重要度评估时，只要m>m0，便可以得出稳定的节点重要度. 因复杂网络的节点和直径可能会很大，这一规律的发现有利于评估效率的提高.4 结语针对复杂网络的节点重要度评估问题，在总结节点删除法、节点收缩法的不足之后，本文综合考虑节点自身的效率值，即节点在网络中的信息传输快慢，节点度值，节点在网络中的位置关系以及m阶邻居节点的度值和介数重要度贡献，建立评估模型. 该模型通过节点的效率值来表征节点的全局重要性，通过m阶邻居节点的重要度贡献来表征节点的局部重要性，并通过实验分析与其他算法进行对比，结果表明本文的算法具有更高的评估精度，验证本文算法的有效性. 此外，为得到邻居阶数m的数值与节点重要度稳定性的关系，借助小世界随机网络进行实验分析，结果表明邻居阶数m趋于网络的平均路径长度时，节点的重要度趋于稳定状态.参考文献：【相关文献】[1] WATTS D J， STROGATZ S H. Collective dynamics of small-world networks[J]. Nature，1998， 393(6684): 440-442.[2] BARABASI A L， ALBERT R. Emergence of scaling in random networks[J]. Science，1999， 286(5439): 509-512.[3] 王甲生，吴晓平，陈永强. 不同信息条件下加权复杂网络抗毁性仿真研究[J]. 中南大学学报(自然科学版)， 2013， 44(5): 1888-1894.[4] 袁铭. 带有层级结构的复杂网络级联失效模型[J]. 物理学报， 2014， 63(22): 77-84.[5] 毛凯. 复杂网络结构的稳定性与鲁棒性研究[J]. 计算机科学， 2015， 42(4): 85-88.[6] 崔文岩，孟相如，康巧燕，等. 基于复合边权重的加权复杂网络级联抗毁性优化[J]. 系统工程与电子技术， 2017， 39(2): 355-361.[7] CALLAWAY D S， NEWMAN M E J， STROGATEZ S H， et al. Network robustness and fragility: percolation on random graphs[J]. Phys Rev Lett， 2000， 85(25): 5468-5471. [8] CORLEY H W， SHA D Y. Most vital links and nodes in weighted networks[J]. Oper Res Lett， 1982， 1(4): 157-160.[9] NARDELLI E， PROIETTI G， WIDMAYER P. Finding the most vital node of a shortest path[J]. Theoretical Computer Science， 2001， 296(1): 167-177.[10] 陈勇，胡爱群，胡骏，等. 通信网中最重要节点的确定方法[J]. 高技术通讯， 2004(1): 573-575.[11] 谭跃进，吴俊，邓宏钟. 复杂网络中节点重要度评估的节点收缩方法[J]. 系统工程理论与实践，2006(11): 79-83； 102.[12] 王甲生，吴晓平，廖巍，等. 改进的加权复杂网络节点重要度评估方法[J]. 计算机工程，2012， 38(10): 74-76.[13] 周漩，张凤鸣，李克武，等. 利用重要度评价矩阵确定复杂网络关键节点[J]. 物理学报，2012， 61(5): 1-7.[14] 赵毅寰，王祖林，郑晶，等. 利用重要性贡献矩阵确定通信网中最重要节点[J]. 北京航空航天大学学报， 2009， 35(9)： 1076-1079[15] 吴建军，高自友. 城市交通复杂性: 复杂网络方法及其应用[M]. 北京: 科学出版社， 2010．[16] 张喜平. 城市复杂交通网络级联动力学与路段重要性评估研究[D]. 重庆：西南交通大学，2014.。

动态融合复杂网络节点重要度评估方法付凯;夏靖波;赵小欢【摘要】为挖掘复杂网络中的关键节点及提高网络鲁棒性,针对有/无线多网融合的层级网络,提出了动态融合复杂网络模型及其节点重要度评估方法.结合动态融合复杂网络的特点,定义了边连通概率、路径连通概率、网络连通概率、融合节点比例、融合节点分布和融合路径比例等与网络动态性和融合性相关的参数.在单层复杂网络节点重要度评估指标的基础上,设计了融合网络节点度中心性、节点介数中心性和节点融合中心性指标.其中,融合节点的节点融合中心性表示融合节点对网络融合的贡献程度,非融合节点的节点融合中心性表示非融合节点对网络融合的辅助作用程度,主要体现在作为融合节点之间的中继节点.最后,综合考虑网络拓扑结构、动态融合特性等因素进行节点重要度评估.以改进的动态交织风筝网络为例进行仿真分析,结果表明该方法能够比较全面地刻画节点在动态融合复杂网络中的重要性.利用NS2搭建由光通信网和卫星通信网融合构成的仿真实验网络,进一步验证了在仿真网络环境中本方法的有效性.%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 indynamic 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.【期刊名称】《哈尔滨工业大学学报》【年(卷),期】2017(049)010【总页数】8页(P112-119)【关键词】复杂网络;动态融合;节点重要度;度中心性;介数中心性;融合中心性【作者】付凯;夏靖波;赵小欢【作者单位】空军工程大学信息与导航学院,西安710077;95246部队,南宁530003;厦门大学嘉庚学院,福建漳州363105;95340部队,广西百色533616【正文语种】中文【中图分类】TP393复杂网络小世界效应[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 理论基础设图Ga=Va,Ea是一个无环无向无权的单层复杂网络，Va={v1,v2,…,vn}表示网络a的节点集合，节点数量为Va=n，Ea={e1,e2,…,em}=Va×Va为网络a的边集合，边的数量为Ea=m.A=Aijn×n为网络a的邻接矩阵，取值为0或1，表示节点之间是否存在连接边.在图Ga中任意两个节点之间最长的路径称为图Ga的直径，记为Dnd.在单层复杂网络中，节点vi的度中心性定义为式中:gi为节点vi的度，n为网络的节点数.节点vi的介数中心性定义为式中:Nsp(s,t)为节点vs和vt之间的最短路径数量，Nsp(s,i,t)为节点vs和vt之间经过节点vi的最短路径数量.1.2 模型概述定义1 动态融合复杂网络.由两种以上单层复杂网络融合而成，且其中至少有一种为动态网络的层级网络称为动态融合复杂网络.动态融合复杂网络中的“动态”是指网络中的边以一定概率进行连通(主要指无线传输手段等间歇连接)，而节点数量保持不变.网络动态性对介数等与路径相关的参数影响较大，而对度等基于网络局部属性的参数影响较小.动态融合复杂网络中的“融合”是指多个网络之间存在部分节点复用，节点之间可能存在两种以上属性的边.为方便研究，本文仅考虑由两种单层复杂网络组成的动态融合复杂网络，且其中一种为动态网络.动态融合复杂网络c(以下简称“融合网络”)由单层复杂网络a和b融合构成，Vc={v1,v2,…,vN}=Va∪Vb为融合网络的节点集，节点数量为表示融合网络的融合节点集，融合节点数量为M.Ec=Ea∪Eb为融合网络的边集，边的数量为Ec，由于边不存在复用，所以融合网络的边集即为各单层复杂网络的边集之和.C=A∪B=CijN×N为网络c的邻接矩阵，取值为0或1，表示融合网络的节点之间是否存在连接边，规定节点之间无连接边时取值为0，节点之间有1条或2条边时取值均为1.1.3 参数定义动态融合复杂网络最重要的特性是动态和融合，因此本文主要从动态和融合两方面设计网络参数.其中，网络连通参数主要包括边连通概率、路径连通概率和网络连通概率，用以描述网络的连通状况；网络融合参数主要包括融合节点比例、融合节点分布和融合路径比例，用以描述网络的融合程度.1.3.1 边连通概率在动态网络中，如果节点vi和vj之间存在连接边，则Pij表示该边的连通概率，并假定非动态网络中边的连通概率为1.令P=PijN×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 网络连通概率网络连通概率定义为反映整个网络的平均连通状况.1.3.4 融合节点比例融合节点比例定义为表示网络节点集中融合节点所占的比例，从融合节点数量的角度反映网络融合程度，融合节点越多则越能促进网络的融合.1.3.5 融合节点分布融合节点比例在一定程度上反映了网络的融合程度，但还存在片面性.如果融合节点比较密集地分布在局部区域，那么与融合节点分散分布的情形相比，其对促进整个网络融合的作用会减弱.因此，定义融合节点分布为表示网络中融合节点的紧密程度，从融合节点位置的角度反映网络融合程度，融合节点在网络中的位置越分散则越能促进网络的融合.其中，Davg为融合节点之间的平均距离，Dnd为融合网络的直径.1.3.6 融合路径比例融合路径比例定义为表示最短路径中融合路径所占的比例，从消息传播的角度反映网络融合程度，融合路径越多则越能促进网络的融合.其中，Nsp为网络中所有节点对之间的最短路径的数量，Ncp为这些最短路径中融合路径的数量.融合路径是指包含两种边的路径，仅包含融合节点但只有一种边的路径不是融合路径.如图1所示，对于路径1-2-3-4，图1(a)、(b)为融合路径，而图1(c)不是融合路径.动态融合复杂网络的节点重要度评估主要是在网络拓扑结构的基础上，考虑动态及融合特性的影响.度中心性和介数中心性是节点重要度评估中最常用的指标，分别基于网络局部属性和全局属性反映单层复杂网络中节点的重要性.但对于动态融合复杂网络，其拓扑结构由于网络融合而具有新的变化，因此本文结合其特性进行重新定义.此外，提出节点融合中心性指标，从节点促进网络融合的角度反映其重要性.定义2 融合网络节点度中心性.融合网络中节点vi的度中心性定义为式中，Na为节点vi的邻居节点中属于单层复杂网络a的节点数量，Nb同理.从理论分析的角度，对于非融合节点，有Na=0或Nb=0，因此Di=di，即非融合节点的度中心性与经典度中心性的计算结果相同；对于融合节点，有Na≠0且Nb≠0，则0<<1，Di>di，即通过式(2)使其度中心性等到加强.并且考虑其邻居节点的性质，与节点vi相邻的不同单层网络节点的数量越均匀(即Na-Nb的值越小)，vi对网络融合的贡献越大，因此其度中心性越得到加强(即Di的值越大).定义3 融合网络节点介数中心性.融合网络中节点vi的介数中心性定义为式中，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，则从而Bi≤bi，即通过式(3)反映了网络动态特性对节点介数中心性的减弱作用.因此，融合网络节点介数中心性既突出了融合性的影响，又考虑了动态性的影响.定义4 融合网络节点融合中心性.融合网络中节点vi的融合中心性定义为对于融合节点，其融合中心性表示融合节点对网络融合的贡献程度.一旦网络拓扑参数确定，所有融合节点的融合中心性是一个与其位置特性无关的固定值，从宏观上反映网络中所有融合节点对网络融合的贡献程度.融合节点比例越低，融合路径比例越低，融合节点分布越密集，则网络的融合程度越低.而在网络融合程度低的情形下，融合节点发挥的作用就越大，从而融合节点对网络融合的贡献程度就越高.另外，加入参数Rncp考虑网络动态性对融合路径的影响，使指标的计算更加客观. 对于非融合节点，其融合中心性表示非融合节点对网络融合的辅助作用程度，主要体现在作为融合节点之间的中继节点.其中，Nacn为节点vi的邻居融合节点数量，ci为节点vi的融合聚类系数，反映其邻居融合节点之间的连通程度，定义为式中，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的作用上减弱了，其融合中心性也要降低.定义5 融合网络节点重要度.根据定义2～定义4，综合考虑局部位置信息、全局位置信息、网络融合特性3个方面，定义融合网络的节点重要度为式中，α、β、γ∈(0,1)，且α+β+γ=1，通过3个参数的设置可以调节各中心性在最终节点重要度评估中的权重.一般来说，网络拓扑结构对节点重要度的影响是主要的，因此参数α和β应设置较大一些.融合中心性是在动态融合网络模型中对节点重要度评估的一个改进和补充，因此参数γ应设置小一些.3.1 典型算例为验证本文节点重要度评估方法的有效性，以文献[15]中的交织风筝网络为基础网络，并加入连边的动态特性以构成动态融合复杂网络(如图3所示).其中，单层网络a包含10个节点、18条边；单层网络b为动态网络，包含8个节点、13条边，边上的数值代表边的连通概率；融合网络c为网络a和b融合构成的网络，包含13个节点、31条边，其中5个融合节点分别由网络a和b中具有相同编号的节点融合形成.实验中设置参数α=0.4，β=0.4，γ=0.2，通过MATLAB 2010a进行仿真实验，分别计算单层网络a和b中各节点的度中心性和介数中心性，以及网络融合后各节点在融合网络中的中心性指标，仿真结果见表1～3.由表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之后.3.2 仿真网络为进一步验证本文方法的适用性，利用NS2搭建仿真网络，仿真场景及其对应的网络拓扑如图5、6所示.该仿真网络由光通信网和卫星通信网融合构成，是典型的有线与无线混合组网的情景.网络中共有15个节点，其中有线节点7个(W1～W7)，无线节点5个(M1～M4，B1)，融合节点3个(B2～B4).网络中共18条链路，其中有线链路11条，无线链路7条.另外，仿真网络中仅反映无线节点之间的连通关系(即两个无线节点之间是否存在无线链路)，而不考虑其运动情况.链路连通率反映了链路两端点之间成功发送或接收数据的情况，因此本文采用链路连通率计算无线链路的边连通概率.设置背景流量模拟网络中的数据传输情况，通过流量发生器的源/目的节点设置使数据流覆盖所有链路.仿真时间共100 s，以1s为时间间隔测量无线链路的连通率，并取仿真时间内测量所得的链路连通率的平均值作为该无线链路的边连通概率，计算结果见表4.设置参数α=0.4，β=0.4，γ=0.2，计算节点的度中心性、介数中心性、融合中心性和节点重要度，见表5.由表5可以看出，B2～B4等3个融合节点的度中心性和介数中心性相对其他非融合节点较高，反映了在动态融合网络环境中融合节点在拓扑结构上的重要性，而对于W1、W6、W7、M4等处于网络边缘的节点，其度中心性和介数中心性均较低.3个融合节点的融合中心性为0.491，而M1～M3等3个非融合节点的融合中心性较高，反映出它们对网络融合的辅助作用程度较大.综合3个中心性指标计算得出，3个融合节点的重要度较高，M3节点由于其融合中心性高而使其重要度也较高，W1、W6、W7、M4等节点由于各中心性指标均较低而使其重要度较低，其他节点的重要度处于中间的位置.通过上述分析，利用本文方法基本能够合理地反映不同节点在动态融合网络中的重要程度，进一步验证了在仿真网络环境中本文方法的有效性.1)针对有/无线多网融合的层级网络，本文综合考虑网络拓扑结构、动态融合特性等因素，提出了动态融合复杂网络模型及其节点重要度评估方法.以改进的动态交织风筝网络和NS2搭建的仿真实验网络为例进行仿真分析，结果表明，该方法能够比较全面地反映动态融合复杂网络中节点的重要度.2)本文定义的动态网络仅限于边的连通性变化，未考虑节点数量的增减[19]，下一步可采用大规模有/无线融合通信网等真实网络进行验证.3)文中节点重要度的计算采用各中心性指标线性加权得出，参数设置比较简单，未来可考虑采用多属性决策[20]等方法作进一步研究.夏靖波(1963—)，男，教授，博士生导师(编辑张红)【相关文献】[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.DOI: 10.3969/j.issn.1001-0548.2014.01.001.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. DOI:10.7498/aps.62.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. DOI: 10.13306/j.1672-3813.2015.02.016.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.[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.DOI:10.7498/aps.63.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.DOI:10.7498/aps.63.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.。