Abstract
In this paper, we introduce and study mathematical programming formulations for the Least Cost Directed Perfect Awareness Problem (LDPAP), an NP-hard optimization problem that arises in the context of influence marketing. In the LDPAP, we seek to identify influential members of a given social network that can disseminate a piece of information and trigger its propagation throughout the network. The objective is to minimize the cost of recruiting the initial spreaders while ensuring that the information reaches everyone. This problem has been previously modeled as two different integer programming formulations that were tested on a collection of 300 small synthetic instances. In this work, we propose two new integer programming models and three constraint programming formulations for the LDPAP. We also present preprocessing techniques capable of significantly reducing the sizes of these models. To investigate and compare the efficiency and effectiveness of our approaches, we perform a series of experiments using the existing small instances and a new publicly available benchmark of 14 large instances. Our findings yield new optimal solutions to 185 small instances that were previously unsolved, tripling the total number of instances with known optima. Regarding both small and large instances, our contributions include a comprehensive analysis of the experimental results and an evaluation of the performance of each formulation in distinct scenarios, further advancing our understanding of the LDPAP toward the design of exact approaches for the problem.
Supported in part by grants from: Santander Bank, Brazil; Brazilian National Council for Scientific and Technological Development (CNPq), Brazil, #313329/2020-6, #314293/2023-0; São Paulo Research Foundation (Fapesp), Brazil, #2023/04318-7, #2023/14427-8; Fund for Support to Teaching, Research and Outreach Activities (Faepex), Brazil; Coordination for the Improvement of Higher Education Personnel (Capes), Brazil – Finance Code 001.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ackerman, E., Ben-Zwi, O., Wolfovitz, G.: Combinatorial model and bounds for target set selection. Theoret. Comput. Sci. 411(44), 4017–4022 (2010). https://doi.org/10.1016/j.tcs.2010.08.021
Banerjee, S., Jenamani, M., Pratihar, D.K.: A survey on influence maximization in a social network. Knowl. Inf. Syst. 62(9), 3417–3455 (2020). https://doi.org/10.1007/s10115-020-01461-4
Bollobás, B., Borgs, C., Chayes, J., Riordan, O.: Directed scale-free graphs. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 132-139. SODA ’03, Society for Industrial and Applied Mathematics, USA (2003)
Campbell, C., Farrell, J.R.: More than meets the eye: the functional components underlying influencer marketing. Bus. Horiz. 63(4), 469–479 (2020). https://doi.org/10.1016/j.bushor.2020.03.003
Chen, N.: On the approximability of influence in social networks. SIAM J. Discret. Math. 23(3), 1400–1415 (2009). https://doi.org/10.1137/08073617X
Cordasco, G., Gargano, L., Rescigno, A.A.: Active influence spreading in social networks. Theoret. Comput. Sci. 764, 15–29 (2019). https://doi.org/10.1016/j.tcs.2018.02.024
Gautam, R.K., Kare, A.S., Bhavani, S.D.: Centrality measures based heuristics for perfect awareness problem in social networks. In: Morusupalli, R., Dandibhotla, T.S., Atluri, V.V., Windridge, D., Lingras, P., Komati, V.R. (eds.) MIWAI 2023. LNCS, vol. 14078, pp. 91–100. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-36402-0_8
Gecode Team: Gecode — generic constraint development environment (2023). http://www.gecode.org
Gurobi Optimization, LLC: Gurobi Optimizer Reference Manual (2023). https://www.gurobi.com
Karp, R.M.: Reducibility Among Combinatorial Problems, pp. 85–103. Springer US, Boston, MA (1972). https://doi.org/10.1007/978-1-4684-2001-2_9
Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137-146. KDD 2003, ACM, New York, NY, USA (2003). https://doi.org/10.1145/956750.956769
Miller, C., Tucker, A., Zemlin, R.: Integer programming formulation of traveling salesman problems. J. ACM 7(4), 326–329 (1960). https://doi.org/10.1145/321043.321046
Pereira, F.C.: A computational study of the Perfect Awareness Problem. Master’s thesis, University of Campinas, Brazil (2021). http://hdl.handle.net/20.500.12733/1641217
Pereira, F.C., de Rezende, P.J.: The Least Cost Directed Perfect Awareness Problem – Benchmark Instances and Solutions. Mendeley Data, V2 (2023). https://doi.org/10.17632/xgtjgzf28r
Pereira, F.C., de Rezende, P.J.: The least cost directed perfect awareness problem: complexity, algorithms and computations. Online Soc. Netw. Media 37–38 (2023). https://doi.org/10.1016/j.osnem.2023.100255
Pereira, F.C., de Rezende, P.J., de Souza, C.C.: Effective heuristics for the perfect awareness problem. Procedia Comput. Sci. 195, 489–498 (2021). https://doi.org/10.1016/j.procs.2021.11.059, proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium
Pereira, F.C., de Rezende, P.J., Yunes, T.: Minimizing the cost of leveraging influencers in social networks: IP and CP approaches - complementary data. Mendeley Data, V2 (2023). https://doi.org/10.17632/tkk5pdswty
Perron, L., Didier, F.: CP-SAT (Google OR-Tools) (2023). https://developers.google.com/optimization/cp/cp_solver/
Prais, M., Ribeiro, C.C.: Reactive grasp: an application to a matrix decomposition problem in TDMA traffic assignment. Informs J. Comput. 12(3), 164–176 (2000). https://doi.org/10.1287/ijoc.12.3.164.12639
Raghavan, S., Zhang, R.: A branch-and-cut approach for the weighted target set selection problem on social networks. Informs J. Optimiz. 1(4), 304–322 (2019). https://doi.org/10.1287/ijoo.2019.0012
Schweimer, C., et al.: Generating simple directed social network graphs for information spreading. In: Proceedings of the ACM Web Conference 2022, pp. 1475–1485. WWW 2022, ACM, New York, USA (2022). https://doi.org/10.1145/3485447.3512194
Shakarian, P., Eyre, S., Paulo, D.: A scalable heuristic for viral marketing under the tipping model. Soc. Netw. Anal. Min. 3(4), 1225–1248 (2013). https://doi.org/10.1007/s13278-013-0135-7
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Ethics declarations
Disclosure of Interests
The authors have no competing interests to declare that are relevant to the content of this article.
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Pereira, F.d.C., de Rezende, P.J., Yunes, T. (2024). Minimizing the Cost of Leveraging Influencers in Social Networks: IP and CP Approaches. In: Dilkina, B. (eds) Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2024. Lecture Notes in Computer Science, vol 14743. Springer, Cham. https://doi.org/10.1007/978-3-031-60599-4_7
Download citation
DOI: https://doi.org/10.1007/978-3-031-60599-4_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-60601-4
Online ISBN: 978-3-031-60599-4
eBook Packages: Computer ScienceComputer Science (R0)