Abstract
We study the least cost influence maximization problem, which has potential applications in social network analysis, as well as in other types of networks. The focus of this paper is on mixed-integer programming (MIP) techniques for the considered problem. The standard arc-based MIP formulation contains a substructure that is a relaxation of the mixed 0-1 knapsack polyhedron. We give a new exponential class of facet-defining inequalities from this substructure and an exact polynomial time separation algorithm for the inequalities. We report preliminary computational results to illustrate the effect of these inequalities.
This material is based on work supported by the AFRL Mathematical Modeling and Optimization Institute.
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. Theor. Comput. Sci. 411(44–46), 4017–4022 (2010)
Chen, N.: On the approximability of influence in social networks. SIAM J. Discret. Math. 23(3), 1400–1415 (2009)
Chen, W., Lakshmanan, L.V., Castillo, C.: Information and influence propagation in social networks. Synth. Lect. Data Manag. 5(4), 1–177 (2013)
Demaine, E.D., et al.: How to influence people with partial incentives. In: Proceedings of the 23rd International Conference on World Wide Web, pp. 937–948 (2014)
Fischetti, M., Kahr, M., Leitner, M., Monaci, M., Ruthmair, M.: Least cost influence propagation in (social) networks. Math. Program. 170(1), 293–325 (2018)
Granovetter, M.: Threshold models of collective behavior. Am. J. Sociol. 83(6), 1420–1443 (1978)
Günneç, D., Raghavan, S., Zhang, R.: A branch-and-cut approach for the least cost influence problem on social networks. Networks 76(1), 84–105 (2020)
Günneç, D., Raghavan, S., Zhang, R.: Least-cost influence maximization on social networks. INFORMS J. Comput. 32(2), 289–302 (2020)
Gursoy, F., Günneç, D.: Influence maximization in social networks under deterministic linear threshold model. Knowl.-Based Syst. 161, 111–123 (2018)
Kempe, D., Kleinberg, J., 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, pp. 137–146 (2003)
Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. Theory Comput. 11(4), 105–147 (2015)
Marchand, H., Wolsey, L.A.: The 0–1 knapsack problem with a single continuous variable. Math. Program. 85(1), 15–33 (1999)
Nannicini, G., Sartor, G., Traversi, E., Wolfler Calvo, R.: An exact algorithm for robust influence maximization. Math. Program. 183(1), 419–453 (2020)
Raghavan, S., Zhang, R.: A branch-and-cut approach for the weighted target set selection problem on social networks. Inf. J. Optim. 1(4), 304–322 (2019)
Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393(6684), 440–442 (1998)
Wu, H.H., Küçükyavuz, S.: A two-stage stochastic programming approach for influence maximization in social networks. Comput. Optim. Appl. 69(3), 563–595 (2018)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Chen, CL., Pasiliao, E.L., Boginski, V. (2020). A Cutting Plane Method for Least Cost Influence Maximization. In: Chellappan, S., Choo, KK.R., Phan, N. (eds) Computational Data and Social Networks. CSoNet 2020. Lecture Notes in Computer Science(), vol 12575. Springer, Cham. https://doi.org/10.1007/978-3-030-66046-8_41
Download citation
DOI: https://doi.org/10.1007/978-3-030-66046-8_41
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-66045-1
Online ISBN: 978-3-030-66046-8
eBook Packages: Computer ScienceComputer Science (R0)