A mathematical model and solution techniques for the influential selection problem

Abstract

In the era of social networks, many companies shift their marketing campaigns to this new media. Any person who influences his/her connections is called an influential. Since companies have limited budgets for advertising, they have to correctly select the influentials, which will forward their message to their connections over the online social network. In this study, the problem of selecting the best influentials regarding different objectives and constraints are modeled. The influential selection problem can be modeled similar to the famous set covering problem. We propose a binary integer programming formulation to represent the influential selection problem. We propose various different solution techniques to obtain close-to-optimal solutions and carry out experimental analysis to determine the performance of the techniques proposed.