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

浅议几种复杂网络节点重要度分析的中心性方法作者：张廷萍来源：《价值工程》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.。

节点重要度法节点重要度法是一种用于网络分析的方法，它通过对网络中节点的连接情况进行分析，得出每个节点在网络中的重要程度。

在实际应用中，节点重要度法被广泛应用于社交网络分析、搜索引擎优化、疾病传播模型等领域。

节点重要度法的基本思想是基于节点的连接情况确定节点的重要程度。

在一个网络中，节点之间的连接可以用边来表示，每个节点的重要程度可以用其在网络中的度数来表示。

度数是指一个节点与其他节点之间连接的数量，度数越大，该节点在网络中的重要程度就越高。

因此，在节点重要度法中，度数是衡量节点重要程度的重要指标之一。

节点重要度法中还有一个重要指标是中心性。

中心性是指一个节点在网络中的中心位置程度。

在一个网络中，中心节点是指连接其他节点的节点，而中心性是一个节点与其他节点之间的距离之和。

中心性越高，该节点在网络中的中心位置就越重要。

节点重要度法还可以通过其他指标来衡量节点在网络中的重要程度。

例如，介数中心性是指一个节点在网络中的短路径数量，介数中心性越高，说明该节点在网络中的传递能力越强。

另外，紧密中心性是指一个节点与其他节点之间的距离的倒数之和，紧密中心性越高，说明该节点在网络中的关联性越强。

节点重要度法的应用十分广泛。

在社交网络分析中，节点重要度法可以用来分析社交网络中的重要人物。

在搜索引擎优化中，节点重要度法可以用来确定网站中的关键页面。

在疾病传播模型中，节点重要度法可以用来分析病毒在网络中的传播路径。

节点重要度法是一种基于节点连接情况进行分析的方法，它可以用来衡量节点在网络中的重要程度。

在实际应用中，节点重要度法被广泛应用于社交网络分析、搜索引擎优化、疾病传播模型等领域。

通过节点重要度法可以更好地理解网络结构，从而更好地设计和优化网络。

基于LeaderRank和节点相似度的复杂网络重要节点排序算法顾亦然;朱梓嫣【摘要】复杂网络中重要节点对网络结构和功能的影响引起了广泛关注.本文在现有LeaderRank算法的基础上,利用节点相似度来衡量节点间的相互作用,建立了SRank算法进行重要节点排序.利用SIR传播模型和斯皮尔曼等级相关系数在真实社会网络数据上对本文算法与经典的重要节点排序算法进行仿真后,发现该算法在无向和有向网络中均具有更高的准确性.%The effect of important nodes in complex networks on the structure and function of the networks causes widespread concern. This paper presents a SRank algorithm based on LeaderRank and nodes similarity which is used to measure the interaction between nodes. The simulation of SIR model and Spearman's correlation coefficient on real social networks show that the SRankalgorithm preforms better on identifying influential nodes both in directed and undirected networks, compared with the other four classical algorithms.【期刊名称】《电子科技大学学报》【年(卷),期】2017(046)002【总页数】8页(P441-448)【关键词】复杂网络;重要节点;相似度;SRank算法【作者】顾亦然;朱梓嫣【作者单位】南京邮电大学自动化学院南京 210023;南京邮电大学自动化学院南京 210023【正文语种】中文【中图分类】TP311,N94随着科学技术的发展，世界变得越来越小，也越来越复杂，涌现了大量难以用经典概念解释的问题，如微博中谣言通过少量节点快速传播到整个网络，传染病通过交通网络中的少量节点快速传播扩散[1]等。

复杂系统的关键节点识别算法综述摘要：复杂网络在各个领域中起着重要的作用，研究复杂网络的关键节点识别算法对于了解网络结构和功能具有重要意义。

本综述将介绍当前常用的复杂系统关键节点识别算法，并分析其优劣势和适用场景。

这些算法包括基于网络结构的方法、基于节点重要性指标的方法、基于动态过程的方法以及混合方法。

在讲解每一种算法之前，将对复杂系统和关键节点的概念进行明确，并给出相应的数学模型。

最后，对未来研究趋势进行讨论，以期为复杂系统关键节点识别算法的进一步研究提供指导。

1. 引言复杂系统是由大量相互连接的节点和边组成的系统，如社交网络、生物网络和物流网络等。

研究复杂系统的关键节点识别算法有助于揭示网络的重要结构和功能，对于优化和改进复杂系统具有重要意义。

关键节点是指在复杂网络中起着重要作用，其移除或扰动可能导致网络功能的降低。

因此，关键节点的识别成为研究复杂系统的一个关键问题。

2. 复杂系统和关键节点概念2.1 复杂系统的定义复杂系统是由大量的节点和边构成的网络结构，具有多样的动态行为和自组织能力。

复杂系统的特点包括网络拓扑结构的复杂性、节点之间的相互依赖性和非线性的动态行为。

2.2 关键节点的定义关键节点是指在复杂网络中对网络结构和功能有重要贡献的节点。

关键节点的移除将导致网络结构变化、网络功能的降级或失效。

3. 基于网络结构的关键节点识别算法基于网络结构的方法是通过分析网络结构的拓扑属性来识别关键节点。

这些方法包括度中心性算法、介数中心性算法、紧密中心性算法和PageRank算法等。

3.1 度中心性算法度中心性是指节点的连接数，即节点所连的边的数量。

度中心性算法将高度连接的节点视为关键节点，因为它们在信息传播、物质交换和能量传输等方面具有重要的作用。

3.2 介数中心性算法介数中心性是指节点在网络中连接其他节点间的最短路径数量，即节点在网络中作为中介的程度。

介数中心性算法将介数中心性较高的节点视为关键节点，因为它们在信息传播和影响传递中起到关键的作用。

关键节点发现相关算法引言：在复杂网络中，关键节点的发现是一项重要的任务，它可以帮助我们理解网络的结构和功能，并为网络的优化和调整提供指导。

关键节点是指对网络的功能和稳定性有重要影响的节点，其删除或瘫痪会导致网络的功能丧失或性能下降。

本文将介绍几种常见的关键节点发现相关算法，包括度中心性、介数中心性、特征向量中心性和PageRank算法。

一、度中心性（Degree Centrality）度中心性是最简单直观的关键节点发现算法之一。

它基于一个假设：节点的重要程度与其度数成正比。

即度数越大的节点，在网络中的地位越重要。

度中心性算法通过计算每个节点的度数，然后将其归一化，得到度中心性值。

度中心性值越大的节点，越有可能是关键节点。

二、介数中心性（Betweenness Centrality）介数中心性是一种基于节点在网络中的中介程度来衡量其重要性的算法。

中介程度指的是节点在网络中作为中介传递信息的次数。

介数中心性算法通过计算每个节点的中介程度，并将其归一化，得到介数中心性值。

介数中心性值越大的节点，越有可能是关键节点。

介数中心性算法在社交网络、交通网络等领域有着广泛的应用。

三、特征向量中心性（Eigenvector Centrality）特征向量中心性是一种基于节点与其邻居节点的关系来衡量其重要性的算法。

特征向量中心性算法假设一个节点的重要程度与其邻居节点的重要程度成正比。

即一个节点的重要性取决于其邻居节点的重要性。

特征向量中心性算法通过迭代计算每个节点的特征向量中心性值，直到收敛。

特征向量中心性值越大的节点，越有可能是关键节点。

四、PageRank算法PageRank算法是一种基于网络链接结构和节点之间的链接关系来衡量节点重要性的算法。

PageRank算法是由Google公司创始人之一Larry Page提出的，用于评估网页的重要性。

在PageRank 算法中，每个节点的重要性通过迭代计算得到，其中节点的重要性取决于其邻居节点的重要性和链接的权重。

作者简介:杨国军(1997-),男,汉族,河北唐山人,硕士,研究方向:质量管理㊂复杂网络关键节点识别方法综述杨国军(天津理工大学管理学院,天津330384)摘㊀要:文章基于国内外学者对复杂网络关键节点识别的研究,对其方法进行了分析总结㊂根据针对的网络类型不同,将其分为四大类,分别为:无向无权网络关键节点识别方法㊁无向加权网络关键节点识别方法㊁有向无权网络关键节点识别方法和有向加权网络关键节点识别方法㊂通过梳理得知目前对复杂网络关键节点识别的研究已经相当成熟尤其是针对无向无权网络,但是对于有向加权网络的识别方法还相对较少㊂关键词:复杂网络;关键节点识别;梳理中图分类号:TB㊀㊀㊀㊀㊀文献标识码:A㊀㊀㊀㊀㊀㊀doi:10.19311/ki.1672-3198.2023.12.0870㊀引言近年来,随着复杂网络关键节点方法研究的不断深入以及国内外研究人员的不断努力,针对如何有效识别关键节点提出了很多经典的指标和方法,根据不同网络类型,可将其大致分为四大类㊂(1)无向无权网络关键节点识别研究㊂(2)无向加权网络关键节点识别研究㊂(3)有向无权网络关键节点识别研究㊂(4)有向加权网络关键节点识别研究㊂1㊀无向无权网络关键节点识别方法研究起初Freeman 等人首先对社会网络开展研究并做了大量的相关试验,此后随着研究的逐渐成熟,又将复杂网络的节点重要性研究进一步扩展至科学领域和网络搜索领域,并对该领域研究做出了巨大的贡献㊂目前,对无向无权网络关键节点识别方法的研究相对成熟,国内外学者从不同角度出发提出了很多方法㊂根据方法针对性的不同主要可以分为以下三类:社会网络分析方法㊁系统科学分析方法㊁信息搜索分析方法㊂1.1㊀基于社会网络分析方法基于社会网络的分析方法的特点是,其在进行节点重要性评估时主要强调的是将其重要性等价于其显著性,同时,该类方法是以不破坏网络结构,保证网络的完整性为前提的㊂例如叶春森等人利用赋权求和的方法,结合聚类系数和平均路径来求得节点的重要值㊂但是由于在赋权时采用的是层次分析法,所以具有很强的人的主观性,得到的结果会有一定的误差㊂陈静等人在评估网络节点重要性时,同时考虑了局部和全局的信息流动㊂在社会网络分析法中,经常用到节点的度㊁介数㊁紧密度等统计特性指标㊂但Jin 等人认为这些指数只是节点某一个特性的表现,较为单一且不够全面㊂比如度指数,节点的度反映的是与该节点直接相连的节点数量,而没有考虑网络中整体信息的流动㊂其后,Freeman 又给出了一个考虑全局意义的指标介数㊂该指标通过计算最短路径数来评价节点在全局的重要度㊂但是一旦研究的网络为大型的复杂网络,因为要计算网络中任意节点相互之间的最短路径数,其计算复杂性是相当高的,这也导致了该指标的使用受到限制㊂1.2㊀基于系统科学分析方法基于系统科学分析的方法是目前比较典型的一种识别方法㊂它是通过删除网络中的节点来观察网络连通性的变化,即网络的连通性越差证明被删除的节点越重要㊂即删除该节点之后对网络的损害范围越大那么这个节点就更重要,反之则重要程度越低㊂其中节点删除方法是最典型的系统科学分析类型,它避免了社交中不合理选择属性和指标而导致的一些问题逆向思维的网络分析㊂这类方法还有很多,例如基于级联失效的方法㊁ 核和核度 理论㊁最小生成树数目的节点删除法等㊂张海舰提出基于级联失效的方法,该方法是以网络的完整性为前提的,将网络发生级联失效后的网络状态分为正常㊁过载㊁失效三个状态,然后通过网络效率的变化来评价节点重要性㊂ 核和核度 理论是由许进等人提出的,该理论将节点的集合看作为网络中的一个 核 ㊂而网络中所有的核组成网络 核度 ,其代表着网络的连通性,如果该 核 中的节点被损坏,就会引起网络 核度 产生问题,进而造成整体系统瘫痪㊂2004年,陈勇等人根据最小生成树,给出了一个新的评价方法㊂这种方法㊃362㊃在评价网络中节点的重要度时,同样是通过删除节点的方式,但不同的是,这种评估方法要在删除节点的同时,也要考虑最小生成树随着删除节点数量是如何变化的,最小生成树的数量变动越小,那么节点越重要在网络中的重要性就越高㊂同年,李鹏翔等人根据删除节点后,网络结构被破环的程度将其进一步分为直接和间接㊂张品等人在对此进一步进行了优化,将生成树和度等特性相结合引入指标评估体系中㊂1.3㊀基于信息搜索分析方法基于信息搜索分析的方法是根据互联网中信息流动提出的,其比较常用的评价算法有两种㊂其中一个是1998年Google创始人Brin和Page提出的PageRank算法,另一个是同年Kleinberg提出的HITS算法㊂这两种方法不仅考虑了节点自身的特性,同时也考虑了邻居节点对其的影响,通过验证表明这两种方法能够很好的识别出网络中的关键节点㊂后人在这两个经典评估方法的基础上,进一步给出改善意见,进而提出了多种有效的评估方法㊂其中,Lü等人以PageRank算法为基础,将背景节点加入其中,解决了参数的影响㊂因为关键节点在数据传播中扮演了至关重要的角色,基于此,近年来产生了许多新的评估方法㊂例如Kitsak等人提出的ks 指标,这种方法是通过将网络中的节点按节点的度值进行分层,度值相同的节点为同一层㊂节点的ks值就是层的表示,按节点度值分的层数越多ks值也就越大,那么该层内的节点的重要性就越大㊂但是该指标不具有一定的适用性,由于该方法按照度值进行分层,虽然可以区别层间的节点重要性,但是层内的节点重要性都是一样的,而且该方法仅能应用于无向无权网络㊂在特定的网络环境下,以上的关键节点评估方法都能取得良好的评估效果,为复杂网络节点重要性的研究打下了坚实的基础㊂2㊀无向加权网络关键节点识别方法研究2.1㊀按对网络边信息的利用程度划分首先,Newman提出了一种针对于于无向有权网络的评价指标,而后LouXuyang等人在此基础上,提出了一种基于同步的加权网络社区发现算法,这种算法首先使网络中的一部分节点开始震荡,应用矩阵来记录被其影响的邻居节点的震动情况,当矩阵不再对称时停止震荡,记录得到的最终结果㊂Biondel等人提出了一种基于模块度的适用于较大规模加权复杂网络的关键节点识别方法㊂除了对模块度的扩展外,Hoffman等人提出了将贝叶斯以及受约束的SBM相结合,提出一种适用于无向无权网络的方法,随后Jiang Qixia等人将此方法进一步扩展到无向加权网络中㊂随着研究的进一步深入,更多针对于加权网络的方法涌现,比如Lu Zongqin 等人提出了一种基于Conductance的加权网络社区发现算法;Saha Tanwistha等人提出了一种基于模糊聚类的识别方法;Cui Aixiang等人利用加权的情感网络提出了一种新的识别方法㊂2.2㊀按能否发现重叠社区的划分前面所提到的大多数算法都属于非重叠情况,因为这些算法考虑的因素比较单一,而现实中的网络的节点一般包含多重信息,所以所取得的效果不是很明显,为了使得算法更加有效,就需要考虑多重信息是否造成了重叠社区,以减少计算过程中所产生的误差㊂为了更加全面的考虑网络中的信息,同时考虑重叠社区存在与否,国内外学者提出了多种针对于此的关键节点识别方法㊂Palla等人提出的CPM算法是一种比较典型的算法㊂CPM算法是以参数k来表示子图规模,然后从网络中抽取所有的子图,通过参数k来约束网络中的社团数量,根据约束条件对进行矩阵多次迭代,看是否满足约束条件,根据约束条件扩大或者结合,直到最终达到稳定的状态㊂3㊀有向无权网络关键节点识别方法研究起初,针对于有向无权网络关键节点识别方法大都考虑的比较片面,后来学者为了克服这一缺点提出了很多具有代表性的方法㊂比如于会等人将度中心性㊁接近中性性㊁介数中心性以及结构洞相结合,很好的解决传统方法考虑条件单一的不足㊂但是由于该方法在评估各个指标权重时用的是层次分析法,而层次分析法具有很强的主观性,所以会对结构造成一定的误差㊂此外,韩忠明等人采用结构洞理论通过ListNet排序方法将节点效率㊁网络规模㊁聚类系数等七个指标综合起来,提出了一种针对于有向无权网络的节点重要性排序方法,虽然这种方法能很好的识别出网络中的重要节点,但是该方法的计算量很大,复杂性比较高,不适用于大型复杂网络且不具有一定的普遍性㊂4㊀有向加权网络关键节点识别方法研究根据已有的研究成果,大部分评估方法都是针对于无向无权网络的,但对有向加权网络的发展仍有一定的帮助㊂例如Xu等人提出的DWCN-NodeRank指标,该评价指标是对PageRank的进一步扩展,其在考虑节点重要性时,能够应用在有向加权网络中,其不仅考虑了网络边的方向,而且同时考虑了边的权值㊂不过,这种算法的复杂性很高,针对大型网络计算,其估计准确度㊃462㊃时算法可能不收敛㊂Liu等人通过分析网络的局部结构,即认为与目标节点直接相连的邻居节点之间能够进行信息的流动,利用节点间信息的交互作用来作为指标,最终计算节点所包含的信息量评价节点的重要性㊂不过,这种方法不能直接应用于加权网络,因为其并没有考虑权值对网络节点重要性的影响㊂对此,王班等人对前者的评价方法进行了改进,即在网络的连边上增加了权重系数,所以该方法能用于有向加权网络的节点重要性评估㊂但是这两种评价方法都仅考虑了邻居节点的影响㊂而网络中的信息交互不仅只存在于邻居节点,与网络中的节点同样有信息交互作用㊂矩阵经常被用来研究网络中节点之间相互作用,许多专家学者借助矩阵制定出了许多有效的评价方法㊂例如,周漩等人用节点效率和节点度来描述节点之间相互影响的关联度,并将其作为评价因素构建矩阵,通过将二者结合评价节点重要性㊂该方法将节点效率和节点度矩阵中的贡献比平均分配,且仅考虑了邻居节点的影响,与实际情况不符,不能在实际网络中广泛应用㊂因此许多学者根据这点不足,同时考虑到非相邻节点间也可能出现相互作用的影响情况,提出了更加全面的节点评价方法㊂例如,Hu等人提出的重要度贡献关联矩阵,以及范文礼等人提出的网络传输效率矩阵,这两种方法都从全局的角度分析节点的重要性,并用最短路径来衡量全网对各个节点之间的信息贡献比㊂由此可见,该评估方法由于将最短路径引入其中,所以在一定程度上克服了只考虑邻居节点的缺点㊂而实际上,最短路径只是其中的一个因素,最短路径的条数对网络中节点的节点重要性贡献同样有一定的影响㊂5　结语通过对复杂网络关键节点识别方法的梳理和分析可知,目前对于复杂网络关键节点方法的研究已经逐渐趋于成熟,尤其是针对于无向无权网络的方法,而现实中大部分网络是有向加权的,但目前对其研究的关键节点识别方法还不是很多,所以今后应当对有向加权网络关键节点识别方法进行研究补充,以解决现实生产生活中的实际问题㊂参考文献[1]Freeman L C.A set of measures of centrality based on be-tweenness[J].Sociometry,1977:35-41.[2]叶春森,汪传雷,刘宏伟,等.网络节点重要度评价方法研究[J].统计与决策,2010,(01):22-24.[3]Jin J,Xu K,Xiong N,et al.Multi-index evaluation algorithm based on principal component analysis for node importance in complex networks[J].IET networks,2012,1(3):108-115.[4]陈勇,胡爱群,胡啸,等.通信网中节点重要性的评价方法[J].通信学报,2004,(08):129-134.[5]李鹏翔,任玉晴,席酉民,等.网络节点(集)重要性的一种度量指标[J].系统工程,2004,(04):13-20.[6]张品,董志远,沈政,等.用于评价通信网节点重要性的多参数优化算法[J].计算机工程,2013,39(06):95-98. [7]LüL,Zhang Y C,Yeung C H,et al.Leaders in social net-works,the delicious case[J].PloS one,2011,6(6):21202.[8]Kitsak M,Gallos L K,Havlin S,et al.Identification of influen-tial spreaders in complex networks[J].Nature physics,2010, 6(11):888-893.[9]Lou X,Suykens J A K.Finding communities in weighted net-works through synchronization[J].Chaos:An Interdiscipli-nary Journal of Nonlinear Science,2011,21(4):043116-1-043116-9.[10]Jiang Qixia,Zhang Yan,Sun munity detection on weighted networks.avariational Bayesian method[A]. Zhou Z.H.and Washio T,ACML,2009,(5828):176-190.[11]Lu Zongqing,Wen Yonggang,Cao munity de-tection in weighted networks:algorithms and applications[A].IEEE International Conference on Pervasive Computing and Communications(PerCom)[C].San Diego,USA:IEEE, 2013,179-184.[12]于会,刘尊,李勇军,等.基于多属性决策的复杂网络节点重要性综合评价方法[J].物理学报,2013,62(02): 54-62.[13]韩忠明,吴杨,谭旭升,等.面向结构洞的复杂网络关键节点排序[J].物理学报,2015,64(05):429-437.[14]Xu J,Li J,Xu S.Quantized innovations Kalman filter:stabil-ity and modificationwith scaling quantization[J].Journal of Zhejiang University SCIENCE C,2012,13(2):118-130.[15]Liu Y,Jin J,Zhang Y,et al.A new clustering algorithm based on data field in complex networks[J].The Journal of Super-computing,2014,67(3):723-737.㊃562㊃。