Seminář G²OAT: Eliminating Majority Illusions

When

31. 3. 2025
13:00 – 14:00

Where

Room TH:A-1247

Thákurova 7, Prague 6

Record

Zoom

In the regular Monday seminar of the G²OAT group, Lluís Sabater Rojas (MFF UK) will present an algorithmic analysis of eliminating majority illusions in social networks. He will discuss how network topology influences these illusions and provide complexity results, including FPT algorithms for specific cases.

Event website

Abstract

An opinion illusion refers to a phenomenon in social networks where agents may witness distributions of opinions among their neighbors 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 has bounded pathwidth. On the positive side, we present an FPT algorithm for networks with bounded vertex cover number. Finally, we construct an FPT algorithm for 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.

The person responsible for the content of this page: Bc. Veronika Dvořáková