复杂网络关键节点识别方法综述

杨国军

摘 要：文章基于国内外学者对复杂网络关键节点识别的研究，对其方法进行了分析总结。根据针对的网络类型不同，将其分为四大类，分别为：无向无权网络关键节点识别方法、无向加权网络关键节点识别方法、有向无权网络关键节点识别方法和有向加权网络关键节点识别方法。通过梳理得知目前对复杂网络关键节点识别的研究已经相当成熟尤其是针对无向无权网络，但是对于有向加权网络的识别方法还相对较少。

关键词：复杂网络；关键节点识别；梳理

中图分类号：TB     文献标识码：A      doi：10.19311/j.cnki.16723198.2023.12.087

0 引言

近年来，随着复杂网络关键节点方法研究的不断深入以及国内外研究人员的不断努力，针对如何有效识别关键节点提出了很多经典的指标和方法，根据不同网络类型，可将其大致分为四大类。

（1）无向无权网络关键节点识别研究。

（2）无向加权网络关键节点识别研究。

（3）有向无权网络关键节点识别研究。

（4）有向加权网络关键节点识别研究。

1 无向无权网络关键节点识别方法研究

起初Freeman等人首先对社会网络开展研究并做了大量的相关试验，此后随着研究的逐渐成熟，又将复杂网络的节点重要性研究进一步扩展至科学领域和网络搜索领域，并对该领域研究做出了巨大的贡献。目前，对无向无权网络关键节点识别方法的研究相对成熟，国内外学者从不同角度出发提出了很多方法。根据方法针对性的不同主要可以分为以下三类：社会网络分析方法、系统科学分析方法、信息搜索分析方法。

1.1 基于社会网络分析方法

基于社会网络的分析方法的特点是，其在进行节点重要性评估时主要强调的是将其重要性等价于其显著性，同时，该类方法是以不破坏网络结构，保证网络的完整性为前提的。例如叶春森等人利用赋权求和的方法，结合聚类系数和平均路径来求得节点的重要值。但是由于在赋权时采用的是层次分析法，所以具有很強的人的主观性，得到的结果会有一定的误差。陈静等人在评估网络节点重要性时，同时考虑了局部和全局的信息流动。

在社会网络分析法中，经常用到节点的度、介数、紧密度等统计特性指标。但Jin等人认为这些指数只是节点某一个特性的表现，较为单一且不够全面。比如度指数，节点的度反映的是与该节点直接相连的节点数量，而没有考虑网络中整体信息的流动。其后，Freeman又给出了一个考虑全局意义的指标介数。该指标通过计算最短路径数来评价节点在全局的重要度。但是一旦研究的网络为大型的复杂网络，因为要计算网络中任意节点相互之间的最短路径数，其计算复杂性是相当高的，这也导致了该指标的使用受到限制。

1.2 基于系统科学分析方法

基于系统科学分析的方法是目前比较典型的一种识别方法。它是通过删除网络中的节点来观察网络连通性的变化，即网络的连通性越差证明被删除的节点越重要。即删除该节点之后对网络的损害范围越大那么这个节点就更重要，反之则重要程度越低。其中节点删除方法是最典型的系统科学分析类型，它避免了社交中不合理选择属性和指标而导致的一些问题逆向思维的网络分析。

这类方法还有很多，例如基于级联失效的方法、“核和核度”理论、最小生成树数目的节点删除法等。张海舰提出基于级联失效的方法，该方法是以网络的完整性为前提的，将网络发生级联失效后的网络状态分为正常、过载、失效三个状态，然后通过网络效率的变化来评价节点重要性。“核和核度”理论是由许进等人提出的，该理论将节点的集合看作为网络中的一个“核”。而网络中所有的核组成网络“核度”，其代表着网络的连通性，如果该“核”中的节点被损坏，就会引起网络“核度”产生问题，进而造成整体系统瘫痪。2004年，陈勇等人根据最小生成树，给出了一个新的评价方法。这种方法在评价网络中节点的重要度时，同样是通过删除节点的方式，但不同的是，这种评估方法要在删除节点的同时，也要考虑最小生成树随着删除节点数量是如何变化的，最小生成树的数量变动越小，那么节点越重要在网络中的重要性就越高。同年，李鹏翔等人根据删除节点后，网络结构被破环的程度将其进一步分为直接和间接。张品等人在对此进一步进行了优化，将生成树和度等特性相结合引入指标评估体系中。

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的进一步扩展，其在考虑节点重要性时，能够应用在有向加权网络中，其不仅考虑了网络边的方向，而且同时考虑了边的权值。不过，这种算法的复杂性很高，针对大型网络计算，其估计准确度时算法可能不收敛。Liu等人通过分析网络的局部结构，即认为与目标节点直接相连的邻居节点之间能够进行信息的流动，利用节点间信息的交互作用来作为指标，最终计算节点所包含的信息量评价节点的重要性。不过，这种方法不能直接应用于加权网络，因为其并没有考虑权值对网络节点重要性的影响。对此，王班等人对前者的评价方法进行了改进，即在网络的连边上增加了权重系数，所以该方法能用于有向加权网络的节点重要性评估。但是这两种评价方法都仅考虑了邻居节点的影响。而网络中的信息交互不仅只存在于邻居节点，与网络中的节点同样有信息交互作用。

矩阵经常被用来研究网络中节点之间相互作用，许多专家学者借助矩阵制定出了许多有效的评价方法。例如，周漩等人用节点效率和节点度来描述节点之间相互影响的关联度，并将其作为评价因素构建矩阵，通过将二者结合评价节点重要性。该方法将节点效率和节点度矩阵中的贡献比平均分配，且仅考虑了邻居节点的影响，与实际情况不符，不能在实际网络中广泛应用。因此许多学者根据这点不足，同时考虑到非相邻节点间也可能出现相互作用的影响情况，提出了更加全面的节点评价方法。例如，Hu等人提出的重要度贡献关联矩阵，以及范文礼等人提出的网络传输效率矩阵，这两种方法都从全局的角度分析节点的重要性，并用最短路径来衡量全网对各个节点之间的信息贡献比。由此可见，该评估方法由于将最短路径引入其中，所以在一定程度上克服了只考虑邻居节点的缺点。而实际上，最短路径只是其中的一个因素，最短路径的条数对网络中节点的節点重要性贡献同样有一定的影响。

5 结语

通过对复杂网络关键节点识别方法的梳理和分析可知，目前对于复杂网络关键节点方法的研究已经逐渐趋于成熟，尤其是针对于无向无权网络的方法，而现实中大部分网络是有向加权的，但目前对其研究的关键节点识别方法还不是很多，所以今后应当对有向加权网络关键节点识别方法进行研究补充，以解决现实生产生活中的实际问题。

参考文献

[1]Freeman L C.A set of measures of centrality based on betweenness[J].Sociometry，1977：3541.

[2]叶春森，汪传雷，刘宏伟，等.网络节点重要度评价方法研究[J].统计与决策，2010，（01）：2224.

[3]Jin J，Xu K，Xiong N，et al.Multiindex evaluation algorithm based on principal component analysis for node importance in complex networks[J].IET networks，2012，1（3）：108115.

[4]陳勇，胡爱群，胡啸，等.通信网中节点重要性的评价方法[J].通信学报，2004，（08）：129134.

[5]李鹏翔，任玉晴，席酉民，等.网络节点（集）重要性的一种度量指标[J].系统工程，2004，（04）：1320.

[6]张品，董志远，沈政，等.用于评价通信网节点重要性的多参数优化算法[J].计算机工程，2013，39（06）：9598.

[7]Lü L，Zhang Y C，Yeung C H，et al.Leaders in social networks，the delicious case[J].PloS one，2011，6（6）：21202.

[8]Kitsak M，Gallos L K，Havlin S，et al.Identification of influential spreaders in complex networks[J].Nature physics，2010，6（11）：888893.

[9]Lou X，Suykens J A K.Finding communities in weighted networks through synchronization[J].Chaos： An Interdisciplinary Journal of Nonlinear Science，2011，21（4）：04311610431169.

[10]Jiang Qixia，Zhang Yan，Sun Maosong.Community detection on weighted networks.avariational Bayesian method[A].Zhou Z.H.and Washio T，ACML，2009，（5828）：176190.

[11]Lu Zongqing，Wen Yonggang，Cao Guohong.Community detection in weighted networks：algorithms and applications[A].IEEE International Conference on Pervasive Computing and Communications（PerCom）[C].San Diego，USA：IEEE，2013，179184.

[12]于会，刘尊，李勇军，等.基于多属性决策的复杂网络节点重要性综合评价方法[J].物理学报，2013，62（02）：5462.

[13]韩忠明，吴杨，谭旭升，等.面向结构洞的复杂网络关键节点排序[J].物理学报，2015，64（05）：429437.

[14]Xu J，Li J，Xu S.Quantized innovations Kalman filter： stability and modificationwith scaling quantization[J].Journal of Zhejiang University SCIENCE C，2012，13（2）：118130.

[15]Liu Y，Jin J，Zhang Y，et al.A new clustering algorithm based on data field in complex networks[J].The Journal of Supercomputing，2014，67（3）：723737.