基于改进引力模型的时序网络关键节点识别

doi:10.6040/j.issn.1672-3961.0.2024.199

摘要/Abstract

摘要： 为解决现有时序网络模型在识别关键节点时存在的评估角度单一和计算效率低下的问题,提出一种基于改进引力模型的时序网络关键节点识别算法。该模型综合节点的混合度分解信息和度信息,同时考虑节点的位置因素,能够有效地捕捉网络的局部和全局信息,从而量化节点的结构影响力;使用网络截断半径来定义节点间的距离,有效降低计算复杂度。使用SIR传播模型、肯德尔相关系数和Top-k指标,对6个真实世界的数据集进行试验,结果表明,该模型在识别时间网络的关键节点方面优于其他6种方法。

关键词: 时序网络, 关键节点, 引力模型, 混合度分解

Abstract: To address the limitations of existing temporal network models in identifying critical nodes, which often suffer from narrow evaluation perspectives and low computational efficiency, an improved gravity model was proposed for key node recognition. This model integrated both the mixed degree decomposition and degree information of nodes while accounting for their positional influence, effectively capturing both local and global structural characteristics to quantify node importance. The computational complexity was reduced by defining the distance between nodes using a truncated network radius. Experiments were conducted on six real-world datasets using the SIR propagation model, Kendall's correlation coefficient, and Top-k metrics. Results demonstrated that the proposed model outperformed six other methods in identifying critical nodes in temporal networks.

Key words: time series networks, key nodes, gravity model, mix degree decomposition

中图分类号:

TP301

蒋沅,施佳文,黎俊亮,刘宇,吴珑雪. 基于改进引力模型的时序网络关键节点识别[J]. 山东大学学报 (工学版), 2026, 56(1): 26-34.

JIANG Yuan, SHI Jiawen, LI Junliang, LIU Yu, WU Longxue. Critical node identification for time series networks based on improved gravity model[J]. Journal of Shandong University(Engineering Science), 2026, 56(1): 26-34.

参考文献

[1] 杨松青, 蒋沅, 童天驰, 等. 基于Tsallis熵的复杂网络节点重要性评估方法[J]. 物理学报, 2021, 70(21): 267-278. YANG Songqing, JIANG Yuan, TONG Tianchi, et al. A method of evaluating the importance of nodes in complex network nodes based on Tsallis entropy[J]. Acta Physica Sinica, 2021, 70(21): 273-284.
[2] BONACICH P. Factoring and weighting approaches to status scores and clique identification[J].The Journal of Mathematical Sociology, 1972, 2(1): 113-120.
[3] FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1): 35-41.
[4] SABIDUSSI G. The centrality index of a graph[J]. Psychometrika, 1966, 31(4): 581-603.
[5] 龚志豪, 蒋沅, 代冀阳. 基于范德华力的节点重要性评估算法[J]. 南昌航空大学学报(自然科学版), 2023, 37(2): 1-9. GONG Zhihao, JIANG Yuan, DAI Jiyang. Node importance evaluation algorithm based on van der waals force[J]. Journal of Nanchang Hangkong University(Natural Sciences), 2023, 37(2): 1-9.
[6] SEIDMAN S B. Network structure and minimum degree[J]. Social Networks, 1983, 5(3): 269-287.
[7] ZENG A, ZHANG C J. Ranking spreaders by decomposing complex networks[J]. Physics Letters A, 2013, 377(14): 1031-1035.
[8] MA L L, MA C, ZHANG H F, et al. Identifying influential spreaders in complex networks based on gravity formula[J].Physica A: Statistical Mechanics and its Applications, 2016, 451: 205-212.
[9] LI Z, REN T, MA X Q, et al. Identifying influential spreaders by gravity model[J]. Scientific Reports, 2019, 9(1): 8387.
[10] YANG X, XIAO F Y. An improved gravity model to identify influential nodes in complex networks based on k-shell method[J]. Knowledge-Based Systems, 2021, 227: 107198.
[11] 阮逸润, 老松杨, 汤俊, 等. 基于引力方法的复杂网络节点重要度评估方法[J]. 物理学报, 2022, 71(17): 264-275. RUAN Yirun, LAO Songyang, TANG Jun, et al. Node importance ranking method in complex network based on gravity method[J]. Acta Physica Sinica, 2022, 71(17): 264-275.
[12] JIANG Y, YANG S Q, YAN Y W, et al. A novel method for identifying influential nodes in complex networks based on gravity model[J]. Chinese Physics B, 2022, 31(5): 58903.
[13] KIM H, ANDERSON R. Temporal node centrality in complex networks[J]. Physical Review E, 2012, 85(2): 26107.
[14] WANG Z Q, PEI X B, WANG Y B, et al. Ranking the key nodes with temporal degree deviation centrality on complex networks[C] //2017 29th Chinese Control and Decision Conference(CCDC). Chongqing, China: IEEE, 2017: 1484-1489.
[15] HUANG D W, YU Z G. Dynamic-sensitive centrality of nodes in temporal networks[J]. Scientific Reports, 2017, 7:41454.
[16] QU C Q, ZHAN X X, WANG G H, et al. Temporal information gathering process for node ranking in time-varying networks[J]. Chaos: An Interdisciplinary Journal of Nonlinear Science, 2019, 29(3): 33116.
[17] 邓志文, 李新春, 孔杰, 等. 基于层间互信息的时序网络节点重要性识别方法[J]. 运筹与管理, 2023, 32(8): 108-113. DENG Zhiwen, LI Xinchun, KONG Jie, et al. Node importance recognition method of temporal network based on mutual information between layers[J]. Operations Research and Management Science, 2023, 32(8): 108-113.
[18] 胡钢, 牛琼, 王琴, 等. 时序多层网络熵值结构洞节点重要性建模[J]. 浙江大学学报(工学版), 2023, 57(4): 719-725. HU Gang, NIU Qiong, WANG Qin, et al. Modeling of node importance in entropy-value structured hole of temporal multilayer network[J]. Journal of Zhejiang University(Engineering Science), 2023, 57(4): 719-725.
[19] 龚志豪, 蒋沅, 代冀阳, 等. 基于交叉熵的节点重要性排序算法[J].电子科技大学学报, 2023, 52(6): 944-953. GONG Zhihao, JIANG Yuan, DAI Jiyang, et al. Node importance ranking algorithm based on cross entropy[J]. Journal of University of Electronic Science and Technology of China, 2023, 52(6): 944-953.
[20] MAO J, ZOU D, SHENG L, et al. Identify critical nodes in complex network with large language models[EB/OL].(2024-03-01)[2024-08-10]. https://arxiv.org/abs/2403.03962
[21] BI J L, JIN J, QU C Q, et al. Temporal gravity model for important node identification in temporal networks[J]. Chaos, Solitons & Fractals, 2021, 147: 110934.
[22] 严玉为, 蒋沅, 杨松青, 等. 基于时间序列的网络失效模型[J]. 物理学报, 2022, 71(8): 325-333. YAN Yuwei, JIANG Yuan, YANG Songqing, et al. Network failure model based on time series [J]. Acta Physica Sinica, 2022, 71(8): 325-333.
[23] PASTOR-SATORRAS R, VESPIGNANI A. Epidemic spreading in scale-free networks[J]. Physical Review Letters, 2001, 86(14): 3200-3203.
[24] KENDALL M G. A new measure of rank correlation[J].Biometrika, 1938, 30(2): 81-93.
[25] ALSHAHRANI M, ZHU F X, SAMEH A, et al. Efficient algorithms based on centrality measures for identification of top-K influential users in social networks[J]. Information Sciences, 2020, 527: 88-107.
[26] YU E Y, FU Y, CHEN X, et al. Identifying critical nodes in temporal networks by network embedding[J]. Scientific Reports, 2020, 10: 12494.
[27] 洪成, 蒋沅, 严玉为, 等. 基于层间邻域信息熵的时序网络节点重要性评估方法[J]. 复杂系统与复杂性科学, 2024, 21(1): 20-27. HONG Cheng, JIANG Yuan, YAN Yuwei, et al. A method of evaluating importance of nodes in temporal networks based on inter-layer neighborhood information entropy[J]. Complex Systems and Complexity Science, 2024, 21(1): 20-27.
[28] GÉNOIS M, VESTERGAARD C L, FOURNET J, et al. Data on face-to-face contacts in an office building suggest a low-cost vaccination strategy based on community linkers[J]. Network Science, 2015, 3(3): 326-347.
[29] FOURNET J, BARRAT A. Contact patterns among high school students[J]. PLoS One, 2014, 9(9): 107878.
[30] MASTRANDREA R, FOURNET J, BARRAT A. Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys[J]. PLoS One, 2015, 10(9): 13400.
[31] ISELLA L,STEHLÉ J, BARRAT A, et al. What's in a crowd? Analysis of face-to-face behavioral networks[J]. Journal of Theoretical Biology, 2011, 271(1): 166-180.
[32] KLIMT B, YANG Y. The enron corpus: a new dataset for email classification research[C] //European Conference on Machine Learning. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004: 217-226.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed