Election control through social influence with voters’ uncertainty

The problem of election control through social influence consists in finding a set of nodes in a social network of voters to be the starters of a political campaign aimed at supporting a particular target candidate. The voters reached by the campaign change their views on the candidates. The goal is to model the spread of the campaign in such a way as to maximize the chances of winning for the target candidate. Herein, differently from previous work, we consider that each voter is associated with a probability distribution over the candidates modeling the likelihood of the voter to vote for each candidate. In a first model we propose, we prove that, under the Gap-ETH, the problem cannot be approximated to within a factor better than $$1/n^{o(1)}$$ 1 / n o ( 1 ) , where n is the number of voters. In a second model, which is a slight relaxation of the first one, the problem instead admits a constant-factor approximation algorithm. Finally, we present simulations on both synthetic and real networks, comparing the results of our algorithm with those obtained by a standard greedy algorithm for Influence Maximization.