×

Identifying influential spreaders in complex networks based on improved k-shell method. (English) Zbl 07528392

Summary: Identifying influential spreaders in complex networks is a fundamental network project. It has drawn great attention in recent years because of its great theoretical significance and practical value in some fields. K-shell is an efficient method for identifying influential spreaders. However, k-shell neglects information about the topological position of the nodes. In this paper, we propose an improved algorithm based on the k-shell and node information entropy named IKS to identify influential spreaders from the higher shell as well as the lower shell. The proposed method employs the susceptible-infected-recovered (SIR) epidemic model, Kendall’s coefficient \(\tau\), the monotonicity M, and the average shortest path length \(L_s\) to evaluate the performance and compare with other benchmark methods. The results of the experiment on eight real-world networks show that the proposed method can rank the influential spreaders more accurately. Moreover, IKS has superior computational complexity and can be extended to large-scale networks.

MSC:

82-XX Statistical mechanics, structure of matter

Software:

KONECT
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Zareie, A.; Sheikhahmadi, A., A hierarchical approach for influential node ranking in complex social networks, Expert Syst. Appl., 93, 200-211 (2018)
[2] Chen, D.; Lü, L.; Shang, M.-S.; Zhang, Y.-C.; Zhou, T., Identifying influential nodes in complex networks, Physica A, 391, 4, 1777-1787 (2012)
[3] Yu, H.; Cao, X.; Liu, Z.; Li, Y., Identifying key nodes based on improved structural holes in complex networks, Physica A, 486, 318-327 (2017)
[4] Jiang, Z.-Y.; Zeng, Y.; Liu, Z.-H.; Ma, J.-F., Identifying critical nodes’ group in complex networks, Physica A, 514, 121-132 (2019)
[5] Wang, Z.; Wang, L.; Szolnoki, A.; Perc, M., Evolutionary games on multilayer networks: a colloquium, Eur. Phys. J., 88, 5, 124 (2015)
[6] Medo, M.; Zhang, Y.-C.; Zhou, T., Adaptive model for recommendation of news, Europhys. Lett., 88, 3, 38005 (2009)
[7] Lü, L.; Zhang, Y.-C.; Yeung, C. H.; Zhou, T., Leaders in social networks, the delicious case, PLoS One, 6, 6, Article e21202 pp. (2011)
[8] Wang, Z.; Andrews, M. A.; Wu, Z.-X.; Wang, L.; Bauch, C. T., Coupled disease-behavior dynamics on complex networks: A review, Phys. Life Rev., 15, 1-29 (2015)
[9] Morone, F.; Min, B.; Bo, L.; Mari, R.; Makse, H. A., Collective influence algorithm to find influencers via optimal percolation in massively large social media, Sci. Rep., 6, 30062 (2016)
[10] Yang, L.; Qiao, Y.; Liu, Z.; Ma, J.; Li, X., Identifying opinion leader nodes in online social networks with a new closeness evaluation algorithm, Soft Comput., 22, 2, 453-464 (2018)
[11] Purevsuren, D.; Cui, G., Efficient heuristic algorithm for identifying critical nodes in planar networks, Comput. Oper. Res., 106, 143-153 (2019) · Zbl 1458.90622
[12] Wen, T.; Duan, S.; Jiang, W., Node similarity measuring in complex networks with relative entropy, Commun. Nonlinear Sci. Numer. Simul., 104867 (2019) · Zbl 1476.05184
[13] Rahimkhani, K.; Aleahmad, A.; Rahgozar, M.; Moeini, A., A fast algorithm for finding most influential people based on the linear threshold model, Expert Syst. Appl., 42, 3, 1353-1361 (2015)
[14] Gao, S.; Ma, J.; Chen, Z.; Wang, G.; Xing, C., Ranking the spreading ability of nodes in complex networks based on local structure, Physica A, 403, 130-147 (2014) · Zbl 1395.05158
[15] Zhao, Y.; Li, S.; Jin, F., Identification of influential nodes in social networks with community structure based on label propagation, Neurocomputing, 210, 34-44 (2016)
[16] Sheikhahmadi, A.; Nematbakhsh, M. A.; Shokrollahi, A., Improving detection of influential nodes in complex networks, Physica A, 436, 833-845 (2015)
[17] Lv, Z.; Zhao, N.; Xiong, F.; Chen, N., A novel measure of identifying influential nodes in complex networks, Physica A, 523, 488-497 (2019)
[18] Freeman, L. C., Centrality in social networks conceptual clarification, Soc. Netw., 1, 3, 215-239 (1978)
[19] Sabidussi, G., The centrality index of a graph, Psychometrika, 31, 4, 581-603 (1966) · Zbl 0152.22703
[20] Freeman, L. C., A set of measures of centrality based on betweenness, Sociometry, 35-41 (1977)
[21] Bae, J.; Kim, S., Identifying and ranking influential spreaders in complex networks by neighborhood coreness, Physica A, 395, 549-559 (2014) · Zbl 1395.92139
[22] Wang, J.; Hou, X.; Li, K.; Ding, Y., A novel weight neighborhood centrality algorithm for identifying influential spreaders in complex networks, Physica A, 475, 88-105 (2017)
[23] Zeng, A.; Zhang, C.-J., Ranking spreaders by decomposing complex networks, Phys. Lett. A, 377, 14, 1031-1035 (2013)
[24] Liu, J.-G.; Wang, Z.-Y.; Guo, Q.; Guo, L.; Chen, Q.; Ni, Y.-Z., Identifying multiple influential spreaders via local structural similarity, Europhys. Lett., 119, 1, 18001 (2017)
[25] Lü, L.; Chen, D.; Ren, X.-L.; Zhang, Q.-M.; Zhang, Y.-C.; Zhou, T., Vital nodes identification in complex networks, Phys. Rep., 650, 1-63 (2016)
[26] Fei, L.; Zhang, Q.; Deng, Y., Identifying influential nodes in complex networks based on the inverse-square law, Physica A, 512, 1044-1059 (2018)
[27] Kitsak, M.; Gallos, L. K.; Havlin, S.; Liljeros, F.; Muchnik, L.; Stanley, H. E.; Makse, H. A., Identification of influential spreaders in complex networks, Nature Phys., 6, 11, 888 (2010)
[28] Jiang, L.; Zhao, X.; Ge, B.; Xiao, W.; Ruan, Y., An efficient algorithm for mining a set of influential spreaders in complex networks, Physica A, 516, 58-65 (2019)
[29] Ren, Z.-M.; Liu, J.-G.; Shao, F.; Hu, Z.-L.; Guo, Q., Analysis of the spreading influence of the nodes with minimum K-shell value in complex networks, Acta Phys. Sin., 62, 10, 956-959 (2013)
[30] Ma, L.-l.; Ma, C.; Zhang, H.-F.; Wang, B.-H., Identifying influential spreaders in complex networks based on gravity formula, Physica A, 451, 205-212 (2016) · Zbl 1400.92403
[31] Ren, X.; Linyuan, L., Review of ranking nodes in complex networks, Chin. Sci. Bull., 59, 13, 1175-1197 (2014)
[32] Salavati, C.; Abdollahpouri, A.; Manbari, Z., Ranking nodes in complex networks based on local structure and improving closeness centrality, Neurocomputing, 336, 36-45 (2019)
[33] Liu, D.; Jing, Y.; Zhao, J.; Wang, W.; Song, G., A fast and efficient algorithm for mining top-k nodes in complex networks, Sci. Rep., 7, 43330 (2017)
[34] Namtirtha, A.; Dutta, A.; Dutta, B., Identifying influential spreaders in complex networks based on kshell hybrid method, Physica A, 499, 310-324 (2018)
[35] Li, C.; Wang, L.; Sun, S.; Xia, C., Identification of influential spreaders based on classified neighbors in real-world complex networks, Appl. Math. Comput., 320, 512-523 (2018) · Zbl 1427.91207
[36] Hu, Z.-L.; Liu, J.-G.; Yang, G.-Y.; Ren, Z.-M., Effects of the distance among multiple spreaders on the spreading, Europhys. Lett., 106, 1, 18002 (2014)
[37] Guo, L.; Lin, J.-H.; Guo, Q.; Liu, J.-G., Identifying multiple influential spreaders in term of the distance-based coloring, Phys. Lett. A, 380, 7-8, 837-842 (2016)
[38] Zhang, J.-X.; Chen, D.-B.; Dong, Q.; Zhao, Z.-D., Identifying a set of influential spreaders in complex networks, Sci. Rep., 6, 27823 (2016)
[39] Bian, T.; Deng, Y., Identifying influential nodes in complex networks: A node information dimension approach, Chaos, 28, 4, 043109 (2018) · Zbl 1390.90093
[40] Sheikhahmadi, A.; Nematbakhsh, M. A., Identification of multi-spreader users in social networks for viral marketing, J. Inf. Sci., 43, 3, 412-423 (2017)
[41] Zareie, A.; Sheikhahmadi, A.; Jalili, M., Influential node ranking in social networks based on neighborhood diversity, Future Gener. Comput. Syst., 94, 120-129 (2019)
[42] Liu, Y.; Wei, B.; Du, Y.; Xiao, F.; Deng, Y., Identifying influential spreaders by weight degree centrality in complex networks, Chaos Solitons Fractals, 86, 1-7 (2016) · Zbl 1382.91067
[43] Li, M.; Zhang, Q.; Deng, Y., Evidential identification of influential nodes in network of networks, Chaos Solitons Fractals, 117, 283-296 (2018) · Zbl 1442.90031
[44] Wang, Y.; Wang, S.; Deng, Y., A modified efficiency centrality to identify influential nodes in weighted networks, Pramana, 92, 4, 68 (2019)
[45] Liu, J.-G.; Lin, J.-H.; Guo, Q.; Zhou, T., Locating influential nodes via dynamics-sensitive centrality, Sci. Rep., 6, 21380 (2016)
[46] Liu, J.-G.; Ren, Z.-M.; Guo, Q., Ranking the spreading influence in complex networks, Physica A, 392, 18, 4154-4159 (2013)
[47] Mirzasoleiman, B.; Babaei, M.; Jalili, M.; Safari, M., Cascaded failures in weighted networks, Phys. Rev. E, 84, 4, 046114 (2011)
[48] Wang, W.-X.; Chen, G., Universal robustness characteristic of weighted networks against cascading failure, Phys. Rev. E, 77, 2, 026101 (2008)
[49] Nie, T.; Guo, Z.; Zhao, K.; Lu, Z.-M., Using mapping entropy to identify node centrality in complex networks, Physica A, 453, 290-297 (2016)
[50] Dorogovtsev, S. N.; Goltsev, A. V.; Mendes, J. F.F., K-core organization of complex networks, Phys. Rev. Lett., 96, 4, 040601 (2006)
[51] Gleiser, P. M.; Danon, L., Community structure in Jazz, Adv. Complex Syst., 6, 4, 565-573 (2003)
[52] Colizza, V.; Pastor-Satorras, R.; Vespignani, A., Reaction-diffusion processes and metapopulation models in heterogeneous networks, Nat. Phys., 3, 4, 276-282 (2007)
[53] Yin, H.; Benson, A. R.; Leskovec, J.; Gleich, D. F., Local higher-order graph clustering, (Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2017), ACM), 555-564
[54] Guimera, R., L. danon, a. dıaz-guilera, f. giralt, a. arenas, Phys. Rev. E, 68, 065103 (2003)
[55] Hamsterster full network dataset - KONECT (2017)
[56] Watts, D. J.; Strogatz, S. H., Collective dynamics of ‘small-world’ networks, Nature, 393, 1, 440-442 (1998) · Zbl 1368.05139
[57] Bogu, M.; Pastor-Satorras, R.; Daz-Guilera, A.; Arenas, A., Models of social networks based on social distance attachment, Phys. Rev. E, 70, 5, 056122 (2004)
[58] Rocha, L. E.; Liljeros, F.; Holme, P., Simulated epidemics in an empirical spatiotemporal network of 50,185 sexual contacts, PLoS Comput. Biol., 7, 3, Article e1001109 pp. (2011)
[59] Kunegis, J., Konect: the koblenz network collection, (Proceedings of the 22nd International Conference on World Wide Web (2013), ACM), 1343-1350
[60] Sharkey, K. J., Deterministic epidemic models on contact networks: correlations and unbiological terms, Theor. Popul. Biol., 79, 4, 115-129 (2011) · Zbl 1403.92313
[61] Castellano, C.; Pastor-Satorras, R., Thresholds for epidemic spreading in networks, Phys. Rev. Lett., 105, 21, 218701 (2010)
[62] Xiao-Ping, S.; Yu-Rong, S., Leveraging neighborhood “structural holes” to identifying key spreaders in social networks, Acta Phys. Sinica, 64, 2 (2015)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.