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

No. 11: IAAI-22, EAAI-22, AAAI-22 Special Programs and Special Track, Student Papers and Demonstrations

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 36

AAAI Student Abstract and Poster Program

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.

10.1609/aaai.v36i11.21596