Eliminating Majority Illusions

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10512161" target="_blank" >RIV/00216208:11320/25:10512161 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21240/25:00389817

Výsledek na webu

<a href="https://dl.acm.org/doi/10.5555/3709347.3743592" target="_blank" >https://dl.acm.org/doi/10.5555/3709347.3743592</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Eliminating Majority Illusions

Popis výsledku v původním jazyce

An opinion illusion refers to a phenomenon in social networks where agents may witness distributions of opinions among their neighbours that do not accurately reflect the true distribution of opinions in the population as a whole. A specific case of this occurs when there are only two possible choices, such as whether to receive the COVID-19 vaccine or vote on EU membership, which is commonly referred to as a majority illusion. In this work, we study the topological properties of social networks that lead to opinion illusions and focus on minimizing the number of agents that need to be influenced to eliminate these illusions. To do so, we propose an initial, but systematic study of the algorithmic behaviour of this problem. We show that the problem is NP-hard even for underlying topologies that are rather restrictive, being planar and of bounded diameter. We then look for exact algorithms that scale well as the input grows (FPT). We argue the in-existence of such algorithms even when the number of vertices that must be influenced is bounded, or when the social network is arranged in a &quot;path-like&quot; fashion (has bounded pathwidth). On the positive side, we present an FPT algorithm for networks with &quot;star-like&quot; structure (bounded vertex cover number). Finally, we construct an FPT algorithm for &quot;treelike&quot; networks (bounded treewidth) when the number of vertices that must be influenced is bounded. This algorithm is then used to provide a PTAS for planar graphs.

Název v anglickém jazyce

Eliminating Majority Illusions

Popis výsledku anglicky

An opinion illusion refers to a phenomenon in social networks where agents may witness distributions of opinions among their neighbours that do not accurately reflect the true distribution of opinions in the population as a whole. A specific case of this occurs when there are only two possible choices, such as whether to receive the COVID-19 vaccine or vote on EU membership, which is commonly referred to as a majority illusion. In this work, we study the topological properties of social networks that lead to opinion illusions and focus on minimizing the number of agents that need to be influenced to eliminate these illusions. To do so, we propose an initial, but systematic study of the algorithmic behaviour of this problem. We show that the problem is NP-hard even for underlying topologies that are rather restrictive, being planar and of bounded diameter. We then look for exact algorithms that scale well as the input grows (FPT). We argue the in-existence of such algorithms even when the number of vertices that must be influenced is bounded, or when the social network is arranged in a &quot;path-like&quot; fashion (has bounded pathwidth). On the positive side, we present an FPT algorithm for networks with &quot;star-like&quot; structure (bounded vertex cover number). Finally, we construct an FPT algorithm for &quot;treelike&quot; networks (bounded treewidth) when the number of vertices that must be influenced is bounded. This algorithm is then used to provide a PTAS for planar graphs.

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í

2025

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

Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems Aamas

ISBN

979-8-4007-1426-9

ISSN

1548-8403

e-ISSN

1558-2914

Počet stran výsledku

9

Strana od-do

749-757

Název nakladatele

International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)

Místo vydání

Richland, SC (USA)

Místo konání akce

Detroit, Michigan, USA

Datum konání akce

19. 5. 2025

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

WRD - Celosvětová akce

Kód UT WoS článku

001532048100085