An efficient linear programming based method for the influence maximization problem in social networks
MetadataShow full item record
CitationGüney, E. (November 01, 2019). An efficient linear programming based method for the influence maximization problem in social networks. Information Sciences, 503, 589-605.
The 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.