复杂网络中的关键节点能够影响系统功能,许多真实网络中存在数目显著的三元闭包模体,为了探索该模体对节点重要度的影响,提出了基于三元闭包模体的关键节点识别方法。该算法衡量了各个模体的重要度,通过模体权重和节点度来评估节点重要度。在6个真实网络中,进行了鲁棒性实验和基于SIR模型的传播实验。实验结果表明,相比于度中心性DC、K-shell分解、WL中心性、映射熵ME方法,该算法能够更加有效地识别出网络中的关键节点。
Critical nodes in complex networks can influence the system functionality. Many real networks have a significant number of closed triangle motifs. To explore the influence of these motifs on the importance of nodes, a critical nodes identification method based on closed triangle motifs is proposed. The algorithm measures the importance of each motif and evaluates the node importance through the motif weights and node degrees. Robustness experiments and propagation experiments based on the SIR model are carried out with six real networks. The experimental results show that this method can identify critical nodes of the network more effectively than the DC method, K-shell method, WL method, and ME method.
[1] LI X Y, LI W K, ZENG M, et al. Network-based methods for predicting essential genes or proteins: a survey[J]. Briefings in Bioinformatics, 2020, 21(2): 566-583.
[2] ZHANG Y P, BAO Y Y, ZHAO S, et al. Identifying node importance by combining betweenness centrality and katz centrality [C]// Proc of International Conference on CCBD. Piscataway, NJ: IEEE Press, 2015: 354-357.
[3] ALBERT R, JEONG H, BARABASI A L. Internet: diameter of the world-wide web[J]. Nature, 1999, 401(6): 130-131.
[4] FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1): 35-41.
[5] KITSAK M, GALLOS L K, HAVLIN S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6(11): 888-893.
[6] 王建伟, 荣莉莉, 郭天柱. 一种基于局部特征的网络节点重要性度量方法[J]. 大连理工大学学报, 2010, 50(5): 822-826.
WANG J W, RONG L L, GUO T Z. A network node importance measurement method based on local characteristics[J]. Journal of Dalian University of Technology, 2010, 50(5): 822-826.
[7] NIE T Y, GUO Z, ZHAO K, et al. Using mapping entropy to identify node centrality in complex networks[J]. Physica A: Statistical Mechanics and Its Applications, 2016, 453: 290-297.
[8] MILO R, SHEN O S, LTZKOVITZ S, et al. Network motifs: simple building blocks of complex networks[J]. Science, 2002, 298(5594): 824-827.
[9] BENSON A R, GLEICH D F, LESKOVEC J. Higher-order organization of complex networks[J]. Science, 2016, 353(6295): 163-166.
[10] SHEN O S, MILO R, MANGAN S, et al. Network motifs in the transcriptional regulation network of Escherichia coli[J]. Nature Genetics, 2002, 31(1): 64-68.
[11] SHIZUKA D, MCDONALD D B. The network motif architecture of dominance hierarchies[J]. Journal of the Royal Society Interface, 2015, 12(105): 20150080.
[12] WANG P, LYU J H, YU X H. Identification of important nodes in directed biological networks: a network motif approach[J]. Plos One, 2014, 9(8): e106132.
[13] TOPIRCEANU A, DUMA A, UDRESCU M. Uncovering the fingerprint of online social networks using a network motif based approach[J]. Computer Communications, 2016, 73(1): 167-175.
[14] BIANCONI G, DARST R K, IACOVACCI J, et al. Triadic closure as a basic generating mechanism of communities in complex networks[J]. Physical Review E: Statistical Nonlinear and Soft Matter Physics, 2014, 90(4): 042806.
[15] LI P Z, HUANG L, WANG C D, et al. Community detection using attribute homogenous motif[J]. IEEE Access, 2018, 6: 47707-47716.
[16] XU M Q, PAN Q, MUSCOLONI A, et al. Modular gateway-ness connectivity and structural core organization in maritime network science[J]. Nature Communications, 2020, 11(1): 1-15.
[17] KOVACS I A, BARABASI A L. Destruction perfected[J]. Nature, 2015, 524(7563): 38-9.
[18] SIEW C S Q. The orthographic similarity structure of English words: insights from network science[J]. Applied Network Science, 2018, 3(1): 1-18.
[19] LIU Z H, JIANG C, WANG J Y, et al. The node importance in actual complex networks based on a multi-attribute ranking method[J]. Knowledge-Based Systems, 2015, 84(8): 56-66.
[20] ATKESON A. On using SIR models to model disease scenarios for COVID-19[J]. Quarterly Review, 2020, 41(1): 1-35.
[21] MAJI G, MANDAL S, SEN S. A systematic survey on influential spreaders identification in complex networks with a focus on K-shell based techniques[J]. Expert Systems with Applications, 2020, 16: 113681.
[22] CHEN C Y, ZHAO Y, GAO J X, et al. Nonlinear model of cascade failure in weighted complex networks considering overloaded edges[J]. Scientific Reports, 2020, 10(1): 1-12.
[23] HUANG K K, WANG Z, JUSUP M. Incorporating latent constraints to enhance inference of network structure[J]. IEEE Transactions on Network Science and Engineering, 2018, 7(1): 466-475.
[24] DEY A K, GEL Y R, POOR H V. What network motifs tell us about resilience and reliability of complex networks[J]. Proceedings of the National Academy of Sciences, 2019, 116(39): 19368-19373.
[25] SHAO C C, CIAMPAGLIA G L, VAROL O, et al. The spread of low-credibility content by social bots[J]. Nature Communications, 2018, 9(1): 1-9.
[26] LI X, LIU Y Y, ZHAO C L, et al. Locating multiple sources of contagion in complex networks under the SIR model[J]. Applied Sciences, 2019, 9(20): 4472.
[27] CASTELLANO C, PASTOR S R. Thresholds for epidemic spreading in networks[J]. Physical Review Letters, 2010, 105(21): 218701.
[28] CHEN D B, LYU L Y, SHANG M S, et al. Identifying influential nodes in complex networks[J]. Physica A: Statistical Mechanics and Its Applications, 2012, 391(4): 1777-1787.
[29] POSSI R, AHMED N. The network data repository with interactive graph analytics and visualization [C]// Proc of 29th AAAI Conference on Artificial Intelligence. Palo Alto, CA: AAAI Press, 2015: 4292-4293.
