Güney, Evren2019-11-072019-11-072019Güney, E. (November 01, 2019). An efficient linear programming based method for the influence maximization problem in social networks. Information Sciences, 503, 589-605.0020-0255https://doi.org/10.1016/j.ins.2019.07.043https://hdl.handle.net/20.500.11779/1148The influence maximization problem (IMP) aims to determine the most influential individuals within a social network. In this study first we develop a binary integer program that approximates the original problem by Monte Carlo sampling. Next, to solve IMP efficiently, we propose a linear programming relaxation based method with a provable worst case bound that converges to the current state-of-the-art 1-1/e bound asymptotically. Experimental analysis indicate that the new method is superior to the state-of-the-art in terms of solution quality and this is one of the few studies that provides approximate optimal solutions for certain real life social networks.eninfo:eu-repo/semantics/closedAccessInfluence maximizationStochastic optimizationSample average approximationPipage methodArticle10.1016/j.ins.2019.07.0432-s2.0-85068861740