基于范德华力的节点重要性评估算法.pdf

基于范德华力的节点重要性评估算法龚志豪，蒋 沅，代冀阳（南昌航空大学 信息工程学院，南昌330063）摘要 精准度量复杂网络中节点的重要程度有助于研究网络的抗毁性和鲁棒性。为弥补现有算法评估角度片面的局限性，该文将范德华力引入复杂网络中，将网络中的节点映射为分子或原子，并将节点的度值表示为分子或原子的范德华常量，用范德华力来定义节点的影响力，综合考虑节点间路径信息的占比率，提出一种基于范德华力的重要节点挖掘算法VDWF(Van der Waals Force)。该算法兼顾网络的局部信息以及全局拓扑结构等特征。为验证该算法的有效性与适用性，分别采用单调性指标、网络效率以及极大连通系数等作为评估指标，并选取 6 个不同领域的真实数据集与其它算法进行对照实验。结果表明，范德华力算法能够更加有效地挖掘复杂网络中的重要节点，精准区分不同节点的重要性差异。关键词 复杂网络；节点重要性；范德华力；路径占比率 中图分类号 TP311 文献标志码 A doi：10.3969/j.issn.2096-8566.2023.02.001 文章编号 2096-8566(2023)02-0001-09Node Importance Evaluation Algorithm Based on Van der Waals ForceGONG Zhi-hao，JIANG Yuan，DAI Ji-yang（School of Information Engineering,Nanchang Hangkong University,Nanchang 330063,China）Abstract:Accurately measuring the importance of nodes in a complex network helps to study the resistance to destruction androbustness of the network.To compensate for the limitations of existing algorithms in assessing one-sided perspectives,this paperintroduces Van der Waals Force into complex networks.It maps the nodes in the network as molecules or atoms,and represents thedegree of nodes as Van der Waals constants of molecules or atoms.It defines the influence of nodes in terms of Van der WaalsForce,takes into account the percentage of path information between nodes,and proposes a Van der Waals Force-based importantnode mining algorithm called VDWF(Van der Waals Force).This algorithm considers both the local information of the network andthe global topology.To verify the effectiveness and applicability of the algorithm,monotonicity index,network efficiency,and greatconnectivity coefficient are used as evaluation indices.Six real data sets from different domains are selected for control experimentswith other algorithms.The results show that the Van der Waals Force algorithm can more effectively mine important nodes incomplex networks and accurately distinguish the differences in the importance of different nodes.Key words:complex network；node importance；Van der Waals Force；path proportion 收稿日期2023-02-12 修回日期2023-04-03基金项目国家自然科学基金(61663030，61663032)；科技部重大研发专项项目(20214ABC28W002)；江西省自然科学基金(20224BAB202028)；江西省“双千”项目(jxsq2020102038)；南昌航空大学研究生创新专项资金(YC2022-049)通讯作者蒋沅(1982)，男，博士，副教授。主要研究方向：复杂系统建模与优化算法。第 37 卷 第 2 期南昌航空大学学报：自然科学版Vol.37 No.22023 年 6 月Journal of Nanchang Hangkong University:Natural SciencesJun.2023 引言近年来，网络信息技术取得了群体性突破，复杂网络已经成为网络科学1中的前沿领域。在各种复杂网络中，对鲁棒性的研究主要是关注移除节点或边后的网络响应情况，而网络如何维持或恢复稳定性决定了其抗毁性。精准地挖掘重要节点有助于网络的鲁棒性与抗毁性研究，并且对于网络的可靠性以及保障网络的正常运行具有重要的现实意义2。例如：识别城市交通网络3中经常发生拥堵的路段并改造完善，可提升交通运行效率、优化出行体验；识别疾病传播网络4中的感染者和超级传播者并进行治疗，可实现多层次全方位避免疫情扩大；识别电力网络5中的各个重要发电厂与变电站并加以保护，可避免变、配电线路受到损坏时造成大面积停电等。针对各种复杂网络研究的背景与意义，广大学者陆续提出各种评价方法以刻画节点的关键程度。早期的典型识别复杂网络节点重要度算法有度排序、K-壳分解法、特征向量中心性、接近中心性和介数中心性等6。其中，度排序算法对网络节点的位置考虑欠缺，因此难以将不同邻居节点的重要程度差异化。时间复杂度较低的 K-壳分解法虽然在网络范围较大时计算速度快，但同一层壳中的节点会被评估为同样的重要程度。而当网络范围较小时，无法进一步精确地评估各个节点之间的重要度差距。特征向量中心性适用于表示各个节点的长期影响力，在传播分析方面具有较大优势。接近中心性和介数中心性等算法应用了网络的全局信息，但没有将节点的局部邻居信息考虑在内，区分度不够精准。为提升评估节点的区分度，杨松青等7综合考察节点的 K-壳中心性与网格约束系数，提出了一种基于 Tsallis 熵的排序算法；Nie等8提出了映射熵来识别网络中的关键节点，该模型兼顾了中心节点相关邻域的局部信息；Yang等9综合了不同角度的中心性标准，提出了一种基于熵权法和 VIKOR 的网络节点重要度排序新方法；Hu 等10提出了节点重要性贡献相关矩阵来识别网络上节点的重要性，该方法考虑了多层和不均匀的节点重要性贡献；韩忠明等11结合节点间三角结构和周围邻居节点，提出了一种基于三角结构的度量模型。结合以上研究，本文将范德华力引入复杂网络中，将网络中的节点视为分子或原子，通过考察每个节点的度值和 2 个节点之间的最短路径距离并将其分别作为范德华常量和距离，综合考虑节点间的路径占比信息，提出一种基于范德华力(Van derWaals Force,VDWF)的指标来识别节点的重要度值。该指标同时兼顾网络的局部信息、节点间的路径信息以及拓扑结构等特征。1 理论基础G=(V,E)V=V1,V2,VnE=e1,e2,emn=|V|m=|E|无向无权的网络拓扑结构。其中是节点集，是边集。节点数，节点间边的条数。1.1 度指标i节点的度定义为与该节点相连的边数，一般来说，若节点的度值越大，则该节点也就越为重要。节点 的度值为：DC(i)=Nj=1aij(1)Naijijaijaij式中，表示该网络中节点的总个数，为节点 和之间的连接状况，若 2 个节点之间有连边，则=1，反之=0。1.2 K-壳分解法K-壳分解法为反复剥离网络中度值小于等于k 的节点。若初始时没有度值为 0 的孤立节点，则首先删除度等于 1 的节点，并将被删除节点的KS 值赋予 1。反复进行以上步骤，直到所有节点都被删除且被赋予 KS 值。1.3 接近中心性接近中心性是指节点到达其他节点的难易程度，假如某个节点越接近其他节点，则该节点向其他节点传播信息越容易。接近中心性为：2 南昌航空大学学报：自然科学版第 37 卷CC(i)=1di=N1Nj=1dij(2)didijij式中，表示某个节点的平均最短路径，为节点和 之间的最短路径距离。1.4 引力模型Li 等12受万有引力的启发，提出了基于引力定律的算法，定义为：SR(i)=dij n 时，O(mn)O(n2)O(n)，通常连边数大于节点数。2.2 示例分析图 1 所示网络中节点在各种排序算法下的排名如表 3 所示。其中，DC 算法认为节点 2、节点3 和节点 4 的重要程度较高，但作为多路径选择中的分支，将其重要性排在前会使信息流通容易局限在区域内部，导致传播效率降低，因此，VDWF 算法认为节点 2、节点 3 和节点 4 的重要性排名相对靠后；KS 算法认为节点 1 的重要程度高于节点 5，但若节点 5 被删除，该网络则不再是连通图，故VDWF 算法认为节点 5 的重要性应高于节点 1；CC、SR、VDWF 算法的排名范围较广，但 CC、SR 算法都认为节点 7 的重要性排名较前，而节点6 与节点 9 之间的信息流通若遇到节点 7 所构成的双路径选择，可能会造成其二阶路径处于空置状态，使得节点 7 的重要程度降低；LLS 算法认为边缘节点 8 的重要性高于节点 10 以及节点 11，其他算法均认为节点 8 的重要性低于节点 10 以及节点 11。通过对比，VDWF 算法能够较为准确地评估各节点的重要性，初步验证了 VDWF算法评估节点重要性的有效性与精确性。3 实验网络与评价指标 3.1 实验网络本文在 6 个来自不同领域的网络上进行实验分析，以更加全面地检验 VDWF 算法对复杂网络节点重要度的评估效果。其中 Everglades 为沼泽地网络16，该网络数据集属于生态网络类别。Cannes 为戛纳的对称图案网络17。Combinatorial为模拟组合网络18，该网络描述了多项式方程组数 表 2 不同评估算法的时间复杂度算法类型时间复杂度DCLocalO(n)KSGlobalO(m+n)CCGlobalO(mn)SRHybridO(n2)LLSLocalO(n)VDWFHybridO(n2)1110123456789 图 1 示例网络 4 南昌航空大学学报：自然科学版第 37 卷字用于模拟组合的问题。Electrophoresis 为 DNA电泳网络19，这是由聚合物中的 7 个单体扩散而成的网络。Matrix 为马尔可夫链转换矩阵网络20。Power 为电力网络21。6 个不同领域网络数据拓扑特征的统计数据如表 4 所示。其中的 N、E、D、和 分别表示整个网络当中的节点个数、边数、密度、平均度值和平均聚类系数。表 4 6 个网络拓扑特征的统计数据网络NEDEverglades699110.388 321260.584 24Cannes1445760.055 94480.740 38Combinatorial2045350.025 83750.024 82Electrophoresis34030840.047 614160.246 80Matrix49618590.016 29170.362 58Power68519670.005 47230.172 47 3.2 评价指标为验证 VDWF 算法的准确性，本文分别从网络的鲁棒性、抗毁性以及排序算法的分辨率等方面进行节点重要度评价实验，采用了单调性指标、网络效率和极大联通系数等评估指标，并将其结果与基于局部信息的度排序(DC)、基于节点位置信息的 K-壳分解法(KS)、基于最短路径的接近中心性(CC)、基于邻域和路径信息的引力模型(SR)以及基于度和邻居节点间的拓扑重合度的邻域相似度(LLS)等指标作对比。M(R)定定义义 1 单调性指标可良好地量化不同排序方法的分辨率，其计算公式为：M(R)=1rRnr(nr1)n(n1)2(9)nrR0,1M(R)式中：表示具有相同关键程度值的节点数量；表示根据不同排序方法得到的排名向量大小；单调性指标量化了排名列表中并列的比例，其取值范围为，若 排 名 向 量 完 全 单 调，则 单 调 性 指 标=1。定定义义 2 网络效率 E 即为节点间距离倒数的平均值，即：E=1N(N1)1ijN1dij(10)iEiE式中：设删除节点 后，剩余网络效率为；网络效率体现了传播能力方面网络抗毁性的强弱，网络效率 越小，说明网络抗毁性越弱、攻击效率越强。Ci定定义义 3 极大连通系数 定义为删除节点 后网络的最大连通分支规模与网络原始规模之比，即：C=NiRN(11)NiRiC式中：表示节点 删除后最大连通分支中的节点数；极大连通系数体现了拓扑结构方面网络抗毁性的强弱，极大连通系数 值越小，说明网络抗毁性越弱、攻击效率越强。定定义义 4 SIR 模型中节点的影响力为传播结束时免疫个体 R 的规模。除免疫个体 R 以外，模型中还有易感染个体 S 以及感染个体 I。其中，免疫个体 R 被治愈后拥有免疫能力，因此该类节点即不会传染，也不会被感染。实验起始时，只有少数感染节点 I，剩余均为易感染节点 S。每个时间步 表 3 示例网络中节点的排名排名1234567891011DCV5V6V9V1V2V3V4V7V10V11V8KSV1V2V3V4V5V6V7V9V10V11V8CCV6V5V9V7V2V3V4V1V10V11V8SRV6V5V9V1V7V2V3V4V10V11V8LLSV6V9V5V2V3V4V1V7V8V10V11VDWFV9V5V6V1V10V11V2V3V4V8V7 第 2 期龚志豪，蒋 沅，代冀阳：基于范德华力的节点重要性评估算法 5 长里，感染节点 I 以感染率 去感染周围的易感染节点 S，并且以恢复率 成为免疫节点 R。直到网络中没有新增的感染节点 I 时实验结束，此时的感染节点 I 数量越多，说明起始时的少数感染节点的传播能力越强。4 仿真实验 4.1 单调性指标分析不同排序算法在 6 个网络中的单调性指标如表 5 所示。可以看出，VDWF 算法在 6 个网络中均具有良好的区分度，并且在Everglades、Combinatorial以及 Matrix 网络中单调性指标达到了 1。这说明在这些网络中，经由 VDWF 算法排序所得到的排名向量完全单调。在其他网络中，VDWF 算法均表现出最优的区分度；其次是 CC 以及 LLS 算法；分辨率最差的是 KS 算法，其在 Matrix 网络中的单调性非常接近于 0，这说明 KS 算法在该网络中所排序的节点大部分具有相同的排名。综上所述，VDWF算法能够更好地区分网络中所有节点的重要程度。4.2 网络效率分析pE选取不同的评估算法攻击节点，被攻击节点的重要程度越高，则其网络效率指标下降越快。实验结果如图 2 所示，其中，表示失效节点个数在整个网络中所占的比例，为网络效率。显然，相较于其他各类算法，VDWF 算法在所有的网络中的攻击效果最为明显，这说明 VDWF 算法能够较为精准地评估节点的影响力。尤其在 Power 网络中，VDWF 算法在删除排序前 10%的节点时，便使得网络效率急剧下降。Electrophoresis 网络中的菱形曲线为根据 CC 算法所得的排序结果攻击网络，当删除排名前 30%的节点时，其攻击效果与 KS 算法类似。这是因为 CC 算法在评估网络中的某些“桥接”节点时，仅侧重与其他节点之间的距离，导致最终结果出现误差。此外，SR、LLS 算法亦有着相对较好的攻击效果。综上，在节点传播能力方面，VDWF 算法的攻击效率优于其他各类算法。表 5 不同排序算法的单调性指标网络DCKSCCSRLLSVDWFEverglades0.950.390.970.9911Cannes0.370.200.600.520.520.87Combinatorial0.650.140.990.990.991Electrophoresis0.800.390.990.980.950.99Matrix0.150.0110.740.381Power0.660.300.990.990.970.99 0.20.40.60.81.0p0.20.40.60.81.0p0.20.40.60.81.0p0.20.40.60.81.0p0.20.40.60.81.0p0.20.40.60.81.0p(a)Everglades00.10.20.30.40.50.60.7EDCKSCCSRLLSVDWFDCKSCCSRLLSVDWFDCKSCCSRLLSVDWFDCKSCCSRLLSVDWFDCKSCCSRLLSVDWFDCKSCCSRLLSVDWF(b)Cannes00.050.100.150.200.25E(c)Combinatorial00.050.100.150.200.250.300.35E(d)Electrophoresis00.050.100.150.200.250.30E(e)Matrix00.020.040.060.080.100.120.14E(f)Power00.020.040.060.080.100.12E 图 2 6 个网络在各类排序算法攻击下网络效率的变化 6 南昌航空大学学报：自然科学版第 37 卷 4.3 极大连通系数分析pC各类评估算法对排序后 6 个网络节点进行攻击，若被攻击的节点重要程度越高，则其极大连通系数指标下降越快。实验结果如图 3 所示，其中，表示失效节点个数在整个网络中所占的比例，为极大连通系数。在大部分网络中，相较于其他算法，采用 VDWF 算法攻击排序靠前的节点使得网络极大连通系数下降的效果最为明显，不仅所攻击的节点数更少，而且所用时间也更短。KS 算法的整体攻击效果较差。在 Cannes 网络中，DC 算法的攻击效果与粗粒化排序的 KS 算法一致，原因是该网络中节点的度值差异较小，此时仅考虑节点局部信息易导致算法的评估效果不精确。而在Combinatorial 网络中，SR、LLS 等算法的攻击效果曲线均出现了不同程度的持平。这是因为该网络中存在着一些连接紧密的节点群，SR、LLS 等算法易将其判断为核心节点，但实际上这些节点群并不在最大连通子图当中，攻击这些节点群并不会成极大连通系数的下降。因此，从节点拓扑结构方面来看，VDWF 算法攻击效果优于其他各类算法。0.20.40.60.81.0p 0.20.40.60.81.0p 0.20.40.60.81.0p 0.20.40.60.81.0p 0.20.40.60.81.0p 0.20.40.60.81.0p(a)Everglades00.20.40.60.81.0CDCKSCCSRLLSVDWFDCKSCCSRLLSVDWFDCKSCCSRLLSVDWFDCKSCCSRLLSVDWFDCKSCCSRLLSVDWFDCKSCCSRLLSVDWF(b)Cannes00.20.40.60.81.0C(c)Combinatorial00.20.40.60.81.0C(d)Electrophoresis00.20.40.60.81.0C(e)Matrix00.20.40.60.81.0C(f)Power00.20.40.60.81.0C 图 3 6 个网络在各类排序算法攻击下极大连通系数的变化 4.4 排名相关性分析VDWF 算法与其他排序算法之间的排名相关性如图 4 所示。其中，横坐标表示经由 VDWF 算法评估得到的节点排名，纵坐标表示经由其他算法排序得到的节点排名，散点的颜色深浅代表节点在 SIR 传播模型中影响力的强弱。由图 4a 所示，除 KS 算法外，其他评估算法均与 VDWF 算法的节点排名呈线性分布，可知 VDWF 算法与其他算法的相关性较高，能够精准评估节点的重要程度。通过分析图 4b 可知，对于在 SIR 模型中影响力一般的节点，VDWF 算法与其他算法的评估结果存在差异。进一步分析图 4c，DC、SR 以及 LLS 算法与 VDWF 算法的相关性同样较高，可知 VDWF 算法能够兼顾网络的局部信息以及节点间的路径信息等特征。因此，VDWF 算法在识别网络中的重要节点方面相较于其他算法的优势更为明显。5 结束语精准度量复杂网络中节点的重要程度对于理论研究以及社会生产都有着重要意义。为增强评估效果，本文将范德华力引入复杂网络中。综合考虑了邻居节点的信息以及节点间拓扑结构，利用节点的影响力以及拓扑信息来体现节点的重要性，提出了一种基于范德华力的重要节点挖掘算法，较好 第 2 期龚志豪，蒋 沅，代冀阳：基于范德华力的节点重要性评估算法 7 10 20 30 40 50 60 70VDWF010203040506070DC10203040506010 20 30 40 50 60 70VDWF01020304050607010203040506010 20 30 40 50 60 70VDWF01020304050607010203040506010 20 30 40 50 60 70VDWF01020304050607010203040506010 20 30 40 50 60 70VDWF010203040506070102030405060KSCCSRLLS(a)Everglades50100150VDWF050100150DC2040608010012014050100150VDWF0501001502040608010012014050100150VDWF0501001502040608010012014050100150VDWF0501001502040608010012014050100150VDWF05010015020406080100120140KSCCSRLLS(b)Cannes50100 150 200 250VDWF05010015020025050100 150 200 250VDWF05010015020025050100 150 200 250VDWF05010015020025050100 150 200 250VDWF05010015020025050100 150 200 250VDWF050100150200250DC50100150200KS20406080100120140160180200CC50100150200SR50100150200LLS20406080100120140160180200(c)Combinatorial 图 4 VDWF 算法与其它排序算法之间的相关性 8 南昌航空大学学报：自然科学版第 37 卷地弥补了度排序、K-壳分解和接近中心性等经典算法评估角度片面的局限性。分别评估了各个算法在 6 个不同领域的真实数据集中的单调性、网络效率以及极大连通系数等指标。结果表明，相比于度排序、K-壳分解法、接近中心性、SR、LLS 等算法，本文所提出的 VDWF 算法评估效果更精准。而如何在有向加权的复杂网络中发挥出同样精准的评估效果将是接下来的研究重点。【参考文献】LI M,LIU R R,LU L,et al.Percolation on complex networks:Theory and application J.Physics reports,2021,907:1-68.1朱军芳,陈端兵,周涛,等.网络科学中相对重要节点挖掘方法综述 J.电子科技大学学报,2019,48(4):595-603.2DIAO M,KONG H,ZHAO J.Impacts of transportation network companies on urban mobility J.Nature sustainability,2021,4(6):494-500.3LUO C,MA Y,JIANG P,et al.The construction and visualization of the transmission networks for COVID-19:A potential solution forcontact tracing and assessments of epidemics J.Scientific reports,2021,11(1):8605.4ELSISI M,TRAN M Q,MAHMOUD K,et al.Effective IoT-based deep learning platform for online fault diagnosis of powertransformers against cyberattacks and data uncertainties J.Measurement,2022,190:110686.5任晓龙,吕琳媛.网络重要节点排序方法综述 J.科学通报,2014,59(13):1175-1197.6杨松青,蒋沅,童天驰,等.基于 Tsallis 熵的复杂网络节点重要性评估方法 J.物理学报,2021,70(21):216401.7NIE T Y,GUO Z,ZHAO K,et al.Using mapping entropy to identify node centrality in complex networks J.Physica A:Statisticalmechanics and its applications,2016,453:290-297.8YANG Y Z,YU L,WANG X,et al.A novel method to evaluate node importance in complex networks J.Physica A:Statisticalmechanics and its applications,2019,526:121118.9HU P,FAN W L,MEI S W.Identifying node importance in complex networks J.Physica A:Statistical mechanics and its applications,2015,429:169-176.10韩忠明,陈炎,李梦琪,等.一种有效的基于三角结构的复杂网络节点影响力度量模型 J.物理学报,2016,65(16):168901.11LI Z,HUANG X Y.Identifying influential spreaders in complex networks by an improved gravity model J.Scientific reports,2021,11(1):22194.12阮逸润,老松杨,王竣德,等.基于领域相似度的复杂网络节点重要度评估算法 J.物理学报,2017,66(3):371-379.13DZYALOSHINSKII I E,LIFSHITZE M,PITAEVSKII L P.The general theory of van der waals forces J.Advances in physics,1961,10(38):165-209.14CHRISTAKIS N A,FOWLER J H.Social contagion theory:Examining dynamic social networks and human behavior J.Statistics inmedicine,2013,32(4):556-577.15TSOPZE N,DOMGUE F G.Boolean factor based community extraction from directed networks with the non reciprocal linkrelationship J.Information sciences,2021,569:544-556.16LIU J W H.Modification of the minimum-degree algorithm by multiple elimination J.ACM transactions on mathematical software(TOMS),1985,11(2):141-153.17YANG F,LI X,XU Y,et al.Ranking the spreading influence of nodes in complex networks:an extended weighted degree centralitybased on a remaining minimum degree decomposition J.Physics letters A,2018,382(34):2361-2371.18YADAV A,GUPTA A K,STEINER A,et al.Mapping the assembly of metalorganic cages into complex coordination networks J.ChemistryA European journal,2017,23(72):18296-18302.19MIYAJIMA S.The relation between two types of error bounds for computed Matrix eigenvalues J.Reliable computing,2012,16:107-113.20CUADRA L,SALCEDO-SANZ S,DEL SER J,et al.A critical review of robustness in power grids using complex networks conceptsJ.Energies,2015,8(9):9211-9265.21 第 2 期龚志豪，蒋 沅，代冀阳：基于范德华力的节点重要性评估算法 9