Abstract：In order to identify important nodes in temporal networks, a node importance evaluation method is proposed in based on inter-layer neighborhood information entropy. Inspired by the directed flows model of temporal networks, the method introduces the parameter ω to fuse the inter-layer neighborhood topology information of node at adjacent snapshots, uses information entropy to describe the complexity of network structure, and also takes into account the global topological information. The effectiveness and applicability of the method is proved by using the SIR propagation model, Kendall correlation coefficient, Top-k metrics, and the proposed method is compared with six evaluation methods on six real datasets. The experimental results demonstrate that the method can more effectively identify the important nodes in the temporal network. Meanwhile, the identification of the nodes of with high importance is more accurate. In addition, the parameter ω can be adjusted to improve the evaluation effect of this method according to the topology of the temporal network. Last but not least, the time complexity of this method is O(mn), which is suitable for large-scale temporal networks.
洪成, 蒋沅, 严玉为, 余荣斌, 杨松青. 基于层间邻域信息熵的时序网络节点重要性评估方法[J]. 复杂系统与复杂性科学, 2024, 21(1): 20-27.
HONG Cheng, JIANG Yuan, YAN Yuwei, YU Rongbin, YANG Songqing. 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.
[1] ALBERT R, BARABÁSI A L. Statistical mechanics of complex networks[J]. Reviews of Modern Physics, 2002, 74(1): 47. [2] BARABÁSI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512. [3] NEWMAN M E J. The structure and function of complex networks[J]. SIAMReview, 2003, 45(2): 167-256. [4] MORONE F, MAKSE H A. Influence maximization in complex networks through optimal percolation[J]. Nature, 2015, 524(7563): 65-68. [5] 杨松青,蒋沅,童天驰,等.基于Tsallis熵的复杂网络节点重要性评估方法[J].物理学报,2021,70(21):273-284. YANG S Q, JIANG Y, TONG T C,et al. A method of evaluating importance of nodes in complex network based on Tsallis entropy[J]. Acta Physica Sinica,2021,70(21):273-284. [6] HOLME P, SARAMÄKI J. Temporal networks[J]. Physics Reports, 2012, 519(3): 97-125. [7] BONACICH P. Factoring and weighting approaches to status scores and clique identification[J]. Journal of Mathematical Sociology, 1972, 2(1): 113-120. [8] WANG Z, PEI X, WANG Y, et al. Ranking the key nodes with temporal degree deviation centrality on complex networks[C]//2017 29th Chinese Control And Decision Conference (CCDC). Piscataway,NJ: IEEE, 2017: 1484-1489. [9] KIM H, ANDERSON R. Temporal node centrality in complex networks[J]. Physical Review E, 2012, 85(2): 026107. [10] TAYLOR D, MYERS S A, CLAUSET A, et al. Eigenvector-based centrality measures for temporal networks[J]. Multiscale Modeling & Simulation, 2015,15(1): 537-574. [11] STEPHENSON K, ZELEN M. Rethinking centrality: methods and examples[J]. Social Networks, 1989, 11(1):1-37. [12] 胡钢,许丽鹏,徐翔.基于时序网络层间同构率动态演化的重要节点辨识[J].物理学报,2021,70(10):355-366. HU G, XU L P,XU X. Identification of important nodes based on dynamic evolution of inter-layer isomorphism rate in temporal networks[J]. Acta Physica Sinica, 2021,70(10):355-366. [13] JIANG J L, FANG H, LI S Q, et al. Identifying important nodes for temporal networks based on the ASAM model[J]. Physica A: Statistical Mechanics and Its Applications, 2022, 586: 126455. [14] QU C, ZHAN X, WANG G, et al.Temporal information gathering process for node ranking in time-varying networks[J]. Chaos: an Interdisciplinary Journal of Nonlinear Science, 2019, 29(3): 033116. [15] OMAR Y M, PLAPPER P. A survey of information entropy metrics for complex networks[J]. Entropy, 2020, 22(12): 1417. [16] LUO L, TAO L, XU H, et al. An information theory based approach for identifying influential spreaders in temporal networks[C]//International Symposium on Cyberspace Safety and Security. Berlin: Springer, 2017: 477-484. [17] MICHALSKI R, JANKOWSKI J, PAZURA P. Entropy-based measure for influence maximization in temporal networks[C]//International Conference on Computational Science. Amsterdam: Springer, Cham, 2020: 277-290. [18] 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). Piscataway,NJ: IEEE, 2017: 1402-1407. [19] LIU J G, LIN J H, GUO Q, et al. Locating influential nodes via dynamics-sensitive centrality[J]. Scientific Reports, 2016, 6(1): 1-8. [20] PASTOR-SATORRAS R, VESPIGNANI A. Epidemic spreading in scale-free networks[J]. Physical Review Letters, 2001, 86(14): 3200. [21] KENDALL M G. A new measure of rank correlation[J]. Biometrika, 1938, 30(1/2): 81-93. [22] YU E Y, FU Y, CHEN X, et al. Identifying critical nodes in temporal networks by network embedding[J]. Scientific Reports, 2020, 10(1): 1-8. [23] KLIMT B, YANG Y. The enron corpus: a new dataset for email classification research[C]//European Conference on Machine Learning. Berlin, Heidelberg: Springer, 2004: 217-226. [24] PARANJAPE A, BENSON A R, LESKOVEC J. Motifs in temporal networks[C]//Proceedings of the Tenth ACM International Conference on Web Search and Data Mining. New York: ACM, 2017: 601-610. [25] FOURNET J, BARRAT A. Contact patterns among high school students[J]. PloS one, 2014, 9(9): e107878. [26] 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. [27] 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.
