Abstract
We consider the election control problem in social
networks which consists in exploiting social influence in a network of voters to change their opinion about a target candidate with the aim of increasing his chances to win (constructive control)
or lose (destructive control) the election. Previous works on this problem focus on plurality voting systems and on a influence model in which
the opinion of the voters about the target candidate
can only change by shifting its ranking by one position, regardless of the amount of influence that
a voter receives. We introduce Linear Threshold
Ranking, a natural extension of Linear Threshold
Model, which models the change of opinions taking
into account the amount of exercised influence. In
this general model, we are able to approximate the
maximum score that a target candidate can achieve
up to a factor of 1 1 1/e by showing submodularity of the objective function. We exploit this result
to provide a 13
(1 1 1/e)-approximation algorithm
for the constructive election control problem and a
12
(1 1 1/e)-approximation ratio in the destructive
scenario. The algorithm can be used in arbitrary
scoring rule voting systems, including plurality rule
and borda count