一种基于局部特征的节点重要性排序方法
2022-12-24朱敬成王伦文
朱敬成，王伦文，吴 涛
(国防科技大学电子对抗学院，安徽 合肥 230037)
1 引言
随着网络科学的快速发展，复杂网络在国民经济、舆情引导、军事斗争等不同领域得到广泛的应用和发展。复杂网络的研究由来已久，早在1998年，Duncan J.Watts和Steven HStrogatz就提出了小世界特性[1]。随后Barabási与Albert在描绘万维网时又提出了无标度特性[2]。自从复杂网络成为科研领域的研究热点以来，研究表明网络的结构和机能主要受某些重要节点的影响，移除这些重要节点时会最大程度地毁坏网络结构，使得网络丧失运转机能。例如，蛋白质网络中的关键节点识别可以探索蛋白质之间的信息传递，进而揭示疾病的发病机理；舆情传播网络中可以通过对关键节点进行监控从而掌握社会舆论动态，避免谣言的传播；在道路网络中，对关键节点采取一定的预防措施可以使得交通拥堵状况得以改善，同时也可以减少交通事故的发生。可见，节点重要性分析有很高的应用价值。
目前众多科研人员已提出了许多关于节点重要性排序的经典方法，常用方法有度中心性排序[3]、介数中心性排序[4]、接近中心性排序[5]等。其中度中心性是节点重要性排序最简单的方法，而介数中心性和接近中心性因为其计算复杂度高而应用受限。文献[6]提出了一种涉及节点四阶邻居信息的半局部中心性(semi-local centrality，SLC)，在重要节点识别精度和耗时之间取得了一个平衡。文献[7]提出了一种基于节点和节点邻居度的方法(WL centrality)，认为节点的度和节点的邻居节点的度越大，节点就越重要，在复杂度和有效性方面都得到了提升。文献[8]提出了一种基于度中心性的粗粒化关键点排序方法，称为K-shell分解方法，然而K-shell方法存在很多节点分有相同值的问题，无法很好区分重要性。文献[9]综合了邻居节点数和邻居连接紧密程度提出了一种基于度和集聚系数的重要性排序方法，该方法可适用于大规模网络。文献[10]考虑了标准化后的节点自身度、节点邻居度之和以及节点K-shell值提出了一种被称为DKN的方法，考虑了不同方法的综合效果。文献[11]考虑到邻居及次邻居节点的个数和边对节点重要性的影响，提出了基于节点和边的NL中心性方法，进一步区分了节点的位置信息带来的影响。文献[12]将信息熵引入到节点重要性排序中，考虑了节点所有邻居的相关性。文献[13]定义了节点领域相似度，利用节点两跳内邻居信息表征了节点的重要性。文献[14]在电力网络上采用了一种改进的泰尔熵的方法提出了一种节点综合评估指标，弥补了信息熵考虑因素单一的缺陷。文献[15]将介数中心性和邻居节点的度中心性结合提出了介度熵概念，获取了更高了效率。文献[16]研究了节点与直接邻居节点及间接邻居节点的关系，通过信息熵的方法定义了一种基于邻接信息熵的节点重要性排序方法，该方法适用于多种类型网络。
上述方法从不同方面评估了节点的重要性程度，考虑到度中心性计算复杂度低且适用于大规模网络[17]，本文针对节点自身及其邻居的度中心性提出一种重要性排序方法，该方法以节点自身以及节点一阶邻居的度值信息来衡量重要性。以网络鲁棒性和脆弱性为评价方法[18]，在不同网络上将本文所提方法与度中心性DC、半局部中心性SLC、基于节点及其邻居度的WL方法、K-shell分解方法、DKN方法以及基于节点和边的NL方法进行比较，发现本文所提方法更能区分节点的重要性。
2 基于局部特征的节点重要性排序方法
2.1 网络表示
假设网络G=(V，E)，其中V和E分别表示网络的节点集合和边集合，对于含有n个节点和m条边的网络而言，网络的邻接矩阵A可以表示为
矩阵中元素aij表示节点i和节点j的连边信息，如果aij=1，表示两个节点相连，否则aij=0，则表示两节点不直接相连。
2.2 局部特征排序方法
本文研究的对象是无权无向网络，在研究中，节点的度中心性实质上就是与节点直接相连的节点的数量，通过邻接矩阵元素的值就可以得到节点的度值以及邻居节点集合。度值可以用下面的式子表示
(1)
归一化的度中心性方法可以表示为
(2)
由上式可知，度中心性方法可以直接用连边信息反映了节点的影响度，从式(1)的计算过程中也可以看出度中心性方法拥有着简单、直观的特点。但是由于度中心性方法仅仅考虑自身信息无法全面反映节点的重要性，会出现大量节点重要性排序结果一致，从而应用受限，不能精准的对节点重要性进行排序，因而引入了邻居信息更加全面的反映节点的重要性。
图1 示例网络
以图1的示例网络进行说明，使用度中心性计算示例的网络的重要性时得到下面结果：kv1=kv7=kv8，kv2=kv4，kv3=kv6，从计算结果来看度中心性由于只考虑自身信息而导致许多节点重要性无法识别，识别的区分度和准确率低。
从上述分析结果来看仅从自身去分析节点的重要性有很大的局限性，考虑到节点的邻居对节点重要性也有一定的影响，本文针对度中心性方法这一局限性对节点及其一阶邻居进行研究，提出了一种新的局部特征的DND方法，该方法定义为
(3)
式(3)中Γi表示节点i的一阶邻居节点的集合。DND方法越大，说明节点的重要性越高，排序越靠前。
以图1的示例网络中节点v2为例，节点v2的邻居集为{v1，v3}，由于kv1=1，则αv1=-1，而kv3=4，则αv3=1，又kv2=2，故
在研究中如果仅按照度中心性区分重要性会存在多个节点度值相同的情形，进而模糊了部分节点的重要性排序。而使用DND方法计算节点重要性时得到的区分结果为DNDv3>DNDv6，DNDv2=DNDv4，DNDv1>DNDv8>DNDv7。从计算结果可以得到DND方法相比度中心性方法在节点重要性排序上更有准确的结论。
3 评价标准
本文基于网络的鲁棒性和脆弱性对节点的重要性进行研究，这种研究方法主要考察的是移除节点对网络的结构和功能造成的影响，节点移除对网络结构影响越大，说明该节点越重要[19]，可以以此来评估节点重要性排序方法的准确性。在这里采用独立部分比例[20]和最大连通子图[21]相对大小来评估节点对网络结构和功能的影响，可以通过变化趋势图直观地得到方法排序结果的准确性。
3.1 独立部分比例
独立部分比例指的是移除节点的边后网络的连通子图数量比例，可以反映节点被摧毁成独立部分的程度。将节点按照方法评估的重要性顺序从大到小排序，观察移除节点边后对网络节点独立化的影响，独立部分比例计算公式可以表示为
(4)
式中，R表示独立子图数量，n表示网络的节点总数。若按照排序结果蓄意攻击使得独立部分数目更多且最快达到完全独立，说明该种方法的节点重要性排序更有效。
3.2 最大连通子图比例
按照节点重要性挖掘的方法得到节点重要性排序后，按照重要性排序结果移除节点，移除节点将会对网络结构造成一定影响，产生的网络巨片[22]的节点数目与网络节点总数之比称之为最大连通子图比例。计算公式为
(5)
式中S为按照排序结果移除一定比例的节点后网络巨片中包含的节点数，n则为网络节点总数，最大连通子图可以很好地反映网络的结构变化，可以通过观察移除节点后网络巨片的变化趋势来衡量排序性结果的有效性，随着节点的移除网络巨片的规模下降的越快，说明该方法对网络的结构性破坏效果更加明显，节点就越重要。
4 实验分析
4.1 实验环境及数据集
本文中实验所用的电脑配置为Intel(R) Core(TM) i5-4210M CPU @ 2.60GHz的处理器，内存为12GB。软件环境为Matlab R2018b。为了评估本文提出的节点重要性排序方法的有效性，选取六个不同结构的真实网络和三个人工生成的网络进行实验。六个真实网络分别为USAir美国航空网络[23]，Slavko在Facebook上的朋友圈关系网络[24]，Infectious人群感染网络[25]，蛋白质间相互作用的Yeast网络[23]，Email邮件网络[25]，Power美国西部国家电力网络[23]。三个人工网络分别为ER随机网络、WS小世界网络以及BA无标度网络，参数设置如下所示：
ER随机网络：节点总数n=5000，节点连边概率p=0.0012；
WS小世界网络：节点总数n=5000，领域节点个数K=6，重连概率p=0.1；
BA无标度网络：节点总数n=5000，初始连通节点个数m0=13，每次引入新节点时新生成的边数ml=6。
实验网络数据集的详细信息如表1所示，其中n和m分别表示网络的节点数量以及网络的连边数目，
表1 网络拓扑参数
4.2 实验结果分析
在多个网络数据集上，将本文提出的DND方法同都由局部信息进行排序的度中心性方法、半局部中心性方法、WL方法、K-shell方法、DKN方法以及基于节点和边的NL方法进行比较和分析。以各方法从大到小结果进行排序，按照各方法排序顺序对相应节点进行蓄意攻击，攻击的形式为按重要性顺序移除节点或者移除节点连边，实验结果如图2和图3所示。
图2(a)-(i)展现的是移除节点边后网络的独立部分比例，独立部分越多，说明网络被化整为零的更彻底，在不同网络中，DND方法相比其它几个方法在相同条件下更能使得网络分成更多的组成部分，且相比其它方法能够使得网络节点最快达到完全独立，即网络节点不存在连边。原因在于要想使得独立部分越多，对于连边多的节点破坏起来就比连边少的节点更有可能分解成更多部分，而度中心性由于区分度不够，无法区分出相同连边的节点，本文提出的DND方法相比度中心性不光考虑自身同时也考虑一阶邻居的影响，使得度值相同的点也能区分出重要性，以本文提出的DND方法对节点重要性更有分辨能力，对网络的分解能力更强。
图2 不同方法对网络重要性排序后移除一定比例节点连边产生的独立部分比例
图3反映的是各方法蓄意攻击所造成的网络最大连通子图变化趋势，是各方法对节点重要性排序后，按照节点重要性程度以一定比例移除节点，所展现的是最大连通子图中的节点数所占总数比例。从图中可以看出对于所有网络而言，本文提出DND方法相比度中心性方法、半局部中心性方法、WL方法、K-shell方法、DKN方法以及NL方法变化趋势更明显，可以观察到Email网络和Yeast网络从一开始就表现出比其它方法更好的效果。由于ER和WS网络是随机网络，节点度值较为均匀，图3(g)(h)在移除小部分节点后各方法之间效果相差不大，而WS网络的度值相对ER网络更加集中，故就度中心性方法而言ER网络在后期破坏效果比WS网络好，而在两个网络中都是K-shell方法破坏网络结构的效果最差，对节点重要性无法做到有效区分，原因在于赋予许多节点相同值。图3(i)展现了BA网络的优先连接特性，即新节点优先与强连接度的节点相连，导致少数关键节点连接了大部分的节点[27]。正是由于优先连接特性，度中心性方法在BA网络中破坏效果相比其它方法优势很大。
总的来说，本文提出的DND方法在独立部分比例实验相比其它方法可以更快将网络分解成一个个独立的部分。在最大连通子图比例实验中可以得到本文所提方法在节点重要性排序上准确性更高，更易摧毁网络。
5 结束语
复杂网络关键节点的识别是复杂网络理论研究的重要一部分，随着网络化的迅猛发展，生活中伴随着各种各样的网络，识别出其中的关键节点有助于提高网络的抗毁性，维持住网络的稳定性[28]，具有重要的理论和现实意义。本文基于节点及其一阶邻居节的点度中心性提出了一种局部特征的重要性排序方法，此方法只需要考虑节点和一阶邻居节点的度中心性方法，容易获得计算参数且适用于大规模网络。本文在六个真实网络和三个人工网络上利用独立部分比例和最大连通子图对提出的方法进行了验证，最终结果表明本文所提的DND方法相比度中心性方法、半局部中心性方法、WL方法、K-shell方法、DKN方法以及NL方法在节点重要性排序上结果更加精准。由于网络的复杂性，结构的多样性，现如今还是没有一个方法可以适用于所有的网络，但本文所提的方法简单且适用网络范围广，为邻居节点对节点重要性影响的研究提供了一个新方法。
图3 不同方法对网络重要性排序后移除一定比例节点后产生的最大连通子图比例
