Abstract
Identifying important nodes in complex networks can help us effectively design protection strategies, improve the security and protection capabilities of network hub nodes, and enhance the network survivability and structural stability. In view of nodes partition being too coarse by the k-shell decomposition method, this paper proposes a new index named k-shell and degree difference, which considers the network node location, the local characteristics of the node and its neighbors and the impact of multi-level nodes on it. In this paper, the network efficiency index is used to quantify the impact of the node removal on the network structure and function, and the destruction-resistance experiment is carried out in four actual networks. Experimental results show that the method proposed in this paper is more accurately to assess the importance of nodes than other four methods.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Opsahl, T., Agneessens, F., Skvoretz, J.: Node centrality in weighted networks: generalizing degree and shortest paths. Soc. Netw. 32(3), 245–251 (2010)
Ren, X.L., Lü, L.Y.: Review of ranking nodes in complex networks. Chin. Sci. Bull. (Chin. Ver.) 59(59), 1175–1197 (2014). (in Chinese)
Ren, Z.M.: Analysis of the spreading influence of the nodes with minimum K-shell value in complex networks. Acta Phys. Sin. 62(10), 956–959 (2013). (in Chinese)
Balthrop, J., Forrest, S., Newman, M.E., et al.: Computer science. Technological networks and the spread of computer viruses. Science 304(5670), 527–529 (2004)
Kinney, R., Crucitti, P., Albert, R., et al.: Modeling cascading failures in the North American power grid. Eur. Phys. J. B – Condens. Matter Complex Syst. 46(1), 101–107 (2005)
Moreno, Y., Nekovee, M., Pacheco, A.F.: Dynamics of rumor spreading in complex networks. Phys. Rev. E Stat. Nonlinear Soft Matter Phys. 69(6 Pt 2), 066130 (2004)
Sabidussi, G.: The centrality index of a graph. Psychometrika 31(4), 581–603 (1966)
Goh, K.I., Oh, E., Kahng, B., et al.: Betweenness centrality correlation in social networks. Phys. Rev. E Stat. Nonlinear Soft Matter Phys. 67(1 Pt 2), 017101 (2016)
Brin, S., Page, L.: Anatomy of a large-scale hypertextual web search engine. J. Comput. Netw. ISDN Syst. 30, 107–117 (1998)
Ruan, Y.R., Lao, S.Y., Wang, J.D., et al.: Node importance measurement based on neighborhood similarity in complex network. Acta Phys. Sin. 66(3), 038902 (2017). (in Chinese)
Chen, D., Lü, L., Shang, M.S., et al.: Identifying influential nodes in complex networks. Phys. A Stat. Mech. Appl. 391(4), 1777–1787 (2012)
Kitsak, M., Gallos, L.K., Havlin, S., et al.: Identifying influential spreaders in complex networks. Nat. Phys. 6(11), 888–893 (2010)
Liu, Y., Tang, M., Zhou, T., et al.: Core-like groups result in invalidation of identifying super-spreader by k-shell decomposition. Sci. Rep. 5, 9602 (2015)
Liu, Y., Tang, M., Zhou, T., et al.: Improving the accuracy of the k-shell method by removing redundant links: from a perspective of spreading dynamics. Sci. Rep. 5, 13172 (2015)
Shan, B., Tao, F.: Design change control of complex products based on important nodes. Comput. Eng. Appl. 54(6), 222–227 (2018)
Lalou, M., Tahraoui, M.A., Kheddouci, H.: The critical node detection problem in networks: a survey. Comput. Sci. Rev. 28, 92–117 (2018)
Liu, Y., Wei, B., Du, Y., et al.: Identifying influential spreaders by weight degree centrality in complex networks. Chaos Solitons Fractals Interdiscip. J. Nonlinear Sci. Nonequilib. Complex Phenom. 86, 1–7 (2016)
Adebayo, I., Jimoh, A.A., Yusuff, A.: Voltage stability assessment and identification of important nodes in power transmission network through network response structural characteristics. IET Gener. Trans. Distrib. 11(6), 1398–1408 (2017)
Bae, J., Kim, S.: Identifying and ranking influential spreaders in complex networks by neighborhood coreness. Phys. A Stat. Mech. Appl. 395(4), 549–559 (2014)
Ma, L.L., Ma, C., Zhang, H.F., et al.: Identifying influential spreaders in complex networks based on gravity formula. Phys. A Stat. Mech. Appl. 451, 205–212 (2016)
Vragović, I., Louis, E., Díaz-Guilera, A.: Efficiency of informational transfer in regular and complex networks. Phys. Rev. E 71(3 Pt 2A), 036122 (2005)
Latora, V., Marchiori, M.: A measure of centrality based on network efficiency. New J. Phys. 9(6), 188 (2007)
Lusseau, D., Schneider, K., Boisseau, O.J., et al.: The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations. Behav. Ecol. Sociobiol. 54(4), 396–405 (2003)
Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. U. S. A. 99(12), 7821–7826 (2001)
Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393(6684), 440–442 (1998)
White, J.G., Southgate, E., Thomson, J.N., et al.: The structure of the nervous system of the nematode Caenorhabditis elegans. Philos. Trans. Roy. Soc. B Biol. Sci. 314(1165), 1–340 (1986)
Zhou, T., Lü, L., Zhang, Y.C.: Predicting missing links via local information. Eur. Phys. J. B 71(4), 623–630 (2009)
Lai, Y.C., Motter, A.E., Nishikawa, T.: Attacks and cascades in complex networks. In: Ben-Naim, E., Frauenfelder, H., Toroczkai, Z. (eds.) Complex Networks. LNP, vol. 650, pp. 299–310. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-44485-5_14
Acknowledgments
The work was supported by the National Natural Science Foundation of China under Grant Nos. 61370083, 61672179, 61402126, the Heilongjiang Province Natural Science Foundation of China under Grant No. F2015030, the Youth Science Foundation of Heilongjiang Province of China under Grant No. QC2016083, and the Postdoctoral Support of Heilongjiang Province of China under Grant No. LBH-Z14071.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Zhang, J., Xu, H., Yang, J., Lun, L. (2018). Mining and Ranking Important Nodes in Complex Network by K-Shell and Degree Difference. In: Zhou, Q., Gan, Y., Jing, W., Song, X., Wang, Y., Lu, Z. (eds) Data Science. ICPCSEE 2018. Communications in Computer and Information Science, vol 901. Springer, Singapore. https://doi.org/10.1007/978-981-13-2203-7_28
Download citation
DOI: https://doi.org/10.1007/978-981-13-2203-7_28
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-13-2202-0
Online ISBN: 978-981-13-2203-7
eBook Packages: Computer ScienceComputer Science (R0)