Heuristics for Opinion Diffusion via Local Elections

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10475619" target="_blank" >RIV/00216208:11320/23:10475619 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-031-23101-8_10" target="_blank" >https://doi.org/10.1007/978-3-031-23101-8_10</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-23101-8_10" target="_blank" >10.1007/978-3-031-23101-8_10</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Heuristics for Opinion Diffusion via Local Elections

Popis výsledku v původním jazyce

Most research on influence maximization considers asimple diffusion model, in which binary information is being diffused (i.e., vertices - corresponding to agents - are either active or passive). Here we consider a more involved model of opinion diffusion: In our model, each vertex in the network has either approval-based or ordinal-based preferences and we consider diffusion processes in which each vertex is influenced by its neighborhood following a local election, according to certain &quot;local&quot; voting rules. We are interested in externally changing the preferences of certain vertices (i.e., campaigning) in order to influence the resulting election, whose winner is decided according to some &quot;global&quot; voting rule, operating after the diffusion converges. As the corresponding combinatorial problem is computationally intractable in general, and as we wish to incorporate probabilistic diffusion processes, we consider classic heuristics adapted to our setting: A greedy heuristic and a local search heuristic. We study their properties for plurality elections, approval elections, and ordinal elections, and evaluate their quality experimentally. The bottom line of our experiments is that the heuristics we propose perform reasonably well on both the real world and synthetic instances. Moreover, examining our results in detail also shows how the different parameters (ballot type, bribery type, graph structure, number of voters and candidates, etc.) influence the run time and quality of solutions. This knowledge can guide further research and applications.

Název v anglickém jazyce

Heuristics for Opinion Diffusion via Local Elections

Popis výsledku anglicky

Most research on influence maximization considers asimple diffusion model, in which binary information is being diffused (i.e., vertices - corresponding to agents - are either active or passive). Here we consider a more involved model of opinion diffusion: In our model, each vertex in the network has either approval-based or ordinal-based preferences and we consider diffusion processes in which each vertex is influenced by its neighborhood following a local election, according to certain &quot;local&quot; voting rules. We are interested in externally changing the preferences of certain vertices (i.e., campaigning) in order to influence the resulting election, whose winner is decided according to some &quot;global&quot; voting rule, operating after the diffusion converges. As the corresponding combinatorial problem is computationally intractable in general, and as we wish to incorporate probabilistic diffusion processes, we consider classic heuristics adapted to our setting: A greedy heuristic and a local search heuristic. We study their properties for plurality elections, approval elections, and ordinal elections, and evaluate their quality experimentally. The bottom line of our experiments is that the heuristics we propose perform reasonably well on both the real world and synthetic instances. Moreover, examining our results in detail also shows how the different parameters (ballot type, bribery type, graph structure, number of voters and candidates, etc.) influence the run time and quality of solutions. This knowledge can guide further research and applications.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

SOFSEM 2023: THEORY AND PRACTICE OF COMPUTER SCIENCE

ISBN

978-3-031-23100-1

ISSN

0302-9743

e-ISSN

1611-3349

Počet stran výsledku

15

Strana od-do

144-158

Název nakladatele

SPRINGER INTERNATIONAL PUBLISHING AG

Místo vydání

CHAM

Místo konání akce

Novy Smokovec

Datum konání akce

15. 1. 2023

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000916960700010