Controlling the Spread of Two Secrets in Diverse Social Networks (Student Abstract)

Authors

  • Václav Blažej Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Prague, Czechia
  • Dušan Knop Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Prague, Czechia
  • Šimon Schierreich Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Prague, Czechia

DOI:

https://doi.org/10.1609/aaai.v36i11.21596

Keywords:

Group Identification, Spreading More Opinions, Computational Complexity

Abstract

Information diffusion in social networks is a well-studied concept in social choice theory. We propose the study of the diffusion of two secrets in a heterogeneous environment from the complexity perspective, that is, there are two different networks with the same set of agents (e.g., the structure of the set of followers might be different in two distinct social networks). Formally, our model combines two group identification processes for which we do have independent desiderata---either constructive, where we would like a given group of agents to be exposed to a secret, or destructive, where a given group of agents should not be exposed to a secret. To be able to reach these targets, we can either delete an agent or introduce a previously latent agent. Our results are mostly negative---all of the problems are NP-hard. Therefore, we propose a parameterized study with respect to the natural parameters, the number of influenced agents, the size of the required/protected agent sets, and the duration of the diffusion process. Most of the studied problems remain W[1]-hard even for a combination of these parameters. We complement these results with nearly optimal XP algorithms.

Downloads

Published

2022-06-28

How to Cite

Blažej, V., Knop, D., & Schierreich, Šimon. (2022). Controlling the Spread of Two Secrets in Diverse Social Networks (Student Abstract). Proceedings of the AAAI Conference on Artificial Intelligence, 36(11), 12919-12920. https://doi.org/10.1609/aaai.v36i11.21596