Influential node detection of social networks based on network invulnerability. (English) Zbl 1448.91210
Summary: Detecting influential nodes is still a popular issue in social networks and many excellent detecting methods have been put forward. However, most of them aim to improve the accuracy and efficiency of the algorithm, but ignore invulnerability of networks. Based on essential factors of influence propagation (such as the location and neighborhood of source node, propagation rate) and network invulnerability, we propose a novel strategy to search the influential nodes in terms of the local topology and the global location. Two important indicators are node diffusion degree and node cohesion degree, which are used to increase the probability of influence diffusion and reduce the feasibility of network collapse. More specially, the loss of global efficiency and the loss of local efficiency are applied to evaluate the impact of the algorithm from the perspective of network invulnerability. The experimental results in the real networks show that our method achieves an excellent balance between detecting accuracy and network invulnerability. The detected influential nodes are the ones that have great influence and can resist certain damage and disturbance of the networks.
MSC:
| 91D30 | Social networks; opinion dynamics |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Wu, X.-D.; Li, Y.; Li, L., Influence analysis of online social networks, Chinese J. Comput., 37, 4, 735-752 (2014) |
| [2] | Lu, J.; Wan, W., Identification of key nodes in microblog networks, ETRI J., 38, 1, 52-61 (2016) |
| [3] | Malliaros, F. D.; Rossi, M.-E. G.; Vazirgiannis, M., Locating influential nodes in complex networks, Sci. Rep., 6, Article 19307 pp. (2016) |
| [4] | Chen, D.-B.; Lü, L.-Y.; Shang, M.-S.; Zhang, Y.-C.; Zhou, T., Identifying influential nodes in complex networks, Phys. A, Stat. Mech. Appl., 391, 1777-1787 (2012) |
| [5] | Lawyer, G., Understanding the influence of all nodes in a network, Sci. Rep., 5, 1, 1-9 (2015) |
| [6] | Bae, J.; Kim, S., Identifying and ranking influential spreaders in complex networks by neighborhood coreness, Phys. A, Stat. Mech. Appl., 395, 549-559 (2014) · Zbl 1395.92139 |
| [7] | Freeman, L. C., Centrality in social networks conceptual clarification, Soc. Netw., 1, 3, 215-239 (1978) |
| [8] | Lü, L.-Y.; Chen, D.-B.; Ren, X.-L.; Zhang, Q.-M.; Zhang, Y.-C.; Zhou, T., Vital nodes identification in complex networks, Phys. Rep., 650, 1-63 (2016) |
| [9] | Maji, G.; Namtirtha, A.; Dutta, A.; Malta, M. C., Influential spreaders identification in complex networks with improved k-shell hybrid method, Expert Syst. Appl., 144, Article 113092 pp. (2020) |
| [10] | Maji, G., Influential spreaders identification in complex networks with potential edge weight based k-shell degree neighborhood method, J. Comput. Sci., 39, Article 101055 pp. (2020) |
| [11] | Zeng, A.; Zhang, C.-J., Ranking spreaders by decomposing complex networks, Phys. Lett. A, 377, 14, 1031-1035 (2013) |
| [12] | Brin, S.; Page, L., The anatomy of a large-scale hypertextual web search engine, Comput. Netw. ISDN Syst., 30, 1-7, 107-117 (1998) |
| [13] | 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) |
| [14] | Lv, L.; Zhang, K.; Zhang, T.; Bardou, D.; Zhang, J.; Cai, Y., Pagerank centrality for temporal networks, Phys. Lett. A, 383, 12, 1215-1222 (2019) · Zbl 1471.91398 |
| [15] | Arulselvan, A.; Commander, C. W.; Elefteriadou, L.; Pardalos, P. M., Detecting critical nodes in sparse graphs, Comput. Oper. Res., 36, 7, 2193-2200 (2009) · Zbl 1158.90411 |
| [16] | Addis, B.; Di Summa, M.; Grosso, A., Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth, Discrete Appl. Math., 161, 16-17, 2349-2360 (2013) · Zbl 1285.05042 |
| [17] | Li, P.-X.; Ren, Y.-Q.; Xi, Y.-M., An importance measure of actors (set) within a network, Syst. Eng., 22, 4, 13-20 (2004) |
| [18] | Chen, Y.; Hu, A.-Q.; Hu, J.; Chen, L., A method for finding the most vital node in communication networks, High Technol. Lett., 1, 2, 573-575 (2004) |
| [19] | Tan, Y.-J.; Wu, J.; Deng, H.-Z., Evaluation method for node importance based on node contraction in complex networks, Syst. Eng. Theory Pract., 11, 11, 79-83 (2006) |
| [20] | Yang, G.-L.; Benko, T. P.; Cavaliere, M.; Huang, J.-C.; Perc, M., Identification of influential invaders in evolutionary populations, Sci. Rep., 9, 1, 1-12 (2019) |
| [21] | Latora, V.; Marchiori, M., Efficient behavior of small-world networks, Phys. Rev. Lett., 87, 19, Article 198701 pp. (2001) |
| [22] | Wang, Y.-C.; Wang, S.-S.; Deng, Y., A modified efficiency centrality to identify influential nodes in weighted networks, Pramana, 92, 4, 68 (2019) |
| [23] | Zareie, A.; Sheikhahmadi, A.; Jalili, M., Influential node ranking in social networks based on neighborhood diversity, Future Gener. Comput. Syst., 94, 120-129 (2019) |
| [24] | Zhong, L.-F.; Liu, Q.-H.; Wang, W.; Cai, S.-M., Comprehensive influence of local and global characteristics on identifying the influential nodes, Phys. A, Stat. Mech. Appl., 511, 78-84 (2018) |
| [25] | Salavati, C.; Abdollahpouri, A.; Manbari, Z., Ranking nodes in complex networks based on local structure and improving closeness centrality, Neurocomputing, 336, 36-45 (2019) |
| [26] | Yang, Y.-Z.; Yu, L.; Wang, X.; Zhou, Z.-L.; Chen, Y.; Kou, T., A novel method to evaluate node importance in complex networks, Phys. A, Stat. Mech. Appl., 526, Article 121118 pp. (2019) · Zbl 07566475 |
| [27] | Gao, C.; Zhong, L.; Li, X.-H.; Zhang, Z.-L.; Shi, N., Combination methods for identifying influential nodes in networks, Int. J. Mod. Phys. C, 26, 06, Article 1550067 pp. (2015) |
| [28] | Sheng, J.-F.; Dai, J.-Y.; Wang, B.; Duan, G.-H.; Long, J.; Zhang, J.-K.; Guan, K.-R.; Hu, S.; Chen, L.; Guan, W.-H., Identifying influential nodes in complex networks based on global and local structure, Phys. A, Stat. Mech. Appl., 541, Article 123262 pp. (2020) |
| [29] | Zhao, J.; Wang, Y.-C.; Deng, Y., Identifying influential nodes in complex networks from global perspective, Chaos Solitons Fractals, 133, Article 109637 pp. (2020) · Zbl 1483.90039 |
| [30] | Wang, M.; Li, W.-C.; Guo, Y.-N.; Peng, X.-Y.; Li, Y.-X., Identifying influential spreaders in complex networks based on improved k-shell method, Phys. A, Stat. Mech. Appl., Article 124229 pp. (2020) · Zbl 07528392 |
| [31] | Pastor-Satorras, R.; Vespignani, A., Epidemic dynamics and endemic states in complex networks, Phys. Rev. E, 63, 6, Article 066117 pp. (2001) |
| [32] | Schneider, C. M.; Mihaljev, T.; Herrmann, H. J., Inverse targeting—an effective immunization strategy, Europhys. Lett., 98, 4, Article 46002 pp. (2012) |
| [33] | Hu, Q.-H., A research of identifying vital nodes algorithm based on graph partition (2019), University of Electronic Science and Technology of China, Master’s thesis |
| [34] | Xu, J.-M., Combinatorial Theory in Networks (2013), Science Press: Science Press Beijing/China |
| [35] | Nguyen, D.-L.; Nguyen, T.-H.; Do, T.-H.; Yoo, M., Probability-based multi-hop diffusion method for influence maximization in social networks, Wirel. Pers. Commun., 93, 4, 903-916 (2017) |
| [36] | Goldenberg, J.; Libai, B.; Muller, E., Using complex systems analysis to advance marketing theory development: modeling heterogeneity effects on new product growth through stochastic cellular automata, Acad. Mark. Sci. Rev., 9, 3, 1-18 (2001) |
| [37] | Granovetter, M., Threshold models of collective behavior, Am. J. Sociol., 83, 6, 1420-1443 (1978) |
| [38] | (Apr. 2017), Zachary karate club network dataset - KONECT |
| [39] | (Apr. 2017), Infectious network dataset - KONECT |
| [40] | Isella, L.; Stehlé, J.; Barrat, A.; Cattuto, C.; Pinton, J.-F.; Van den Broeck, W., What’s in a crowd? Analysis of face-to-face behavioral networks, J. Theor. Biol., 271, 1, 166-180 (2011) · Zbl 1405.92255 |
| [41] | Newman, M. E., Finding community structure in networks using the eigenvectors of matrices, Phys. Rev. E, 74, 3, Article 036104 pp. (2006) |
| [42] | (Apr. 2017), Protein network dataset - KONECT |
| [43] | Coulomb, S.; Bauer, M.; Bernard, D.; Marsolier-Kergoat, M.-C., Gene essentiality and the topology of protein interaction networks, Proc. R. Soc. B, Biol. Sci., 272, 1573, 1721-1725 (2005) |
| [44] | Castellano, C.; Pastor-Satorras, R., Thresholds for epidemic spreading in networks, Phys. Rev. Lett., 105, 21, Article 218701 pp. (2010) |
| [45] | Hoeffding, W., A non-parametric test of independence, Ann. Math. Stat., 546-557 (1948) · Zbl 0032.42001 |
| [46] | Kendall, M. G., The treatment of ties in ranking problems, Biometrika, 33, 3, 239-251 (1945) · Zbl 0063.03216 |
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.
