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
Citation
Technical Report -TRIE1801- MEF University, Department of Industrial Engineering, 2018/07