Identifying nodes with high spreader power in social networks by considering positive and negative influence weights

Document Type : Original Article

Authors

1 Department of Computer Engineering, Sanandaj Branch, Islamic Azad University, Sanandaj, Iran

2 Department of Mathematics, Sanandaj Branch, Islamic Azad University, Sanandaj, Iran

Abstract

Social networks have gained significant importance in society. The high number of users and the large volume of data exchanged daily through these networks have turned them into a suitable opportunity for commercial advertising. However, due to budget limitations, companies are forced to select only a limited set of users to start their propagation process. To succeed in spreading advertisements and informing the majority of the community, the selected collection must include influential individuals. Many studies have focused on selecting an optimal subset of influential individuals, but most of them have assumed that the influence between individuals is positive and have not considered the negative influence of individuals on each other. Therefore, this paper proposes a method for selecting an optimal subset of influential individuals considering both positive and negative influences between individuals. In the proposed method, the set of positive and negative influences of one and two steps for each individual is obtained. Then, a multi-criteria decision-making method is used to propose an approach to select the best individuals. The Wikipedia dataset is utilized for evaluations. The obtained results for the spreading power of the selected set indicate that while some methods may have more positive propagation than the proposed method in some cases, the proposed method outperforms other methods in terms of negative emission across all scenarios.

Keywords


[1] Rukuni T. F., Shaw G., Chetty Y., Kgama P., Kekana P., and Rogers K., "Viral Marketing Strategies and Customer Buying Behavioural Intentions at Retail Store in Johannesburg," Business Management and Strategy, 8(1): 59-83, 2017.
[2] Sheikhahmadi A. and Zareie A., "Identifying influential spreaders using multi-objective artificial bee colony optimization," Applied Soft Computing, 94:106436, 2020.
[3] Malliaros F. D., Rossi M.-E. G., and Vazirgiannis M., "Locating influential nodes in complex networks," Scientific reports, vol. 6, 2016.
[4] Wang S., Du Y., and Deng Y., "A new measure of identifying influential nodes: Efficiency centrality," Communications in Nonlinear Science and Numerical Simulation, 47:151-163, 2017.
[5] Wei D., Deng X., Zhang X., Deng Y., and Mahadevan S.,"Identifying influential nodes in weighted networks based on evidence theory," Physica A: Statistical Mechanics and its Applications, 392(10): 2564-2575, 2013.
[6] Yang Y., Wang Z., Pei J., and Chen E., "Tracking influential nodes in dynamic networks," arXiv preprint arXiv: 1602.04490, 2016.
[7] Zhang X., Zhu J., Wang Q., and Zhao H., "Identifying influential nodes in complex networks with community structure," Knowledge-Based Systems, 42: 74-84, 2013.
[8] کی پور ا.، براری م. و شیرازی ح.، «پیشگویی پیوند در شبکه‌های اجتماعی با استفاده از ترکیب دسته‌بندی کننده‌ها»، مجله محاسبات نرم، جلد 4، شماره 2، ص. 2-17، 1394.
[9] محفوظ ا. و فتحی تبار غ.، «مجموع فاصله بین رئوس گراف»، مجله محاسبات نرم، جلد 5، شماره 2، ص. 28-33، 1395.
[10] Zareie A., Sheikhahmadi     A., Jalili M., and Fasaei M. S. K., "Finding influential nodes in social networks based on neighborhood correlation coefficient," vol. 194, 2020.
[11] Zareie A., Sheikhahmadi A., and Jalili M., "Influential node ranking in social networks based on neighborhood diversity," 94: 129, 2019.
[12] Zareie A. and Sheikhahmadi A., "A hierarchical approach for influential node ranking in complex social networks," Expert Systems with Applications, 93: 200-211, 2018.
[13] Zareie A., Sheikhahmadi A., and Fatemi A., "Influential nodes ranking in complex networks: An entropy-based approach," 104: 494, 2017.
[14] Sheikhahmadi A., Nematbakhsh M. A., and Shokrollahi A., "Improving detection of influential nodes in complex networks," 436: 845, 2015.
[15] Chen W., Collins A., Cummings R., Ke T., Liu Z., Rincon D., Sun X., Wang Y., Wei W., and Yuan Y., "Influence maximization in social networks when negative opinions may emerge and propagate," in Proceedings of the 2011 SIAM International Conference on Data Mining, 2011, pp. 379-390: SIAM.
[16] خلیلی درمنی م.، «الگوریتم چندمعیاره برای تعیین مسیر حرکت گره چاهک در شبکه‌های حسگر بی‌سیم»، مجله محاسبات نرم، جلد 7، شماره 2، ص. 74-83، 1397.
[17] Du Y., Gao C., Hu Y., Mahadevan S., and Deng Y., "A new method of identifying influential nodes in complex networks based on TOPSIS," Physica A: Statistical Mechanics and its Applications, 399: 57-69, 2014.
[18] Hu J., Du Y., Mo H., Wei D., and Deng Y., "A modified weighted TOPSIS to identify influential nodes in complex networks," Physica A: Statistical Mechanics and its Applications, 444: 73-85, 2016.
[19] Jia H., Han Y., Wu X., and Zhu S., "Node Importance Evaluation Algorithm for Complex Network Based on Time Series and TOPSIS," in Conference: 2020 39th Chinese Control Conference (CCC), pp. 790, 2020.
[20] Kempe D., Kleinberg J., and Tardos E., "Influential nodes in a diffusion model for social networks," in International Colloquium on Automata, Languages, and Programming, 2005, pp. 1127-1138: Springer.
[21] Woo J., Son J., and Chen H., "An SIR model for violent topic diffusion in social media," in 2011 IEEE International Conference on Intelligence and Security Informatics (ISI), pp. 15-19, 2011.
[22] Li D., Xu Z.-M., Chakraborty N., Gupta A., Sycara K., and Li S., "Polarity related influence maximization in signed social networks," PloS one, 9(7): e102199, 2014.
[23] Li Q., Zhou T., Lü L., and Chen D., "Identifying influential spreaders by weighted LeaderRank," Physica A: Statistical Mechanics and its Applications, 404: 47-55, 2014.
[24] Bae J. and Kim S., "Identifying and ranking influential spreaders in complex networks by neighborhood coreness," Physica A: Statistical Mechanics and its Applications, 395: 549-559, 2014.
[25] Wang Z., Zhao Y., Xi J., and Du C., "Fast ranking influential nodes in complex networks using a k-shell iteration factor," Physica A: Statistical Mechanics and its Applications, 461: 171-181, 2016.
[26] Sheikhahmadi A. and Nematbakhsh M. A., "Identification of multi-spreader users in social networks for viral marketing," Journal of Information Science, 43(3): 412-423, 2017.
[27] Lü L., Zhang Y.-C., Yeung C. H., and Zhou T., "Leaders in social networks, the delicious case," PloS one, 6(6): e21202, 2011.
[28] Namtirtha A., Dutta A., and Dutta B., "Weighted kshell degree neighborhood: A new method for identifying the influential spreaders from a variety of complex network connectivity structures," Expert Systems with Applications, 139: 112859, 2020.
[29] Maji G., "Influential spreaders identification in complex networks with potential edge weight based k-shell degree neighborhood method," Journal of Computational Science, 39: 101055, 2020.
[30] Ma L.-L., Ma C., Zhang H.-F., and Wang B.-H., "Identifying influential spreaders in complex networks based on gravity formula," Physica A: Statistical Mechanics and its Applications, 451: 205-212, 2016.
[31] Li Z., Ren T., Ma X., Liu S., Zhang Y., and Zhou T., "Identifying influential spreaders by gravity model," Scientific reports, 9(1): 1-7, 2019.
[32] Liu F., Wang Z., and Deng Y., "GMM: A generalized mechanics model for identifying the importance of nodes in complex networks," Knowledge-Based Systems, 193: 105464, 2020.
[33] Yang X. and Xiao F., "An improved gravity model to identify influential nodes in complex networks based on k-shell method," Knowledge-Based Systems, p. 107198, 2021.