为识别时序网络中的重要节点,提出基于层间邻域信息熵的时序网络节点重要性评估方法。受明显路径流网络模型的启发,该方法通过引入参数ω,融合节点在相邻时间快照的层间邻域拓扑信息,使用信息熵来刻画网络结构的复杂性,并且兼顾了相邻时间快照的全局拓扑信息。通过使用SIR传播模型、Kendall相关系数、以及Top-k指标来验证该方法的有效性与适用性,在6个真实数据集上与其他6种评估方法进行比较。实验结果表明,提出的方法能够更为有效的识别出时序网络中的重要节点,同时对重要性排名靠前的节点的识别更为准确;可根据时序网络的拓扑结构调整ω从而提升该方法的评估效果;该方法的时间复杂度仅为O(mn),适用于大型时序网络。
洪成
,
蒋沅
,
严玉为
,
余荣斌
,
杨松青
,
洪成
,
蒋沅
,
严玉为
,
余荣斌
,
杨松青
. 基于层间邻域信息熵的时序网络节点重要性评估方法[J]. 复杂系统与复杂性科学, 2024
, 21(1)
: 20
-27
.
DOI: 10.13306/j.1672-3813.2024.01.003
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.
[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.
