Mehmet Güray GÜLER, Muhammed Emre KESKİN

Influence maximization in social networks: an integer programming approach

The use of social networks has been spreading rapidly in recent years. There is a growing interest in influencemaximization in social networks, especially after observing that the effects of social events of the Arab Spring, Gezi eventsof Turkey, uprising in Ukraine, etc. have been built by the help of social networks. Consequently, many institutionslike political parties or commercial firms are willing to spread their messages throughout social networks. There aremany studies that concentrate on finding the most influential initial nodes, called seeds, which maximize the spreadof an intended message over the social network. However, most of these works provide numeric algorithmic methodswithout including an integer program that seeks for a theoretical optimal point. Integer programs, on the other hand,are provided in very few studies, and they mostly assume an independent cascade model, which is a diffusion modeldepending on probabilistic affection rates, to formulate the diffusion in the network. In this study, we first provide abasic integer program that works under a linear threshold model, which is a diffusion model assuming threshold affectionlevels, and extend it for the situation in which there is a competing opinion (like black propaganda for a product, anevent, or an opinion). Finally, we provide heuristic solution procedures and efficiency analysis with extensive numericalinstances

PDF

___

Hiasdasdnz O, Skiera B, Barrot C, Becker JU. Seeding strategies for viral marketing: an empirical comparison. J Mark 2011; 75: 55-71.
Aral S, Muchnik L, Sundararajan A. Engineering social contagions: optimal network seeding in the presence of homophily. Netw Sci 2013; 1: 125-153.
Chen W, Wang C, Wang Y. 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; 2010. pp. 1029-1038.
Sangachin M, Samadi M, Cavuoto L. Modeling the spread of an obesity intervention through a social network. J Healthc Eng 2014; 5: 293-312.
Kimura M, Saito K, Motoda H. Blocking links to minimize contamination spread in a social network. ACM T Knowl Discov D 2009; 3: 9.
Macy MW. Chains of cooperation: threshold effects in collective action. Am Sociol Rev 1991; 56: 730-747.
Deroian F. Formation of social networks and diffusion of innovations. Res Policy 2002; 31: 835-846.
Borgatti S. Identifying sets of key players in a social network. Comput Math Organ Theory 2006; 12: 21-34.
Wasserman S, Faust K. Social Network Analysis: Methods and Applications. Cambridge, UK: Cambridge University Press, 1994.
Campbell A. Word-of-mouth communication and percolation in social networks. Am Econ Rev 2013; 103: 2466- 2498.
Domingos P, Richardson M. Mining the network value of customers. In: Proceedings of the seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; 26–29 August 2001; San Francisco, CA, USA. New York, NY, USA: ACM. pp. 57-66.
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; 24–27 August 2003; Washington, DC, USA. New York, NY, USA: ACM. pp. 137-146.
Leskovec J, Krause A, Guestrin C, Faloutsos C, Van Briesen J, Glance N. Cost-effective outbreak detection in networks. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; 12–15 August 2007; San Jose, CA, USA. New York, NY, USA: ACM. pp. 420-429.
Goyal A, Bonchi F, Lakshmanan LV, Venkatasubramanian S. On minimizing budget and time in influence propagation over social networks. Soc Netw Anal Min 2013; 3: 179-192.
Ackerman E, Ben-Zwi O, Wolfovitz G. Combinatorial model and bounds for target set selection. Theor Comput Sci 2010; 411: 4017-4022.
Wu HH, Küçükyavuz S. A two-stage stochastic programming approach for influence maximization in social networks. Comput Optim Appl 2018; 69: 563-595.
Kermani MA, Aliahmadi A, Hanneman R. Optimizing the choice of influential nodes for diffusion on a social network. Int J Commun Syst, 2016; 29: 1235-1250.
Güney E. On the optimal solution of budgeted influence maximization problem in social networks. https://doi.org/10.1007/s12351-017-0305-x, 2017.
Günneç D, Raghavan S, Zhang R. Tailored Incentives and Least Cost Influence Maximization on Social Networks. Technical Report. College Park, MD, USA: University of Maryland, 2016.
Günneç D, Raghavan S. Integrating social network effects in the share-of-choice problem. Decis Sci 2017; 48: 1098-1131.
Fischetti M, Kahr M, Leitner M, Monaci M, Ruthmair M. Least cost influence propagation in (social) networks. Math Program 2018; 170: 293-325.
Gillen CP, Veremyev A, Prokopyev OA, Pasiliao EL Critical arcs detection in influence networks. Netw Int J 2018; 71: 412-431.
Sheldon D, Dilkina B, Elmachtoub AN, Finseth R, Sabharwal A, Conrad J, Gomes CP, Shmoys D, Allen W, Amundsen O et. al. Maximizing the spread of cascades using network design. arXiv preprint, arXiv:1203.3514, 2012.
Yang L, Giua A, Li Z. Minimizing the influence propagation in social networks for linear threshold models. IFACPapersOnLine 2017; 50: 14465-14470.
Szolnoki A, Perc M. Collective influence in evolutionary social dilemmas. EPL-Europhys Lett 2016; 113: 58004.
Berger J, Sorensen AT, Rasmussen SJ. Positive effects of negative publicity: when negative reviews increase sales. Market Sci 2010; 29: 815-827.
Samadi M, Nikolaev A, Nagi R. A subjective evidence model for influence maximization in social networks. OmegaInt J Manage S 2016; 59: 263-278.
Samadi M, Nikolaev A, Nagi R. The temporal aspects of the evidence-based influence maximization on social networks. Optim Methods Softw 2017; 32: 290-311.
Jalili M, Perc M. Information cascades in complex networks. J Complex Netw 2017; 5: 665-693.
Dantzig GB. Origins of the simplex method. In: Nash SG, editor. A History of Scientific Computing. New York, NY, USA: ACM Press History Series, 1990. pp. 141-151.
Karmarkar N. A new polynomial-time algorithm for linear programming. In: Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing; 30 April–2 May 1984; Washington, DC, USA. New York, NY, USA: ACM. pp. 302-311.
Land AH, Doig AG. An automatic method of solving discrete programming problems. Econometrica 1960; 28: 497-520.
Marchand H, Martin A, Weismantel R, Wolsey L. Cutting planes in integer and mixed integer programming. Discrete Appl Math 2002; 123: 397-446.
Mitchell JE. Branch-and-cut algorithms for combinatorial optimization problems. In: Pardoslos PM, Resende MGC, editors. Handbook of Applied Optimization. New York, NY, USA: Oxford University Press Inc, 2002. pp. 65-77.
Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MW, Vance PH. Branch-and-price: column generation for solving huge integer programs. Oper Res 1998; 46: 316-329.
Wolsey LA. Integer Programming. Hoboken, NJ, USA: Wiley-Interscience, 1998