Balancing the Spread of Two Opinions in Sparse Social Networks (Student Abstract)

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F22%3A00358760" target="_blank" >RIV/68407700:21240/22:00358760 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Balancing the Spread of Two Opinions in Sparse Social Networks (Student Abstract)

Original language description

We propose a new discrete model for simultaneously spreading two opinions within a social network inspired by the famous Target Set Selection problem. We are given a social network, a seed-set of agents for each opinion, and two thresholds per agent. The first threshold represents the willingness of an agent to adopt an opinion if she has no opinion at all, while the second threshold states the readiness to acquire a second opinion. The goal is to add as few agents as possible to the initial seed-sets such that, once the process started with these seed-set stabilises, each agent has either both opinions or none. We perform an initial study of its computational complexity. It is not surprising that the problem is NP-hard even in quite restricted settings. Therefore, we investigate the complexity of the problem from the parameterized point-of-view with special focus on sparse networks, which appears often in practice. Among other things, we show that the proposed problem is in the FPT complexity class if we parameterize by the vertex cover number of the underlying graph.

Czech name

—

Czech description

—

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)

Project

<a href="/en/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Research Center for Informatics</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Publication year

2022

Confidentiality

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

Article name in the collection

Proceedings of the 36th AAAI Conference on Artificial Intelligence

ISBN

978-1-57735-876-3

ISSN

2159-5399

e-ISSN

2374-3468

Number of pages

2

Pages from-to

12987-12988

Publisher name

AAAI Press

Place of publication

Menlo Park

Event location

- virtual

Event date

Feb 22, 2022

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

000893639105175