Journal of East China Normal University(Natural Science) >

2019 , Vol. 2019 >Issue 3: 101 - 109

DOI: https://doi.org/10.3969/j.issn.1000-5641.2019.03.011

Computer Science

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

  • WANG Huan ,
  • ZHU Min
Expand
  • 1. Department of Computer Science and Technology, East China Normal University, Shanghai 200062, China;
    2. The Computer Center, East China Normal University, Shanghai 200062, China

Received date: 2018-04-09

  Online published: 2019-05-30

Fold

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

Cite this article

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 Science), 2019 , 2019(3) : 101 -109 . DOI: 10.3969/j.issn.1000-5641.2019.03.011

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.
Options
Outlines

/

〈 〉