Abstract：Focused on the issue that the connection mode and activity of nodes in the identification of important nodes in temporal networks are changed with time, and the complexity of the network structure around nodes is considered. In this paper, a new algorithm called Temporal Penalized Local structure Entropy Advancement (TPLEA) was proposed to identify important nodes. The algorithm was combined with the time window graph model and the Penalty Local Structure Entropy Advancement (PLEA) model, and introduced node activity weight and the contribution rate weight of node degree to determine the comprehensive weight of the node, and finally obtained the importance of each node. The effectiveness and applicability of the method were verified on six real datasets, and ablation experiments were carried out on the introduced weight factors. The experimental results show that this method can effectively identify the important nodes in the temporal network, and the comprehensive weight factors of the nodes have a great influence on the recognition effect of this method.
余路粉, 孙文静, 潘文林, 张天军, 胡志涛, 聂腾涛. 基于加权惩罚局部结构熵的时序网络重要节点识别[J]. 复杂系统与复杂性科学, 2026, 23(2): 57-66.
YU Lufen, SUN Wenjing, PAN Wenlin, ZHANG Tianjun, HU Zhitao, NIE Tengtao. Identification of Important Nodes in Temporal Networks Based on Weighted Penalty Local Structure Entropy[J]. Complex Systems and Complexity Science, 2026, 23(2): 57-66.
[1] 任晓龙,吕琳媛.网络重要节点排序方法综述[J].科学通报,2014,59(13):1175-1197. REN X L, LÜ L Y. Review of ranking nodes in complex networks[J]. Chinese Science Bulletin, 2014, 59(13): 1175-1197. [2] 陈诗,任卓明,刘闯,等.时序网络中关键节点的识别方法研究进展[J].电子科技大学学报,2020,49(2):291-314. CHEN S, REN Z M, LIU C, et al. Identification methods of vital nodes on temporal networks[J]. Journal of University of Electronic Science and Technology of China, 2020, 49(2): 291-314. [3] 贾汉,韩益亮,吴旭光.基于时序和TOPSIS的社交网络节点重要性评价算法[J].山东大学学报(理学版),2020, 55(5): 88-94. JIA H, HAN Y L, WU X G. Node importance evaluation algorithm for complex network based on time series and TOPSIS[J]. Journal of Shandong University (Natural Science), 2020, 55(5): 88-94. [4] HU W, ZOU H, GONG Z. Temporal pagerank on social networks[C]//Web Information Systems Engineering-WISE 2015: 16th International Conference. Miami, FL, USA:Springer International Publishing, 2015. [5] PSALTOGLOU A, CALLE E. Enhanced connectivity index-a new measure for identifying critical points in urban public transportation networks[J]. International Journal of Critical Infrastructure Protection, 2018, 21: 22-32. [6] HOSSEINZADEH M M, CANNATARO M, GUZZI P H, et al. Temporal networks in biology and medicine: a survey on models, algorithms, and tools[J]. Network Modeling Analysis in Health Informatics and Bioinformatics, 2022, 12(1): 10. [7] BONACICH P. Factoring and weighting approaches to status scores and clique identification[J]. Journal of Mathematical Sociology, 1972, 2(1): 113-120. [8] FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1): 35-41. [9] SABIDUSSI G. The centrality index of a graph[J]. Psychometrika, 1966, 31(4): 581-603. [10] BRIN S, PAGE L. The anatomy of a large-scale hypertextual web search engine[J]. Computer Networks and ISDN Systems, 1998, 30(1-7): 107-117. [11] KITSAK M, GALLOS L K, HAVLIN S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6(11): 888-893. [12] 李鹏,王世林,陈光武,等.基于改进的局部结构熵复杂网络重要节点挖掘[J].计算机应用,2023,43(4):1109-1114. LI P, WANG S, CHEN G, et al. Key node mining in complex network based on improved local structural entropy[J]. Journal of Computer Applications, 2023, 43(4): 1109-1114. [13] TANG J, MUSOLESI M, MASCOLO C, et al. Analysing information flows and key mediators through temporal centrality metrics[C]//Proceedings of the 3rd Workshop on Social Network Systems. New York, USA: Association for Computing Machinery, 2010: 1-6. [14] TANG J, MUSOLESI M, MASCOLO C, et al. Temporal distance metrics for social network analysis[C]//Proceedings of the 2nd ACM workshop on Online social networks. Barcelona, Spain: ACM, 2009: 31-36. [15] KIM H, ANDERSON R. Temporal node centrality in complex networks[J]. Physical Review E, 2012, 85(2): 026107. [16] WANG Z, PEI X, WANG Y, et al. Ranking the key nodes with temporal degree deviation centrality on complex networks[C]//29th Chinese Control And Decision Conference (CCDC). Piscataway, NJ: IEEE, 2017: 1484-1489. [17] YE Z, ZHAN X, ZHOU Y, et al. Identifying vital nodes on temporal networks: an edge-based k-shell decomposition[C]//2017 36th Chinese Control Conference (CCC). Dalian, China: IEEE, 2017: 1402-1407. [18] TAYLOR D, MYERS S A, CLAUSET A, et al. Eigenvector-based centrality measures for temporal networks[J]. Multiscale Modeling & Simulation, 2017, 15(1): 537-574. [19] 杨剑楠,刘建国,郭强.基于层间相似性的时序网络节点重要性研究[J]. 物理学报, 2018, 67(4): 279-286. YANG J N, LIU J G, GUO Q. Node importance idenfication for temporal network based on inter-layer similarity[J]. Acta Physica Sinica, 2018, 67(4): 279-286. [20] ROZENSHTEIN P, GIONIS A. Temporal pageRank[C]//Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016. Riva del Garda, Italy: Springer International Publishing, 2016. [21] 胡钢,牛琼,王琴,等.时序多层网络熵值结构洞节点重要性建模[J]. 浙江大学学报 (工学版), 2023, 57(4): 719-725. HU G, NIU Q, WANG Q, 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. [22] 洪成,蒋沅,严玉为,等.基于层间邻域信息熵的时序网络节点重要性评估方法[J].复杂系统与复杂性科学, 2024, 21(1):20-27. HONG C, JIANG Y, YAN Y W, et al. A method of evaluating importance of nodes in temporal network based on inter-layer neighborhood information entropy[J]. Complex Systems and Complexity Science, 2024, 21(1):20-27. [23] BI J, JIN J, QU C, et al. Temporal gravity model for important node identification in temporal networks[J]. Chaos, Solitons & Fractals, 2021, 147: 110934. [24] 李盛庆,姜久雷,方辉,等.一种时序网络建模方法及重要节点识别方法:中国,CN202110372657.0[P/OL]. (2021-04-07)[2021-06-25].http://static.tianyancha.com/patent/contentPDF/96476b03cfdc679606e8a04c77e5074e.pdf. LI S Q, JIANG J L, FANG J, et al. A temporal network modeling method and an important node identification method: China, CN202110372657.0[P/OL]. (2021-04-07)[2021-06-25].http://static.tianyancha.com/patent/contentPDF/96476b03cfdc679606e8a04c77e5074e.pdf. [25] FERREIRA A. Building a reference combinatorial model for MANETs[J]. IEEE Network, 2004, 18(5): 24-29. [26] FOURNET J, BARRAT A. Contact patterns among high school students[J]. PLOS One, 2014, 9(9): e107878. [27] VANHEMS P, BARRAT A, CATTUTO C, et al. Estimating potential infection transmission routes in hospital wards using wearable proximity sensors[J]. PLOS One, 2013, 8(9): e73970. [28] GENOIS M, BARRAT A. Can co-location be used as a proxy for face-to-face contacts?[J]. EPJ Data Science, 2018, 7(1): 1-18. [29] ISELLA L, STEHLE 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. [30] GEMMETTO V, BARRAT A, CATTUTO C. Mitigation of infectious disease at school: targeted class closure vs school closure[J]. BMC Infectious Diseases, 2014, 14(1): 1-10. [31] 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): e0136497. [32] KENDALL M G. A new measure of rank correlation[J]. Biometrika, 1938, 30(1/2): 81-93.
