Heuristics for Opinion Diffusion via Local Elections
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Heuristics for Opinion Diffusion via Local Elections
Original language description
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 "local" 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 "global" 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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
SOFSEM 2023: THEORY AND PRACTICE OF COMPUTER SCIENCE
ISBN
978-3-031-23100-1
ISSN
0302-9743
e-ISSN
1611-3349
Number of pages
15
Pages from-to
144-158
Publisher name
SPRINGER INTERNATIONAL PUBLISHING AG
Place of publication
CHAM
Event location
Novy Smokovec
Event date
Jan 15, 2023
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000916960700010