A New Greedy Algorithm For Influence Maximization On Signed Social Networks

Abstract

The social influence is one of the major phenomenons that shapes people's decisions. In this respect, Influence Maximization (IM) problem is one of the most attractive research topics in the social network analysis because its practical benefits in viral marketing, public opinions shaping etc. The IM problem aims to maximize the spread of an influence (e.g. an opinion, an advertisement) in a social network by using a small number of the most effective individuals, whom is called influencers. Detecting the influencers is the NP-Hard combinatorial optimization problem in most cases. Therefore, many algorithms have been and are being developed for the IM problem. However, the algorithms have not yet achieved to the desired solution quality and speed. In this study, we focused on the signed IM problem that is considers both positive and negative influence between the individuals. For this purpose, we developed a greedy algorithm called the Elitist Greedy Algorithm (EGA) for detecting  influencers set. We compared the EGA’s performance on 2 public datasets with random seed selection, out degree heuristic, and one state-of-the-art greedy algorithm. The EGA outperforms the competitors in terms of the achieved total influence.

Keywords

• Influence maximization,online social networks,information diffusion,greedy algorithm

İşaretli Sosyal Ağlarda Etki Maksimizasyonu İçin Yeni Bir Aç Gözlü Algoritma

Abstract

Sosyal etki insanların görüşlerini şekillendiren büyük olgulardan biridir. Bu bakımdan, Etki Maksimizasyonu (EM) problemi viral pazarlama, kamuoyu şekillendirme gibi pratik faydaları olduğu için sosyal ağ analizinde en fazla ilgili çeken araştırma alanlarından biridir. EM probleminin amacı bir sosyal ağ üzerindeki etkili kişi olarak adlandırılan az sayıdaki kişiyi kullanarak bir etkinin (bir fikir veya reklam) ağ üzerindeki yayılımını maksimize etmektir. Etkili kişilerin tespiti birçok durumda NP-Hard bir kombinasyonal optimizasyon problemidir. Bundan dolayı, EM problemi için birçok algoritma geliştirilmiştir ve geliştirilmeye devam etmektedir. Ne var ki, geliştirilen algoritmalar henüz çözüm kalitesi ve hız açısından istenen seviyede değildirler. Bu çalışmada, bireyler arasındaki olumlu ve olumsuz ilişkileri göz önünde bulunduran işaretli EM problemine odaklanılmıştır. Bu amaçla, en iyi  adet etkili kişiyi tespit etmek için Elitist Aç Gözlü Algoritma (EGA) olarak adlandırılan bir aç gözlü algoritma geliştirmiştir. EGA’nın performansı 2 adet açık veriseti üzerinde rasgele seçim, çıkış derecesi merkeziliği, ve bir güncel algoritma ile kıyaslanmıştır. EGA çözüm kalitesi açısından rakiplerine göre daha iyi sonuçlar vermiştir.

Keywords

• Etki maksimizasyonu,online sosyal ağlar,bilgi yayılımı,aç gözlü algoritma

References

1. G. A. Tong, S. Li, W. Wu, and D.-Z. Du, “Effector Detection in Social Networks,” IEEE Trans. Comput. Soc. Syst., vol. 3, no. 4, pp. 151–163, Dec. 2016.
2. D. Kempe, J. Kleinberg, and É. Tardos, “Maximizing the spread of influence through a social network,” in Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining - KDD ’03, 2003, p. 137.
3. T. Lappas, E. Terzi, D. Gunopulos, and H. Mannila, “Finding effectors in social networks,” in Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD ’10, 2010, p. 1059.
4. M. Samadi, R. Nagi, A. Semenov, and A. Nikolaev, “Seed activation scheduling for influence maximization in social networks,” Omega, vol. 77, pp. 96–114, Jun. 2018.
5. D. Li, C. Wang, S. Zhang, G. Zhou, D. Chu, and C. Wu, “Positive influence maximization in signed social networks based on simulated annealing,” Neurocomputing, vol. 260, pp. 69–78, Oct. 2017.
6. D. Li, Z.-M. Xu, N. Chakraborty, A. Gupta, K. Sycara, and S. Li, “Polarity Related Influence Maximization in Signed Social Networks,” PLoS One, vol. 9, no. 7, p. e102199, Jul. 2014.
7. X. Weng, Z. Liu, and Z. Li, “An Efficient Influence Maximization Algorithm Considering Both Positive and Negative Relationships,” in 2016 IEEE Trustcom/BigDataSE/ISPA, 2016, pp. 1931–1936.
8. M. Talluri, H. Kaur, and J. S. He, “Influence maximization in social networks: Considering both positive and negative relationships,” in 2015 International Conference on Collaboration Technologies and Systems (CTS), 2015, pp. 479–480.

9. H. Zhang, T. N. Dinh, and M. T. Thai, “Maximizing the Spread of Positive Influence in Online Social Networks,” in 2013 IEEE 33rd International Conference on Distributed Computing Systems, 2013, pp. 317–326.
10. A. Nazemian and F. Taghiyareh, “Influence maximization in Independent Cascade model with positive and negative word of mouth,” in 6th International Symposium on Telecommunications (IST), 2012, pp. 854–860.
11. D. Kempe, J. Kleinberg, and E. Tardos, “Maximizing the spread of influence through a social network,” in KDD ’03 Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, 2003, pp. 137–146.
12. J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance, “Cost-effective outbreak detection in networks,” in Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD ’07, 2007, p. 420.
13. W. Chen, Y. Wang, and S. Yang, “Efficient influence maximization in social networks,” in Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD ’09, 2009, p. 199.
14. F. Lu, W. Zhang, L. Shao, X. Jiang, P. Xu, and H. Jin, “Scalable influence maximization under independent cascade model,” J. Netw. Comput. Appl., vol. 86, pp. 15–23, May 2017.
15. Z. Abbassi, A. Bhaskara, and V. Misra, “Optimizing Display Advertising in Online Social Networks,” in Proceedings of the 24th International Conference on World Wide Web - WWW ’15, 2015, pp. 1–11.
16. W. Liu, X. Chen, B. Jeon, L. Chen, and B. Chen, “Influence maximization on signed networks under independent cascade model,” Appl. Intell., vol. 49, no. 3, pp. 912–928, Mar. 2019.
17. S. Chen and K. He, “Influence Maximization on Signed Social Networks with Integrated PageRank,” in 2015 IEEE International Conference on Smart City/SocialCom/SustainCom (SmartCity), 2015, pp. 289–292.
18. J. Li and Y. Yu, “Scalable Influence Maximization in Social Networks Using the Community Discovery Algorithm,” in 2012 Sixth International Conference on Genetic and Evolutionary Computing, 2012, pp. 284–287.
19. S. Peng, Y. Zhou, L. Cao, S. Yu, J. Niu, and W. Jia, “Influence analysis in social networks: A survey,” J. Netw. Comput. Appl., vol. 106, pp. 17–32, Mar. 2018.
20. S. P. Borgatti, “Identifying sets of key players in a social network,” Comput. Math. Organ. Theory, vol. 12, no. 1, pp. 21–34, Apr. 2006.
21. K. Zhang, H. Du, and M. W. Feldman, “Maximizing influence in a social network: Improved results using a genetic algorithm,” Phys. A Stat. Mech. its Appl., vol. 478, pp. 20–30, Jul. 2017.
22. M. Gong, C. Song, C. Duan, L. Ma, and B. Shen, “An Efficient Memetic Algorithm for Influence Maximization in Social Networks,” IEEE Comput. Intell. Mag., vol. 11, no. 3, pp. 22–33, Aug. 2016.
23. M. Gong, J. Yan, B. Shen, L. Ma, and Q. Cai, “Influence maximization in social networks based on discrete particle swarm optimization,” Inf. Sci. (Ny)., vol. 367–368, pp. 600–614, Nov. 2016.
24. Qixiang Wang, M. Gong, Chao Song, and Shanfeng Wang, “Discrete particle swarm optimization based influence maximization in complex networks,” in 2017 IEEE Congress on Evolutionary Computation (CEC), 2017, pp. 488–494.
25. A. ŞİMŞEK and R. KARA, “Using swarm intelligence algorithms to detect influential individuals for influence maximization in social networks,” Expert Syst. Appl., vol. 114, pp. 224–236, Dec. 2018.
26. R. Zafarani, M. A. Abbasi, and H. Liu, Social Media Mining, 1st ed. Cambridge University Press, 2014.
27. J.-R. Lee and C.-W. Chung, “A Query Approach for Influence Maximization on Specific Users in Social Networks,” IEEE Trans. Knowl. Data Eng., vol. 27, no. 2, pp. 340–353, Feb. 2015.
28. J. Leskovec, D. Huttenlocher, and J. Kleinberg, “Signed networks in social media,” in Proceedings of the 28th international conference on Human factors in computing systems - CHI ’10, 2010, p. 1361.