(Elsevier, 2020) Güney, Evren; 02.01. Department of Industrial Engineering; 02. Faculty of Engineering; 01. MEF University
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 thatapproximates the original problem by Monte Carlo sampling. Next, to solve IMP efficiently,we propose a linear programming relaxation based method with a provable worst casebound 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 termsof solution quality and this is one of the few studies that provides approximate optimalsolutions for certain real life social networks.