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 , 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.
Election control through social influence with voters’ uncertainty
AboueiMehrizi, Mohammad;Coro, Federico;Cruciani, Emilio;D'Angelo, Gianlorenzo
2022-01-01
Abstract
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 , 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.File | Dimensione | Formato | |
---|---|---|---|
PostPrint_2022_JCombOptim_44_AboueiMehrizi.pdf
accesso aperto
Tipologia:
Documento in Post-print
Licenza:
Creative commons
Dimensione
282.28 kB
Formato
Adobe PDF
|
282.28 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.