复杂网络中基于多特征引力模型的关键节点识别方法

doi:10.16088/j.issn.1001-6600.2025041001

摘要/Abstract

摘要： 关键节点识别一直是社会系统、生物系统、电力系统和交通系统等领域的研究热点。本文提出一种基于多特征的引力模型算法(HKGM)识别复杂网络中有影响力的节点。具体而言,该方法综合考虑节点自身度值、一阶邻居及二阶邻居的局部传播能力,并引入节点全局位置信息,构建兼顾网络局部与全局属性的评估方案。同时,针对大规模网络中算法复杂度与计算成本问题,本研究优化了方案的计算效率。为验证所提方法的有效性,在9个真实数据集上开展仿真实验,将HKGM方法与9种经典算法进行对比评估。实验结果表明,HKGM在SIR模型、Kendall相关系数和CCDF单调函数等评价指标中表现出色,验证本文提出的方法在复杂网络关键节点识别任务中具有更高的区分精度,能够有效提升关键节点检测的准确性。

关键词: 引力模型, H指数, 节点影响力, 关键节点识别, 复杂网络

Abstract: Critical node identification has been a research focus in social system, biological system, power system, and transportation system. Existing works exhibit excessive reliance on node degree, k-shell values, or their simplistic combinations while neglecting the influence of adjacent nodes and global positional information. This article proposes a multi-feature gravity model algorithm, termed as HKGM, to identify key nodes within complex networks. Specifically, the proposed scheme comprehensively considers node degree, local propagation capacity involving both first-order and second-order neighboring nodes, and introduces the global location information of nodes, aiming to construct an evaluation scheme that takes into account both the local and global properties of the network. Meanwhile, in response to the issues of algorithm complexity and computational cost in large-scale networks, this study optimizes the computational efficiency of the proposed scheme. To validate its effectiveness, simulation experiments are conducted on nine real-world datasets, comparing HKGM against nine classical algorithms. Results demonstrate that the proposed method outperforms others under evaluation metrics including the SIR propagation model, Kendall correlation coefficient, and CCDF monotonicity function. These findings confirm that HKGM achieves superior discrimination accuracy in key node identification tasks for complex networks, significantly enhancing detection accuracy.

Key words: gravity model, H-index, node influence, crucial node identification, complex networks

中图分类号: TP39; O157.5

陈斯淋, 刘佳飞, 周何馨, 吴璟莉, 李高仕. 复杂网络中基于多特征引力模型的关键节点识别方法[J]. 广西师范大学学报（自然科学版）, 2026, 44(2): 132-144.

CHEN Silin, LIU Jiafei, ZHOU Hexin, WU Jingli, LI Gaoshi. Critical Node Identification in Complex Network Based on Multi-feature Gravity Model[J]. Journal of Guangxi Normal University(Natural Science Edition), 2026, 44(2): 132-144.

参考文献

[1] 高超, 蒋世洪, 王震, 等.基于动态客流的城市轨道交通关键站点识别[J].中国科学:信息科学, 2021, 51(9):1490-1506.DOI:10.1360/SSI-2020-0303.
[2] SCABINI L F S, RIBAS L C, NEIVA M B, et al.Social interaction layers in complex networks for the dynamical epidemic modeling of COVID-19 in Brazil[J].Physica A:Statistical Mechanics and Its Applications, 2021, 564:125498.DOI:10.1016/j.physa.2020.125498.
[3] BASNARKOV L.SEAIR Epidemic spreading model of COVID-19[J].Chaos, Solitons & Fractals, 2021, 142:110394.DOI:10.1016/j.chaos.2020.110394.
[4] ZHOU D Y, HU F N, WANG S L, et al.Power network robustness analysis based on electrical engineering and complex network theory[J].Physica A:Statistical Mechanics and Its Applications, 2021, 564:125540.DOI:10.1016/j.physa.2020.125540.
[5] LIU Y Y, SONG A B, SHAN X, et al.Identifying critical nodes in power networks:a group-driven framework[J].Expert Systems with Applications, 2022, 196:116557.DOI:10.1016/j.eswa.2022.116557.
[6] BONACICH P.Factoring and weighting approaches to status scores and clique identification[J].Journal of Mathematical Sociology, 1972, 2(1):113-120.DOI:10.1080/0022250X.1972.9989806.
[7] NEWMAN M E J.A measure of betweenness centrality based on random walks[J].Social Networks, 2005, 27(1):39-54.DOI:10.1016/j.socnet.2004.11.009.
[8] FREEMAN L C.Centrality in social networks conceptual clarification[J].Social Networks, 1978, 1(3):215-239.DOI:10.1016/0378-8733(78)90021-7.
[9] BONACICH P, LLOYD P.Eigenvector-like measures of centrality for asymmetric relations[J].Social Networks, 2001, 23(3):191-201.DOI:10.1016/S0378-8733(01)00038-7.
[10] BUZZANCA M, CARCHIOLO V, LONGHEU A, et al.Black hole metric:overcoming the pagerank normalization problem[J].Information Sciences, 2018, 438:58-72.DOI:10.1016/j.ins.2018.01.033.
[11] LÜ L Y, ZHOU T, ZHANG Q M, et al.The H-index of a network node and its relation to degree and coreness[J].Nature Communications, 2016, 7:10168.DOI:10.1038/ncomms10168.
[12] KITSAK M, GALLOS L K, HAVLIN S, et al.Identification of influential spreaders in complex networks[J].Nature Physics, 2010, 6(11):888-893.DOI:10.1038/nphys1746.
[13] ZAREIE A, SHEIKHAHMADI A, JALILI M.Influential node ranking in social networks based on neighborhood diversity[J].Future Generation Computer Systems, 2019, 94:120-129.DOI:10.1016/j.future.2018.11.023.
[14] LI Z, REN T, MA X Q, et al.Identifying influential spreaders by gravity model[J].Scientific Reports, 2019, 9:8387.DOI:10.1038/s41598-019-44930-9.
[15] LIU F, WANG Z, DENG Y.GMM:a generalized mechanics model for identifying the importance of nodes in complex networks[J].Knowledge-Based Systems, 2020, 193:105464.DOI:10.1016/j.knosys.2019.105464.
[16] LI S Y, XIAO F Y.The identification of crucial spreaders in complex networks by effective gravity model[J].Information Sciences, 2021, 578:725-749.DOI:10.1016/j.ins.2021.08.026.
[17] YANG P L, MENG F Y, ZHAO L J, et al.AOGC:an improved gravity centrality based on an adaptive truncation radius and omni-channel paths for identifying key nodes in complex networks[J].Chaos, Solitons & Fractals, 2023, 166:112974.DOI:10.1016/j.chaos.2022.112974.
[18] ZHU S Q, ZHAN J, LI X.Identifying influential nodes in complex networks using a gravity model based on the H-index method[J].Scientific Reports, 2023, 13:16404.DOI:10.1038/s41598-023-43585-x.
[19] LIU Y, CHENG Z J, LI X Q, et al.An entropy-based gravity model for influential spreaders identification in complex networks[J].Complexity, 2023, 2023(1):6985650.DOI:10.1155/2023/6985650.
[20] 左忠义, 刘泽宇, 杨广川.基于引力影响模型的轨道交通网络关键节点识别研究[J].交通运输系统工程与信息, 2025, 25(1):102-112.DOI:10.16097/j.cnki.1009-6744.2025.01.011.
[21] 周明洋, 吴向阳, 曹扬, 等.基于群体影响力的网络传播关键节点选择策略[J].中国科学:信息科学, 2019, 49(10):1333-1342.DOI:10.1360/N112019-00041.
[22] XU G Q, MENG L.A novel algorithm for identifying influential nodes in complex networks based on local propagation probability model[J].Chaos, Solitons & Fractals, 2023, 168:113155.DOI:10.1016/j.chaos.2023.113155.
[23] 罗余, 王建波, 李平, 等.基于多阶邻居传播度量和拓扑特征的高影响力节点识别[J].中国科学:信息科学, 2024, 54(4):944-959.DOI:10.1360/SSI-2023-0201.
[24] 邹艳丽, 姚飞, 汪洋, 等.基于网络结构和潮流追踪的电网关键节点识别[J].广西师范大学学报(自然科学版), 2019, 37(1):133-141.DOI:10.16088/j.issn.1001-6600.2019.01.015.
[25] LIU Y, ZHONG Y B, LI X Y, et al.Vital nodes identificationvia evolutionary algorithm with percolation optimization in complex networks[J].IEEE Transactions on Network Science and Engineering, 2024, 11(4):3838-3850.DOI:10.1109/TNSE.2024.3388994.
[26] CURADO M, TORTOSA L, VICENT J F.A novel measure to identify influential nodes:return random walk gravity centrality[J].Information Sciences, 2023, 628:177-195.DOI:10.1016/j.ins.2023.01.097.
[27] REN G J, ZHANG M, GUO Y S.Node importance evaluation in air route networks based on Laplacian energy relative entropy[J].Journal of Beijing Jiaotong University, 2023, 47(2).DOI:10.11860/j.issn.1673-0291.20220034.
[28] LEE Y L, WEN Y F, XIE W B, et al.Identifying influential nodes on directed networks[J].Information Sciences, 2024, 677:120945.DOI:10.1016/j.ins.2024.120945.
[29] ZENG A, ZHANG C J.Ranking spreaders by decomposing complex networks[J].Physics Letters A,2013, 377(14):1031-1035.DOI:10.1016/j.physleta.2013.02.039.
[30] LIU J, ZHENG J M.Identifying important nodes in complex networks based on extended degree and E-shell hierarchy decomposition[J].Scientific Reports, 2023, 13:3197.DOI:10.1038/s41598-023-30308-5.
[31] COHEN J E.Infectious diseases of humans:dynamics and control[J].JAMA, 1992, 268(23):3381.DOI:10.1001/jama.1992.03490230111047.
[32] 李翔, 李聪, 王建波.复杂网络传播理论流行的隐秩序[M].北京:高等教育出版社, 2020.
[33] KENDALL M G.A new measure of rank correlation[J].Biometrika, 1938, 30(1/2):81-93.DOI:10.1093/biomet/30.1-2.81.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed