Abstract
Social networks are in continuous evolution, and its spreading has attracted the interest of both practitioners and the scientific community. In the last decades, several new interesting problems have aroused in the context of social networks, mainly due to an overabundance of information, usually named as infodemic. This problem emerges in several areas, such as viral marketing, disease prediction and prevention, and misinformation, among others. Then, it is interesting to identify the most influential users in a network to analyze the information transmitted, resulting in Social Influence Maximization (SIM) problems. In this research, the Budget Influence Maximization Problem (BIMP) is tackled. BIMP proposes a realistic scenario where the cost of selecting each node is different. This is modeled by having a budget that can be spent to select the users of a network, where each user has an associated cost. Since BIMP is a hard optimization problem, a metaheuristic algorithm based on Greedy Randomized Adaptive Search (GRASP) framework is proposed.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Data availability
Data availability is public at https://grafo.etsii.urjc.es/BIMP/.
References
Banerjee S, Jenamani M, Pratihar DK (2019) ComBIM: a community-based solution approach for the budgeted influence maximization problem. Expert Syst Appl 125:1–13. https://doi.org/10.1016/j.eswa.2019.01.070
Banerjee S, Jenamani M, Pratihar DK (2020) A survey on influence maximization in a social network. Knowl Inf Syst 62:3417–3455. https://doi.org/10.1007/s10115-020-01461-4
Barabási A-L, Pòsfai M (2016) Network science. Cambridge University Press, Cambridge
Bello-Orgaz G, Hernandez-Castro J, Camacho D (2017) Detecting discussion communities on vaccination in twitter. Future Gener Comput Syst 66:125–136. https://doi.org/10.1016/j.future.2016.06.032
Chen W, Wang C, Wang Y (2010) Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining—KDD ’10. ACM Press, Hoboken. https://doi.org/10.1145/1835804.1835934
Chen E, Lerman K, Ferrara E (2020) Tracking social media discourse about the covid-19 pandemic: development of a public coronavirus twitter data set. JMIR Public Health Surveill 6(2):e19273. https://doi.org/10.2196/19273
Feo TA, Resende MGC (1989) A probabilistic heuristic for a computationally difficult set covering problem. Oper Res Lett 8(2):67–7. https://doi.org/10.1016/0167-6377(89)90002-3
Feo TA, Resende MGC, Smith SH (1994) A greedy randomized adaptive search procedure for maximum independent set. Oper Res 42(5):860–878. https://doi.org/10.1287/opre.42.5.860
Gong M, Song C, Duan C, Ma L, Shen B (2016) An efficient memetic algorithm for influence maximization in social networks. IEEE Comput Intell Mag 11(3):22–33. https://doi.org/10.1109/mci.2016.2572538
Goyal A, Lu W, Lakshmanan Laks VS (2011) CELF++. In: Proceedings of the 20th international conference companion on World wide web—WWW ’11. ACM Press, Hoboken. https://doi.org/10.1145/1963192.1963217
Granovetter M (1978) Threshold models of collective behavior. Am J Sociol 83(6):1420–1443
Guney E, Cakir V, Ozdemir Y, Duzdar I (2015) Budgeted influence maximization in social networks with independent cascade diffusion model. In: Proceedings of the 4th international symposium & 26th national conference on operational research, pp 291–296
Han S, Zhuang F, He Q, Shi Z (2014) Balanced seed selection for budgeted influence maximization in social networks. In: Advances in knowledge discovery and data mining, pp 65–77. Springer International Publishing, Berlin. https://doi.org/10.1007/978-3-319-06608-0_6
Hansen P, Mladenović N (2006) First vs. best improvement: an empirical study. IV. ALIO/EURO workshop on applied combinatorial optimization. Discrete Appl Math 154(5):802–817. https://doi.org/10.1016/j.dam.2005.05.020
Hayes JL, Britt BC, Evans W, Rush SW, Towery NA, Adamson AC (2021) Can social media listening platforms’ artificial intelligence be trusted? Examining the accuracy of crimson hexagon’s (now brandwatch consumer research’s) ai-driven analyses. J Advert 50(1):81–91. https://doi.org/10.1080/00913367.2020.1809576
Jos N-V, del Mar G-PM, Villar-Rodríguez G, Martín A, Camacho D (2023) Disinformation and vaccines on social networks: behavior of hoaxes on twitter. Rev Latina Comun Soc 81:44–62
Kempe D, Kleinberg J, Tardos E (2015) Maximizing the spread of influence through a social network. Theory Comput 11(1):105–147. https://doi.org/10.4086/toc.2015.v011a004
Kempe D, Kleinberg J, Tardos É (2003) 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. ACM Press, Hoboken. https://doi.org/10.1145/956750.956769
Leskovec J, Kleinberg J, Faloutsos C (2007) Graph evolution. ACM Trans Knowl Discov Data 1(1):2. https://doi.org/10.1145/1217299.1217301
Lozano-Osorio I, Sánchez-Oro J, Duarte A, Cordón Ó (2021) A quick GRASP-based method for influence maximization in social networks. J Ambient Intell Hum Comput 1:1. https://doi.org/10.1007/s12652-021-03510-4
Nguyen H, Zheng R (2013) On budgeted influence maximization in social networks. IEEE J Sel Areas Commun 31(6):1084–1094. https://doi.org/10.1109/jsac.2013.130610
Rafael M, Anna M-G, Jesús S-O, Abraham D (2018) Tabu search for the dynamic bipartite drawing problem. Comput. Oper. Res. 91:1–12
Resende Mauricio GC, Martí R, Gallego M, Duarte A (2010) GRASP and path relinking for the max-min diversity problem. Comput Oper Res 37(3):498–508. https://doi.org/10.1016/j.cor.2008.05.011
Resende Mauricio GC, Ribeiro Celso C (2013) GRASP: Greedy randomized adaptive search procedures. In: Search methodologies, pp 287–312. Springer, New York. https://doi.org/10.1007/978-1-4614-6940-7_11
Reza Z, Ali AM, Huan L (2014) Social media mining: an introduction. Cambridge University Press. Cambridge. https://doi.org/10.1017/CBO9781139088510
Richardson M, Agrawal R, Domingos P (2003) Trust management for the semantic web. In: Lecture notes in computer science, pp 351–368. Springer, Berlin Heidelberg. https://doi.org/10.1007/978-3-540-39718-2_23
Stanley W, Katherine F (1994) Social network analysis. Cambridge University Press, Cambridge. https://doi.org/10.1017/cbo9780511815478
Tretiakov A, Martín A, Camacho D (2022) Detection of false information in spanish using machine learning techniques. In: Hujun Y, David C, Peter T (eds) Intelligent data engineering and automated learning—IDEAL 2022, pp 42–53. Springer International Publishing, Cham
Wenzheng X, Weifa L, Lin Xiaola Yu, Jeffrey X (2016) Finding top-k influential users in social networks under the structural diversity model. Information Sciences 355–356:110–126. https://doi.org/10.1016/j.ins.2016.03.029
Wrubel L, Littman J, Bonnett W, Kerchner D (2020) gwu-libraries/tweetsets: Version 1.1.1. https://zenodo.org/record/1289426
Acknowledgements
The authors acknowledge support from the Spanish Ministry of “Ciencia, Innovaciòn MCIN/AEI/10.13039/501100011033/FEDER, UE) under grant ref. PID2021-126605NB-I00 and PID2021-125709OA-C22, the “Comunidad de Madrid” and “Fondos Estructurales” of the European Union with grant reference S2018/TCS-4566.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Lozano-Osorio, I., Sánchez-Oro, J. & Duarte, A. An efficient and effective GRASP algorithm for the Budget Influence Maximization Problem. J Ambient Intell Human Comput 15, 2023–2034 (2024). https://doi.org/10.1007/s12652-023-04680-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12652-023-04680-z