On the optimal solution of budgeted influence maximization problem in social networks

The budgeted influence maximization problem is a challenging stochastic optimization problem defined on social networks. In this problem, the objective is identifying influential individuals who can influence the maximum number of members within a limited budget. In this work an integer program that approximates the original problem is developed and solved by a sample average approximation (SAA) scheme. Experimental analyses indicate that SAA method provides better results than the greedy method without worsening the solution time performance.