Applying Heuristic-Based Greedy Approaches for Influence Maximization-Cost Minimization in Social Networks

Document Type : Research Article

Authors

1 Department of Computer Engineering, University of Isfahan, Iran.

2 Department of Computer Engineering, Shahreza Campus, University of Isfahan, Iran.

3 Faculty of Computer Engineering, University of Isfahan, Iran.

Abstract

Influence maximization in social networks has been an important research issue in the recent decade. This issue is identifying the most influential individuals in a social network who can convey influence to the largest number of the network’s members. However, in influence maximization, the costs of all of the nodes to be selected as seeds are considered the same for the companies that do not hold in the real world. Accordingly, influence maximization-cost minimization has gained attention recently. Available studies have applied multi-objective optimization methods which are time-consuming. Applying the existing approaches of influence maximization for other variants of this problem has been considered in some studies about other multi-objective versions of the influence maximization problem. In this study, extending and well-applying run time-efficient methods of influence maximization are considered to influence maximization-cost minimization. Accordingly, two methods are proposed. The first, Local Lowest Degree Rank (LLDR) is a heuristic-based one which by considering the degree of nodes aims to find the cost-affordable influential nodes with minimum influence overlap among them. The second proposed method, Ratio-aware-CELF-based (RCELF) method, is a Cost Effective Lazy Forward (CELF)-based algorithm which extends CELF as a run-time efficient greedy approach for influence maximization by incorporating the cost function of the nodes into consideration. The proposed methods are evaluated by applying two real-world datasets, Facebook and Last.fm. The results establish the outperformance which in comparison with the most effective benchmark method is between 4% to 32% for LLDR and between 34% to 96% for RCELF.

Keywords

Main Subjects

References

[1] Li, Yuchen and Fan, Ju and Wang, Yanhao and Tan, Kian-Lee. Influence maximization on social graphs: A survey. IEEE Transactions on Knowledge and Data Engineering. 30(10): 1852--1872, IEEE. 2018. [DOI ]
[2] Ye, Mao and Liu, Xingjie and Lee, Wang-Chien. Exploring social influence for recommendation: a generative model approach. Proceedings of the 35th international ACM SIGIR conference on Research and development in information retrieval. 671--680, 2012. [DOI ]
[3] Yao, Shunyu and Fan, Neng and Hu, Jie. Modeling the spread of infectious diseases through influence maximization. Optimization letters. 16(5): 1563--1586, Springer. 2022. [DOI ]
[4] Vega-Oliveros, Didier A and da Fontoura Costa, Luciano and Rodrigues, Francisco Aparecido. Influence maximization by rumor spreading on correlated networks through community identification. Communications in Nonlinear Science and Numerical Simulation. 83: 105094, Elsevier. 2020. [DOI ]
[5] Huang, Huimin and Shen, Hong and Meng, Zaiqiao and Chang, Huajian and He, Huaiwen. Community-based influence maximization for viral marketing. Applied Intelligence. 49: 2137--2150, Springer. 2019. [DOI ]
[6] Yang, Jie and Liu, Jing. Influence maximization-cost minimization in social networks based on a multiobjective discrete particle swarm optimization algorithm. IEEE Access. 6: 2320--2329, IEEE. 2017. [DOI ]
[7] De, Sagar S and Dehuri, Satchidananda. Multi-objective biogeography-based optimization for influence maximization-cost minimization in social networks. Biologically Inspired Techniques in Many-Criteria Decision Making: International Conference on Biologically Inspired Techniques in Many-Criteria Decision Making (BITMDM-2019). 11--34, 2020. [DOI ]
[8] Wang, Ping and Zhang, Ruisheng. A multi-objective crow search algorithm for influence maximization in social networks. Electronics. 12(8): 1790, MDPI. 2023. [DOI ]
[9] Qian, Fulan and Zhu, Cunliang and Chen, Xi and Zhao, Shu and Zhang, Yanping. PRNSGA-II: A novel approach for influence maximization and cost minimization based on NSGA-II. 2020 IEEE International Conference on Knowledge Graph (ICKG). 396--403, 2020. [DOI ]
[10] Wang, Chao and Ma, Liangliang and Ma, Lei and Lai, Joel Weijia and Zhao, Jie and Wang, Lu and Cheong, Kang Hao. Identification of influential users with cost minimization via an improved moth flame optimization. Journal of Computational Science. 67: 101955, Elsevier. 2023. [DOI ]
[11] Li, Cheng-Te and Huang, Mei-Yuan and Yan, Rui. Team formation with influence maximization for influential event organization on social networks. World Wide Web. 21: 939--959, Springer. 2018. [DOI ]
[12] Nguyen, Hung T and Thai, My T and Dinh, Thang N. A billion-scale approximation algorithm for maximizing benefit in viral marketing. IEEE/ACM Transactions On Networking. 25(4): 2419--2429, IEEE. 2017. [DOI ]
[13] Leskovec, Jure and Krause, Andreas and Guestrin, Carlos and Faloutsos, Christos and VanBriesen, Jeanne and Glance, Natalie. Cost-effective outbreak detection in networks. Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. 420--429, 2007. [DOI ]
[14] Kempe, David and Kleinberg, Jon and Tardos, {\'E}va. Maximizing the spread of influence through a social network. Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. 137--146, 2003. [DOI ]
[15] Azaouzi, Mehdi and Mnasri, Wassim and Romdhane, Lotfi Ben. New trends in influence maximization models. Computer Science Review. 40: 100393, Elsevier. 2021. [DOI ]
[16] Banerjee, Suman and Jenamani, Mamata and Pratihar, Dilip Kumar. A survey on influence maximization in a social network. Knowledge and Information Systems. 62: 3417--3455, Springer. 2020. [DOI ]
[17] Goyal, Amit and Lu, Wei and Lakshmanan, Laks VS. Celf++ optimizing the greedy algorithm for influence maximization in social networks. Proceedings of the 20th international conference companion on World wide web. 47--48, 2011. [DOI ]
[18] Goyal, Amit and Lu, Wei and Lakshmanan, Laks VS. Simpath: An efficient algorithm for influence maximization under the linear threshold model. 2011 IEEE 11th international conference on data mining. 211--220, 2011. [DOI ]
[19] Wang, Chi and Chen, Wei and Wang, Yajun. Scalable influence maximization for independent cascade model in large-scale social networks. Data Mining and Knowledge Discovery. 25: 545--576, Springer. 2012. [DOI ]
[20] Zhou, Chuan and Zhang, Peng and Guo, Jing and Guo, Li. An upper bound based greedy algorithm for mining top-k influential nodes in social networks. Proceedings of the 23rd International Conference on World Wide Web. 421--422, 2014. [DOI ]
[21] Galhotra, Sainyam and Arora, Akhil and Virinchi, Srinivas and Roy, Shourya. Asim: A scalable algorithm for influence maximization under the independent cascade model. Proceedings of the 24th International Conference on World Wide Web. 35--36, 2015. [DOI ]
[22] Borgs, Christian and Brautbar, Michael and Chayes, Jennifer and Lucier, Brendan. Maximizing social influence in nearly optimal time. Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. 946--957, 2014. [DOI ]
[23] Tang, Youze and Xiao, Xiaokui and Shi, Yanchen. Influence maximization: Near-optimal time complexity meets practical efficiency. Proceedings of the 2014 ACM SIGMOD international conference on Management of data. 75--86, 2014. [DOI ]
[24] Tang, Youze and Shi, Yanchen and Xiao, Xiaokui. Influence maximization in near-linear time: A martingale approach. Proceedings of the 2015 ACM SIGMOD international conference on management of data. 1539--1554, 2015. [DOI ]
[25] Nguyen, Hung T and Thai, My T and Dinh, Thang N. Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks. Proceedings of the 2016 international conference on management of data. 695--710, 2016. [DOI ]
[26] Li, Xiang and Smith, J David and Dinh, Thang N and Thai, My T. Tiptop:(almost) exact solutions for influence maximization in billion-scale networks. IEEE/ACM Transactions on Networking. 27(2): 649--661, IEEE. 2019. [DOI ]
[27] Landherr, Andrea and Friedl, Bettina and Heidemann, Julia. A critical review of centrality measures in social networks. Business \& Information Systems Engineering. 2: 371--385, Springer. 2010. [DOI ]
[28] Chen, Wei and Wang, Yajun and Yang, Siyu. Efficient influence maximization in social networks. Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. 199--208, 2009. [DOI ]
[29] Pal, Sankar K and Kundu, Suman and Murthy, CA. Centrality measures, upper bound, and influence maximization in large scale directed social networks. Fundamenta Informaticae. 130(3): 317--342, IOS Press. 2014. [DOI ]
[30] Liu, Qi and Xiang, Biao and Chen, Enhong and Xiong, Hui and Tang, Fangshuang and Yu, Jeffrey Xu. Influence maximization over large-scale social networks: A bounded linear approach. Proceedings of the 23rd ACM international conference on conference on information and knowledge management. 171--180, 2014. [DOI ]
[31] Liu, Dong and Jing, Yun and Zhao, Jing and Wang, Wenjun and Song, Guojie. A fast and efficient algorithm for mining top-k nodes in complex networks. Scientific reports. 7(1): 43330, Nature Publishing Group UK London. 2017. [DOI ]
[32] Namtirtha, Amrita and Dutta, Animesh and Dutta, Biswanath. 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, Elsevier. 2020. [DOI ]
[33] Hosseini-Pozveh, Maryam and Zamanifar, Kamran and Naghsh-Nilchi, Ahmad Reza. Assessing information diffusion models for influence maximization in signed social networks. Expert Systems with Applications. 119: 476--490, Elsevier. 2019. [DOI ]
[34] Mor{\u{a}}rescu, IC and Varma, Vineeth S and Bu{\c{s}}oniu, L and Lasaulce, Samson. Space--time budget allocation policy design for viral marketing. Nonlinear Analysis: Hybrid Systems. 37: 100899, Elsevier. 2020. [DOI ]
[35] Doshi, Ronak and Ramesh, Ajay and Rao, Shrisha. Modeling influencer marketing campaigns in social networks. IEEE Transactions on Computational Social Systems. 10(1): 322--334, IEEE. 2022. [DOI ]
[36] Leskovec, Jure and Mcauley, Julian. Learning to discover social circles in ego networks. Advances in neural information processing systems. 25: 2012.
[37] Rozemberczki, Benedek and Sarkar, Rik. Characteristic functions on graphs: Birds of a feather, from statistical descriptors to parametric models. Proceedings of the 29th ACM international conference on information \& knowledge management. 1325--1334, 2020. [DOI ]

Files

History

  • Receive Date: 13 November 2023
  • Revise Date: 13 March 2024
  • Accept Date: 21 May 2024

Share

How to cite

Statistics