Vital nodes identification by the hybrid K-shell method based on vertex strength

doi:10.3969/j.issn.1000-5641.2019.03.011

Abstract

Abstract: In complex networks, evaluating the importance of individual nodes is of great significance to studying the structure of the network and the propagation process. Based on the location of nodes, the K-shell decomposition algorithm can identify key nodes well; however, it results in many nodes with the same K-shell (Ks) value. Meanwhile, most other algorithms only consider local or global indicators, which can lead to a single factor in judging the importance of a node. In order to better identify key nodes, we propose the extended K-shell and degree of neighbors (EKSDN) algorithm, which considers the global index weighted kernel value of the node and the local index degree of the node comprehensively. A comparison of our experimental results with results from the SIR (Susceptible-Infectious-Recovered) model on real complex networks, show that the proposed algorithm can better quantify the influence of a node.

Key words: complex network, vital nodes, K-shell decomposition algorithm, weighted kernel value, degree index

CLC Number:

TP391

WANG Huan, ZHU Min. Vital nodes identification by the hybrid K-shell method based on vertex strength[J]. Journal of East China Normal University(Natural Sc, 2019, 2019(3): 101-109.

References

[1] LAWYER G. Understanding the influence of all nodes in a network[J]. Scientific Reports, 2015(5):8665.
[2] LÜ L Y, CHEN D B, REN X L, et al. Vital nodes identification in complex networks[J]. Physics Reports, 2016, 650:1-63.
[3] BONACICH P. Factoring and weighting approaches to status scores and clique identification[J]. Journal of Mathematical Sociology, 1972, 2(1):113-120.
[4] FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1):35-41.
[5] BONACICH P. Some unique properties of eigenvector centrality[J]. Social Networks, 2007, 29(4):555-564.
[6] LATORA V, MARCHIORI M. Efficient behavior of small-world networks.[J]. Physical Review Letters, 2001, 87(19):198701.
[7] WENG J S, LIM E P, JIANG J, et al. TwitterRank:finding topic-sensitive influential twitterers[C]//Proceedings of the 3rd International Conference on Web Search and Web Data Mining, WSDM 2010. ACM, 2010:261-270.
[8] HIRSCH J E. An index to quantify an individual's scientific research output[J]. Proceedings of the National Academy of Sciences of the United States of America, 2005, 102(46):16569-16572.
[9] POULIN R, BOILY M C, MâSSE B R. Dynamical systems to define centrality in social networks[J]. Social Networks, 2000, 22(3):187-220.
[10] CHEN D B, LÜ 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.
[11] FEI L G, DENG Y. A new method to identify influential nodes based on relative entropy[J]. Chaos Solitons & Fractals, 2017, 104:257-267.
[12] KITSAK M, GALLOS L K, HAVLIN S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6(11):888-893.
[13] ZENG A, ZHANG C J. Ranking spreaders by decomposing complex networks[J]. Physics Letters A, 2013, 377(14):1031-1035.
[14] WEI B, LIU J, WEI D J, et al. Weighted k-shell decomposition for complex networks based on potential edge weights[J]. Physica A:Statistical Mechanics and its Applications, 2015, 420:277-283.
[15] BAE J, KIM S. Identifying and ranking influential spreaders in complex networks by neighborhood coreness[J]. Physica A:Statistical Mechanics and its Applications, 2014, 395(4):549-559.
[16] YANG F, ZHANG R S, YANG Z, et al. Identifying the most influential spreaders in complex networks by an Extended Local K-Shell Sum[J]. International Journal of Modern Physics C, 2017, 28(1):925-214.
[17] RUAN Y R,LAO S Y, XIAO Y D, et al. Identifying influence of nodes in complex networks with coreness centrality:Decreasing the impact of densely local connection[J]. Chinese Physics Letters, 2016, 33(2):149-152.
[18] ZACHARY W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977, 33(4):452-473.
[19] NEWMAN M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E:Statistical Nonlinear & Soft Matter Physics, 2006, 74(3 Pt 2):036104.
[20] LESKOVEC J, LANG K J, DASGUPTA A, et al. Community structure in large networks:Natural cluster sizes and the absence of large well-defined clusters[J]. Internet Mathematics, 2009, 6(1):29-123.
[21] GUIMERÀ R, DANON L, DÍAZ-GUILERA A, et al. Self-similar community structure in a network of human interactions[J]. Physical Review E:Statistical Nonlinear & Soft Matter Physics, 2003, 68(6 Pt 2):065103.
[22] NWEMAN M E. Spread of epidemic disease on networks[J]. Physical Review E:Statistical Nonlinear & Soft Matter Physics, 2002, 66(1 Pt 2):016128.
[23] BALKEW T, MODEL S, RATE R R, et al. The SIR Model When S(t) is a Multi-Exponential Function[J]. Dissertations & Theses-Gradworks, 2010, 14(6):50-50.
[24] WANG X Y. An image blocks encryption algorithm based on spatiotemporal chaos[J]. Nonlinear Dynamics, 2012, 67(1):365-371.